H.B. Keller Colloquium

A solution of a system is sparse if the number of non-zero entries is small. 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. It is well-known that  sparse real solutions of linear systems are relevant for signal processing and they have remarkable applications in inverse problems and compression in image processing. For instance, work by Candes and Tao shows that sparse solutions over the reals using structured matrices $A$ is central  in the theory of the classical compressed sensing, where a linear programming relaxation provides a guaranteed approximation to the sparsest solution. In this lecture I will discuss the closely related problem of finding sparse integer  solutions of linear systems.

Sparsity of solutions to linear Diophantine equations certainly remains interesting and relevant for the theory of compressed sensing for integer-valued signals motivated by applications in which the signal is known to have integer entries. My own motivation (which I will briefly use to introduce the mathematical problem) came from integer and combinatorial optimization where integer support minimization was also investigated because several combinatorial optimization problems have useful interpretations based on sparse representations of elements in a lattice or a semigroup. For example, the minimum edge-coloring problem of graphs can be seen as a problem in the semigroup generated by the matchings of the input graph. 

I discuss several new and old results about the sparsity of  the solutions to systems of linear Diophantine equations with and without non-negativity of variables. Our main new results are new improved bounds on the minimal $\ell_0$-norm of solutions to systems $A\ve x=\ve b$, where $A\in \Z^{m\times n}$, ${\ve b}\in \Z^m$ and $\ve 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 our bounds are tight. Of independent interest, our bounds can be seen as functions naturally generalizing the rank of a matrix over $\R$, to other subdomains such as $\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 $n$.

This is all joint work with Iskander Aliev (Cardiff Univ), Gennadiy Averkov (BTU Cottbus - Senftenberg) and Timm Oertel (Cardiff Univ).