Sparse representation of vectors in lattices and semigroups

Aliev I, Averkov G, De Loera JA, Oertel T (2021)

Publication Type: Journal article

Publication year: 2021

Journal

Mathematical Programming Springer Verlag (Germany)

DOI: 10.1007/s10107-021-01657-8

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 ℓ-norm of the vector. Our main results are new improved bounds on the minimal ℓ-norm of solutions to systems Ax= b, where A∈ Zm×n, b∈ Zm and 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 ℓ-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 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.

Authors with CRIS profile

Timm Oertel

Additional Organisation(s)

Professur für Mathematische Analyse von Daten (Data Analytics)

Involved external institutions

Brandenburgische Technische Universität Cottbus-Senftenberg (BTU) DE Germany (DE) University of California Davis (UCDAVIS) US United States (USA) (US) Cardiff University GB United Kingdom (GB)

How to cite

APA:

Aliev, I., Averkov, G., De Loera, J.A., & Oertel, T. (2021). Sparse representation of vectors in lattices and semigroups. Mathematical Programming. https://dx.doi.org/10.1007/s10107-021-01657-8

MLA:

Aliev, Iskander, et al. "Sparse representation of vectors in lattices and semigroups." Mathematical Programming (2021).

BibTeX: Download