Sparse Approximation is Hard

Ali Civril

Given a redundant dictionary $\Phi$, represented by an $M\times N$ matrix ($\Phi \in {\mathbb{R}}^{M\times N}$) and a target signal $y\in {\mathbb{R}}^M$, the \emph{sparse approximation pr…