This paper deals with the following question: Suppose that there exist an integer or a non-negative integer solution <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$\varvec{x}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="bold-italic">x</mi> </mrow> </math></EquationSource> </InlineEquation> to a system <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$\varvec{A}\varvec{x}= \varvec{b}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mrow> <mi mathvariant="bold-italic">A</mi> </mrow> <mrow> <mi mathvariant="bold-italic">x</mi> </mrow> <mo>=</mo> <mrow> <mi mathvariant="bold-italic">b</mi> </mrow> </mrow> </math></EquationSource> </InlineEquation>, where the number of non-zero components of <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$\varvec{x}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="bold-italic">x</mi> </mrow> </math></EquationSource> </InlineEquation> is n. The target is, for a given natural number <InlineEquation ID="IEq4"> <EquationSource Format="TEX">$k < n$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>k</mi> <mo><</mo> <mi>n</mi> </mrow> </math></EquationSource> </InlineEquation>, to approximate <InlineEquation ID="IEq5"> <EquationSource Format="TEX">$\varvec{b}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="bold-italic">b</mi> </mrow> </math></EquationSource> </InlineEquation> with <InlineEquation ID="IEq6"> <EquationSource Format="TEX">$\varvec{A}\varvec{y}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mrow> <mi mathvariant="bold-italic">A</mi> </mrow> <mrow> <mi mathvariant="bold-italic">y</mi> </mrow> </mrow> </math></EquationSource> </InlineEquation> where <InlineEquation ID="IEq7"> <EquationSource Format="TEX">$\varvec{y}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="bold-italic">y</mi> </mrow> </math></EquationSource> </InlineEquation> is an integer or non-negative integer solution with at most k non-zero components. We establish upper bounds for this question in general. In specific cases, these bounds are tight. If we view the approximation quality as a function of the parameter k, then the paper explains why the quality of the approximation increases exponentially as k goes to n. This paper is a complete version of an extended abstract that appeared at the 26th International Conference on Integer Programming and Combinatorial Optimization (IPCO) [<CitationRef CitationID="CR28">28</CitationRef>].

Sparse approximation in lattices and semigroups

期刊论文
发表日期：

2026年3月9日

查看全文

Stefan Kuhlmann,
Timm Oertel,
Robert Weismantel

摘要

This paper deals with the following question: Suppose that there exist an integer or a non-negative integer solution $\varvec{x}$ $x$ to a system $\varvec{A}\varvec{x}= \varvec{b}$ $A x = b$ , where the number of non-zero components of $\varvec{x}$ $x$ is n. The target is, for a given natural number $k < n$ $k < n$ , to approximate $\varvec{b}$ $b$ with $\varvec{A}\varvec{y}$ $A y$ where $\varvec{y}$ $y$ is an integer or non-negative integer solution with at most k non-zero components. We establish upper bounds for this question in general. In specific cases, these bounds are tight. If we view the approximation quality as a function of the parameter k, then the paper explains why the quality of the approximation increases exponentially as k goes to n. This paper is a complete version of an extended abstract that appeared at the 26th International Conference on Integer Programming and Combinatorial Optimization (IPCO) [28].