Compressed sensing with sparse binary matrices: Instance optimal error guarantees in near-optimal time

A compressed sensing method consists of a rectangular measurement matrix, M∈Rm×NM∈Rm×N with m≪Nm≪N, together with an associated recovery algorithm, A:Rm→RNA:Rm→RN. Compressed sensing methods aim to construct a high quality approximation to any given input vector x∈RN using only Mx∈Rm as input. In particular, we focus herein on instance optimal nonlinear approximation error bounds for MM and AA of the form ‖x−A(Mx)‖p≤‖x−xkopt‖p+Ck1/p−1/q‖x−xkopt‖q for x∈RN, where xkopt is the best possible kk-term approximation to x.In this paper we develop a compressed sensing method whose associated recovery algorithm, AA, runs in O((klogk)logN)O((klogk)logN)-time, matching a lower bound up to a O(logk)O(logk) factor. This runtime is obtained by using a new class of sparse binary compressed sensing matrices of near optimal size in combination with sublinear-time recovery techniques motivated by sketching algorithms for high-volume data streams. The new class of matrices is constructed by randomly subsampling rows from well-chosen incoherent matrix constructions which already have a sub-linear number of rows. As a consequence, fewer random bits than previously required are needed in order to select the rows utilized by the fast reconstruction algorithms considered herein.