Iterative Hard Thresholding (IHT)

The algorithm proceeds via a simple, fixed-point iteration:

1. Gradient Descent Step: A standard gradient step is taken to minimize the objective function (e.g., least-squares loss). This moves the current estimate towards a lower-error solution but typically violates the desired sparsity constraint.
2. Hard Thresholding Projection: The result is then projected onto the constraint set. For sparse vector recovery, this means keeping only the k largest-magnitude entries (in absolute value) and setting all others to zero. For low-rank matrix recovery, it involves computing the singular value decomposition (SVD) and keeping only the top r singular values and vectors (Truncated SVD). The iteration is: x_{t+1} = H_k( x_t - μ * ∇f(x_t) ), where H_k is the hard thresholding operator.

IHT is defined by its strict, non-convex constraint enforcement via hard thresholding.

• k-Sparse Vectors: The constraint set C is the set of all vectors with at most k non-zero entries (l_0 "norm" constraint). The projection finds the best k-term approximation.
• Rank-r Matrices: The constraint set is the set of all matrices with rank at most r. The projection is the best rank-r approximation via the Eckart–Young theorem, implemented via truncated SVD. This is in contrast to methods using convex relaxations like the lasso (l_1 norm) or nuclear norm minimization, which encourage but do not strictly enforce sparsity/rank.

IHT's convergence relies critically on the choice of step size μ and the properties of the objective function f(x).

• Restricted Isometry Property (RIP): For compressed sensing problems, if the measurement matrix satisfies RIP, IHT is guaranteed to converge to the true sparse signal, provided μ is chosen appropriately.
• Step Size Rule: A common practical choice is μ = 1. For quadratic objectives like f(x) = ||Ax - b||^2, a safe and effective step size is μ = 1 / ||A^T A||, where ||·|| is the spectral norm. This ensures the gradient step is a contraction on the relevant subspace.
• Monotonicity: With a proper step size, the objective function value f(x_t) is non-increasing, though convergence can be to a local minimum due to the non-convex constraint.

IHT is favored for its low per-iteration computational cost, especially compared to interior-point methods for l_1 minimization.

• Dominant Cost: The gradient step is typically a matrix-vector product (A*x or A^T*(Ax-b)). The hard thresholding step for vectors requires a partial sort (O(n log k)) to find the top k magnitudes. For matrices, it requires a truncated SVD.
• Memory Efficiency: It operates directly on the primal variable (x or the matrix), avoiding dual variables or large linear system solves.
• Scalability: This simplicity makes IHT applicable to very large-scale problems where more complex convex optimization solvers become prohibitive.

The basic IHT framework has been extended to improve its performance and robustness:

• Normalized IHT (NIHT): Adapts the step size μ_t at each iteration using a line search, leading to faster convergence and eliminating the need to know the Lipschitz constant of the gradient.
• Compressive Sampling Matching Pursuit (CoSaMP) & Subspace Pursuit: More sophisticated greedy algorithms that perform a larger combinatorial search at each iteration (e.g., merging candidate support sets) for better empirical recovery.
• Hard Thresholding Pursuit (HTP): After thresholding, it solves a least-squares problem on the identified support set to compute the next iterate, often improving accuracy.
• Accelerated IHT: Uses momentum techniques (e.g., Nesterov acceleration) to speed up convergence.

While discussed in model compression for inducing sparsity, IHT's primary theoretical grounding is in signal processing and statistical estimation.

• Compressed Sensing: Recovering a sparse signal from far fewer linear measurements than its ambient dimension.
• Low-Rank Matrix Completion: Filling in missing entries of a matrix (e.g., a ratings matrix) under the assumption it is low-rank.
• Robust PCA (Principal Component Pursuit): Separating a low-rank matrix from sparse corruptions.
• Sparse Coding / Dictionary Learning: In the M-step, finding sparse codes for a set of signals given a fixed dictionary.

The hard thresholding operator, denoted H_k(·), is the nonlinear projection at the core of IHT. For a vector x, it sets all but the k largest (in magnitude) entries to zero. For a matrix, it can be applied to singular values to enforce a low-rank constraint via the singular value thresholding operator. This operation is non-convex and non-linear, making the overall IHT optimization problem challenging but highly effective for enforcing strict sparsity.

Compressed Sensing is a signal processing paradigm that enables accurate reconstruction of sparse signals from far fewer linear measurements than required by the Nyquist-Shannon theorem. IHT is a fundamental greedy pursuit algorithm for solving the sparse recovery problem in compressed sensing. The core problem is: recover a sparse vector x from measurements y = Ax + e, where A is a measurement matrix. IHT directly tackles the l0-pseudo-norm constrained minimization: minimize ||y - Ax||² subject to ||x||₀ ≤ k.

Gradient Descent is the foundational first-order iterative optimization algorithm that IHT modifies. Standard gradient descent minimizes a loss function L(θ) by updating parameters: θ_{t+1} = θ_t - η ∇L(θ_t). IHT incorporates a projection step after each gradient update: θ_{t+1} = H_k( θ_t - η ∇L(θ_t) ). This simple yet powerful combination of gradient-based minimization with a sparsity-enforcing projection defines IHT's iterative structure. The learning rate η is critical for convergence guarantees.

Low-Rank Matrix Completion is the problem of recovering a complete matrix from a small subset of its observed entries, under the assumption that the true matrix has low rank. IHT is adapted for this by applying gradient descent on the observed data fit, followed by hard thresholding of singular values. The update becomes: X_{t+1} = T_r( X_t - η ∇_X ||P_Ω(X) - P_Ω(M)||_F² ), where T_r(·) is the rank-r singular value thresholding operator, P_Ω is the observation mask, and M is the observed data.

LASSO (Least Absolute Shrinkage and Selection Operator) is a convex relaxation method for sparse regression that uses L1-norm regularization: minimize ||y - Ax||² + λ||x||₁. Unlike IHT's direct l0 constraint, LASSO promotes sparsity via a continuous, convex penalty. Key comparisons:

• Convex vs. Non-Convex: LASSO is convex (guaranteed global minima); IHT tackles the non-convex l0 problem directly.
• Regularization Parameter: LASSO uses λ; IHT uses the explicit sparsity level k.
• Solution Character: LASSO solutions may not be truly sparse; IHT enforces exact k-sparsity.

Orthogonal Matching Pursuit (OMP) is another greedy algorithm for sparse approximation. While both IHT and OMP are iterative and enforce sparsity, their mechanisms differ fundamentally:

• IHT: Takes a gradient step, then applies hard thresholding to the entire vector. It's a parallel method.
• OMP: Selects one atom (column of A) per iteration based on maximum correlation with the residual, then solves a least-squares problem on the selected support. It's a sequential method. IHT often has lower computational cost per iteration but may require careful step-size tuning, whereas OMP's support selection is more deliberate but sequential.