Least sparsity of p-norm based optimization problems with p>1

DOI10.1137/17M1140066zbMATH Open1461.65186arXiv1708.06055MaRDI QIDQ4687239FDOQ4687239

Authors: Jinglai Shen, Seyedahmad Mousavi 

Publication date: 11 October 2018

Published in: SIAM Journal on Optimization (Search for Journal in Brave)

Abstract: Motivated by $el{l}_p$-optimization arising from sparse optimization, high dimensional data analytics and statistics, this paper studies sparse properties of a wide range of $p$-norm based optimization problems with $p>1$, including generalized basis pursuit, basis pursuit denoising, ridge regression, and elastic net. It is well known that when $p>1$, 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 $p$-norm based optimization problems for a general $p>1$ 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 $el{l}_p$-optimization with $0<ple1$ and implications to robustness are also given. These results shed light on analysis and computation of general $p$-norm based optimization problems in various applications.

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

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

zbMATH Keywords

convex optimizationsparse optimizationnonlinear program\(\ell_p\)-optimization

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Convex programming (90C25) Nonlinear programming (90C30)

Cites Work

• Probing the Pareto frontier for basis pursuit solutions
• The elements of statistical learning. Data mining, inference, and prediction
• Title not available (Why is that?)
• Regularization and Variable Selection Via the Elastic Net
• Ridge Regression: Biased Estimation for Nonorthogonal Problems
• Title not available (Why is that?)
• A simple proof of the restricted isometry property for random matrices
• Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information
• Compressed sensing
• Sparse Reconstruction by Separable Approximation
• Sparsity constrained nonlinear optimization: optimality conditions and algorithms
• Lower bound theory of nonzero entries in solutions of \(\ell_2-\ell_p\) minimization
• A mathematical introduction to compressive sensing
• Title not available (Why is that?)
• Sparse recovery by non-convex optimization - instance optimality
• Sparsest solutions of underdetermined linear systems via \( \ell _q\)-minimization for \(0<q\leqslant 1\)
• An unconstrained \(\ell_q\) minimization with \(0<q\leq 1\) for sparse solution of underdetermined linear systems
• Title not available (Why is that?)
• A note on the complexity of \(L _{p }\) minimization
• Atomic decomposition by basis pursuit
• On \(\ell_ p\) programming
• Mathematical programs with cardinality constraints: reformulation by complementarity-type conditions and a regularization method
• Stable recovery of sparse signals via \(\ell_p\)-minimization
• Robustness to Unknown Error in Sparse Regularization
• Rank-deficient submatrices of Fourier matrices
• Making do with less: an introduction to compressed sensing
• Poisson Image Reconstruction With Hessian Schatten-Norm Regularization

Cited In (16)

• A new nonmonotone adaptive trust region algorithm.
• Sparse solutions of a class of constrained optimization problems
• Variational analysis of norm cones in finite dimensional Euclidean spaces
• A penalty decomposition algorithm with greedy improvement for mean‐reverting portfolios with sparsity and volatility constraints
• Title not available (Why is that?)
• Deforming \(\|.\|_1\) into \(\|.\|_{\infty}\) via polyhedral norms: a pedestrian approach
• A variational approach to sparsity optimization based on Lagrange multiplier theory
• Sparsity and persistence: mixed norms provide simple signal models with dependent coefficients
• Did you say parsimony
• Norm sensitivity of sparsity regularization with respect to p
• Trading accuracy for sparsity in optimization problems with sparsity constraints
• Solution uniqueness of convex piecewise affine functions based optimization with applications to constrained \(\ell_1\) minimization
• Some advances in theory and algorithms for sparse optimization
• Quadratic surface support vector machine with L1 norm regularization
• A survey on compressive sensing: classical results and recent advancements
• A globally convergent gradient-like method based on the Armijo line search

Uses Software

• PDCO
• SPGL1
• ElemStatLearn

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)