2013/02/24 by Iwen, M. A. · 1 citation
#FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT) #Numerical Analysis (math.NA)
paper · doi:10.48550/arxiv.1302.5936
A compressed sensing method consists of a rectangular measurement matrix, M ∈ \mathbbmRm × N with m ≪ N, together with an associated recovery algorithm, A: \mathbbmRm → \mathbbmRN. Compressed sensing methods aim to construct a high quality approximation to any given input vector \bf x ∈ \mathbbmRN using only M \bf x ∈ \mathbbmRm as input. In particular, we focus herein on instance optimal nonlinear approximation error bounds for M and A of the form ‖ \bf x - A (M \bf x) ‖p ≤ ‖ \bf x - \bf x\rm optk ‖p + C k1/p - 1/q ‖ \bf x - \bf x\rm optk ‖q for \bf x ∈ \mathbbmRN, where \bf x\rm optk is the best possible k-term approximation to \bf x. In this paper we develop a compressed sensing method whose associated recovery algorithm, A, runs in O((k log k) log N)-time, matching a lower bound up to a O(log k) 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.