Sparse Approximation in Lattices and Semigroups - Kuhlmann, Stefan; Oertel, Timm; Weismantel, Robert (Lecture Notes in Computer Science, 2025)
Given an integer or a non-negative integer solution x to a system Ax=b, where the number of non-zero components of x is at most n. This paper addresses the following question: How closely can we approximate b with Ay, where y is an integer or non-negative integer solution constrained to have at most k non-zero components with k<n? We establish upper bounds for this question in general. In specific cases, these bounds are tight. The key finding is that the quality of the approximation increases exponentially as k goes to n.
CRIS-Team Scopus Importer:2025-07-04