Restricted normal cones and sparsity optimization with affine constraints

DOI10.1007/S10208-013-9161-0zbMATH Open1298.49047arXiv1205.0320OpenAlexW2107479212MaRDI QIDQ404252FDOQ404252

D. Russell Luke, Hung M. Phan, Heinz H. Bauschke, Xianfu Wang

Publication date: 4 September 2014

Published in: Foundations of Computational Mathematics (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1205.0320

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

zbMATH Keywords

alternating projections methodrestricted normal conessparsity optimization

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Nonlinear programming (90C30) Nonsmooth analysis (49J52) Numerical methods of relaxation type (49M20)

Cites Work

• Near-Optimal Signal Recovery From Random Projections: Universal Encoding Strategies?
• Theory of Reproducing Kernels
• Convex analysis and monotone operator theory in Hilbert spaces
• Optimally sparse representation in general (nonorthogonal) dictionaries via ℓ ¹ minimization
• Convex Analysis
• From Sparse Solutions of Systems of Equations to Sparse Modeling of Signals and Images
• Proximal Alternating Minimization and Projection Methods for Nonconvex Problems: An Approach Based on the Kurdyka-Łojasiewicz Inequality
• Title not available (Why is that?)
• Techniques of variational analysis
• Implicit Functions and Solution Mappings
• An Unconstrained $\ell_q$ Minimization with $0q\leq1$ for Sparse Solution of Underdetermined Linear Systems
• Sparse Approximate Solutions to Linear Systems
• Best approximation in inner product spaces
• Restricted normal cones and the method of alternating projections: applications
• Restricted normal cones and the method of alternating projections: theory
• Alternating Projections on Manifolds
• Local linear convergence for alternating and averaged nonconvex projections
• Method of successive projections for finding a common point of sets in metric spaces
• Reflection-projection method for convex feasibility problems with an obtuse cone
• Entropic Regularization of the ℓ 0 Function
• Local linear convergence of approximate projections onto regularized sets
• A Linearly Convergent Algorithm for Solving a Class of Nonconvex/Affine Feasibility Problems

Cited In (26)

• 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
• Cardinality minimization, constraints, and regularization: a survey
• Optimization on Spheres: Models and Proximal Algorithms with Computational Performance Comparisons
• Restricted normal cones and the method of alternating projections: applications
• Restricted normal cones and the method of alternating projections: theory
• Recent results on Douglas-Rachford methods for combinatorial optimization problems
• Kurdyka-Łojasiewicz property of zero-norm composite functions
• Sequential M-stationarity conditions for general optimization problems
• A convergent relaxation of the Douglas-Rachford algorithm
• Algorithms based on unions of nonexpansive maps
• Orbital geometry and group majorisation in optimisation
• Sparsity constrained optimization problems via disjunctive programming
• Phase Retrieval with Sparse Phase Constraint
• Malitsky-Tam forward-reflected-backward splitting method for nonconvex minimization problems
• Solution sets of three sparse optimization problems for multivariate regression
• Quantitative Convergence Analysis of Iterated Expansive, Set-Valued Mappings
• 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
• Regularity properties of non-negative sparsity sets
• Restricted Robinson constraint qualification and optimality for cardinality-constrained cone programming
• 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)