Author: Zhaosong Lu
Published: 2012
Introduction
In the fields of compressed sensing, signal processing, and high-dimensional statistics, researchers often seek "sparse" solutions—mathematical models where only a few variables are active or non-zero. The most direct way to enforce this sparsity is through $l_0$ regularization, which explicitly counts the number of non-zero entries in a solution vector. However, the $l_0$ norm is notoriously difficult to optimize because it is non-convex and discontinuous, rendering the resulting optimization problems NP-hard in the general case.
While Iterative Hard Thresholding (IHT) methods have previously demonstrated success in solving unconstrained sparse least-squares problems, a significant gap remained in the theoretical literature: how to apply these methods when variables must satisfy complex geometric constraints. Such constraints include box constraints (e.g., variables within a specific range) or membership in a convex cone (e.g., the positive semi-definite cone). This paper bridges that gap by providing a rigorous theoretical framework for $l_0$ regularized convex cone programming.
Problem Formulation
The paper addresses the optimization of a smooth convex function $f(x)$ subject to $l_0$ regularization and additional constraints. The general form can be expressed as:
$$\min \{ f(x) + \lambda \|x\|_0 : x \in X \}$$
where $X$ represents a convex set, often defined by box constraints or cone constraints. The challenge lies in the fact that the objective function is non-convex due to the $l_0$ term, and the feasible region $X$ can be complex, making traditional gradient-based methods insufficient on their own.
Proposed Methodologies
The author introduces two primary algorithmic frameworks to handle these constraints efficiently:
1. IHT for Box-Constrained Problems
For problems where the variables are bounded by simple box constraints (e.g., $l \le x \le u$), the author develops a specialized IHT method. Each iteration involves a gradient descent step followed by a "hard thresholding" projection onto the intersection of the $l_0$ ball and the box constraints. A key contribution of this work is the demonstration that this specific subproblem possesses a simple closed-form solution. This allows the algorithm to remain computationally efficient even as it handles non-convexity.
2. Quadratic Penalty Relaxation for Cone Programming
To address more general convex cone constraints (such as $Ax - b \in K^*$), the paper employs a penalty-based approach. The hard constraints are moved into the objective function as a squared distance penalty. This relaxation allows the previously developed box-constrained IHT framework to be applied to the penalized objective. By iteratively updating the penalty parameter, the algorithm can approximate the solution to the original constrained problem.
3. Adaptive Variants
Recognizing that global properties like the Lipschitz constant of the gradient are not always known, the paper introduces adaptive variants of the algorithms. These versions dynamically update step sizes and penalty parameters, making the framework more robust and practical for real-world applications where prior knowledge of the function's global properties is limited.
Theoretical Insights and Results
The primary contribution of this paper is its rigorous mathematical foundation, providing several "firsts" for $l_0$ constrained optimization:
- Guaranteed Local Optimality: Given the non-convex nature of the $l_0$ norm, finding a global minimum is generally intractable. The author proves that the proposed IHT sequence is guaranteed to converge to a local minimizer, providing a reliable performance floor for practitioners.
- Iteration Complexity Bounds: The paper establishes concrete iteration complexity. For strongly convex objective functions, the author proves that the number of iterations required to find an $\epsilon$-approximate local minimizer is proportional to $\log(1/\epsilon)$. This establishes a mathematical "speed limit" for the algorithm's convergence.
- Penalty Method Convergence: The author rigorously proves that by carefully managing the penalty parameter $\rho$, every accumulation point generated by the algorithm is a local minimizer of the original, non-relaxed cone programming problem.
Conclusion and Future Directions
This work provides the necessary "blueprints" for solving complex sparse optimization problems with geometric constraints. While the paper is primarily theoretical and does not include empirical benchmarks (which the author addressed in subsequent working papers), it establishes the convergence and complexity guarantees required for reliable solver development.
Future research directions suggested by the author include extending these IHT methods to rank minimization problems—the matrix equivalent of vector sparsity—and exploring scenarios where the objective function $f(x)$ is itself non-convex. These extensions would further broaden the applicability of hard thresholding methods in modern data science.
Summary updated