| Paper ID | D4-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.
|
