Sparse representation of vectors in lattices and semigroups
Open Access
- 4 May 2021
- journal article
- research article
- Published by Springer Nature in Mathematical Programming
- Vol. 192 (1-2) , 519-546
Abstract
We study the sparsity of the solutions to systems of linear Diophantine equations with and without non-negativity constraints. The sparsity of a solution vector is the number of its nonzero entries, which is referred to as the $$\ell _0$$ -norm of the vector. Our main results are new improved bounds on the minimal $$\ell _0$$ -norm of solutions to systems $$A\varvec{x}=\varvec{b}$$ , where $$A\in \mathbb {Z}^{m\times n}$$ , $${\varvec{b}}\in \mathbb {Z}^m$$ and $$\varvec{x}$$ is either a general integer vector (lattice case) or a non-negative integer vector (semigroup case). In certain cases, we give polynomial time algorithms for computing solutions with $$\ell _0$$ -norm satisfying the obtained bounds. We show that our bounds are tight. Our bounds can be seen as functions naturally generalizing the rank of a matrix over $$\mathbb {R}$$ , to other subdomains such as $$\mathbb {Z}$$ . We show that these new rank-like functions are all NP-hard to compute in general, but polynomial-time computable for fixed number of variables.
Keywords
Funding Information
- National Science Foundation (1818969)
- Deutsche Forschungsgemeinschaft (413995221)
This publication has 26 references indexed in Scilit:
- PROMP: A sparse recovery approach to lattice-valued signalsApplied and Computational Harmonic Analysis, 2018
- A Graph Partition ProblemThe American Mathematical Monthly, 2015
- A Survey of Compressed Sensing2015
- Carathéodory bounds for integer conesOperations Research Letters, 2006
- Stable signal recovery from incomplete and inaccurate measurementsCommunications on Pure and Applied Mathematics, 2006
- Decoding by Linear ProgrammingIEEE Transactions on Information Theory, 2005
- Effective lattice point counting in rational convex polytopesJournal of Symbolic Computation, 2004
- Sparse Approximate Solutions to Linear SystemsSIAM Journal on Computing, 1995
- Matching structure and the matching latticeJournal of Combinatorial Theory, Series B, 1987
- A geometric inequality with applications to linear formsPacific Journal of Mathematics, 1979