Sparse approximation over the cube

DOI10.1007/978-3-031-32726-1_4MaRDI QIDQ6085987zbMATH OpenOpenAlexFDO

Authors Sabrina Bruckmeier, Christoph Hunkenschröder, Robert Weismantel

Publication date 9 November 2023

Published in Integer Programming and Combinatorial Optimization (Search for Journal in Brave)

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

zbMATH Keywords

signal recoverysparse approximationsubset selection

Mathematics Subject Classification ID

Nonlinear programming (90C30) Applications of mathematical programming (90C90)

Abstract: This paper presents an anlysis of the NP-hard minimization problem $min|b-Ax{|}_2:xin[0,1{]}^n,|extsupp(x)|leqsigma$, where $extsupp(x)=iin[n]:x_{i}eq0$ and $sigma$ is a positive integer. The object of investigation is a natural relaxation where we replace $|extsupp(x)|leqsigma$ by $su{m}_i{x}_{i}leqsigma$. Our analysis includes a probabilistic view on when the relaxation is exact. We also consider the problem from a deterministic point of view and provide a bound on the distance between the images of optimal solutions of the original problem and its relaxation under $A$. This leads to an algorithm for generic matrices $Ainmathbb{Z}^{mimesn}$ and achieves a polynomial running time provided that $m$ and $|A{|}_{infty}$ are fixed.

Recommendations

• Sparse Approximate Solutions to Linear Systems
• A note on the complexity of \(L _{p }\) minimization
• Algorithms for simultaneous sparse approximation. II: Convex relaxation
• For most large underdetermined systems of linear equations the minimal 𝓁₁‐norm solution is also the sparsest solution
• Approximation hardness for a class of sparse optimization problems

Cites work

• A concave optimization-based approach for sparse portfolio selection
• A general solution to least squares problems with box constraints and its applications
• A note on the complexity of \(L _{p }\) minimization
• A note on the hardness of sparse approximation
• A polynomial algorithm for best-subset selection problem
• A polynomial case of the cardinality-constrained quadratic optimization problem
• A smoothing method for sparse optimization over polyhedral sets
• Atomic decomposition by basis pursuit
• Complementarity formulations of \(\ell_0\)-norm optimization
• Compressed sensing
• Concave programming for finding sparse solutions to problems with convex constraints
• Concave programming for minimizing the zero-norm over polyhedral sets
• Decoding by Linear Programming
• Equivalence of minimal \(\ell _{0}\)- and \(\ell _{p }\)-norm solutions of linear equalities, inequalities and linear programs for sufficiently small \(p\)
• Greed is Good: Algorithmic Results for Sparse Approximation
• scientific article; zbMATH DE number 5485514 (Why is no real title available?)
• scientific article; zbMATH DE number 729680 (Why is no real title available?)
• scientific article; zbMATH DE number 2079345 (Why is no real title available?)
• Minimum-support solutions of polyhedral concave programs^*
• On the Optimality of the Backward Greedy Algorithm for the Subset Selection Problem
• Restricted strong convexity implies weak submodularity
• Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information
• Sharp Thresholds for High-Dimensional and Noisy Sparsity Recovery Using $\ell _{1}$-Constrained Quadratic Programming (Lasso)
• Stable signal recovery from incomplete and inaccurate measurements
• Subset selection in sparse matrices
• The Dantzig selector: statistical estimation when \(p\) is much larger than \(n\). (With discussions and rejoinder).

Cited in

(2)

• Sparse bounds for the discrete cubic Hilbert transform
• Efficient quantisation and weak covering of high dimensional cubes

This page was built for publication: Sparse approximation over the cube

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6085987)