Testing the nullspace property using semidefinite programming
From MaRDI portal
Abstract: Recent results in compressed sensing show that, under certain conditions, the sparsest solution to an underdetermined set of linear equations can be recovered by solving a linear program. These results either rely on computing sparse eigenvalues of the design matrix or on properties of its nullspace. So far, no tractable algorithm is known to test these conditions and most current results rely on asymptotic properties of random matrices. Given a matrix A, we use semidefinite relaxation techniques to test the nullspace property on A and show on some numerical examples that these relaxation bounds can prove perfect recovery of sparse solutions with relatively high cardinality.
Recommendations
- scientific article; zbMATH DE number 6312913
- scientific article; zbMATH DE number 7678028
- Real versus complex null space properties for sparse vector recovery
- Block-sparse recovery of semidefinite systems and generalized null space conditions
- Linear program relaxation of sparse nonnegative recovery in compressive sensing microarrays
Cites work
- scientific article; zbMATH DE number 516161 (Why is no real title available?)
- A Direct Formulation for Sparse PCA Using Semidefinite Programming
- Compressed sensing and best \(k\)-term approximation
- Concentration inequalities and model selection. Ecole d'Eté de Probabilités de Saint-Flour XXXIII -- 2003.
- Counting the faces of randomly-projected hypercubes and orthants, with applications
- Decoding by Linear Programming
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- Integration and optimization of multivariate polynomials by restriction onto a random subspace
- Introductory lectures on convex optimization. A basic course.
- Linear Matrix Inequalities in System and Control Theory
- Near-Optimal Signal Recovery From Random Projections: Universal Encoding Strategies?
- Nineteen Dubious Ways to Compute the Exponential of a Matrix, Twenty-Five Years Later
- On verifiable sufficient conditions for sparse signal recovery via \(\ell_{1}\) minimization
- Optimal solutions for sparse principal component analysis
- Random projections of regular simplices
- SDPT3 — A Matlab software package for semidefinite programming, Version 1.3
- Smooth minimization of non-smooth functions
- Smoothing technique and its applications in semidefinite optimization
- Sparse nonnegative solution of underdetermined linear equations by linear programming
- Uncertainty principles and ideal atomic decomposition
- Using SeDuMi 1.02, A Matlab toolbox for optimization over symmetric cones
Cited in
(13)- Minimizers of sparsity regularized Huber loss function
- Sparse PCA: convex relaxations, algorithms and applications
- scientific article; zbMATH DE number 7678028 (Why is no real title available?)
- Regularity properties for sparse regression
- Computing the spark: mixed-integer programming for the (vector) matroid girth problem
- On the computation of sparse solutions to the controllability problem for discrete-time linear systems
- Bounds of restricted isometry constants in extreme asymptotics: formulae for Gaussian matrices
- Phase retrieval for sparse signals
- Necessary and Sufficient Conditions for Noiseless Sparse Recovery via Convex Quadratic Splines
- Self-concordant analysis for logistic regression
- A survey on compressive sensing: classical results and recent advancements
- \(s\)-goodness for low-rank matrix recovery
- On the solution uniqueness characterization in the L1 norm and polyhedral gauge recovery
This page was built for publication: Testing the nullspace property using semidefinite programming
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q633104)
