On optimal solutions of the constrained _0 regularization and its penalty problem
From MaRDI portal
Publication:2965692
Abstract: The constrained 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 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 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 problem when the penalty parameter is sufficiently large. Based on the conditions, we further propose exact penalty problems for the constrained problem. Finally, we present a numerical example to illustrate our main theoretical results.
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₀-regularization
- New insights on the optimality conditions of the \(\ell_2-\ell_0\) minimization problem
Cites work
- Adaptive greedy approximations
- Compressed sensing
- Convergence Analysis of Generalized Iteratively Reweighted Least Squares Algorithms on Convex Function Spaces
- Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward-backward splitting, and regularized Gauss-Seidel methods
- Convex analysis and monotone operator theory in Hilbert spaces
- CoSaMP: Iterative signal recovery from incomplete and inaccurate samples
- Description of the minimizers of least squares regularized with _0-norm. Uniqueness of the global minimizer
- Efficient Reconstruction of Piecewise Constant Images Using Nonsmooth Nonconvex Minimization
- Enhancing sparsity by reweighted \(\ell _{1}\) minimization
- From Sparse Solutions of Systems of Equations to Sparse Modeling of Signals and Images
- scientific article; zbMATH DE number 1821400 (Why is no real title available?)
- Iterative reweighted minimization methods for \(l_p\) regularized unconstrained nonlinear programming
- Iterative thresholding for sparse approximations
- Just relax: convex programming methods for identifying sparse signals in noise
- Nearly unbiased variable selection under minimax concave penalty
- New convergence results for the scaled gradient projection method
- Penalty methods for a class of non-Lipschitz optimization problems
- Relationship between the optimal solutions of least squares regularized with \(\ell_{0}\)-norm and constrained by \(k\)-sparsity
- Signal Recovery From Random Measurements Via Orthogonal Matching Pursuit
- Sparse Approximate Solutions to Linear Systems
- Sparse Optimization with Least-Squares Constraints
- Sparse Reconstruction by Separable Approximation
- Variable Selection via Nonconcave Penalized Likelihood and its Oracle Properties
Cited in
(21)- Capped \(\ell_p\) approximations for the composite \(\ell_0\) regularization problem
- Optimality conditions for locally Lipschitz optimization with l₀-regularization
- New insights on the optimality conditions of the \(\ell_2-\ell_0\) minimization problem
- Solving \(\ell_0\)-penalized problems with simple constraints via the Frank-Wolfe reduced dimension method
- An active set Barzilar-Borwein algorithm for \(l_0\) regularized optimization
- 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 _0-norm. Uniqueness of the global minimizer
- Erratum: A Continuous Exact \ell₀ Penalty (CEL0) for Least Squares Regularized Problem
- A continuous exact _0 penalty (CEL0) for least squares regularized problem
- On the local and global minimizers of _0 gradient regularized model with box constraints for image restoration
- Alternating method based on framelet l0-norm and TV regularization for image restoration
- One-bit compressed sensing via \(\ell_p\) \((0<p<1)\)-minimization method
- A unified view of exact continuous penalties for _2-_0 minimization
- Sparse solutions of a class of constrained optimization problems
- Exact penalization for cardinality and rank-constrained optimization problems via partial regularization
- Solution sets of three sparse optimization problems for multivariate regression
- Solve exactly an under determined linear system by minimizing least squares regularized with an _0 penalty
- On the convergence of inexact alternate minimization in problems with \(\ell_0\) penalties
- A bisection method for computing the proximal operator of the \(\ell_p\)-norm for any \(0 < p < 1\) with application to Schatten \(p\)-norms
- A review on the adaptive-ridge algorithm with several extensions
- Parameterized proximal-gradient algorithms for L1/L2 sparse signal recovery
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)
