Projection onto the Cosparse Set is NP-Hard
classification
💻 cs.CC
keywords
projectionontocoefficientscosparsematrixnp-hardomegonly
pith:6HBRZ2KS Add to your LaTeX paper
What is a Pith Number?\usepackage{pith}
\pithnumber{6HBRZ2KS}
Prints a linked pith:6HBRZ2KS badge after your title and writes the identifier into PDF metadata. Compiles on arXiv with no extra files. Learn more
read the original 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.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.