Nonuniform compressed sensing schemes with sublinear measurements, sublinear time, and low entropy

Let x be an unknown vector of length N which has at most k relatively large entries, so that x is well-approximated by its best k-term approximation xk. A compressed sensing scheme consists of a measurement matrix M ∈ C m×N and a recovery algorithm ∆ that approximates xk as xb = ∆ (M,Mx). The scheme is considered accurate if, regardless of the unknown vector x, the approximation xb satisfies kx − xbkp ≤ Ck1/p−1/qkx − xkkq with high probability for some absolute constants C and p ≥ q ≥ 1. Other desirable properties are few measurements (m = O(k polylog N)), fast recovery algorithm (O(k polylog N) runtime), and low entropy. In 2014, Iwen presented two compressed sensing schemes: the fastest known accurate scheme, and the only known fast accurate scheme requiring sublinear entropy. We present a compressed sensing scheme that combines the speed of Iwen's first scheme with the low entropy of Iwen's second scheme, drawing on ideas from disjunct matrix construction due to Porat-Rothschild and Kautz-Singleton. We also give two variants of our scheme. The first variant is deterministic, and has a faster recovery algorithm than all other deterministic accurate schemes. The second variant is measurement-optimal, and requires lower entropy than all other measurement-optimal accurate schemes