Sparse representation of vectors in lattices and semigroups

• 成果类型: Article
• 署名作者: Aliev, Iskander; Averkov, Gennadiy; De Loera, Jesus A.; Oertel, Timm
• 署名单位: Cardiff University; Brandenburg University of Technology Cottbus; University of California System; University of California Davis
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-021-01657-8
• 发表日期: 2022
• 页码: 519-546
• 关键词: rational generating-functions; RECOVERY

摘要

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 l(0)-norm of the vector. Our main results are new improved bounds on the minimal l(0)-norm of solutions to systems Ax = b, where A is an element of Z(mxn), b is an element of Z(m) 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 l(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.