Sparse representation of vectors in lattices and semigroups
研究线性丢番图方程组解向量的稀疏性，给出非负约束下解的最小非零元个数的新上界，并证明界是紧的，同时提供多项式时间算法。
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 $$\ell _0$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:msub><mml:mi>ℓ</mml:mi><mml:mn>0</mml:mn></mml:msub></mml:math> -norm of the vector. Our main results are new improved bounds on the minimal $$\ell _0$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:msub><mml:mi>ℓ</mml:mi><mml:mn>0</mml:mn></mml:msub></mml:math> -norm of solutions to systems $$A\varvec{x}=\varvec{b}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>A</mml:mi><mml:mrow><mml:mi>x</mml:mi></mml:mrow><mml:mo>=</mml:mo><mml:mrow><mml:mi>b</mml:mi></mml:mrow></mml:mrow></mml:math> , where $$A\in \mathbb {Z}^{m\times n}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>A</mml:mi><mml:mo>∈</mml:mo><mml:msup><mml:mrow><mml:mi>Z</mml:mi></mml:mrow><mml:mrow><mml:mi>m</mml:mi><mml:mo>×</mml:mo><mml:mi>n</mml:mi></mml:mrow></mml:msup></mml:mrow></mml:math> , $${\varvec{b}}\in \mathbb {Z}^m$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mrow><mml:mi>b</mml:mi></mml:mrow><mml:mo>∈</mml:mo><mml:msup><mml:mrow><mml:mi>Z</mml:mi></mml:mrow><mml:mi>m</mml:mi></mml:msup></mml:mrow></mml:math> and $$\varvec{x}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>x</mml:mi></mml:mrow></mml:math> 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 $$\ell _0$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:msub><mml:mi>ℓ</mml:mi><mml:mn>0</mml:mn></mml:msub></mml:math> -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 $$\mathbb {R}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>R</mml:mi></mml:math> , to other subdomains such as $$\mathbb {Z}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>Z</mml:mi></mml:math> . 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.