On unique recovery of finite-valued integer signals and admissible lattices of sparse hypercubes

Abstract

The paper considers the problem of unique recovery of sparse finite-valued integer signals using a single linear integer measurement. For l-sparse signals in Zn, 2l<n, with absolute entries bounded by r, we construct an 1×n measurement matrix with maximum absolute entry Δ=O(r2l−1). Here the implicit constant depends on l and n and the exponent 2l−1 is optimal. Additionally, we show that, in the above setting, a single measurement can be replaced by several measurements with absolute entries sub-linear in Δ. The proofs make use of results on admissible (n−1)-dimensional integer lattices for m-sparse n-cubes that are of independent interest.