Sparsity Constrained Nonlinear Optimization: Optimality Conditions and Algorithms

By Amir Beck, Yonina C. Eldar. SIAM Journal on Optimization, 2012

382 citations recorded by the source corpus.

This paper treats the problem of minimizing a general continuously differentiable function subject to sparsity constraints. We present and analyze several different optimality criteria which are based on the notions of stationarity and coordinatewise optimality. These conditions are then used to derive three numerical algorithms aimed at finding points satisfying the resulting optimality criteria: the iterative hard thresholding method and the greedy and partial sparse-simplex methods. The first algorithm is essentially a gradient projection method, while the remaining two algorithms are of a coordinate descent type. The theoretical convergence of these techniques and their relations to the derived optimality conditions are studied. The algorithms and results are illustrated by several numerical examples.

Subfields: Computational Mechanics, Computer Vision and Pattern Recognition, Numerical Analysis

View Paper: https://www.semanticscholar.org/paper/3367332acbc68cd49dc9be665556a7815a09b44b

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mechanics

In Computer Vision and Pattern Recognition

In Numerical Analysis

Citations in the corpus

Tradeoffs Between Convergence Speed and Reconstruction Accuracy in Inverse Problems (2016, neutral): “in [52], and more recently in [23] for a set of the form”
GESPAR: Efficient Phase Retrieval of Sparse Signals (2013, methodology): “Sparsity constrained nonlinear optimization problems have been considered recently in [14]; the method derived in this paper is motivated—although different in many aspects—by the local search-type techniques of”
On Solutions of Sparsity Constrained Optimization (2015, background): “28) is weaker than s-regularity of matrix A in [11], which means that every s column of A is linearly independent.”
Phase Retrieval with Application to Optical Imaging: A contemporary overview (2015, background): “The relationship between the fields of sparsity and optical imaging has led to an important generalization of the basic principles of sparsity-based reconstruction to nonlinear measurement systems [41], [44], [46]–[53].”