ISTA [medium]

v1 Soft thresholding 은 한 번의 proximal 연산. ISTA (Iterative Shrinkage-Thresholding Algorithm) 는 이를 gradient descent 와 결합 해서 LASSO 문제를 반복적으로 푸는 전체 알고리즘.

LASSO 목적함수

$\min_w \; \tfrac{1}{2} \|y - X w\|^2 + \lambda \|w\|_1$

ISTA 반복

매 iteration:

1. Gradient step (smooth 부분의 그래디언트): $g = X^\top (X w - y)$
2. Proximal step (L1 페널티의 proximal operator = soft threshold): $w \gets S_{\lambda / L}\!\left(w - \frac{1}{L} g\right)$

여기서 $L \ge \|X^\top X\|_2$ (= largest eigenvalue, Lipschitz 상수). 실무엔 L = np.linalg.eigvalsh(X.T@X).max() 또는 보수적으로 np.linalg.norm(X, 2)**2.

수렴

$O(1/t)$ (FISTA 는 $O(1/t^2)$ 로 가속). 동일 해 → coordinate descent (LASSO 전용) 와 일치.

과제

함수 ista(X, y, lam, max_iter=200) 를 완성하세요.

• X shape (N, D), y shape (N,), lam > 0.
• 반환: w shape (D,).
• L = np.linalg.eigvalsh(X.T @ X).max() 로 step size.
• 초기화 w = 0.

테스트 케이스

#	이름	검증
1	shape (D,)
2	lam=0 → OLS 해 근사 (수렴 가정)
3	큰 lam → w = 0
4	중간 lam → 희소
5	실제 희소 signal 복원
6	sklearn Lasso 와 유사 (	w
7	반복 수 많을수록 수렴