Algebraic compressed sensing
arXiv:2108.13208 · doi:10.1016/j.acha.2023.03.006
Abstract
We introduce the broad subclass of algebraic compressed sensing problems, where structured signals are modeled either explicitly or implicitly via polynomials. This includes, for instance, low-rank matrix and tensor recovery. We employ powerful techniques from algebraic geometry to study well-posedness of sufficiently general compressed sensing problems, including existence, local recoverability, global uniqueness, and local smoothness. Our main results are summarized in thirteen questions and answers in algebraic compressed sensing. Most of our answers concerning the minimum number of required measurements for existence, recoverability, and uniqueness of algebraic compressed sensing problems are optimal and depend only on the dimension of the model.
30 pages, 1 figure
References in corpus (14)
- Efficient classical simulation of slightly entangled quantum computations
- Structured Compressed Sensing: From Theory to Applications
- Moment Varieties of Gaussian Mixtures
- A deterministic algorithm to compute approximate roots of polynomial systems in polynomial average time
- Tensor network ranks
- Numerical Algebraic Geometry for Macaulay2
- The condition number of Riemannian approximation problems
- Computing images of polynomial maps
- Sensitivity of low-rank matrix recovery
- An algorithmic approach to Chevalley's Theorem on images of rational morphisms between affine varieties
- Moment Identifiability of Homoscedastic Gaussian Mixtures
- Injection dimensions of projective varieties
- Nonlinear Algebra and Applications
- Asymptotic Log-Det Sum-of-Ranks Minimization via Tensor (Alternating) Iteratively Reweighted Least Squares