All Dates/Times are Australian Eastern Standard Time (AEST)

Technical Program

Paper Detail

Paper IDD4-S2-T3.2
Paper Title Construction of binary matrices for near-optimal compressed sensing
Authors Ivan Lau, Jonathan Jedwab, Simon Fraser University, Canada
Session D4-S2-T3: Phase Transitions in Sparse Recovery
Chaired Session: Thursday, 15 July, 22:20 - 22:40
Engagement Session: Thursday, 15 July, 22:40 - 23:00
Abstract 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.