Derandomizing Compressed Sensing With Combinatorial Design

Abstract

Read online

Compressed sensing is the art of effectively reconstructing structured n-dimensional vectors from substantially fewer measurements than naively anticipated. A plethora of analytical reconstruction guarantees support this credo. The strongest among them are based on deep results from large-dimensional probability theory and require a considerable amount of randomness in the measurement design. Here, we demonstrate that derandomization techniques allow for a considerable reduction in the randomness required for such proof strategies. More precisely, we establish uniform s-sparse reconstruction guarantees for Cs log(n) measurements that are chosen independently from strength-4 orthogonal arrays and maximal sets of mutually unbiased bases, respectively. These are highly structured families of C~n2 vectors that imitate signed Bernoulli and standard Gaussian vectors in a (partially) derandomized fashion.

Keywords

• compressed sensing
• k-wise independence
• orthogonal arrays
• spherical design
• derandomization