[경고] 아래 글을 읽지 않고 "선형 최소 제곱법"을 보면 바보로 느껴질 수 있습니다.
함수의 최대값 혹은 최소값을 구하는 문제는 현실에서도 매우 중요하다. 예를 들면 [그림 1]에 있는 2차 함수(quadratic function)를 본다.
[그림 1] 아래로 볼록한 2차 함수(출처: wikipedia.org)
[그림 1]의 2차 함수는 아래로 볼록하기 때문에 최소값을 가진다. 직관적으로는 최소값이 있다고 바로 알 수 있지만, 수학적으로 [그림 1]의 함수가 최소값이 있다는 사실은 어떻게 알 수 있을까? 함수 $f(x)$를 두 번 미분하면 함수가 아래로 볼록한지 알 수 있다. 즉 1차 미분이 $0$이 되는 점이 존재하고[$f'(x)$ = $0$], 이 점에서 2차 미분이 $0$보다 크면[$f''(x) > 0$] $f(x)$는 아래로 볼록하다. [그림 1]에 사용한 2차 함수는 $x^2-x-2$이다. 이 함수에 적용한 평행 이동을 제거하고 보면, 일반형은 $f(x)$ = $ax^2$이 된다. 따라서 $a > 0$이면 간단하게 아래로 볼록이라고 할 수 있다. 이 경우 모든 $x$에 대해 $f(x) \ge 0$가 성립하므로, $f(x)$는 양의 준정부호(陽의 準正符號, positive semi-definiteness)를 가진다고 한다. 비슷하게 모든 $x$에 대해 $f(x) > 0$라면 $f(x)$는 양의 정부호(陽의 正符號, positive definiteness)를 가진다고 한다.
아래로 볼록한 2차 함수의 특성을 기억하면서 다음과 같은 벡터 크기[정확히는 벡터 노름(vector norm) $\| \cdot \|_2$ 혹은 유클리드 노름(Euclidean norm)]의 제곱을 고려한다.
(1)여기서 $\bf A$는 행렬(matrix), $\bf x$와 $\bf b$는 열 벡터(column vector), $(\cdot)^T$는 전치 행렬(transpose)이다. 식 (1)은 행렬을 포함하고 있지만 제곱 형태이며 아래로 볼록하기 때문에 양의 준정부호를 가진다. 또한 $\bf x$가 다음 조건을 만족하는 위치에서 식 (1)은 최소값을 가진다.
(2)따라서 식 (1)의 최소값을 구하면 자연스럽게 1차 연립 방정식인 식 (2)를 풀게 된다. [그림 1]처럼 식 (1)은 $\bf x$에 대해 아래로 볼록함은 명확하다. 그래서 $\bf x$의 원소인 $x_i$에 대해 식 (1)을 편미분해서 $0$으로 둔다.
(3)식 (3)에 의해 원소 $x_i$에 관계없이 만족해야 하는 행렬 방정식은 다음과 같다.
(4)행렬 $\bf A$가 정방 행렬이며 역행렬이 있다면 통상적인 방정식의 해법과 동일하다.
(5)식 (4)의 강점은 $\bf A$가 정방 행렬이 아닐 때 드러난다. 1차 연립 방정식에서 미지수의 개수와 방정식의 개수는 반드시 같아야 한다. 하지만 식 (4)는 미지수보다 방정식의 개수가 클 때에도 미지수를 식 (1)과 같은 제곱 형태로 추정하도록 해준다. 그래서 식 (4)를 최소 제곱 근사(least squares approximation)라 부른다. 통계(statistics) 분야에서는 식 (4)를 정규 방정식(normal equation)이라고도 한다. 최소 제곱 근사에 등장하는 행렬과 전치 행렬의 곱 ${\bf A}^T {\bf A}$는 최소 제곱 행렬(least squares matrix)로 정의한다.
[그림 2] 줄자로 동전의 직경을 재는 모습(출처: wikipedia.org)
하지만 굳이 미지수보다 방정식을 더 만들어서 식 (4)처럼 복잡하게 계산할 필요가 있을까? [그림 2]와 같은 측정 과정을 생각한다. 측정에는 반드시 잡음(noise)이나 불확도(uncertainty)가 생겨서 동일한 측정을 하더라도 결과는 다르게 나온다. 이 경우 측정으로부터 참값을 추정할 효과적인 방법은 무엇일까? 이 질문에 대한 해답이 제곱의 합을 활용하는 최소 제곱 근사이다. 통계에서 제곱의 합은 우리가 잘 아는 분산(分散, variance)에 쓰인다. 측정의 예를 들면, 원래는 $ax$ = $b$이지만, 잡음이 생겨서 $ax$ = $b + \nu_i$가 된다고 가정한다. 여기서 $\nu_i$는 $i$번째 측정에 생긴 잡음이다. 동일한 측정을 $n$번 반복한 경우, $x$를 추정하기 위한 최소 제곱 근사는 다음과 같다.
(6)여기서 $E(\nu)$는 잡음 $\nu$의 기대값(expectation or expected value)이다. 보통 잡음의 기대값 혹은 평균은 $0$이므로, 측정 회수 $n$을 늘리면 참값은 $x$ = $b/a$에 수렴한다. 식 (6)은 매우 간단한 경우를 가정해 얻지만, 식 (4)를 참값 추정에 쓰면 측정에 따라 계수 $a, b$가 바뀌고 $x$가 벡터이더라도 최소 제곱법(least squares) 기반으로 $x$를 잘 추정할 수 있다.
[그림 3] 최소 제곱 근사를 이용한 곡선 맞춤(curve fitting)(출처: wikipedia.org)
최소 제곱 근사의 핵심인 최소 제곱 행렬 ${\bf A}^T {\bf A}$와 ${\bf A} {\bf A}^T$의 다양한 성질을 소개한다.
1. 기본(basics)
[대칭 행렬(symmetric matrix)]
최소 제곱 행렬은 대칭 행렬이다.
(1.1)[증명]
식 (1.1)의 첫째식에 전치 행렬(transpose)을 적용하면 다음과 같다.
(1.2)마찬가지로 전치 행렬의 특성에 의해, ${\bf A} {\bf A}^T$도 대칭 행렬이다.
______________________________
식 (1.1)을 다른 관점으로 보면, 행렬 ${\bf A}$의 대칭성에 관계없이 행렬을 ${\bf A}^T {\bf A}$ 혹은 ${\bf A} {\bf A}^T$로 만들면 항상 대칭 행렬이 된다. 대칭 행렬의 장점은 고유 벡터(eigenvector)와 결합될 때 나타난다. 대칭 행렬의 고유 벡터는 항상 직교하기 때문에, 고유 벡터로 만든 행렬은 직교 행렬(orthogonal matrix)이 될 수 있다.
[행렬의 계수 혹은 계급수(rank)]
(1.3)[증명]
식 (1.3)은 원래 행렬과 최소 제곱 행렬의 계수(階數, rank)가 같다는 뜻이다. 즉 식 (2), (4)에 있는 1차 연립 방정식의 좌변인 ${\bf Ax}$와 ${\bf A}^T {\bf Ax}$의 독립적인 방정식 수가 같음을 의미한다. 따라서 행렬의 계수는 독립적인 방정식의 수를 의미하므로, ${\bf Ax}$ = $0$과 ${\bf A}^T {\bf Ax}$ = $0$을 만족하는 $\bf x$가 같음을 보임으로써 $\operatorname{rank}({\bf A})$ = $\operatorname{rank}({\bf A}^T {\bf A})$를 증명할 수 있다[2]. 먼저 다음 관계식을 살펴본다.
(1.4)여기서 $|| \cdot ||$는 행렬식 $|\cdot|$과 구별되는 벡터의 크기[정확히는 벡터 노름(vector norm) $\| \cdot \|_2$ 혹은 유클리드 노름(Euclidean norm)]를 의미한다. 식 (1.4)의 역도 쉽게 증명할 수 있다. 식 ${\bf Ax}$ = $0$에 ${\bf A}^T$를 곱하면 ${\bf A}^T {\bf Ax}$ = $0$이 성립한다. 따라서 다음 두 행렬에 대한 1차 연립 방정식의 해 $\bf x$는 서로 같다.
(1.5)예를 들어 ${\bf Ax}$를 구성하는 모든 방정식이 독립적이면, 역행렬 ${\bf A}^{-1}$이 존재해서 $\bf x$는 영 벡터가 된다. 이 결과는 선형 독립(linear independence)의 조건과 동일하다. 일부 방정식이 종속이면, 가우스 소거법(Gaussian elimination)으로 독립인 방정식만 연립해서 정리하면 계수 $\operatorname{rank}({\bf A})$를 계산할 수 있다. 그러면 식 (1.5)에 의해 $\operatorname{rank}({\bf A}^T {\bf A})$도 정해지므로, $\operatorname{rank}({\bf A})$ = $\operatorname{rank}({\bf A}^T {\bf A})$임을 알 수 있다. 이번에는 ${\bf A}^T {\bf y}$ = $0$을 고려한다. 식 (1.5)와 비슷하게 이 식은 ${\bf A}{\bf A}^T {\bf y}$ = $0$과 동치(同値, equivalence)이다. 그러면 동일한 방식으로 $\operatorname{rank}({\bf A})$ = $\operatorname{rank}({\bf A} {\bf A}^T)$를 증명할 수 있다.
______________________________
[양의 준정부호(positive semi-definiteness)]
(1.6)[증명]
식 (1.4)에 의해 항상 식 (1.6)이 성립한다.
______________________________
[고유치(eigenvalue)]
(a) 최소 제곱 행렬의 고유치는 음수가 아니다.
(b) 두 최소 제곱 행렬의 고유치는 서로 같다.
(1.7)여기서 ${\bf A}^T {\bf A}$와 ${\bf A} {\bf A}^T$에 대한 고유 벡터(eigenvector)는 각각 $\bf v$와 $\bf u$이다.
[명제 (a)의 증명]
식 (1.6)의 열 벡터를 최소 제곱 행렬 ${\bf A}^T {\bf A}$에 대한 고유 벡터(eigenvector) $\bf v$로 생각하면 다음과 같다.
(1.7)따라서 좌변이 항상 $0$보다 크거나 같기 때문에, 고유치도 $0$이거나 양수가 되어야 한다. 마찬가지로 ${\bf A} {\bf A}^T$의 고유치도 음수가 아니다.
[명제 (b)의 증명]
식 (1.7)의 첫째식에서 양변에 $\bf A$를 곱하여 서로 비교해보자[3].
(1.8)그러면 식 (1.7)의 둘째식과 동일한 결과를 얻어서 두 최소 제곱 행렬의 고유치는 같다. 식 (1.7)의 둘째식부터 출발하면 다음 식도 얻을 수 있다.
(1.9)______________________________
식 (1.8), (1.9)를 조합하면 $k_u k_v$ = $\lambda$가 된다. 스칼라(scalar) $k_u, k_v$는 임의로 선택할 수 있어서 $k_u$ = $k_v$라 두면, 음수가 아닌 새로운 상수를 $\sigma$ = $k_u$ = $k_v$ = $\sqrt{\lambda}$로 정할 수 있다. 이 경우 $\sigma$를 행렬 $\bf A$의 특이값(singular value)이라 한다. 특이값의 영어 알파벳이 s로 시작하므로, 특이값의 알파벳은 $\sigma$가 된다. 특이값은 고유치(eigenvalue)와 비슷하지만 서로 구별되도록 다른 이름으로 부른다.[특이값의 원래 이름이 고유치였다.] 특이값 $\sigma$를 이용해서 식 (1.8), (1.9)를 다시 쓰면 다음과 같다.
(1.10)여기서 $\sigma \ge 0$, $\bf u$와 $\bf v$는 $\bf A$ 기준으로 왼쪽과 오른쪽에 위치해서 각각 좌특이 벡터(left-singular vector), 우특이 벡터(right-singular vector)라 부른다.
[벡터 노름(vector norm)]
행렬 $\bf Ax$에 대한 벡터 노름의 최대값은 최대 특이값이다.
(1.11)여기서 벡터 노름은 유클리드 노름(Euclidean norm), 행렬 $\bf A$의 차원은 $m \times n$, 열 벡터 $\bf x$의 크기는 $1$이다.
[증명]
식 (1.11)의 좌변을 제곱해서 식 (1.7)을 대입하면 다음과 같다[4].
(1.12)여기서 $\bf x$는 정규 직교 기저이며 우특이 벡터인 ${\bf v}_i$의 선형 결합(linear combination)으로 표현, ${\bf v}_i$의 특이값은 $\sigma_i$, $r$ = $\operatorname{rank}({\bf A})$이다. 열 벡터 $\bf x$를 정규 직교 기저의 선형 결합으로 표현할 때, 특이값이 $0$인 기저까지 사용할 수도 있다. 하지만 식 (1.12)의 마지막식에 의해, 이 기저는 벡터 노름에 기여하지 않으므로 선형 결합에서 제외한다. 만약 $\sigma_1$이 특이값 중에서 최대값이라면, 다음 부등식이 성립한다.
(1.13)따라서 식 (1.13)에 의해 식 (1.11)이 증명된다.
______________________________
식 (1.13)을 보면, 식 (1.11)이 성립하는 경우는 $\bf x$ = ${\bf v}_\text{max}$일 때이다.
[참고문헌]
[1] G. Strang, Linear Algebra and its Applications, 4th ed., Brooks/Cole, 2006.
[2] G. Gundersen, "Proof of the singular value decomposition," Blog, 2018. (방문일 2020-08-03)
[3] 다크 프로그래머, [선형대수학 #4] 특이값 분해(Singular Value Decomposition, SVD)의 활용, 수학 이야기, 2013. (방문일 2020-08-03)
[4] M. Hutchings, "Notes on singular value decomposition for Math 54," Linear Algebra and Differential Equations, UC Berkeley, 2017. (방문일 2020-08-04)
(1)
(2)
(3)
(4)
(5)
(6)
(7)
(8)
(9)
(10)
(11)
(12)
(13)
(14)
(15)
(16)
(17)
(18)
(19)
(20)
(21)
(21)
(22)
(23)
(24)
(25)
(26)
(27)
(28)
(29)