Sparse representation of vectors in lattices and semigroups

Iskander Aliev, Gennadiy Averkov, Jesús A. De Loera, Timm OertelMath. Program 2022 · OpenReview

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:

  1. 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.
  2. 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.
  3. Geometry of Numbers: Minkowski’s first theorem and Vaaler’s cube-slicing inequality are applied to prove the existence and optimality of sparse solutions.
  4. 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

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.
BibTeX
@inproceedings{aliev2022sparse,
  author = {Iskander Aliev and Gennadiy Averkov and Jesús A. De Loera and Timm Oertel},
  title = {{Sparse representation of vectors in lattices and semigroups}},
  booktitle = {Math. Program},
  year = {2022},
  url = {https://openreview.net/forum?id=bLezBQ5Bog},
}
Figure