Projection Onto The k-Cosparse Set is NP-Hard - Inria - Institut national de recherche en sciences et technologies du numérique Access content directly
Conference Papers Year : 2013

Projection Onto The k-Cosparse Set is NP-Hard

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.
Fichier principal
Vignette du fichier
OPEA_SPARS13_Complexity_k-CoSP.pdf (176.41 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

hal-00811671 , version 1 (22-04-2013)

Identifiers

  • HAL Id : hal-00811671 , version 1

Cite

Andreas M. Tillmann, Rémi Gribonval, Marc E. 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⟩
664 View
180 Download

Share

Gmail Facebook X LinkedIn More