  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.
