A Caltech Library Service

Encoding the ℓ_p ball from limited measurements

Candès, Emmanuel and Romberg, Justin (2006) Encoding the ℓ_p ball from limited measurements. In: DCC 2006: Data Compression Conference, Proceedings. IEEE Data Compression Conference. IEEE , Los Alamitos, CA, pp. 33-42. ISBN 0-7695-2545-8.

PDF - Published Version
See Usage Policy.


Use this Persistent URL to link to this item:


We address the problem of encoding signals which are sparse, i.e. signals that are concentrated on a set of small support. Mathematically, such signals are modeled as elements in the ℓ_p ball for some p ≤ 1. We describe a strategy for encoding elements of the ℓ_p ball which is universal in that 1) the encoding procedure is completely generic, and does not depend on p (the sparsity of the signal), and 2) it achieves near-optimal minimax performance simultaneously for all p < 1. What makes our coding procedure unique is that it requires only a limited number of nonadaptive measurements of the underlying sparse signal; we show that near-optimal performance can be obtained with a number of measurements that is roughly proportional to the number of bits used by the encoder. We end by briefly discussing these results in the context of image compression.

Item Type:Book Section
Related URLs:
Candès, Emmanuel0000-0001-9234-924X
Additional Information:© 2006 IEEE. Issue Date: 28-30 March 2006. Date of Current Version: 10 April 2006.
Other Numbering System:
Other Numbering System NameOther Numbering System ID
INSPEC Accession Number: 8946867
Series Name:IEEE Data Compression Conference
Record Number:CaltechAUTHORS:20110225-083247917
Persistent URL:
Official Citation:Candes, E.; Romberg, J.; , "Encoding the ℓp ball from limited measurements," Data Compression Conference, 2006. DCC 2006. Proceedings , vol., no., pp. 33- 42, 28-30 March 2006 doi: 10.1109/DCC.2006.86 URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:22507
Deposited By: Ruth Sustaita
Deposited On:25 Feb 2011 17:12
Last Modified:09 Nov 2021 16:05

Repository Staff Only: item control page