An algebraic perspective on integer sparse recovery
From MaRDI portal
Publication:2007643
DOI10.1016/J.AMC.2018.08.007zbMATH Open1428.94036arXiv1801.01526OpenAlexW2963078993WikidataQ129277739 ScholiaQ129277739MaRDI QIDQ2007643FDOQ2007643
D. Needell, Benny Sudakov, Lenny Fukshansky
Publication date: 22 November 2019
Published in: Applied Mathematics and Computation (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1801.01526
Signal theory (characterization, reconstruction, filtering, etc.) (94A12) Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20) Approximation by arbitrary nonlinear expressions; widths and entropy (41A46)
Cites Work
- Title not available (Why is that?)
- Decoding by Linear Programming
- Stable signal recovery from incomplete and inaccurate measurements
- Signal Recovery From Random Measurements Via Orthogonal Matching Pursuit
- Iterative hard thresholding for compressed sensing
- CoSaMP: Iterative signal recovery from incomplete and inaccurate samples
- Diophantine approximation
- A geometric inequality with applications to linear forms
- A mathematical introduction to compressive sensing
- Sparse Recovery With Orthogonal Matching Pursuit Under RIP
- Combinatorial Nullstellensatz
- Counting faces of randomly projected polytopes when the projection radically lowers dimension
- Probability of unique integer solution to a system of linear equations
- A deterministic single exponential time algorithm for most lattice problems based on Voronoi cell computations
- On the singularity probability of discrete random matrices
- Spatial Compressive Sensing for MIMO Radar
- Simultaneous rational approximation to binomial functions
- PROMP: a sparse recovery approach to lattice-valued signals
- On an effective variation of Kronecker’s approximation theorem avoiding algebraic sets
- Covering lattice points by subspaces and counting point-hyperplane incidences
Cited In (14)
- Sparse recovery properties of discrete random matrices
- Sparse representation of vectors in lattices and semigroups
- Lattices from tight frames and vertex transitive graphs
- On sparse geometry of numbers
- On a new absolute version of Siegel's lemma
- Optimizing Sparsity over Lattices and Semigroups
- Robust sparse recovery with sparse Bernoulli matrices via expanders
- On Theorem 10 in “On Polar Polytopes and the Recovery of Sparse Representations” [Sep 07 3188-3195]
- Covering point-sets with parallel hyperplanes and sparse signal recovery
- Integer sampling matrices with small entries ensuring vector recovery
- Recovery of sparse integer vectors from linear measurements
- On unique recovery of finite-valued integer signals and admissible lattices of sparse hypercubes
- An extremal problem for integer sparse recovery
- Algebraic-exponential data recovery from moments
Uses Software
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)
