Projection onto the Cosparse Set is NP-Hard

Andreas M. Tillmann, Rémi Gribonval, Marc E. Pfetsch

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…