# A frame construction and a universal distortion bound for sparse representations

Published

Journal Article

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 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(N2operations, as long as the number of non-zero coefficients in the sparse representation of r is ∈N for some 0 ≤ ∈ 0.5. It is known that ∈ ≤ 0.5 cannot be relaxed without violating uniqueness. The noisy sparse representation problem is to find sparse representations of a signal r satisfying a distortion criterion. In this case, we establish a lower bound on the tradeoff between the sparsity of the representation, the underlying distortion and the redundancy of any given frame. © 2008 IEEE.

### Full Text

### Duke Authors

### Cited Authors

- Akçakaya, M; Tarokh, V

### Published Date

- June 1, 2008

### Published In

### Volume / Issue

- 56 / 6

### Start / End Page

- 2443 - 2450

### International Standard Serial Number (ISSN)

- 1053-587X

### Digital Object Identifier (DOI)

- 10.1109/TSP.2007.914344

### Citation Source

- Scopus