Computer Science – Information Theory
Scientific paper
2007-03-09
Computer Science
Information Theory
8 pages, 1 figure, Submitted to IEEE Transactions on Signal Processing
Scientific paper
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.
Akçakaya Mehmet
Tarokh Vahid
No associations
LandOfFree
Performance Bounds on Sparse Representations Using Redundant Frames 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 Performance Bounds on Sparse Representations Using Redundant Frames, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Performance Bounds on Sparse Representations Using Redundant Frames will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-692994