Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published March 2012 | public
Journal Article Open

Restricted isometries for partial random circulant matrices


In the theory of compressed sensing, restricted isometry analysis has become a standard tool for studying how efficiently a measurement matrix acquires information about sparse and compressible signals. Many recovery algorithms are known to succeed when the restricted isometry constants of the sampling matrix are small. Many potential applications of compressed sensing involve a data-acquisition process that proceeds by convolution with a random pulse followed by (nonrandom) subsampling. At present, the theoretical analysis of this measurement technique is lacking. This paper demonstrates that the sth-order restricted isometry constant is small when the number m of samples satisfies m ≳ (s logn)^(3/2), where n is the length of the pulse. This bound improves on previous estimates, which exhibit quadratic scaling.

Additional Information

© 2011 Elsevier Inc. Received 9 October 2010; Revised 4 May 2011; Accepted 6 May 2011; Available online 11 May 2011; Communicated by Charles K. Chui. The author acknowledges generous support by the Hausdorff Center for Mathematics, and through the WWTF project SPORTS (MA07-004). The author was supported by ONR Young Investigator Award N00014-08-1-0884 and a Packard Fellowship. The author has been supported by ONR award N00014-08-1-0883, DARPA award N66001-08-1-2065, and AFOSR award FA9550-09-1-0643.

Attached Files

Submitted - 1010.1847.pdf


Files (248.8 kB)
Name Size Download all
248.8 kB Preview Download

Additional details

August 22, 2023
August 22, 2023