|| Construction of binary matrices for near-optimal compressed sensing
||Ivan Lau, Jonathan Jedwab, Simon Fraser University, Canada|
||D4-S2-T3: Phase Transitions in Sparse Recovery
||Thursday, 15 July, 22:20 - 22:40
||Thursday, 15 July, 22:40 - 23:00
An efficient compressed sensing scheme requires a small number of measurements, a fast recovery algorithm, a small approximation error, and little or no randomness. In 2014, Iwen presented two compressed sensing schemes with near-optimal runtime, based on binary matrices. We combine ideas from these two schemes with a classical construction, used by Porat and Rothschild for near-optimal group testing, to produce a new compressed sensing scheme requiring significantly less randomness without compromising runtime. We give two variants of this compressed sensing scheme: the first is measurement-optimal, and the second is deterministic.