Pith. sign in

REVIEW

Projection onto the Cosparse Set is NP-Hard

Not yet reviewed by Pith; the record is open.

Re-run · record.json Download PDF Read on arXiv ↗

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 1303.5305 v2 pith:6HBRZ2KS submitted 2013-03-21 cs.CC

Andreas M. Tillmann , Rémi Gribonval (INRIA - IRISA) , Marc E. Pfetsch This is my paper · ORCID
classification cs.CC
keywords projectionontocoefficientscosparsematrixnp-hardomegonly
verification ladder T0 review T1 audit T2 compute T3 formal
0 comments
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.

Discussion (0). Continue with ORCID to comment.

Pith tools