Sparse coding with ISTA

Shrink small coefficients to exactly zero

Sparse coding asks for a coefficient vector x that reconstructs y from the dictionary D while keeping x sparse. It minimizes 0.5 * ||y - D x||^2 + lam * ||x||_1. The L1 term is not differentiable at zero, so the iterative shrinkage-thresholding algorithm (ISTA) alternates a gradient step with a soft threshold.

Implement two functions.

• soft_threshold(z, t): returns sign(z) * max(|z| - t, 0), elementwise.

• sparse_code(D, y, lam=0.1, iters=100): starts from x = 0. Each iteration:

  1. g = D^T (D x - y)
  2. x = soft_threshold(x - step * g, step * lam)

  The step is 1 / L, where L = ||D||_2^2 (the largest singular value squared). If L is zero, use a step of 1.0.

Return x after iters iterations.

Constraints

• D is 2-D with n rows, y has length n, otherwise raise ValueError.
• lam < 0 or iters < 0 raise ValueError.
• Do not modify the inputs.

Hints