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.

@inproceedings{TillmannGribonvalPfetsch2014,

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}

}