An algebraic perspective on integer sparse recovery
From MaRDI portal
Abstract: Compressed sensing is a relatively new mathematical paradigm that shows a small number of linear measurements are enough to efficiently reconstruct a large dimensional signal under the assumption the signal is sparse. Applications for this technology are ubiquitous, ranging from wireless communications to medical imaging, and there is now a solid foundation of mathematical theory and algorithms to robustly and efficiently reconstruct such signals. However, in many of these applications, the signals of interest do not only have a sparse representation, but have other structure such as lattice-valued coefficients. While there has been a small amount of work in this setting, it is still not very well understood how such extra information can be utilized during sampling and reconstruction. Here, we explore the problem of integer sparse reconstruction, lending insight into when this knowledge can be useful, and what types of sampling designs lead to robust reconstruction guarantees. We use a combination of combinatorial, probabilistic and number-theoretic methods to discuss existence and some constructions of such sensing matrices with concrete examples. We also prove sparse versions of Minkowski's Convex Body and Linear Forms theorems that exhibit some limitations of this framework.
Recommendations
Cites work
- A deterministic single exponential time algorithm for most lattice problems based on Voronoi cell computations
- A geometric inequality with applications to linear forms
- A mathematical introduction to compressive sensing
- Combinatorial Nullstellensatz
- CoSaMP: Iterative signal recovery from incomplete and inaccurate samples
- Counting faces of randomly projected polytopes when the projection radically lowers dimension
- Covering lattice points by subspaces and counting point-hyperplane incidences
- Decoding by Linear Programming
- Diophantine approximation
- Iterative hard thresholding for compressed sensing
- On an effective variation of Kronecker's approximation theorem avoiding algebraic sets
- On the singularity probability of discrete random matrices
- Probability of unique integer solution to a system of linear equations
- PROMP: a sparse recovery approach to lattice-valued signals
- Signal Recovery From Random Measurements Via Orthogonal Matching Pursuit
- Simultaneous rational approximation to binomial functions
- Sparse Recovery With Orthogonal Matching Pursuit Under RIP
- Spatial Compressive Sensing for MIMO Radar
- Stable signal recovery from incomplete and inaccurate measurements
- The probabilistic method. With an appendix on the life and work of Paul Erdős.
Cited in
(17)- Sparse representation of vectors in lattices and semigroups
- Integer sampling matrices with small entries ensuring vector recovery
- Sparse recovery with integrality constraints
- On sparse geometry of numbers
- An extremal problem for integer sparse recovery
- Lattices from tight frames and vertex transitive graphs
- Compressed sensing for finite-valued signals
- Covering point-sets with parallel hyperplanes and sparse signal recovery
- On unique recovery of finite-valued integer signals and admissible lattices of sparse hypercubes
- Optimizing sparsity over lattices and semigroups
- Recovery of sparse integer vectors from linear measurements
- On Theorem 10 in “On Polar Polytopes and the Recovery of Sparse Representations” [Sep 07 3188-3195]
- Sparse recovery properties of discrete random matrices
- On a new absolute version of Siegel's lemma
- Robust sparse recovery with sparse Bernoulli matrices via expanders
- Sparse approximation in lattices and semigroups
- Algebraic-exponential data recovery from moments
This page was built for publication: An algebraic perspective on integer sparse recovery
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2007643)
