Restricted normal cones and sparsity optimization with affine constraints
From MaRDI portal
Abstract: The problem of finding a vector with the fewest nonzero elements that satisfies an underdetermined system of linear equations is an NP-complete problem that is typically solved numerically via convex heuristics or nicely-behaved non convex relaxations. In this paper we consider the elementary method of alternating projections (MAP) for solving the sparsity optimization problem without employing convex heuristics. In a parallel paper we recently introduced the restricted normal cone which generalizes the classical Mordukhovich normal cone and reconciles some fundamental gaps in the theory of sufficient conditions for local linear convergence of the MAP algorithm. We use the restricted normal cone together with the notion of superregularity, which is naturally satisfied for the affine sparse optimization problem, to obtain local linear convergence results with estimates for the radius of convergence of the MAP algorithm applied to sparsity optimization with an affine constraint.
Recommendations
- Sparsity constrained nonlinear optimization: optimality conditions and algorithms
- Convex optimization under combinatorial sparsity constraints
- On solutions of sparsity constrained optimization
- Structural properties of affine sparsity constraints
- Concave programming for finding sparse solutions to problems with convex constraints
- On constrained optimization with nonconvex regularization
- A unifying framework for sparsity-constrained optimization
- Sparse solutions of a class of constrained optimization problems
- Structured sparsity through convex optimization
- Sparse Optimization with Least-Squares Constraints
Cites work
- scientific article; zbMATH DE number 1382772 (Why is no real title available?)
- A linearly convergent algorithm for solving a class of nonconvex/affine feasibility problems
- Alternating Projections on Manifolds
- An unconstrained \(\ell_q\) minimization with \(0<q\leq 1\) for sparse solution of underdetermined linear systems
- Best approximation in inner product spaces
- Convex Analysis
- Convex analysis and monotone operator theory in Hilbert spaces
- Entropic regularization of the \(\ell _{0}\) function
- From Sparse Solutions of Systems of Equations to Sparse Modeling of Signals and Images
- Implicit Functions and Solution Mappings
- Local linear convergence for alternating and averaged nonconvex projections
- Local linear convergence of approximate projections onto regularized sets
- Method of successive projections for finding a common point of sets in metric spaces
- Near-Optimal Signal Recovery From Random Projections: Universal Encoding Strategies?
- Optimally sparse representation in general (nonorthogonal) dictionaries via ℓ 1 minimization
- Proximal Alternating Minimization and Projection Methods for Nonconvex Problems: An Approach Based on the Kurdyka-Łojasiewicz Inequality
- Reflection-projection method for convex feasibility problems with an obtuse cone
- Restricted normal cones and the method of alternating projections: applications
- Restricted normal cones and the method of alternating projections: theory
- Sparse Approximate Solutions to Linear Systems
- Techniques of variational analysis
- Theory of Reproducing Kernels
Cited in
(28)- A quadratic penalty method for hypergraph matching
- On solutions of sparsity constrained optimization
- The first-order necessary conditions for sparsity constrained optimization
- Prox-regularity of rank constraint sets and implications for algorithms
- Inertial Proximal Block Coordinate Method for a Class of Nonsmooth Sum-of-Ratios Optimization Problems
- Restricted normal cones and the method of alternating projections: applications
- Restricted normal cones and the method of alternating projections: theory
- Cardinality minimization, constraints, and regularization: a survey
- Optimization on Spheres: Models and Proximal Algorithms with Computational Performance Comparisons
- Recent results on Douglas-Rachford methods for combinatorial optimization problems
- Kurdyka-Łojasiewicz property of zero-norm composite functions
- A convergent relaxation of the Douglas-Rachford algorithm
- Algorithms based on unions of nonexpansive maps
- Orbital geometry and group majorisation in optimisation
- Sequential M-stationarity conditions for general optimization problems
- Sparsity constrained optimization problems via disjunctive programming
- Malitsky-Tam forward-reflected-backward splitting method for nonconvex minimization problems
- Quantitative Convergence Analysis of Iterated Expansive, Set-Valued Mappings
- Solution sets of three sparse optimization problems for multivariate regression
- Optimality conditions for sparse nonlinear programming
- Optimality conditions and constraint qualifications for cardinality constrained optimization problems
- An augmented Lagrangian method for optimization problems with structured geometric constraints
- Second-order optimality conditions for sparse optimization via Fréchet second-order subdifferential
- Regularity properties of non-negative sparsity sets
- Restricted Robinson constraint qualification and optimality for cardinality-constrained cone programming
- Phase retrieval with sparse phase constraint
- Projected gradient descent accumulates at Bouligand stationary points
- Duality and Convex Programming
This page was built for publication: Restricted normal cones and sparsity optimization with affine constraints
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q404252)
