Linear Inverse Problems with Norm and Sparsity Constraints
This work addresses sparse recovery for applications like signal processing, but it appears incremental as it builds on known constraints without a major paradigm shift.
The authors tackled the problem of sparse recovery in linear inverse problems by proposing two algorithms, GAME and CLASH, that jointly use convex and non-convex constraints, resulting in improved theoretical guarantees and empirical performance beyond existing solvers.
We describe two nonconventional algorithms for linear regression, called GAME and CLASH. The salient characteristics of these approaches is that they exploit the convex $\ell_1$-ball and non-convex $\ell_0$-sparsity constraints jointly in sparse recovery. To establish the theoretical approximation guarantees of GAME and CLASH, we cover an interesting range of topics from game theory, convex and combinatorial optimization. We illustrate that these approaches lead to improved theoretical guarantees and empirical performance beyond convex and non-convex solvers alone.