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 |