Sparse representation of vectors in lattices and semigroups
Sparse representation of vectors in lattices and semigroups
复制标题
DOI：
10.1007/s10107-021-01657-8
复制
发表时间：
2021-05
影响因子：
2.7
通讯作者：
I. Aliev;G. Averkov;J. D. De Loera;Timm Oertel
中科院分区：
文献类型：
--
作者：
I. Aliev;G. Averkov;J. D. De Loera;Timm Oertel
我们研究有或没有非负约束的线性丢番图方程组解的稀疏性。解向量的稀疏度是其非零条目的数量，称为向量的范数。我们的主要结果是系统解决方案的最小范数的新改进边界 \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{文档}$$A\varvec{x}=\varvec{b}$$\end{文档}，其中，\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\varvec{b}}\in \mathbb {Z}^m$$\end{document} 和 \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\varvec{x}$$\end{document} 是一般整数向量（格子情况）或非负整数向量（半群情况）。在某些情况下，我们给出多项式时间算法来计算范数满足所获得的界限的解。我们表明我们的界限很严格。我们的界限可以看作是自然地将矩阵的秩推广到其他子域的函数，例如。我们证明，这些新的类排序函数一般来说都是 NP 难计算的，但对于固定数量的变量来说，多项式时间是可计算的。
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 \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$A\varvec{x}=\varvec{b}$$\end{document}, where, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\varvec{b}}\in \mathbb {Z}^m$$\end{document} and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\varvec{x}$$\end{document} 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, to other subdomains such as. 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.