Performance Bounds on Sparse Representations Using Redundant Frames
| dc.creator | Akçakaya, Mehmet | |
| dc.creator | Tarokh, Vahid | |
| dc.date | 2007-03-09 | |
| dc.date.accessioned | 2026-07-07T08:17:07Z | |
| dc.date.available | 2026-07-07T08:17:07Z | |
| dc.description | 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 $εN$ for some $0 \le ε\le 0.5$, thus improving on a result of Candes and Tao \cite{Candes-Tao}. We also show that $ε\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. | |
| dc.description | 8 pages, 1 figure, Submitted to IEEE Transactions on Signal Processing | |
| dc.identifier | https://arxiv.org/abs/cs/0703045 | |
| dc.identifier | http://arxiv.org/abs/cs/0703045 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/134014 | |
| dc.subject | Information Theory | |
| dc.title | Performance Bounds on Sparse Representations Using Redundant Frames | |
| dc.type | text |