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 July 2011 | Submitted
Book Section - Chapter Open

Summary Based Structures with Improved Sublinear Recovery for Compressed Sensing

Abstract

We introduce a new class of measurement matrices for compressed sensing, using low order summaries over binary sequences of a given length. We prove recovery guarantees for three reconstruction algorithms using the proposed measurements, including ℓ_1 minimization and two combinatorial methods. In particular, one of the algorithms recovers k-sparse vectors of length N in sublinear time poly(k log N), and requires at most O(k log N log log N) measurements. The empirical oversampling constant of the algorithm is significantly better than existing sublinear recovery algorithms such as Chaining Pursuit and Sudocodes. In particular, for 10^3 ≤ N ≤ 10^(12) and k = 100, the oversampling factor is between 5 to 25. We provide preliminary insight into how the proposed constructions, and the fast recovery scheme can be used in a number of practical applications such as market basket analysis, and real time compressed sensing implementation.

Additional Information

© 2011 IEEE. Date of Current Version: 03 October 2011.

Attached Files

Submitted - Summary_20Based_20Structures_20with_20Improved_20Sublinear_20Recovery_20for_20Compressed_20Sensing.pdf

Files

Summary_20Based_20Structures_20with_20Improved_20Sublinear_20Recovery_20for_20Compressed_20Sensing.pdf

Additional details

Created:
August 19, 2023
Modified:
March 5, 2024