Analysis of Basis Pursuit Via Capacity Sets

Joseph Shtok, Michael Elad

Finding the sparsest solution $\alpha$ for an under-determined linear system of equations $D\alpha =s$ is of interest in many applications. This problem is known to be NP-hard. Recent work st…