Projection matrices and least squares

1. Projection - Two extreme cases

■ 투영 행렬 \( P = A (A^T A)^{-1} A^T \)는 \( A \mathbf{x} = b \)의 우변 벡터 \( b \)를 \( A \)의 열공간에서 가장 가까운(근사한) 벡터로 바꿔주는 역할을 한다.

■ 그러므로 \( P \)에 \( b \)를 곱하면 벡터 \( b \)를 열공간에서 가장 가까운 벡터 \( p \)로 투영한다. \( p = Pb \)

■ 여기서 말하는 두 가지 극단적인 경우는 벡터 \( b \)가 이미 \( A \)의 열공간에 존재하는 경우와 벡터 \( b \)가 열공간에 수직인 경우이며, 두 가지 경우의 벡터 \( b \)에 투영 행렬 \( P \)를 곱했을 때 어떤 결과가 발생하는지 확인하려 한다.

■ 먼저 벡터 \( b \)가 열공간에 존재하는 경우 투영 행렬 \( P \)에 \( b \)를 곱하면, 다시 \( b \)를 얻는다. 즉, \( Pb = b \)

■ 벡터 \( b \)가 열공간에 존재하는 벡터라는 것은 \( A \)의 열벡터들의 선형 결합으로 벡터 \( b \)를 만들 수 있다는 것이며, \( A \mathbf{x} = b \)이므로 여기서의 선형 결합은 \( A \mathbf{x} \)이다. 

■ 벡터 \( b \)가 열공간에 존재하는 경우 \( A \mathbf{x} = b \)가 성립한다. 이때 투영 행렬 \( P = A (A^T A)^{-1} A^T \)에 \( b \)를 곱하면 \( Pb = A(A^TA)^{-1} A^TAx = Ax = b \)가 성립하게 된다. 이는 투영 행렬이 이미 열공간에 존재하는 벡터 \( b \)를 그대로 유지시킨 것으로 볼 수 있다.

■ 두 번째 경우는 벡터 \( b \)가 열공간에 수직인 경우이다. 열공간을 어떤 평면이라고 생각했을 때, 열공간이 벡터 \( b \)와 수직이라는 것은 벡터 \( b \)와 평면의 모든 벡터들의 내적 결과가 0이라는 것을 의미한다. 

■ \( A \)의 대표적인 열공간의 벡터는 열공간의 기저이며 \( A \mathbf{x} = b \)에서 \( b \)는 열벡터이고 \( A \)의 열은 \( A^T \)에서 행으로 바뀌므로,

■ \( A^T b \)는 \( b \)와 수직인 벡터들(여기서는 \( A \)의 기저)과 \( b \)의 내적들의 계산을 하는 것이므로 \( A^T b = 0 \)이 성립한다.

■ \( P = A (A^T A)^{-1} A^T \)에 벡터 \( b \)를 곱하면 \( Pb = A (A^T A)^{-1} A^Tb \)이며 \( A^T b = 0 \)이므로 \( Pb = A (A^T A)^{-1} A^Tb = 0 \)이 성립한다.

■ 또한, \( b \)가 열공간과 수직이라는 것은 \( b \)가 열공간이 아닌 다른 공간에 존재한다는 것을 의미한다. 바로 left null space에 벡터 \( b \)가 존대한다. 다음과 같이 열공간과 수직인 공간은 left nullspace이기 때문이다.

[출처] Gilbert Strang - Introduction  to Linear  Algebra

■ 열공간과 left nullspace는 서로 직교하므로 열공간에 있는 모든 벡터와 left nullspace에 있는 모든 벡터들의 내적은 0이 되어야 한다. 

■ 여기서 알 수 있는 것은 \( p \)는 열공간에 있는 \( b \)와 근사한 벡터이다. 즉, \( p \)는 열공간에 존재한다.

■ 그리고 오차 벡터 \( e \)는 \( p \)와 직교한다. \( p \)는 열공간에 있기 때문에 \( p \)와 수직 관계를 갖는 \( e \)는 left nullspace에 존재한다.

■ 그리고 벡터 \( b \)는 위의 두 극단적인 경우처럼, 열공간에 존재하거나 left nullspace에 존재할 수 있으며, 열공간과 left nullspace의 교집합에 있을 수도 있다. 

■ 만약, 다음과 같이 벡터 \( p \)는 열공간에, 벡터 \( e \)는 left nullspace에 존재하는데 벡터 \( b \)가 열공간에 존재하지 않는 경우

벡터 \( b \)를 열공간에 투영한 벡터가 \( p \)가 되고 left nullspace에 투영한 벡터가 \( e \)가 되는 것을 알 수 있다.

■ \( p \)는 벡터 \( b \)를 열공간에 투영한 것이기 때문에 \( p = Pb \)가 된다. \( b = p + e \)임을 이용하면, \( b = Pb + e \Leftrightarrow e = b - Pb = (I-P)b \)가 성립한다. 즉 오차 벡터 \( e \)는 \( I - P \)라는 투영 행렬에 벡터 \( b \)를 곱한 결과로 볼 수 있다.

- \( (I - P) \)도 투영 행렬이기 때문에 \( (I - P)^T = (I - P) \)와 \( (I - P)^2 = (I - P) \)를 만족한다.

■ \( p = Pb \)와 \( e = (I - P)b \)임을 이용하면, \( b = p + e \)는 다음과 같이 전개되므로 \( b = p + e = b\)가 된다.

\( b = p + e = P b + (I - P) b = P b + I b - P b = b \)

 

2. Least Square Method(최소자승법 또는 최소제곱법)

■ 투영(projection)을 사용하는 이유는 \( A \mathbf{x} = b \)에서 미지수보다 방정식이 많아서 해가 존재하지 않을 때, 정확한 해가 아니더라도 주어진 모든 방정식을 최대한 만족시키는 근사해(또는 최적해)를 찾기 위함이다.

■ Least Square Method는 주어진 정보(방정식)를 최대한 만족시키는 하나의 직선 방정식을 찾는 방법이다. 

- 즉, 최소자승법(최소제곱법)의 가설은 직선 방정식 \( y = ax+b \)가 된다.

■ 예를 들어 다음과 같이 가로 축이 시간에 대한 축이고 세로 축이 시간에 따른 점수를 나타내는 축이라고 했을 때, 1시간에 1점, 2시간에 2점, 3시간에 2점을 받았다고 하자.

■ 이렇게 주어진 정보 (1, 1), (2, 2), (3, 2)를 이용해 미래 시점에 발생하는, 4시간, 5시간일 때 받을 수 있는 점수를 예측하기 위해 최소자승법은 위의 데이터 포인트들을 잘 표현할 수 있는 하나의 최적의 직선을 찾는다.

■ 최소자승법의 가설은 직선의 방정식 \( y = ax + b\)이기 때문에, 위의 데이터들을 잘 표현할 수 있는 최적의 직선을 찾는 문제는 최적의 \( a, b \)를 구하는 문제가 된다.

■ 문제를 푸는 방법은 다음과 같이 최소자승법의 가설인 \( y = ax + b \)에 주어진 정보 \( (x, y) = (1, 1), (2, 2), (3, 2) \)를 넣는다. 넣으면, 방정식을 얻을 수 있으며, 방정식을 \( A \mathbf{x} = b \)형태로 바꿀 수 있다.

\(
\begin{bmatrix} 1 & 1 \\ 2 & 1 \\ 3 & 1 \end{bmatrix}
\begin{bmatrix} a \\ b \end{bmatrix}
=
\begin{bmatrix} 1 \\ 2 \\ 2 \end{bmatrix}
\)

■ 이 에에서 미지수보다 방정식이 더 많으므로( 행렬 \( A \)가 m > n )) \( A \mathbf{x} = b \)를 완벽하게 만족시키는 정확한 해 \( \mathbf{x} \)는 존재하지 않는다.

■ 그러므로 다음과 같이 근사해(또는 최적해)를 구하기 위해 \( A \mathbf{x} = b \)의 양변에 \( A^T \)를 곱해 \( A^T A \hat{\mathbf{x}} = A^T b \)를 계산하면 된다.

■ 현재 찾고자 하는 직선은 주어진 데이터를 잘 표현할 수 있는 최적의 직선이며, 데이터를 잘 표현하는 직선은 실제값과 예측값의 오차(error)가 최소가 되게 만드는 직선을 의미하며, 결국 각 데이터와 직선 사이의 오차에 대해 오차의 총합이 최소가 되게 만드는 직선의 파라미터 \( a, b \)를 찾아야 한다.

■ 이상적인 경우는 모든 오차가 0이 되는 상황이다. \( A \mathbf{x} \)는 주어진 데이터를 직선 \( y = ax+b \)에 대입한 상태이며, 우변 \( b \)는 그 결과인 \( y \)이므로 모든 오차가 0이 되는 상황은 \( A \mathbf{x} - b = 0 \)이다.

■ 즉, 오차 벡터를 \( e \)라고 했을 때, \( A \mathbf{x} - b = e \)이며, 최소화 하고자 하는 것은 오차'값'이므로 \( A \mathbf{x} - b = e \)에 norm을 씌워야 한다. 그리고 오차 결과가 음수가 나오는 것을 방지하기 위해서 다음과 같이 제곱을 해야 한다.

\( \|Ax - b\|^2 = \|e\|^2 \)

■ 그러므로 최소자승법은 \( \text{Minimize} \) \( \|Ax - b\|^2 = \|e\|^2 \)를 푸는 문제가 된다. (정확히는 목적 함수를 최소화하는 파라미터를 찾기 위함)

- \( A \mathbf{x} - b \)의 결과는 오차 벡터 \( e \)이며, 오차 벡터에 대한 길이는 오차의 총 크기를 나타낸다.

■ 만약 다음과 같이 최적의 직선을 찾았을 때, 기존의 데이터와 직선의 거리가 가까우면 오차가 적은 것이며, 거리가 멀면 오차가 큰 상황이다. 

- 이 예에서는 다음과 같이 오차 \( e_1, e_2 ,e_3 \)를 얻었다고 하자.

■ 위의 그림은 주어진 데이터를 이용해 직선의 파라미터 \( a, b \)를 추정해서 \( t-s \)평면에 그린 그림이다. 하얀색 점은 실제값, 파란색 점은 예측값이며, 빨간색 선은 실제값과 예측값이 차이. 즉, 오차를 나타낸다.

■ 오차 벡터를 \( \mathbf{e} = [e_1, e_2, e_3]^T \)라고 했을 때, 오차의 총합은 각 오차의 자승(square)의 합으로 표현할 수 있다. \( \text{overall error} = e_1^2 + e_2^2 + e_3^2 \)

■ \( \text{overall error} = e_1^2 + e_2^2 + e_3^2 \) 이 값이 최소화하고자 하는 오차(손실)값이다.

2.1 Outliers in Least Square

■ 이상치(outlier)란, 데이터들의 분포에서 크게 벗어난 소수의 데이터를 의미한다. 이러한 outlier는 대부분 쓸모없는 값. 즉, noise data인 경우가 많다.

■ 최소자승법은 모든 데이터에 대한 오차를 최소화해야 하는데 만약 다음과 같이 (0, 3)의 outlier가 추가 된다면, outlier의 영향을 크게 받아 직선의 파라미터값이 바뀔 것이다.(직선의 형태가 바뀐다.)

■ 즉, outlier가 존재하면 최소자승법은 전체 데이터를 잘 반영하지 못하게 될 가능성이 커진다.

2.2 Solution of Least Square

■ 이 문제는 앞서 얘기한 것처럼 \( A^T A \hat{\mathbf{x}} = A^T b \)를 계산하면 된다.

■ \( A^T A \hat{\mathbf{x}} = A^T b \)를 계산하면 \(
\begin{bmatrix} 14 & 6 \\ 6 & 3 \end{bmatrix}
\begin{bmatrix} \hat{a} \\ \hat{b} \end{bmatrix}
=
\begin{bmatrix} 11 \\ 5 \end{bmatrix}
\) \( \quad \) \(
\begin{bmatrix} 14 \\ 6 \end{bmatrix} \hat{a} +
\begin{bmatrix} 6 \\ 3 \end{bmatrix} \hat{b} =
\begin{bmatrix} 11 \\ 5 \end{bmatrix}
\)이므로 계산하면 \( \hat{a} = \frac{1}{2}, \quad \hat{b} = \frac{2}{3} \)이므로 최적의 직선 방정식은 \( y = \dfrac{1}{2}x + \dfrac{2}{3} \)이 된다. 

- 좌변을 우변으로 넘겨 풀 수 도 있는데. 즉 \( \hat{\mathbf{x}} \)에 대한 식으로 정리할 수 있는데, 이는 \( A^T A \)의 역행렬이 존재해야 한다는 조건이 있다. 

- \( A^T A \)의 역행렬이 존재하는 조건은 \( A \)의 열벡터들이 독립이어야 한다는 것이며, 앞서 \( \text{rank} A = \text{rank} A^TA \)와 \( N(A) = N(A^TA) \)가 성립함을 확인하였다.
■ 다음 문제에서 순서대로 \( A, \mathbf{x}, b \)라고 한다면, 

■ 행렬 \( A \)의 열벡터는 독립이므로 두 열벡터는 행렬 \( A \)의 열공간의 기저이다. 
■ 그리고 \( b \)는 해가 존재하지 않는 상황이므로 열공간에 존재하지 않는다. 

■ 이렇게 정확한 해는 존재하지 않지만 최대한 유사한 해를 구하기 위해 투영을 사용한다. 정확히는 \( b \)를 열공간에 투영시킨다.

■ \( b \)를 열공간에 투영시켜 얻은 벡터를 \( p \)라고 한다면, \( b = [1 2 2]^T \)에서 \( p = [p_1, p_2, p_3]^T \)으로 바꾼 것이며 \( A \mathbf{x} = b \)의 문제는 \( A \hat{\mathbf{x}} = p \)를 푸는 문제가 된다.

\(
\begin{bmatrix} 1 & 1 \\ 2 & 1 \\ 3 & 1 \end{bmatrix}
\begin{bmatrix} \hat{a} \\ \hat{b} \end{bmatrix}
=
\begin{bmatrix} p_1 \\ p_2 \\ p_3 \end{bmatrix}
\)

■ 여기서 얻은 \( p_1, p_2, p_3 \)이 바로 최적의 직선을 통해 계산한 '예측값'이다.

■ 위에서 구한 \( \hat{a} = \frac{1}{2}, \quad \hat{b} = \frac{2}{3} \)를 위에 넣으면 \( p_1 = \frac{7}{6}, p_2 =\frac{5}{3}. p_3 = \frac{13}{6} \)이며, \( p = [p_1 p_2 p_3]^T \)를 통해 \( e = b - p \)임을 이용하여 오차 벡터 \( e \)를 다음과 같이 구할 수 있다. 여기서 얻은 \( e_1, e_2, e_3 \)이 각 포인트에서의 오차값이다. \[
e =
\begin{bmatrix} 1 \\ 2 \\ 2 \end{bmatrix} -
\begin{bmatrix} \frac{7}{6} \\ \frac{5}{3} \\ \frac{13}{6} \end{bmatrix}
=
\begin{bmatrix} -\frac{1}{6} \\ \frac{2}{6} \\ -\frac{1}{6} \end{bmatrix}
\] ■ 이와 같은 최소자승법은 통계학에서 회귀(= 관찰된 연속형 변수들에 대해 두 변수 사이의 모형을 구한 뒤 적합도를 측정)이며, 찾고자 하는 것은 최적의 직선. 즉 선형이므로, 최소자승법은 통계학의 선형 회귀(Linear Regression)과 같다. 

2.3 error vector

■ 원래 값인 \( b \)는 오차 벡터 \( e \)와 투영 벡터 \( p \)의 합으로 표현된다. 그리고 \( p \)는 열공간에 \( e \)는 left nullspace에 있기 때문에 \( p \)와 \( e \)는 직교한다.

\(
\mathbf{b} =
\begin{bmatrix} 1 \\ 2 \\ 2 \end{bmatrix}
=
\mathbf{e} +
\mathbf{p} =
\begin{bmatrix} -\frac{1}{6} \\ \frac{2}{6} \\ -\frac{1}{6} \end{bmatrix}
+
\begin{bmatrix} \frac{7}{6} \\ \frac{10}{6} \\ \frac{13}{6} \end{bmatrix}
\)

■ 위에서 계산한 \( p \)와 \( e \)를 내적하면 -7/36 + 20/36 - 13/36 = 0이 된다. 

■ 단, \( e \)와 직교하는 것은 \( p \)만 있는 것이 아니다. 열공간에는 \( p \)와 행렬 \( A \)의 열공간을 생성하는 열공간의 기저도 포함되어 있다. 즉, left nullspace에 있는 \( e \)는 열공간의 모든 벡터와 직교하므로 행렬 \( A \)의 열공간의 기저와도 직교한다.

- 행렬 \( A \)의 열공간의 기저 두 개를 \( a_1, a_2 \)라고 했을 때, 오차 벡터 \( e \)와의 내적 \( e^T a_1 \)과 \( e^T a_2 \)를 계산하면 \( e^T a_1 = 0\), \( e^T a_2 = 0 \)이 되는 것을 확인할 수 있다.