Computer Science – Information Theory
Scientific paper
2011-02-27
Computer Science
Information Theory
Scientific paper
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 $\ell_1$ minimization and two combinatorial methods. In particular, one of the algorithms recovers $k$-sparse vectors of length $N$ in sublinear time $\text{poly}(k\log{N})$, and requires at most $\Omega(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\leq N\leq 10^8$ and $k=100$, the oversampling factor is between 3 to 8. 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.
Anandkumar Animashree
Hassibi Babak
Khajehnejad Amin M.
Yoo Juhwan
No associations
LandOfFree
Summary Based Structures with Improved Sublinear Recovery for Compressed Sensing does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Summary Based Structures with Improved Sublinear Recovery for Compressed Sensing, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Summary Based Structures with Improved Sublinear Recovery for Compressed Sensing will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-53777