Performance Bounds on Sparse Representations Using Redundant Frames
<|reference_start|>Performance Bounds on Sparse Representations Using Redundant Frames: 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.<|reference_end|>
@article{akçakaya2007performance,
    title={Performance Bounds on Sparse Representations Using Redundant Frames},
    author={Mehmet Akc{c}akaya and Vahid Tarokh},
    journal={arXiv preprint arXiv:cs/0703045},
    year={2007},
    archivePrefix={arXiv},
    eprint={cs/0703045},
    primaryClass={cs.IT math.IT}
}