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.
Type de document :
Communication dans un congrès
ICASSP14 - International Conference on Acoustics, Speech, and Signal Processing, May 2014, Florence, Italy. IEEE, 2014, 〈10.1109/ICASSP.2014.6854987〉
Liste complète des métadonnées

Littérature citée [18 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00802359
Contributeur : Rémi Gribonval <>
Soumis le : mardi 11 mars 2014 - 08:50:04
Dernière modification le : jeudi 15 novembre 2018 - 11:58:45
Document(s) archivé(s) le : mercredi 11 juin 2014 - 10:45:45

Fichiers

kCSP_preprint_semifinal.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

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. IEEE, 2014, 〈10.1109/ICASSP.2014.6854987〉. 〈hal-00802359v2〉

Partager

Métriques

Consultations de la notice

1100

Téléchargements de fichiers

295