# Projection onto the Cosparse Set is NP-Hard

2 PANAMA - Parcimonie et Nouveaux Algorithmes pour le Signal et la Modélisation Audio
Inria Rennes – Bretagne Atlantique , IRISA-D5 - SIGNAUX ET IMAGES NUMÉRIQUES, ROBOTIQUE
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.
Keywords :
Document type :
Conference papers
Domain :

Cited literature [18 references]

https://hal.inria.fr/hal-00802359
Contributor : Rémi Gribonval <>
Submitted on : Tuesday, March 11, 2014 - 8:50:04 AM
Last modification on : Thursday, November 15, 2018 - 11:58:45 AM
Document(s) archivé(s) le : Wednesday, June 11, 2014 - 10:45:45 AM

### Files

kCSP_preprint_semifinal.pdf
Files produced by the author(s)

### Citation

Andreas M. Tillmann, Rémi Gribonval, Marc E. Pfetsch. Projection onto the Cosparse Set is NP-Hard. ICASSP14 - International Conference on Acoustics, Speech, and Signal Processing, May 2014, Florence, Italy. ⟨10.1109/ICASSP.2014.6854987⟩. ⟨hal-00802359v2⟩

Record views