Compressed Sensing with Sparse Binary Matrices: Instance Optimal Error Guarantees in Near-Optimal Time

preprint2013arXivOpen access

Abstract

A compressed sensing method consists of a rectangular measurement matrix, $M \in \mathbbm{R}^{m \times N}$ with m≪Nm \ll N, together with an associated recovery algorithm, $\mathcal{A}: \mathbbm{R}^m \rightarrow \mathbbm{R}^N$. Compressed sensing methods aim to construct a high quality approximation to any given input vector ${\bf x} \in \mathbbm{R}^N$ using only $M {\bf x} \in \mathbbm{R}^m$ as input. In particular, we focus herein on instance optimal nonlinear approximation error bounds for MM and A\mathcal{A} of the form ∥x−A(Mx)∥p≤∥x−xkopt∥p+Ck1/p−1/q∥x−xkopt∥q \| {\bf x} - \mathcal{A} (M {\bf x}) \|_p \leq \| {\bf x} - {\bf x}^{\rm opt}_k \|_p + C k^{1/p - 1/q} \| {\bf x} - {\bf x}^{\rm opt}_k \|_q for ${\bf x} \in \mathbbm{R}^N$, where xkopt{\bf x}^{\rm opt}_k is the best possible kk-term approximation to x{\bf x}. In this paper we develop a compressed sensing method whose associated recovery algorithm, A\mathcal{A}, runs in O((klog⁡k)log⁡N)O((k \log k) \log N)-time, matching a lower bound up to a O(log⁡k)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.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.