A Caltech Library Service

Explicit measurements with almost optimal thresholds for compressed sensing

Parvaresh, Farzad and Hassibi, Babak (2008) Explicit measurements with almost optimal thresholds for compressed sensing. In: 2008 IEEE International Conference on Acoustics, Speech and Signal Processing. International Conference on Acoustics Speech and Signal Processing (ICASSP). IEEE , Piscataway, NJ, pp. 3853-3856. ISBN 978-1-4244-1483-3.

PDF - Published Version
See Usage Policy.


Use this Persistent URL to link to this item:


We consider the deterministic construction of a measurement matrix and a recovery method for signals that are block sparse. A signal that has dimension N = nd, which consists of n blocks of size d, is called (s, d)-block sparse if only s blocks out of n are nonzero. We construct an explicit linear mapping Φ that maps the (s, d)-block sparse signal to a measurement vector of dimension M, where s•d <N(1-(1-M/N)^(d/(d+1))-o(1). We show that if the (s, d)- block sparse signal is chosen uniformly at random then the signal can almost surely be reconstructed from the measurement vector in O(N^3) computations.

Item Type:Book Section
Related URLs:
URLURL TypeDescription DOIArticle
Additional Information:© 2008 IEEE. This work was supported in parts by the National Science Foundation under grants no. CCR-0133818 and CCR-0326554, by the David and Lucille Packard Foundation, and by Caltech's Lee Center for Advanced Networking.
Funding AgencyGrant Number
David and Lucille Packard FoundationUNSPECIFIED
Caltech Lee Center for Advanced NetworkingUNSPECIFIED
Series Name:International Conference on Acoustics Speech and Signal Processing (ICASSP)
Record Number:CaltechAUTHORS:20100721-154038572
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:19150
Deposited By: Tony Diaz
Deposited On:30 Jul 2010 21:32
Last Modified:08 Nov 2021 23:50

Repository Staff Only: item control page