Cardiff University | Prifysgol Caerdydd ORCA
Online Research @ Cardiff 
WelshClear Cookie - decide language by browser settings

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

[thumbnail of Aliev2021_Article_SparseRepresentationOfVectorsI.pdf]
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 Edit Item

Downloads

Downloads per month over past year

View more statistics