TY - GEN

T1 - On sparsity, redundancy and quality of frame representations

AU - Akçakaya, Mehmet

AU - Tarokh, Vahid

PY - 2007/12/1

Y1 - 2007/12/1

N2 - 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(N2) operations, as long as the number of non-zero coefficients in the sparse representation of r is ∈N for some 0 ≤ ∈ ≤ 0.5, thus improving on a result of Candès and Tao [3]. We also show 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 trade-off between the sparsity of the representation, the underlying distortion and the redundancy of any given frame.

AB - 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(N2) operations, as long as the number of non-zero coefficients in the sparse representation of r is ∈N for some 0 ≤ ∈ ≤ 0.5, thus improving on a result of Candès and Tao [3]. We also show 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 trade-off between the sparsity of the representation, the underlying distortion and the redundancy of any given frame.

UR - http://www.scopus.com/inward/record.url?scp=51649094858&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=51649094858&partnerID=8YFLogxK

U2 - 10.1109/ISIT.2007.4557114

DO - 10.1109/ISIT.2007.4557114

M3 - Conference contribution

AN - SCOPUS:51649094858

SN - 1424414296

SN - 9781424414291

T3 - IEEE International Symposium on Information Theory - Proceedings

SP - 951

EP - 955

BT - Proceedings - 2007 IEEE International Symposium on Information Theory, ISIT 2007

T2 - 2007 IEEE International Symposium on Information Theory, ISIT 2007

Y2 - 24 June 2007 through 29 June 2007

ER -