Source-linked AI summary
Sparse Approximation via Penalty Decomposition Methods
Zhaosong Lu, Yong Zhang
TL;DR
The paper studies general sparse approximation problems formulated with l0 constraints or objectives, whose applications include compressed sensing, sparse logistic regression, and sparse inverse covariance selection. It develops penalty decomposition methods that solve penalty subproblems with block coordinate descent, establishes optimality properties under suitable assumptions, and reports generally better solution quality and/or speed than existing methods.
Problem
General sparse approximation applications involve l0 minimization problems, while specialized algorithms and l1 or lp relaxations do not cover the full problem class.
Method
Penalty decomposition methods solve a sequence of penalty subproblems using block coordinate descent.
Results
The methods’ accumulation points satisfy first-order optimality conditions under suitable assumptions, and computational tests generally outperform existing methods in solution quality and/or speed.
Takeaways & Limitations
For cases where the l0 component is the only nonconvex part, the analyzed accumulation points are local minimizers of the original problems and penalty subproblems.
Takeaways & Limitations
The BCD subproblems are nonconvex and may converge to stationary points, motivating repeated runs from perturbed solutions.
Abstract
from arXiv · showhide
In this paper we consider sparse approximation problems, that is, general $l_0$ minimization problems with the $l_0$-"norm" of a vector being a part of constraints or objective function. In particular, we first study the first-order optimality conditions for these problems. We then propose penalty decomposition (PD) methods for solving them in which a sequence of penalty subproblems are solved by a block coordinate descent (BCD) method. Under some suitable assumptions, we establish that any accumulation point of the sequence generated by the PD methods satisfies the first-order optimality conditions of the problems. Furthermore, for the problems in which the $l_0$ part is the only nonconvex part, we show that such an accumulation point is a local minimizer of the problems. In addition, we show that any accumulation point of the sequence generated by the BCD method is a saddle point of the penalty subproblem. Moreover, for the problems in which the $l_0$ part is the only nonconvex part, we establish that such an accumulation point is a local minimizer of the penalty subproblem. Finally, we test the performance of our PD methods by applying them to sparse logistic regression, sparse inverse covariance selection, and compressed sensing problems. The computational results demonstrate that our methods generally outperform the existing methods in terms of solution quality and/or speed.
1 Introduction
The paper frames diverse sparse-approximation applications as general l0 minimization problems and motivates methods beyond specialized algorithms and norm relaxations. It proposes penalty decomposition methods coupled with block coordinate descent for these problems.
- Applications: Compressed sensing, inverse covariance selection, and sparse logistic regression are presented as applications requiring sparse solutions.Compressed sensing uses relatively few linear measurements, inverse covariance selection targets conditional independence, and sparse logistic regression supports feature selection.
- Problem formulation: General l0 minimization problems place the cardinality of selected entries in constraints or objectives over differentiable functions and a closed convex feasible set.The sparsity level is controlled by integer parameters such as r and ν.
- Existing approaches: Specialized iterative hard thresholding and matching pursuit algorithms do not apply to the general l0 minimization problems considered here.The paper also describes l1 and lp relaxations as alternative approaches, with recovery guarantees only under suitable assumptions for some applications.
- Contribution: The proposed PD methods solve a sequence of penalty subproblems using BCD and are reported to generally outperform existing methods in solution quality and/or speed.The paper studies both optimality conditions and computational applications.
2 First-order optimality conditions
This section develops first-order necessary conditions for general l0 minimization and sufficient conditions under which those conditions imply local minimality. The sufficient results apply when the l0 component is the only nonconvex part.
- Necessary conditions: The paper establishes first-order necessary optimality conditions for general l0 minimization problems.The conditions are derived for both problem formulations studied in the paper.
- Necessary conditions: Under a Robinson condition, a local minimizer of problem (1) admits multipliers and a vector satisfying the stated first-order conditions.The construction uses an index set containing the allowed nonzero coordinates and its complement.
- Necessary conditions: The same Robinson-condition framework yields first-order conditions for local minimizers of problem (2).The proof reduces the sparsity formulation to a problem with selected coordinates fixed at zero.
- Sufficient conditions: When h is affine and f and g are convex, the stated first-order conditions are sufficient for local minimality of problem (1).The result requires the conditions to hold for every admissible index set of r coordinates.
- Sufficient conditions: Under the same affine-equality and convexity assumptions, the first-order conditions imply that a feasible point of problem (2) is a local minimizer.For problem (2), the condition is imposed on the index set corresponding to the nonzero entries of the point.
- Further conditions: Second-order necessary and sufficient conditions can be established similarly.
3 A class of special l0 minimization
The paper identifies a separable class of l0 minimization problems with closed-form solutions. These solutions support the construction of penalty decomposition methods for general l0 problems.
- Problem class: A separable l0 minimization class is formulated over scalar sets Xi containing zero, with coordinate functions φi and a sparsity limit.The paper gives separate propositions for cardinality-constrained and l0-penalized forms.
- Cardinality-constrained case: For the cardinality-constrained problem, an optimal solution keeps the coordinatewise minimizers associated with the r largest improvement values and sets the remaining coordinates to zero.The selected index set I* contains r coordinates, while all other entries are zero.
- Cardinality-constrained case: The cardinality-constrained construction is feasible because zero belongs to every Xi, and its optimality follows by comparing any feasible support with the selected support.The proof uses the fact that every feasible vector has at most r nonzero entries.
- Penalized case: The paper also presents a coordinatewise closed-form construction for the l0-penalized problem.The resulting vector retains coordinates satisfying the stated coordinatewise criterion and sets the others to zero.
4 Penalty decomposition methods for general l0 minimization
The paper develops penalty decomposition methods that solve sequences of penalty subproblems with block coordinate descent, establishing convergence properties for general l0 minimization problems. Under convexity and affinity conditions, accumulation points are local minimizers of both problem classes and their penalty subproblems.
- Method: Penalty decomposition methods solve general l0 minimization problems through a sequence of penalty subproblems approximately solved by block coordinate descent.The formulation can be equivalently represented with an auxiliary variable y enforcing x_J = y, and the associated quadratic penalty function is used in the subproblems.
- Assumptions: The method assumes feasibility and a known feasible solution, which supports the convergence analysis and initialization of the penalty decomposition iterations.The assumption may be dropped, but the resulting theoretical convergence guarantees may become weaker.
- Implementation: The block coordinate descent method can be terminated using penalty-objective progress or relative iterate changes, and restarts from perturbed solutions may improve performance.The restart strategy reduces the sparsity level of the current solution when possible and retains a new point if its penalty objective is sufficiently smaller.
- Inner solver: Every accumulation point of the inner block coordinate descent sequence is a saddle point of the corresponding penalty subproblem.When h is affine and f and g are convex, such a saddle point is also a local minimizer of the penalty subproblem.
- Problem (1): For problem (1), every accumulation point of the outer sequence is feasible and satisfies the first-order optimality conditions under suitable assumptions.When the l0 part is the only nonconvex component, with affine h and convex f and g, the accumulation point is a local minimizer.
- Problem (2): For problem (2), every accumulation point of the outer sequence satisfies its first-order optimality conditions under suitable assumptions.With affine h and convex f and g, the accumulation point is a local minimizer.
5 Numerical results
Numerical experiments apply the PD method to sparse logistic regression, sparse inverse covariance selection, and compressed sensing, comparing solution quality and speed with existing methods. Across these tasks, PD generally achieves better solution quality, while its speed advantage depends on the problem and baseline.
- Experimental setup: The experiments evaluate PD on sparse logistic regression, sparse inverse covariance selection, and compressed sensing problems.Implementations compare PD with SLEP, PPA, SPGL1, IHT, or GPSR depending on the task.
- Sparse logistic regression: For sparse logistic regression, PD generally achieves lower average logistic loss and error rate than SLEP at the same sparsity.SLEP is faster in most cases, but PD provides better solution quality on real and random data sets.
- Sparse inverse covariance selection: For sparse inverse covariance selection, PD is substantially faster than PPA and achieves larger log-likelihood with smaller normalized entropy loss.On sparse recovery instances, PD also completely recovers the original sparsity patterns, whereas PPA misrecovers a few patterns.
- Overall findings: The experiments conclude that PD generally produces better approximate solutions than the compared methods when the same sparsity is considered.This conclusion is stated for sparse logistic regression and the broader numerical experiments, with speed varying by task and baseline.
- Compressed sensing: With orthonormal-row sensing matrices, PD outperforms SPGL1 in recoverability, while PD and IHT are generally slower than GPSR but achieve better residuals.The comparison includes PD, IHT, and GPSR across increasing sparsity levels using warm starts.
6 Concluding remarks
The paper proposes penalty decomposition methods for general l0 minimization, solving penalty subproblems with block coordinate descent. Under suitable assumptions, the methods have convergence guarantees, and experiments show generally better solution quality and/or speed than existing methods.
- Penalty decomposition methods solve general l0 minimization problems through penalty subproblems handled by block coordinate descent.
- Under suitable assumptions, accumulation points generated by the methods satisfy the problems’ first-order optimality conditions.
- When the l0 term is the only nonconvex component, such accumulation points are local minimizers.
- Across compressed sensing, sparse logistic regression, and sparse inverse covariance selection, the proposed methods generally outperform existing methods in solution quality and/or speed.
- Augmented Lagrangian decomposition methods can also be developed, but their practical performance is generally worse than penalty decomposition methods in the experiments.
Appendix
The appendix gives an example where lp-norm regularization fails to recover a sparse solution. For every p in (0, 1], the true sparse solution is not optimal and may be a poor approximation.
- The appendix constructs a linear system with a known sparse solution that lp-norm regularization cannot recover.
- For any ν > 0, the sparse solution has a larger objective value than a denser feasible alternative and therefore is not optimal.
- The true sparse solution may therefore not be a good approximate solution to the lp-norm regularization problem.