Low-Rank Approximation [medium]

v1 Frobenius norm 은 행렬 크기 측정. 이제 이를 사용해 행렬을 더 작은 rank 로 근사. 이미지 압축, 추천 시스템 (latent factor model), 차원 축소의 기본.

Eckart-Young-Mirsky 정리

임의 행렬 $A \in \mathbb{R}^{m \times n}$ 의 SVD: $A = U \Sigma V^\top = \sum_{i=1}^{r} \sigma_i \, u_i v_i^\top$

rank $k$ (with $k < r$) 최적 근사 $A_k$ 는 상위 $k$ 성분만 유지: $A_k = \sum_{i=1}^{k} \sigma_i \, u_i v_i^\top = U_k \Sigma_k V_k^\top$

그리고 Frobenius 오차는 정확히: $\|A - A_k\|_F = \sqrt{\sum_{i=k+1}^{r} \sigma_i^2}$

이 값보다 더 낮은 rank-k 근사는 존재하지 않음 (optimal).

활용

• 이미지 압축: $m \times n$ pixel 행렬 → rank-k 저장 필요 공간 $k(m+n+1)$.
• 추천 시스템: 사용자-항목 평점 행렬의 latent factor.
• 노이즈 제거: 작은 특이값이 noise → 잘라냄.

구현 힌트

U, s, Vt = np.linalg.svd(A, full_matrices=False)
A_k = U[:, :k] * s[:k] @ Vt[:k]         # or U[:, :k] @ np.diag(s[:k]) @ Vt[:k]
error = np.sqrt(np.sum(s[k:] ** 2))

U[:, :k] * s[:k] 는 열 단위 scaling (broadcasting).

과제

함수 low_rank_approx(A, k) 를 완성하세요.

• 반환: (A_k, error) — A_k shape = A.shape, error Python float.
• k > min(A.shape) 일 때 → A_k = A, error = 0.

테스트 케이스

#	이름	검증
1	shape 유지	A_k.shape == A.shape
2	error = sqrt(sum σ_{k+1:}²)	Eckart-Young
3	k=rank → error = 0, A_k = A
4	실제 ‖A - A_k‖_F == error 검증
5	rank-1 행렬에 k=1 → 완벽 복원
6	임의 rank-k 근사보다 낮은 오차	최적성 확인
7	k > min(m, n) → error=0