Published in

2014 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)

DOI: 10.1109/icassp.2014.6854987

Links

Tools

Export citation

Search in Google Scholar

Projection onto the cosparse set is NP-hard

Journal article published in 2014 by Andreas M. Tillmann, Remi Gribonval, Marc E. Pfetsch
This paper is available in a repository.
This paper is available in a repository.

Full text: Download

Green circle
Preprint: archiving allowed
Upload
Green circle
Postprint: archiving allowed
Upload
Red circle
Published version: archiving forbidden
Policy details
Data provided by SHERPA/RoMEO

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. ; Comment: to appear in ICASSP 2014