Least sparsity of p-norm based optimization problems with p>1
From MaRDI portal
Publication:4687239
Abstract: Motivated by -optimization arising from sparse optimization, high dimensional data analytics and statistics, this paper studies sparse properties of a wide range of -norm based optimization problems with , including generalized basis pursuit, basis pursuit denoising, ridge regression, and elastic net. It is well known that when , these optimization problems lead to less sparse solutions. However, the quantitative characterization of the adverse sparse properties is not available. In this paper, by exploiting optimization and matrix analysis techniques, we give a systematic treatment of a broad class of -norm based optimization problems for a general and show that optimal solutions to these problems attain full support, and thus have the least sparsity, for almost all measurement matrices and measurement vectors. Comparison to -optimization with and implications to robustness are also given. These results shed light on analysis and computation of general -norm based optimization problems in various applications.
Recommendations
- Sparse solutions of a class of constrained optimization problems
- The sparsity of underdetermined linear system via \(l_p\) minimization for \(0 < p < 1\)
- Sparse recovery by non-convex optimization - instance optimality
- Stability analysis of a class of sparse optimization problems
- Some advances in theory and algorithms for sparse optimization
Cites work
- scientific article; zbMATH DE number 46153 (Why is no real title available?)
- scientific article; zbMATH DE number 1460605 (Why is no real title available?)
- scientific article; zbMATH DE number 1461253 (Why is no real title available?)
- scientific article; zbMATH DE number 845714 (Why is no real title available?)
- A mathematical introduction to compressive sensing
- A note on the complexity of \(L _{p }\) minimization
- A simple proof of the restricted isometry property for random matrices
- An unconstrained \(\ell_q\) minimization with \(0<q\leq 1\) for sparse solution of underdetermined linear systems
- Atomic decomposition by basis pursuit
- Compressed sensing
- Lower bound theory of nonzero entries in solutions of \(\ell_2-\ell_p\) minimization
- Making do with less: an introduction to compressed sensing
- Mathematical programs with cardinality constraints: reformulation by complementarity-type conditions and a regularization method
- On \(\ell_ p\) programming
- Poisson Image Reconstruction With Hessian Schatten-Norm Regularization
- Probing the Pareto frontier for basis pursuit solutions
- Rank-deficient submatrices of Fourier matrices
- Regularization and Variable Selection Via the Elastic Net
- Ridge Regression: Biased Estimation for Nonorthogonal Problems
- Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information
- Robustness to Unknown Error in Sparse Regularization
- Sparse Reconstruction by Separable Approximation
- Sparse recovery by non-convex optimization - instance optimality
- Sparsest solutions of underdetermined linear systems via \( \ell _q\)-minimization for \(0<q\leqslant 1\)
- Sparsity constrained nonlinear optimization: optimality conditions and algorithms
- Stable recovery of sparse signals via \(\ell_p\)-minimization
- The elements of statistical learning. Data mining, inference, and prediction
Cited in
(16)- Sparsity and persistence: mixed norms provide simple signal models with dependent coefficients
- Some advances in theory and algorithms for sparse optimization
- Trading accuracy for sparsity in optimization problems with sparsity constraints
- Deforming \(\|.\|_1\) into \(\|.\|_{\infty}\) via polyhedral norms: a pedestrian approach
- A survey on compressive sensing: classical results and recent advancements
- scientific article; zbMATH DE number 6746123 (Why is no real title available?)
- Variational analysis of norm cones in finite dimensional Euclidean spaces
- A variational approach to sparsity optimization based on Lagrange multiplier theory
- Did you say parsimony
- Solution uniqueness of convex piecewise affine functions based optimization with applications to constrained \(\ell_1\) minimization
- A globally convergent gradient-like method based on the Armijo line search
- A penalty decomposition algorithm with greedy improvement for mean‐reverting portfolios with sparsity and volatility constraints
- A new nonmonotone adaptive trust region algorithm.
- Norm sensitivity of sparsity regularization with respect to p
- Quadratic surface support vector machine with L1 norm regularization
- Sparse solutions of a class of constrained optimization problems
This page was built for publication: Least sparsity of \(p\)-norm based optimization problems with \(p>1\)
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4687239)
