SVD-based 최소제곱 [medium]

v1 다변수 회귀 의 정규방정식 $(X^\top X)^{-1} X^\top y$ 는 $X^\top X$ 가 특이(singular) 하면 폭발. 원인:

• $N < D$: 언더디터민드.
• 특성 간 강한 상관 (collinearity).
• 상수 열 포함.

SVD 방식

$X = U \Sigma V^\top$ 분해. Moore-Penrose 유사역행렬:

$X^+ = V \Sigma^+ U^\top$

$\Sigma^+$ 는 각 $\sigma_i$ 에 대해 $1/\sigma_i$ (충분히 큰 경우) 또는 0 (작은 경우).

$w = X^+ y$

임계값 규칙

tol 미만의 작은 singular value 는 노이즈 로 간주해 0 처리. NumPy 기본 규칙:

$\text{tol} = \max(N, D) \cdot \epsilon \cdot \max(\sigma)$

($\epsilon \approx 10^{-15}$ for fp64)

성질

• rank-deficient 에서도 finite 해.
• 반환은 최소 norm 해 (null space 성분 0).
• $X$ 가 full-rank 면 일반 정규방정식 해와 일치.
• np.linalg.lstsq, np.linalg.pinv 의 내부 로직.

과제

함수 fit_linear_svd(X, y, tol=None) 를 완성하세요.

• X shape (N, D), y shape (N,).
• tol: singular value 임계값. None 이면 max(N, D) * eps * max(σ).
• 반환: w shape (D,).
• 힌트: U, s, Vt = np.linalg.svd(X, full_matrices=False) → s_inv = np.where(s > tol, 1/s, 0).

테스트 케이스

#	이름	검증
1	shape (D,)
2	full-rank → 정규방정식 해와 일치
3	N < D (언더디터민드) → finite + min-norm
4	collinear 특성 → finite
5	상수 열 포함 → finite
6	np.linalg.lstsq 와 일치
7	Xw ≈ y residual 최소화 (full-rank)