On optimal solutions of the constrained _0 regularization and its penalty problem

DOI10.1088/1361-6420/33/2/025010zbMATH Open1360.65183arXiv1610.02125OpenAlexW3099238915MaRDI QIDQ2965692FDOQ2965692

Authors: Na Zhang, Qia Li 

Publication date: 3 March 2017

Published in: Inverse Problems (Search for Journal in Brave)

Abstract: The constrained $el{l}_0$ regularization plays an important role in sparse reconstruction. A widely used approach for solving this problem is the penalty method, of which the least square penalty problem is a special case. However, the connections between global minimizers of the constrained $el{l}_0$ problem and its penalty problem have never been studied in a systematic way. This work provides a comprehensive investigation on optimal solutions of these two problems and their connections. We give detailed descriptions of optimal solutions of the two problems, including existence, stability with respect to the parameter, cardinality and strictness. In particular, we find that the optimal solution set of the penalty problem is piecewise constant with respect to the penalty parameter. Then we analyze in-depth the relationship between optimal solutions of the two problems. It is shown that, in the noisy case the least square penalty problem probably has no common optimal solutions with the constrained $el{l}_0$ problem for any penalty parameter. Under a mild condition on the penalty function, we establish that the penalty problem has the same optimal solution set as the constrained $el{l}_0$ problem when the penalty parameter is sufficiently large. Based on the conditions, we further propose exact penalty problems for the constrained $el{l}_0$ problem. Finally, we present a numerical example to illustrate our main theoretical results.

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

Recommendations

• A penalty decomposition method for the optimization problem with two 0-norm constraints
• Optimality conditions for the constrained \(L_p\)-regularization
• Sparse solutions of a class of constrained optimization problems
• Optimality conditions for locally Lipschitz optimization with \(l_0\)-regularization
• New insights on the optimality conditions of the \(\ell_2-\ell_0\) minimization problem

zbMATH Keywords

numerical examplesstabilityoptimal solutionspenalty methodsconstrained \(\ell_0\) regularization

Mathematics Subject Classification ID

Numerical optimization and variational techniques (65K10) Existence theories for optimal control problems involving ordinary differential equations (49J15) Discrete approximations in optimal control (49M25)

Cites Work

• Sparse Optimization with Least-Squares Constraints
• Nearly unbiased variable selection under minimax concave penalty
• Variable Selection via Nonconcave Penalized Likelihood and its Oracle Properties
• Convex analysis and monotone operator theory in Hilbert spaces
• Enhancing sparsity by reweighted \(\ell _{1}\) minimization
• Just relax: convex programming methods for identifying sparse signals in noise
• Signal Recovery From Random Measurements Via Orthogonal Matching Pursuit
• From Sparse Solutions of Systems of Equations to Sparse Modeling of Signals and Images
• Compressed sensing
• Sparse Reconstruction by Separable Approximation
• CoSaMP: Iterative signal recovery from incomplete and inaccurate samples
• Title not available (Why is that?)
• Efficient Reconstruction of Piecewise Constant Images Using Nonsmooth Nonconvex Minimization
• Adaptive greedy approximations
• Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward-backward splitting, and regularized Gauss-Seidel methods
• Iterative reweighted minimization methods for \(l_p\) regularized unconstrained nonlinear programming
• Sparse Approximate Solutions to Linear Systems
• Iterative thresholding for sparse approximations
• Relationship between the optimal solutions of least squares regularized with \(\ell_{0}\)-norm and constrained by \(k\)-sparsity
• Description of the minimizers of least squares regularized with \(\ell_0\)-norm. Uniqueness of the global minimizer
• Penalty methods for a class of non-Lipschitz optimization problems
• New convergence results for the scaled gradient projection method
• Convergence Analysis of Generalized Iteratively Reweighted Least Squares Algorithms on Convex Function Spaces

Cited In (19)

• Alternating method based on framelet l₀-norm and TV regularization for image restoration
• Erratum: A Continuous Exact $\ell_0$ Penalty (CEL0) for Least Squares Regularized Problem
• A bisection method for computing the proximal operator of the \(\ell_p\)-norm for any \(0 < p < 1\) with application to Schatten \(p\)-norms
• Exact penalization for cardinality and rank-constrained optimization problems via partial regularization
• One-bit compressed sensing via \(\ell_p\) \((0<p<1)\)-minimization method
• Relationship between the optimal solutions of least squares regularized with \(\ell_{0}\)-norm and constrained by \(k\)-sparsity
• A review on the adaptive-ridge algorithm with several extensions
• A unified view of exact continuous penalties for \(\ell_2\)-\(\ell_0\) minimization
• New insights on the optimality conditions of the \(\ell_2-\ell_0\) minimization problem
• Sparse solutions of a class of constrained optimization problems
• Solution sets of three sparse optimization problems for multivariate regression
• Capped \(\ell_p\) approximations for the composite \(\ell_0\) regularization problem
• A continuous exact \(\ell_0\) penalty (CEL0) for least squares regularized problem
• Optimality conditions for locally Lipschitz optimization with \(l_0\)-regularization
• Solving \(\ell_0\)-penalized problems with simple constraints via the Frank-Wolfe reduced dimension method
• On the local and global minimizers of \(\ell_0\) gradient regularized model with box constraints for image restoration
• Description of the minimizers of least squares regularized with \(\ell_0\)-norm. Uniqueness of the global minimizer
• Solve exactly an under determined linear system by minimizing least squares regularized with an \(\ell_0\) penalty
• An active set Barzilar-Borwein algorithm for \(l_0\) regularized optimization

Uses Software

• SPGL1
• CoSaMP

This page was built for publication: On optimal solutions of the constrained \({\ell}_{0}\) regularization and its penalty problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2965692)