Introduction
In classical signal processing and compressed sensing, the objective is often to find the sparsest solution to a system of linear equations $Ax = b$. For real-valued vectors $x \in \mathbb{R}^n$, linear algebra provides a straightforward bound: a solution exists with sparsity (the number of non-zero entries, or $\ell_0$-norm) no greater than the rank of the matrix $A$. However, many practical applications—ranging from wireless communication and error-correcting codes to combinatorial optimization—require solutions to be integer-valued. In these discrete domains, such as lattices ($\mathbb{Z}^n$) and semigroups ($\mathbb{Z}_{\ge 0}^n$), the standard notion of rank is insufficient. This paper establishes a theoretical foundation for integer-valued compressed sensing by providing tight upper bounds on sparsity and analyzing the computational complexity of finding these solutions.
Theoretical Framework: Discrete Rank Functions
To characterize sparsity in discrete domains, the authors introduce four "rank-like" functions that generalize the concept of matrix rank:
- Integer Linear Rank (ILR) and Complexity (ILC) for the lattice case ($x \in \mathbb{Z}^n$).
- Integer Carathéodory Rank (ICR) and Complexity (ICC) for the semigroup case ($x \in \mathbb{Z}_{\ge 0}^n$).
These functions account for the "holes" in discrete structures. While rank over $\mathbb{R}$ is a simple integer, these discrete measures act as complexity metrics that reflect the underlying number-theoretic properties of the system.
Methodological Approach
The research employs a multi-disciplinary approach to derive sparsity bounds:
- Finite Abelian Group Theory: The structure of quotient groups, such as $\mathbb{Z}^m / \mathcal{L}(A)$, is used to bound the number of generators required for a specific vector.
- Number Theory: A critical tool is the truncated prime $\Omega$-function, $\Omega_m(z)$, which counts the prime factors of an integer $z$ up to a threshold $m$. This links sparsity directly to the prime factorization of the matrix's minors.
- Geometry of Numbers: Minkowski’s first theorem and Vaaler’s cube-slicing inequality are applied to prove the existence and optimality of sparse solutions.
- Presburger Arithmetic: To analyze computational complexity, the authors utilize the first-order theory of integers with addition, demonstrating that these values are computable in polynomial time when the number of variables is fixed.
Key Results and Insights
The paper provides the first tight upper bounds for integer sparsity:
- Lattice Bound: For a matrix of rank $m$, a solution exists with sparsity $\|x\|_0 \le m + \Omega_m(\frac{|\det(A_\tau)|}{\text{gcd}(A)})$.
- Semigroup Bound: For non-negative integer solutions, the bound is $\|x\|_0 \le 2m + \Omega_m(\frac{|\det(A_\tau)|}{\text{gcd}(A)})$, provided the columns of $A$ positively span $\mathbb{R}^m$.
A significant insight is the Average-Case Sparsity. While worst-case bounds involve logarithms, the number of prime factors $\Omega(z)$ grows very slowly on average (roughly $\log \log z$). This suggests that in practice, integer solutions are often much sparser than theoretical limits might imply.
Computational Complexity
The authors establish that finding the sparsest integer solution is generally NP-hard. Specifically, verifying if the Integer Linear Complexity is less than $k$ is NP-complete even for a single-row matrix ($m=1$). However, the problem becomes tractable in the fixed-variable regime. Using properties of short Presburger formulas, the authors prove that these values can be computed in polynomial time if the dimension $n$ is held constant.
Conclusion and Future Directions
This work bridges the gap between continuous compressed sensing and discrete optimization. While the general problem remains computationally difficult, the tight bounds and fixed-variable tractability offer a path forward for specific applications. A remaining open question is whether these sparsity values can be computed in pseudo-polynomial time for the knapsack case ($m=1$), as standard dynamic programming techniques do not immediately apply to the non-linear $\ell_0$ objective.
Summary updated