Sparse Approximation Over the Cube

Abstract

This paper presents an anlysis of the NP-hard minimization problem $\min \{\Vert b-Ax{\Vert }_2:x\in [0,1{]}^n,|\text{supp}(x)|\le \sigma \}$, where $\text{supp}(x)=\{i\in [n]:x_i\ne 0\}$ and $\sigma$ is a positive integer. The object of investigation is a natural relaxation where we replace $|\text{supp}(x)|\le \sigma$ by ${\sum }_i{x}_i\le \sigma$. Our analysis includes a probabilistic view on when the relaxation is exact. We also consider the problem from a deterministic point of view and provide a bound on the distance between the images of optimal solutions of the original problem and its relaxation under $A$. This leads to an algorithm for generic matrices $A\in {\mathbb{Z}}^{m\times n}$ and achieves a polynomial running time provided that $m$ and $\Vert A{\Vert }_{\infty }$ are fixed.