Sparse representation of vectors in lattices and semigroups

Aliev, Iskander ORCID: https://orcid.org/0000-0002-2206-9207, Averkov, Gennadiy, Loera, Jesús A. De and Oertel, Timm ORCID: https://orcid.org/0000-0001-5720-8978 2022. Sparse representation of vectors in lattices and semigroups. Mathematical Programming 192 , pp. 519-546. 10.1007/s10107-021-01657-8

Preview

PDF - Published Version Available under License Creative Commons Attribution. Download (513kB) | Preview

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

Item Type:	Article
Date Type:	Publication
Status:	Published
Schools:	Mathematics
Additional Information:	This article is licensed under a Creative Commons Attribution 4.0 International License
Publisher:	Springer Verlag
ISSN:	0025-5610
Date of First Compliant Deposit:	28 April 2021
Date of Acceptance:	18 April 2021
Last Modified:	02 May 2023 11:49
URI:	https://orca.cardiff.ac.uk/id/eprint/140840

Citation Data

Cited 1 time in Scopus. View in Scopus. Powered By Scopus® Data

Actions (repository staff only)

Edit Item