Projection Onto The Cosparse Set is NP-Hard

Andreas Tillmann, RĂ©mi Gribonval, Marc Pfetsch
International Conference on Acoustics, Speech and Signal Processing (ICASSP)

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 M. It is shown that this projection problem is (strongly) NP-hard, even in the special cases in which the matrix M 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.

» Show BibTeX

author = {A. M. Tillmann and R. Gribonval and M. E. Pfetsch},
title = {{Projection Onto The Cosparse Set is NP-Hard}},
booktitle = {{Proc. ICASSP 2014}},
pages = {7148--7152},
year = {2014},
note = {DOI: 10.1109/ICASSP.2014.6854987}

Disclaimer Home Visual Computing institute RWTH Aachen University