Sparse Approximation Over the Cube

Sabrina Bruckmeier, Christoph Hunkenschröder, Robert Weismantel

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…