Projection Onto The k-Cosparse Set is NP-Hard

Andreas Tillmann 1, * Rémi Gribonval 2 Marc Pfetsch 1
* Auteur correspondant
1 Research Group Optimization
Department of Mathematics [Darmstadt]
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 : We investigate the computational complexity of a problem arising in the context of sparse optimization, namely, the projection onto the set of k-cosparse vectors w.r.t. some given matrix Ω. We show that this projection problem is (strongly) NP-hard, even in the special cases where the matrix Ω contains only ternary or bipolar coefficients. Interestingly, this is in stark 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
Signal Processing with Adaptive Sparse Structured Representations 2013 (2013), Jul 2013, Lausanne, Switzerland. 2013
Liste complète des métadonnées

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

https://hal.inria.fr/hal-00811671
Contributeur : Rémi Gribonval <>
Soumis le : lundi 22 avril 2013 - 17:17:37
Dernière modification le : mercredi 11 avril 2018 - 01:51:21
Document(s) archivé(s) le : lundi 3 avril 2017 - 03:52:21

Fichier

OPEA_SPARS13_Complexity_k-CoSP...
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00811671, version 1

Citation

Andreas Tillmann, Rémi Gribonval, Marc Pfetsch. Projection Onto The k-Cosparse Set is NP-Hard. Signal Processing with Adaptive Sparse Structured Representations 2013 (2013), Jul 2013, Lausanne, Switzerland. 2013. 〈hal-00811671〉

Partager

Métriques

Consultations de la notice

1264

Téléchargements de fichiers

294