Projection onto the Cosparse Set is NP-Hard

Abstract

The computational complexity of a problem arising in the context of sparse optimization is considered, namely, the projection onto the set of $k$-cosparse vectors w.r.t. some given matrix $\Omeg$. It is shown that this projection problem is (strongly) \NP-hard, even in the special cases in which the matrix $\Omeg$ contains only ternary or bipolar coefficients. Interestingly, this is in contrast to the projection onto the set of $k$-sparse vectors, which is trivially solved by keeping only the $k$ largest coefficients.

to appear in ICASSP 2014

References in corpus (1)

• Greedy-Like Algorithms for the Cosparse Analysis Model

Cited by in corpus (2)

• ${\ell }^1$-Analysis Minimization and Generalized (Co-)Sparsity: When Does Recovery Succeed?
• Efficient Least Residual Greedy Algorithms for Sparse Recovery