선형대수학 최소제곱해에 대한 반올림오차를 해결하려는 노력

선형대수학에서는 강력한 방정식인 normal equation 이 존재한다.

이렇게 한방에 구할 수 있는데 왜 gradient descent 를 사용하는 것인지 이유에 대해 여러가지가 있지만 오늘 주로 다룰 이유는 반올림오차이다.

이론적으론 완벽하지만 실제 컴퓨터에 코딩을 하는 과정을 보면 수를 저장할 때 컴퓨터는 어떤 수가 저장될 메모리 공간을 확보하는데 한정적으로 확보하게된다. (예: 32bit, 64bit 등). 하지만 이론에서는 자연상수 e , 원주율 파이 등 많은 무리수 등이 존재하고 이를 컴퓨터로 구현하게 되면 한정된 자릿수까지만 확보하게 된다. 이런 무리수 같이 정확하게 그 수를 다 담을 수 없는데 여기에다가 이런 수를 반복적으로 곱셈 등 연산을 하게 되면 점점 이론적으로 나와야 되는 수에 멀어져 생각치 못한 이상한 수가 나오게 되는 결과를 초래한다. 이를 반올림 오차라고 한다.

선형대수학에서는 (X’X)^-1X’y 를 구할 때 X를 제곱하는 항에 대해서 반올림 오차가 발생하게 된다(역행렬을 구하는 과정에서도). 이런 오차를 줄이려고, X 그 자체를 분해함으로써 제곱오차를 없애는 노력을 하게되는데 이 방법이 QR알고리즘이다. 이론적으로 완벽한 QR분해를 사용하는 방법은 그람슈미트 과정이 있다. 하지만 이 방법 또한 반올림 오차의 늪에서 벗어나지 못한다. 실제 컴퓨터 알고리즘에서 QR 분해를 그람슈미트 과정을 사용하지 않고 하우스홀더 변환 등 다른 방법을 사용하고 있다. (이런 방법이 반올림 오차를 크게 줄여주기 때문).

이 포스트에 쓸 주된 내용은 선형대수학에서 최소제곱법 문제를 현실에서 풀기위해  반올림 오차를 어떻게 줄여왔는지 그 과정을 들여다 볼 것이다.

그에 앞서 행렬분해에 있어 가장 기초가 되는 개념들을 다시 짚고 넘어간다. ( norm ,직교집합, 직교사영 )

그람슈미트 과정

행렬의 QR 분해

그람슈미트 과정을 사용한 QR분해의 문제점 :

그 문제를 해결하기 위해 실제 컴퓨터는 하우스 홀드변환으로 코딩된다. 이 개념을 익히기 전에 몇 가지 정리와 반사(reflection) 에 대한 개념을 살펴보고 간다.

하우스 홀더 변환

하우스 홀더 변환은 아직 개념이 익숙치 않아 나중에 한번 더 공부해볼 것이다. 정리하자면 실제 문제를 풀 때 반올림 오차가 발생하는데 이를 없앨 수는 없으니 최대한 줄일 수 있는 방법을 찾아가는 것이다. 현재 쓰고 있는 하우스 홀드 변환을 이용한 QR분해는 reflection 을 이용해 구하는데 이는 기존에 그람슈미트 과정에서 정규직교기저를 구하기 위한 반올림오차를 대폭 낮추었다. 하지만 이러한 노력에도 불구하고 여전히 반올림오차는 없앨 수 없는 문제로 남아있다.

여기서 궁금한 점은 gradient descent 를 사용해도 반올림오차는 여전히 발생하지만 이를 선호하는 이유는 계산비용이 위 방법보다 적기 때문에 사용할 것이다. 그럼 구체적으로 어떤 부분에 대해서 그런지 생각해볼 필요가 있겠다.