Lower Bound Theory of Nonzero Entries in Solutions of $\ell_2$-$\ell_p$ Minimization

DOI10.1137/090761471zbMath1242.90174OpenAlexW1973397215MaRDI QIDQ3006142

Publication date: 10 June 2011

Published in: SIAM Journal on Scientific Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/090761471

zbMATH Keywords

linear least-squares problem variable selection smoothing approximation sparse solution second order condition $\ell_p$ regularization first order condition

Mathematics Subject Classification ID

Applications of mathematical programming (90C90) Nonconvex programming, global optimization (90C26) Optimality conditions and duality in mathematical programming (90C46)

Related Items

An efficient semismooth Newton method for adaptive sparse signal recovery problems, Solving constrained nonsmooth group sparse optimization via group Capped-$\ell_1$ relaxation and group smoothing proximal gradient algorithm, Local optimality for stationary points of group zero-norm regularized problems and equivalent surrogates, Doubly majorized algorithm for sparsity-inducing optimization problems with regularizer-compatible constraints, Zero-norm regularized problems: equivalent surrogates, proximal MM method and statistical error bound, A convergent iterative support shrinking algorithm for non-Lipschitz multi-phase image labeling model, A Regularized Newton Method for ${\boldsymbol{\ell}}_{q}$ -Norm Composite Optimization Problems, A decentralized smoothing quadratic regularization algorithm for composite consensus optimization with non-Lipschitz singularities, $k$-sparse vector recovery via truncated $\ell_1 -\ell_2$ local minimization, Optimal correction of infeasible equations system as Ax + B|x|= b using ℓ p-norm regularization, A smoothing iterative method for quantile regression with nonconvex $\ell_p$ penalty, Robust distribution-based nonnegative matrix factorizations for dimensionality reduction, $S_{1/2}$ regularization methods and fixed point algorithms for affine rank minimization problems, A General Non-Lipschitz Infimal Convolution Regularized Model: Lower Bound Theory and Algorithm, A Barzilai-Borwein-like iterative half thresholding algorithm for the $L_{1/2}$ regularized problem, Iterative thresholding algorithm based on non-convex method for modified $l_p$-norm regularization minimization, Smoothing projected Barzilai-Borwein method for constrained non-Lipschitz optimization, A smoothing SQP framework for a class of composite $L_q$ minimization over polyhedron, Linearly Constrained Non-Lipschitz Optimization for Image Restoration, A truncated Newton algorithm for nonconvex sparse recovery, Optimality conditions for the constrainedL_p-regularization, Sparse solutions of linear complementarity problems, Optimization conditions and decomposable algorithms for convertible nonconvex optimization, A penalty decomposition approach for multi-objective cardinality-constrained optimization problems, DC approximation approaches for sparse optimization, High-Dimensional Learning Under Approximate Sparsity with Applications to Nonsmooth Estimation and Regularized Neural Networks, A smoothing majorization method for matrix minimization, Unnamed Item, Point source super-resolution via non-convex $L_1$ based methods, Global optimality condition and fixed point continuation algorithm for non-Lipschitz $\ell_p$ regularized matrix minimization, An interior stochastic gradient method for a class of non-Lipschitz optimization problems, The smoothing objective penalty function method for two-cardinality sparse constrained optimization problems, The sparsity of underdetermined linear system via $l_p$ minimization for $0 < p < 1$, Convergence and stability analysis of the half thresholding based few-view CT reconstruction, A globally convergent algorithm for a constrained non-Lipschitz image restoration model, Recent advances in mathematical programming with semi-continuous variables and cardinality constraint, The equivalence of three types of error bounds for weakly and approximately convex functions, Half thresholding eigenvalue algorithm for semidefinite matrix completion, $l_{p}$-norm regularization method ($ 0<p<1 $) and DC programming for correction system of inconsistency linear inequalities, An improved algorithm for the $L_2-L_p$ minimization problem, Folded concave penalized sparse linear regression: sparsity, statistical performance, and algorithmic theory for local solutions, Feature selection in machine learning: an exact penalty approach using a difference of convex function algorithm, A generalized elastic net regularization with smoothed $\ell _{q}$ penalty for sparse vector recovery, Adaptive projected gradient thresholding methods for constrained $l_0$ problems, Proximal linearization methods for Schatten $p$-quasi-norm minimization, An Augmented Lagrangian Method for Non-Lipschitz Nonconvex Programming, Recovery of sparsest signals via $\ell^q $-minimization, $\ell _p$ regularized low-rank approximation via iterative reweighted singular value minimization, Affine matrix rank minimization problem via non-convex fraction function penalty, A nonconvex truncated regularization and box-constrained model for CT reconstruction, Effective zero-norm minimization algorithms for noisy compressed sensing, Linear-step solvability of some folded concave and singly-parametric sparse optimization problems, Complexity of unconstrained $L_2 - L_p$ minimization, A superlinearly convergent $R$-regularized Newton scheme for variational models with concave sparsity-promoting priors, Restricted $p$-isometry properties of partially sparse signal recovery, A unified algorithm for mixed $l_{2,p}$-minimizations and its application in feature selection, An iterative support shrinking algorithm for non-Lipschitz optimization in image restoration, Iterative reweighted minimization methods for $l_p$ regularized unconstrained nonlinear programming, Mathematical programs with complementarity constraints and a non-Lipschitz objective: optimality and approximation, Global solutions of non-Lipschitz $S_{2}$-$S_{p}$ minimization over the positive semidefinite cone, Minimal zero norm solutions of linear complementarity problems, Unnamed Item, Complexity of Partially Separable Convexly Constrained Optimization with Non-Lipschitzian Singularities, Relating $\ell_p$ regularization and reweighted $\ell_1$ regularization, On monotone and primal-dual active set schemes for $\ell^p$-type problems, $p \in (0,1$], Robust $L_p$-norm least squares support vector regression with feature selection, A note on the smoothing quadratic regularization method for non-Lipschitz optimization, Non-convex ℓ_p regularization for sparse reconstruction of electrical impedance tomography, On the Edge Recovery Property of Noncovex Nonsmooth Regularization in Image Restoration, Unnamed Item, A general truncated regularization framework for contrast-preserving variational signal and image restoration: motivation and implementation, Iterative reweighted methods for $\ell _1-\ell _p$ minimization, A reweighted nuclear norm minimization algorithm for low rank matrix recovery, A new globally convergent algorithm for non-Lipschitz $\ell_{p}-\ell_q$ minimization, Penalty Methods for a Class of Non-Lipschitz Optimization Problems, High-order evaluation complexity for convexly-constrained optimization with non-Lipschitzian group sparsity terms, Smoothing methods for nonsmooth, nonconvex minimization, Linear convergence of inexact descent method and inexact proximal gradient algorithms for lower-order regularization problems, Novel iterative ensemble smoothers derived from a class of generalized cost functions, Recovery of seismic wavefields by an $l_{q}$-norm constrained regularization method, Evaluating and selecting features via information theoretic lower bounds of feature inner correlations for high-dimensional data, Least Sparsity of $p$-Norm Based Optimization Problems with $p>1$, Spherical Designs and Nonconvex Minimization for Recovery of Sparse Signals on the Sphere, Convergent inexact penalty decomposition methods for cardinality-constrained problems, New regularization method and iteratively reweighted algorithm for sparse vector recovery, A truncation algorithm for minimizing the Frobenius-Schatten norm to find a sparse matrix, A gradient descent based algorithm for $\ell_p$ minimization, Complexity analysis of interior point algorithms for non-Lipschitz and nonconvex minimization, Convergence analyses on sparse feedforward neural networks via group lasso regularization, Computation of second-order directional stationary points for group sparse optimization, On sparse beamformer design with reverberation, Convergence of the reweighted $\ell_1$ minimization algorithm for $\ell_2-\ell_p$ minimization, A constrained optimization reformulation and a feasible descent direction method for $L_{1/2}$ regularization, Successive convex approximations to cardinality-constrained convex programs: a piecewise-linear DC approach, An efficient optimization approach for a cardinality-constrained index tracking problem, Image retinex based on the nonconvex TV-type regularization, $L_p$-norm Regularization Algorithms for Optimization Over Permutation Matrices, Non-Lipschitz Models for Image Restoration with Impulse Noise Removal, The $\ell_{2,q}$ regularized group sparse optimization: lower bound theory, recovery bound and algorithms, Sparse Solutions by a Quadratically Constrained ℓq (0 <q< 1) Minimization Model, EXACT LOW-RANK MATRIX RECOVERY VIA NONCONVEX SCHATTEN p-MINIMIZATION, Optimality condition and complexity analysis for linearly-constrained optimization without differentiability on the boundary, Minimization of $\ell_{1-2}$ for Compressed Sensing, Truncated $l_{1-2}$ Models for Sparse Recovery and Rank Minimization, Bilevel Optimization of Regularization Hyperparameters in Machine Learning, Isotropic non-Lipschitz regularization for sparse representations of random fields on the sphere, An accelerated majorization-minimization algorithm with convergence guarantee for non-Lipschitz wavelet synthesis model ^*, Sparse Solutions of a Class of Constrained Optimization Problems, An alternating direction method with continuation for nonconvex low rank minimization, Entropy function-based algorithms for solving a class of nonconvex minimization problems

Uses Software

GradSamp