Projection Onto The k-Cosparse Set is NP-Hard

Andreas Tillmann 1, * Rémi Gribonval 2 Marc Pfetsch 1
* Corresponding author
1 Research Group Optimization
Department of Mathematics [Darmstadt]
2 PANAMA - Parcimonie et Nouveaux Algorithmes pour le Signal et la Modélisation Audio
IRISA-D5 - SIGNAUX ET IMAGES NUMÉRIQUES, ROBOTIQUE, Inria Rennes – Bretagne Atlantique
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.
Complete list of metadatas

Cited literature [4 references]  Display  Hide  Download

https://hal.inria.fr/hal-00811671
Contributor : Rémi Gribonval <>
Submitted on : Monday, April 22, 2013 - 5:17:37 PM
Last modification on : Friday, November 16, 2018 - 1:40:26 AM
Long-term archiving on : Monday, April 3, 2017 - 3:52:21 AM

File

OPEA_SPARS13_Complexity_k-CoSP...
Files produced by the author(s)

Identifiers

  • 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. ⟨hal-00811671⟩

Share

Metrics

Record views

1651

Files downloads

383