Computer Science – Computational Complexity
Scientific paper
2011-08-23
Computer Science
Computational Complexity
This paper has been withdrawn by the author as the results are subsumed by another straightforward reduction
Scientific paper
Given a redundant dictionary $\Phi$, represented by an $M \times N$ matrix ($\Phi \in \mathbb{R}^{M \times N}$) and a target signal $y \in \mathbb{R}^M$, the \emph{sparse approximation problem} asks to find an approximate representation of $y$ using a linear combination of at most $k$ atoms. In this paper, a new complexity theoretic hardness result for sparse approximation problem is presented via considering a different measure of quality for the solution. It is argued that, from an algorithmic standpoint, the problem is more meaningful if it asks to maximize the norm of the target signal's projection onto the selected atoms which are represented by column vectors. Then, a multiplicative inapproximability result is established with this new measure, under a reasonable complexity theoretic assumption. This result in turn implies additive inapproximability for the problem with the standard measure. Specifically, if $ZPP \neq NP$, all polynomial time algorithms which provide a $k$-sparse vector $x$ should satisfy $$ {\|y-\Phi x\|}_2^2 \geq (1-c){\|y-\Phi x^*\|}_2^2 + c {\|y\|}_2^2, $$ \noindent for $1/4(1-1/e) > c \geq 0$ where $x^*$ is the optimal $k$-sparse solution. This result provides a quantification of the hardness for the case $y-\Phi x^* = 0$, revealing more details about the inherent structure of the problem.
No associations
LandOfFree
Sparse Approximation is Hard does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Sparse Approximation is Hard, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Sparse Approximation is Hard will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-67698