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_0\)-regularization
- New insights on the optimality conditions of the \(\ell_2-\ell_0\) minimization problem
Cites work
- scientific article; zbMATH DE number 1821400 (Why is no real title available?)
- Adaptive greedy approximations
- CoSaMP: Iterative signal recovery from incomplete and inaccurate samples
- 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
- Description of the minimizers of least squares regularized with \(\ell_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
- 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
(20)- Solving \(\ell_0\)-penalized problems with simple constraints via the Frank-Wolfe reduced dimension method
- Solution sets of three sparse optimization problems for multivariate regression
- On the convergence of inexact alternate minimization in problems with \(\ell_0\) penalties
- One-bit compressed sensing via \(\ell_p\) \((0<p<1)\)-minimization method
- A unified view of exact continuous penalties for \(\ell_2\)-\(\ell_0\) minimization
- 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
- Alternating method based on framelet l0-norm and TV regularization for image restoration
- 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
- Erratum: A Continuous Exact $\ell_0$ Penalty (CEL0) for Least Squares Regularized Problem
- New insights on the optimality conditions of the \(\ell_2-\ell_0\) minimization problem
- Exact penalization for cardinality and rank-constrained optimization problems via partial regularization
- 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
- 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
- Capped \(\ell_p\) approximations for the composite \(\ell_0\) regularization problem
- Sparse solutions of a class of constrained optimization problems
- Optimality conditions for locally Lipschitz optimization with \(l_0\)-regularization
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)
