Iterative Hard Thresholding

Simple iterative hard thresholding algorithm.

mr_utils.cs.thresholding.iterative_hard_thresholding.IHT(A, y, k, mu=1, maxiter=500, tol=1e-08, x=None, disp=False)[source]

Iterative hard thresholding algorithm (IHT).

Parameters:
  • A (array_like) – Measurement matrix.
  • y (array_like) – Measurements (i.e., y = Ax).
  • k (int) – Number of expected nonzero coefficients.
  • mu (float, optional) – Step size.
  • maxiter (int, optional) – Maximum number of iterations.
  • tol (float, optional) – Stopping criteria.
  • x (array_like, optional) – True signal we are trying to estimate.
  • disp (bool, optional) – Whether or not to display iterations.
Returns:

x_hat – Estimate of x.
Return type:

array_like

Notes

Solves the problem:

\[\min_x || y - Ax ||^2_2 \text{ s.t. } ||x||_0 \leq k\]

If disp=True, then MSE will be calculated using provided x. mu=1 seems to satisfy Theorem 8.4 often, but might need to be adjusted (usually < 1). See normalized IHT for adaptive step size.

Implements Algorithm 8.5 from [1].

References

[1]Eldar, Yonina C., and Gitta Kutyniok, eds. Compressed sensing: theory and applications. Cambridge University Press, 2012.