Projection onto the cosparse set is NP-hard

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