  We consider approximations of signals by the elements of a frame in a complex
vector space of dimension $N$ and formulate both the noiseless and the noisy
sparse representation problems. The noiseless representation problem is to find
sparse representations of a signal $\mathbf{r}$ given that such representations
exist. In this case, we explicitly construct a frame, referred to as the
Vandermonde frame, for which the noiseless sparse representation problem can be
solved uniquely using $O(N^2)$ operations, as long as the number of non-zero
coefficients in the sparse representation of $\mathbf{r}$ is $\epsilon N$ for
some $0 \le \epsilon \le 0.5$, thus improving on a result of Candes and Tao
\cite{Candes-Tao}. We also show that $\epsilon \le 0.5$ cannot be relaxed
without violating uniqueness.
  The noisy sparse representation problem is to find sparse representations of
a signal $\mathbf{r}$ satisfying a distortion criterion. In this case, we
establish a lower bound on the trade-off between the sparsity of the
representation, the underlying distortion and the redundancy of any given
frame.
