H5 · 변분원리와 최적 저계수 근사: 가장 좋은 몇 방향만 남기기

내용

H5 · 변분원리와 최적 저계수 근사: 가장 좋은 몇 방향만 남기기#

H4의 SVD는 입력 방향마다 서로 다른 길이 배율을 알려 주었습니다. 저장량이나 계산량 때문에 몇 방향만 남겨야 한다면, 어떤 방향을 버리는 것이 가장 나을까요?

먼저 작은 방향 오차가 Rayleigh 몫에 미치는 영향을 계산하고, 부분공간을 고르는 최적화로 확장합니다. 그 결과를 자료의 분산과 저계수 근사의 오차에 연결하겠습니다.

1. 고유벡터를 조금 틀리게 알면 고윳값은 얼마나 틀릴까?#

세 변수의 공분산 또는 에너지 행렬을

\[\begin{split}A=\begin{pmatrix}6&6&0\\6&9&6\\0&6&12\end{pmatrix}\end{split}\]

로 두겠습니다. 직접 곱하면

\[q_1=(1,2,2)^\top/3,\quad q_2=(2,1,-2)^\top/3,\quad q_3=(2,-2,1)^\top/3\]

에 대해 $Aq_1=18q_1,Aq_2=9q_2,Aq_3=0$입니다. $q_1$ 대신 $v=q_1+\varepsilon q_2$를 사용하면

\[r(v)=\frac{\langle Av,v\rangle}{\langle v,v\rangle} =\frac{18+9\varepsilon^2}{1+\varepsilon^2} =18-\frac{9\varepsilon^2}{1+\varepsilon^2}.\]

방향 오차는 $\arctan|\varepsilon|$로 일차이지만 Rayleigh 값 오차는 이차입니다. 이것이 변분원리의 첫 질문입니다.

1.1 세 변수의 주성분을 실제로 계산하기#

자료의 세 변수에 같은 단위를 적용하고, 공분산을 앞 절의 $A$로 두겠습니다. 첫 주성분 점수는 $ q_1^\top x=\frac{x_1+2x_2+2x_3}{3} $ 입니다. 관측 $x=(3,0,0)^\top$에서는 점수가 1이고, 원래 벡터의 $A$-에너지는 $ x^\top Ax=(3,0,0)\begin{pmatrix}18\\18\\0\end{pmatrix}=54. $ 첫 방향으로만 남긴 벡터는 $(q_1^\top x)q_1=(1,2,2)^\top/3$입니다. 나머지 두 직교 방향의 성분을 버리는 것이 어떤 의미인지 보려면 $ \|x-(q_1^\top x)q_1\|^2 =9-\frac{1^2+2^2+2^2}{9} =9-1=8 $ 을 계산하면 됩니다. PCA는 “가장 큰 고윳값을 고른다”는 문장만이 아니라, 원자료를 특정 부분공간에 투영하고 버린 제곱오차를 최소화하는 절차입니다.

2. Rayleigh 몫과 고윳값#

정규직교 고유기저에서 $v=\sum c_iq_i$라 쓰면

\[r(v)=\frac{\sum_i\lambda_i|c_i|^2}{\sum_i|c_i|^2}.\]

계수 $|c_i|^2/\sum_j|c_j|^2$는 음이 아니고 합이 1이므로 $r(v)$는 고윳값들의 볼록결합입니다. 따라서

\[\lambda_n\le r(v)\le\lambda_1.\]

$q_1,q_n$에서 양 끝을 달성합니다. 두 고윳값이 다르면 $v=\sqrt t\,q_1+\sqrt{1-t}\,q_n$($0\le t\le1$)에서 $r(v)=t\lambda_1+(1-t)\lambda_n$이므로 그 사이의 값도 모두 달성합니다. 두 값이 같으면 모든 방향의 Rayleigh 몫이 그 값입니다.

$Av_i=\lambda_i v_i$, $\|v_i\|=\|w\|=1$, $w\perp v_i$이면

\[\begin{split}\begin{aligned} \langle A(v_i+\varepsilon w),v_i+\varepsilon w\rangle &=\lambda_i+\varepsilon\langle Av_i,w\rangle+\varepsilon\langle Aw,v_i\rangle +\varepsilon^2\langle Aw,w\rangle\\ &=\lambda_i+\varepsilon^2\langle Aw,w\rangle, \end{aligned}\end{split}\]

입니다. 두 교차항은 자기수반성과 직교성으로 0입니다. 분모는 $1+\varepsilon^2$이므로

\[r(v_i+\varepsilon w)-\lambda_i =\frac{\varepsilon^2(\langle Aw,w\rangle-\lambda_i)}{1+\varepsilon^2}.\]

따라서 절댓값은 $\varepsilon^2(\lambda_1-\lambda_n)$ 이하입니다.

단위 원 위에서 Rayleigh 몫이 고윳값 사이를 오가고 고유방향에서 극값을 갖는 그래프 — 그림 73 수평축은 방향 각도, 수직축은 Rayleigh 몫입니다. 자기수반 행렬에서 고유방향은 극값이며, 고윳값 사이의 모든 값이 나타납니다.#

2.1 Rayleigh 몫의 분모를 왜 남겨 두는가?#

벡터를 $c v$로 바꾸면 분자와 분모가 각각 $|c|^2$배가 됩니다. $ r(cv)=\frac{\langle A(cv),cv\rangle}{\langle cv,cv\rangle} =\frac{|c|^2\langle Av,v\rangle}{|c|^2\langle v,v\rangle}=r(v). $ 따라서 단위구에서만 계산해도 충분하지만, 분모를 없애고 $\|v\|=1$이라고 써 버리면 이 동차성을 잊기 쉽습니다. 고유기저에서 $v=\sum c_iq_i$를 대입할 때도 먼저 분모 $\sum|c_i|^2$를 남겨 두어야 볼록결합 계수가 합 1임을 확인할 수 있습니다.

3. Courant–Fischer min–max#

고윳값을 $\lambda_1\ge\cdots\ge\lambda_n$라 하겠습니다. $k$차원 부분공간 $S$에서 Rayleigh 몫의 최솟값을 $\underline r(S)$라 두면

\[\lambda_k=\max_{\dim S=k}\underline r(S).\]

증명하겠습니다. $T=\operatorname{span}\{q_k,\ldots,q_n\}$의 차원은 $n-k+1$입니다. 임의의 $k$차원 $S$에 대해

\[\dim(S\cap T)\ge k+(n-k+1)-n=1\]

이므로 0이 아닌 $z\in S\cap T$가 있습니다. $z=\sum_{i\ge k}c_iq_i$이므로 $r(z)\le\lambda_k$, 따라서 $\underline r(S)\le\lambda_k$입니다. 반대로 $S_*=\operatorname{span}\{q_1,\ldots,q_k\}$에서는 모든 $z$가 $r(z)\ge\lambda_k$이고 $q_k$에서 등호입니다. 최대값이 $\lambda_k$입니다.

$-A$에 같은 결과를 적용하면

\[\lambda_k=\min_{\dim S=n-k+1}\max_{0\ne z\in S}r(z)\]

도 얻습니다. $k=1,n$은 각각 $\lambda_1=\max r,\lambda_n=\min r$입니다.

3.1 교집합 벡터를 실제로 만드는 방법#

$A=\operatorname{diag}(7,2,-1)$, $k=2$라면 $T=\operatorname{span}(e_2,e_3)$입니다. 임의의 2차원 평면 $S$는 $T$와 0이 아닌 교집합을 가집니다. 예를 들어 $S=\operatorname{span}((1,1,0),(0,1,1))$에서 벡터를 $\alpha(1,1,0)+\beta(0,1,1)$로 쓰고 첫 좌표가 0이 되게 $\alpha=0$을 택하면 $e_2+e_3\in S\cap T$입니다. 이 벡터의 Rayleigh 몫은 $ r(e_2+e_3)=\frac{2-1}{2}=1\le2=\lambda_2. $ 일반 증명의 차원 공식은 이 구체적 소거를 임의의 부분공간에 대해 보장하는 장치입니다.

4. Ky Fan 정리와 PCA#

$U\in\mathbb F^{n\times k}$, $U^*U=I$를 정규직교 프레임이라 하겠습니다. 고유기저에서

\[\operatorname{tr}(U^*AU)=\sum_{j=1}^n\lambda_j c_j,\qquad c_j=\|U^*q_j\|^2.\]

$UU^*$는 직교사영이므로 $0\le c_j\le1$이고

\[\sum_jc_j=\operatorname{tr}(UU^*)=\operatorname{tr}(U^*U)=k.\]

왜 앞의 $k$개 방향에 무게를 모두 주는 것이 최선인지 부등식으로 확인하겠습니다. $\sum_{j\le k}(1-c_j)=\sum_{j>k}c_j$이고, 앞쪽 고윳값은 $\lambda_k$ 이상, 뒤쪽은 $\lambda_k$ 이하입니다. 따라서

\[ \sum_{j=1}^k\lambda_j-\sum_{j=1}^n\lambda_jc_j =\sum_{j\le k}\lambda_j(1-c_j)-\sum_{j>k}\lambda_jc_j \ge\lambda_k\left(\sum_{j\le k}(1-c_j)-\sum_{j>k}c_j\right)=0. \]

$U=[q_1,\ldots,q_k]$를 선택하면 앞 $k$개의 $c_j$가 1이고 나머지는 0이므로 이 상한을 달성합니다.

\[\max_{U^*U=I_k}\operatorname{tr}(U^*AU)=\sum_{j=1}^k\lambda_j.\]

고윳값 간극 $\lambda_k>\lambda_{k+1}$이면 등호에서 $c_j=1$ ($j\le k$), $c_j=0$ ($j>k$)가 강제되어 부분공간이 유일합니다. 프레임의 열 자체는 그 부분공간 안의 임의 유니터리 회전만큼 자유롭습니다.

공분산 행렬에서 $\operatorname{tr}(U^*\Sigma U)$는 선택한 주성분들이 설명하는 분산의 합입니다. PCA의 최적성은 알고리즘의 경험칙이 아니라 Ky Fan 정리입니다.

4.1 PCA의 설명분산을 성분별로 계산하기#

중심화 자료행렬 $X$의 공분산을 $\Sigma=X^\top X/N$이라 하겠습니다. $U=[u_1,\ldots,u_k]$이면 투영된 자료는 $XU$이고 설명된 제곱합은 $ \|XU\|_F^2=\operatorname{tr}(U^\top X^\top XU) =N\operatorname{tr}(U^\top\Sigma U). $ 따라서 Ky Fan의 최대값 $N(\lambda_1+\cdots+\lambda_k)$는 “상위 $k$개 주성분이 설명하는 총 변동”의 정확한 상한입니다. 각 열을 따로 최대화하는 것이 아니라 하나의 공통 $k$차원 공간을 선택한다는 점이 중요합니다.

5. Cauchy 교대와 Poincaré 분리#

$B$가 $A$의 첫 $n-1$개 좌표에 대한 주부분행렬이면 $B$는 부분공간 $S=\operatorname{span}(e_1,\ldots,e_{n-1})$ 위 압축입니다. Courant–Fischer를 $S$에 적용하면

\[\lambda_k(A)\ge\lambda_k(B)\ge\lambda_{k+1}(A),\qquad1\le k<n.\]

이를 Cauchy 교대정리라 합니다.

더 일반적으로 $U^*U=I_k$이고 $C=U^*AU$이면

\[\lambda_j(A)\ge\lambda_j(C)\ge\lambda_{n-k+j}(A),\qquad1\le j\le k.\]

첫 부등식은 $C$의 $j$차원 부분공간을 원래 공간으로 올려 Courant–Fischer 상한을 쓰는 것이고, 둘째는 $-A$에 같은 논리를 적용한 것입니다. 표본에서 일부 변수만 남길 때 분산 고윳값이 원래 스펙트럼 사이에 끼는 이유입니다.

6. 특이값은 계수 결손까지의 거리다#

$A\in\mathbb F^{m\times n}$의 특이값을 $\sigma_1\ge\cdots\ge\sigma_p\ge0$, $p=\min(m,n)$이라 하겠습니다. 이 절에서는 $1\le k\le p$입니다. 임의의 rank $\le k-1$ 행렬 $B$에 대해 $\ker B$의 차원은 적어도 $n-k+1$입니다. $V_k=\operatorname{span}(v_1,\ldots,v_k)$와의 차원 합은 $n+1$ 이상이므로 교집합에 단위벡터 $z$가 있습니다. $Bz=0$이고

\[\|Az\|^2=\sum_{i=1}^k\sigma_i^2|\langle z,v_i\rangle|^2\ge\sigma_k^2.\]

따라서 $\|A-B\|_2\ge\sigma_k$. $B=\sum_{i=1}^{k-1}\sigma_i u_i v_i^*$를 택하면 계수는 $k-1$ 이하이고, 잔차는 $\sum_{i=k}^{p}\sigma_i u_i v_i^*$입니다. 잔차의 최대 특이값이 $\sigma_k$이므로 하한을 달성합니다. 하나의 특이항만 지우면 다른 뒤쪽 특이항들이 남기 때문에 일반적으로 필요한 계수 제약을 만족하지 않습니다.

\[\sigma_k(A)=\min_{\operatorname{rank}(A+E)\le k-1}\|E\|_2.\]

6.1 rank 제약의 차원 세기#

$B$의 rank가 $k$ 이하이면 rank-nullity에 의해 $ \dim\ker B\ge n-k. $ 상위 $k+1$개 오른쪽 특이벡터가 만드는 공간 $V_{k+1}$의 차원은 $k+1$입니다. 그러므로 $ \dim(\ker B\cap V_{k+1}) \ge(n-k)+(k+1)-n=1. $ 교집합에서 단위벡터 $z$를 잡으면 $Bz=0$입니다. $z=\sum_{i=1}^{k+1}c_iv_i$이고 $\sum|c_i|^2=1$이므로 $ \|(A-B)z\|^2=\|Az\|^2 =\sum_{i=1}^{k+1}\sigma_i^2|c_i|^2 \ge\sigma_{k+1}^2. $ 이것이 모든 경쟁자 $B$에 대한 하한입니다.

7. Eckart–Young: 스펙트럼과 Frobenius#

SVD 절단을

\[A_k=\sum_{i=1}^k\sigma_iu_iv_i^*\]

라 하겠습니다. 위 절의 하한을 $A-B$에 적용하면 rank $B\le k$에서

\[\|A-B\|_2\ge\sigma_{k+1}.\]

한편 $A-A_k$의 SVD가 나머지 특이쌍이므로 $\|A-A_k\|_2=\sigma_{k+1}$입니다.

Frobenius 노름에서는 $W=\operatorname{range}(B)$를 잡고 직교사영 $P_W$를 적용합니다. 각 열 $a_j$에 대해 H1의 최적근사로

\[\|a_j-b_j\|^2\ge\|a_j-P_Wa_j\|^2.\]

합하면 $\|A-B\|_F^2\ge\|(I-P_W)A\|_F^2$. 따라서

\[\|A-B\|_F^2\ge\|A\|_F^2-\|P_WA\|_F^2.\]

$W$의 프레임을 $Q$라 하면

\[\|P_WA\|_F^2=\operatorname{tr}(Q^*AA^*Q)\le\sum_{i=1}^k\sigma_i^2\]

(Ky Fan)입니다. 그러므로

\[\|A-B\|_F^2\ge\sum_{i>k}\sigma_i^2.\]

$B=A_k$에서 등호이므로 최적입니다.

행렬의 특이값을 일부만 남겼을 때 원래 자료와 절단 자료의 잔차를 비교하는 그림 — 그림 74 상위 특이방향을 남길수록 Frobenius 잔차가 감소하며, 남은 특이값 제곱합이 정확한 잔차 제곱입니다.#

7.1 Frobenius 최적성에서 사영이 등장하는 이유#

$B$의 열공간을 $W$라 할 때 각 $b_j$는 $W$ 안에 있습니다. H1의 직교분해로 $ a_j=P_Wa_j+(I-P_W)a_j,\qquad b_j=P_Wa_j+d_j,\quad d_j\in W $ 입니다. 두 항의 차이는 $ a_j-b_j=(I-P_W)a_j-d_j $ 이고 첫 항은 $W^\perp$, 둘째는 $W$에 있습니다. 따라서 피타고라스에 의해 $ \|a_j-b_j\|^2=\|(I-P_W)a_j\|^2+\|d_j\|^2 \ge\|(I-P_W)a_j\|^2. $ 각 열에서 최선의 $b_j$는 $P_Wa_j$이며, 남은 문제는 어떤 $W$가 투영된 에너지를 가장 크게 하는가입니다. 그 두 번째 선택이 Ky Fan 문제입니다.

7.2 작은 행렬의 압축을 손으로 확인하기#

$ M=\begin{pmatrix}3&2&0\\2&3&0\\0&0&1\end{pmatrix} $ 은 두 변수의 공통 변동과 독립적인 셋째 변수를 함께 담은 자료라고 하겠습니다. 첫 두 좌표의 합·차 방향에서 고윳값은 5와 1이고, 셋째 방향의 고윳값도 1입니다. rank-1 절단은 $ M_1=5q_+q_+^\top =\frac52\begin{pmatrix}1&1&0\\1&1&0\\0&0&0\end{pmatrix}. $ 잔차는 $ M-M_1=

(1)#\[\begin{pmatrix}1/2&-1/2&0\\-1/2&1/2&0\\0&0&1\end{pmatrix}\]

$ 이고 Frobenius 제곱은 $1/4+1/4+1/4+1/4+1=2$입니다. 남은 특이값 제곱합 $1^2+1^2=2$와 정확히 일치합니다.

이 계산은 절단오차 공식이 추상적인 합이 아니라 실제로 버린 성분의 에너지임을 보여 줍니다.

8. 유니터리 불변 노름과 핵노름 쌍대성#

노름 $\|\cdot\|$가 유니터리 불변이라는 것은 적절한 크기의 유니터리행렬 $U,V$에 대해 $\|UXV\|=\|X\|$라는 뜻입니다. SVD를 대입하면 이 노름은 특이값을 대각에 둔 직사각행렬의 노름으로 결정됩니다. 스펙트럼·Frobenius·핵노름이 그 예입니다.

먼저 대각의 비음수 성분을 줄이면 이런 노름도 커지지 않음을 확인하겠습니다. 한 성분을 부호만 바꾼 대각행렬은 원래 행렬과 노름이 같습니다. 두 행렬의 볼록결합을 취하면 그 성분을 원래 값의 $t$배($0\le t\le1$)로 줄일 수 있고, 삼각부등식에 의해 노름은 커지지 않습니다. 성분마다 반복하면 성분별 단조성을 얻습니다.

이제 $\operatorname{rank}B\le k$라 하고 $R=A-B$의 상위 $j-1$개 특이항을 $R_{j-1}$라 하겠습니다. $B+R_{j-1}$의 계수는 $k+j-1$ 이하이므로 6절의 거리 하한에서

\[ \sigma_{k+j}(A)\le\|A-(B+R_{j-1})\|_2 =\|R-R_{j-1}\|_2=\sigma_j(R) \quad(1\le j\le p-k) \]

입니다. $A-A_k$의 특이값은 $\sigma_{k+1}(A),\ldots,\sigma_p(A)$ 뒤에 0을 채운 목록입니다. 방금 얻은 성분별 부등식과 단조성으로 $\|A-A_k\|\le\|A-B\|$입니다. 따라서 절단은 모든 유니터리 불변 노름에서 최적입니다.

다음으로 von Neumann 자취부등식을 증명하겠습니다. 같은 크기의 두 행렬을 $A=\sum_i a_i u_iv_i^*$, $B=\sum_j b_j x_jy_j^*$로 쓰되 $a_i,b_j$는 내림차순 비음수 특이값입니다. 외적의 내적을 전개하고 삼각부등식을 쓰면

\[ |\operatorname{tr}(A^*B)|\le\sum_{i,j}a_ib_j c_{ij}, \qquad c_{ij}=|u_i^*x_j|\,|y_j^*v_i|. \]

Cauchy–Schwarz와 정규직교 목록의 Bessel 부등식에서 $\sum_j c_{ij}\le1$, $\sum_i c_{ij}\le1$입니다. 따라서 앞 $r$행과 앞 $s$열에 있는 $c_{ij}$의 합은 $\min(r,s)$ 이하입니다.

$a_{p+1}=b_{p+1}=0$으로 놓고 $a_i=\sum_{r\ge i}(a_r-a_{r+1})$, $b_j=\sum_{s\ge j}(b_s-b_{s+1})$를 대입하면

\[ \sum_{i,j}a_ib_jc_{ij} \le\sum_{r,s}(a_r-a_{r+1})(b_s-b_{s+1})\min(r,s) =\sum_i a_i b_i. \]

마지막 등식은 $\min(r,s)=\sum_i1\{i\le r\}1\{i\le s\}$를 대입해 유한합의 순서를 바꾸면 얻습니다. 이로써 자취부등식이 증명됩니다. 두 행렬의 좌우 특이벡터를 같게 선택하면 등호입니다.

핵노름은 $\|A\|_*=\sum_i\sigma_i(A)$입니다. 자취부등식으로 $|\operatorname{tr}(A^*B)|\le\|A\|_2\|B\|_*$를 얻습니다. $\|B\|_*\le1$에서 $B=u_1v_1^*$를 택하면 최대값 $\|A\|_2$를 달성합니다. 반대로 $\|B\|_2\le1$에서 $B=U_rV_r^*$를 택하면 최대값 $\|A\|_*$를 달성합니다. 영행렬의 경우에는 두 최대값이 모두 0입니다. 이것이 두 노름이 서로 쌍대라는 뜻입니다.

작은 특이값이 줄어들 때 정규방정식의 오차 규모가 더 빠르게 증가하는 로그 그래프 — 그림 75 작은 특이값은 정규방정식에서 제곱되어 수치 오차를 확대합니다. 이 그림은 개념적 규모 비교이며 특정 구현의 보편적 오차정리를 대신하지 않습니다.#

9. 절단의 한계#

비음수 행렬 $ A=\begin{pmatrix}1&1\\1&1\end{pmatrix} $ 의 rank-1 절단은 그대로 비음수입니다. 그러나 $ A=\begin{pmatrix}1&0\\0&1\end{pmatrix} $ 의 중복 특이공간에서 다른 최적 rank-1 근사는 음수 성분을 만들 수 있습니다. 예를 들어 $B=(1,-1)^\top(1,-1)/2$는 rank 1이지만 비음수가 아닙니다. 따라서 비음수 제약을 추가하면 SVD 절단은 제약 최적해라는 보장이 없습니다.

희소성 제약도 마찬가지입니다. 절단의 특이벡터는 대개 모든 좌표가 0이 아니므로, 희소한 근사를 요구하면 별도의 조합최적화가 필요합니다. 결측 자료에서 결측을 0으로 채운 뒤 SVD를 하는 것은 관측되지 않은 값을 0이라고 가정하는 것이며, 관측 패턴이 한 행 전체를 가리면 서로 다른 저랭크 행렬이 같은 자료를 만들 수 있어 식별 자체가 실패합니다.

9.1 제약이 붙으면 유니터리 회전 논리가 끊긴다#

SVD 절단의 최적성은 특이값만으로 노름이 결정된다는 UI 구조에 의존합니다. 비음수 제약은 좌표별 부등식 $B_{ij}\ge0$이고, 희소성은 특정 좌표의 0을 요구합니다. 둘 다 $B\mapsto UBV^*$에서 보존되지 않습니다. 예를 들어 $ B=\frac12\begin{pmatrix}1&-1\\-1&1\end{pmatrix} $ 은 rank 1이지만 음수 성분을 포함합니다. 결측 행렬에서는 관측 연산자 $P_\Omega$가 좌표를 선택하므로 $\|P_\Omega(A-B)\|$는 전체 Frobenius 노름이 아닙니다. 따라서 Eckart–Young의 하한을 그대로 적용할 수 없습니다.

9.2 결측 패턴이 식별을 막는 구체적 예#

$2\times2$ 자료의 첫째 행만 관측되어 $(1,1)$을 얻었다고 합시다. $ A=\begin{pmatrix}1&1\\0&0\end{pmatrix},\qquad B=\begin{pmatrix}1&1\\7&-7\end{pmatrix} $ 는 모두 관측된 첫째 행이 같지만 rank는 각각 1과 2입니다. 결측 둘째 행에 어떤 값을 넣었는지 관측만으로 결정할 수 없습니다. 결측을 0으로 채우면 첫 행의 정보만으로 선택한 하나의 임의 해를 만들 뿐입니다. 무작위 결측, 저랭크 가정, 관측 패턴의 충분한 분포 같은 추가 조건이 있어야 SVD 기반 복원이 의미를 가집니다.

10. 계산 랩#

아래 셀은 Rayleigh·PCA·절단오차·핵노름 쌍대성의 수치 항등식을 확인합니다. 무작위 실험은 일반 증명을 대신하지 않습니다.

import numpy as np
A=np.diag([5.,4.,3.,0.])
U,s,Vt=np.linalg.svd(A,full_matrices=False)
A2=(U[:,:2]*s[:2])@Vt[:2]
assert np.isclose(np.linalg.norm(A-A2,2),3)
assert np.isclose(np.linalg.norm(A-A2,'fro'),3)
Q=np.eye(4)[:,:2]
assert np.isclose(np.trace(Q.T@A@Q),9)
assert np.isclose(np.sum(s),12)
B=U@Vt
assert np.isclose(np.sum(s), np.trace(A.T@B))
print("H5 검산 완료")

H5 검산 완료

11. 직접 풀어 보는 연습과 전체 풀이#

연습 1. 대각행렬의 rank-2 최적근사#

$A=\operatorname{diag}(5,4,3,0)$의 rank-2 절단과 두 노름 오차를 구하세요.

풀이. $A_2=\operatorname{diag}(5,4,0,0)$입니다. 잔차는 $\operatorname{diag}(0,0,3,0)$이므로 $\|A-A_2\|_2=3$, $\|A-A_2\|_F=3$입니다. $B=\operatorname{diag}(5,0,3,0)$도 rank 2지만 잔차의 스펙트럼노름은 4, Frobenius 노름은 4로 더 큽니다.

연습 2. Courant–Fischer#

$A=\operatorname{diag}(7,2,-1)$에서 $k=2$의 max–min 값을 구하세요.

풀이. $S_*=\operatorname{span}(e_1,e_2)$에서 $r(x)=(7x_1^2+2x_2^2)/(x_1^2+x_2^2)$의 최솟값은 2입니다. 임의의 2차원 $S$는 $\operatorname{span}(e_2,e_3)$와 0이 아닌 교집합을 가지므로 그 안에 $r\le2$인 벡터가 있습니다. 따라서 최대값은 2입니다.

연습 3. Ky Fan과 PCA#

$\Sigma=\operatorname{diag}(6,3,1)$에서 두 개의 정규직교 방향이 설명할 수 있는 최대 분산을 구하세요.

풀이. Ky Fan 정리에 따라 $6+3=9$입니다. $U=[e_1,e_2]$에서 $\operatorname{tr}(U^\top\Sigma U)=6+3=9$입니다. $U=[e_1,e_3]$이면 7로 작습니다.

연습 4. 특이값과 rank 거리#

$A=\operatorname{diag}(4,1,0)$를 rank-1 이하로 만들기 위한 최소 스펙트럼노름 섭동을 구하세요.

풀이. 두 번째 특이값이 1이므로 최소값은 1입니다. $E=\operatorname{diag}(0,-1,0)$를 택하면 $A+E=\operatorname{diag}(4,0,0)$이고 $\|E\|_2=1$입니다. 교집합 하한은 어떤 다른 섭동도 1보다 작게 만들 수 없음을 보입니다.

연습 5. 핵노름 쌍대성#

$A=\operatorname{diag}(3,1)$에 대해 $\max_{\|B\|_2\le1}\operatorname{tr}(A^\top B)$를 구하세요.

풀이. 쌍대성에 따라 상한은 $\|A\|_*=4$입니다. $B=I$는 $\|B\|_2=1$이고 $\operatorname{tr}(A^\top B)=4$이므로 최대값이 4입니다.

12. 지금까지의 내용을 수학의 언어로 정리해 봅시다#

지금까지 실제 자료의 분산, 방향별 에너지, 저랭크 근사를 계산했습니다. 수학에서는 이를 다음처럼 정의하고 증명합니다.

Rayleigh 정리. 자기수반 $A$의 Rayleigh 몫은 고윳값의 구간을 정확히 채우고, 단위구의 극값은 고유벡터에서 달성합니다.

증명. 고유기저 전개가 $r(v)$를 고윳값의 볼록결합으로 만들므로 구간 안에 있습니다. 양 끝 고유벡터에서 등호입니다. $v_i+\varepsilon w$의 분자·분모를 전개하면 앞 절의 정확한 이차식이 나옵니다.

Courant–Fischer 정리.

\[\lambda_k=\max_{\dim S=k}\min_{0\ne v\in S}r(v) =\min_{\dim S=n-k+1}\max_{0\ne v\in S}r(v).\]

증명. $S$와 $\operatorname{span}(q_k,\ldots,q_n)$의 차원 공식으로 교집합의 0 아닌 벡터를 잡아 상한을 얻고, 앞 $k$개 고유벡터의 공간에서 달성합니다. $-A$를 적용하면 둘째 식입니다.

Ky Fan 정리.

\[\max_{U^*U=I_k}\operatorname{tr}(U^*AU)=\sum_{i=1}^k\lambda_i.\]

증명. $c_i=\|U^*q_i\|^2$는 $0\le c_i\le1,\sum c_i=k$입니다. 내림차순 계수에 예산을 앞에서부터 배분하는 것이 가장 크므로 결론입니다.

Eckart–Young 정리.

\[\min_{\operatorname{rank}B\le k}\|A-B\|_2=\sigma_{k+1},\qquad \min_{\operatorname{rank}B\le k}\|A-B\|_F^2=\sum_{i>k}\sigma_i^2.\]

증명. rank 제약으로 생기는 핵 교집합에 단위벡터 $z$를 잡으면 스펙트럼 하한이 $\sigma_{k+1}$입니다. Frobenius의 경우 열공간 사영과 Ky Fan으로 잔차의 하한을 얻습니다. $A_k$의 나머지 SVD가 각 하한을 달성합니다.

유니터리 불변 노름과 쌍대성. 특이값만으로 정해지는 노름에서는 같은 절단이 최적이며, 핵노름과 스펙트럼노름은 Frobenius 내적에 대해 서로 쌍대입니다. 비음수·희소·결측 제약은 유니터리 불변 구조를 깨므로 별도 최적화가 필요합니다.

특이값 절단의 최적성은 오차 노름과 허용하는 근사의 범위에 달려 있습니다. 다음 장에서는 원자료가 조금 바뀌었을 때 고윳값과 선택한 부분공간이 얼마나 움직이는지 살펴봅니다. H6로 이어 읽기.