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

Abstract: A compressed sensing method consists of a rectangular measurement matrix,

M i n m a t h b b m R^{m i m e s N}

with

m l l N

, together with an associated recovery algorithm,

m a t h c a l A : m a t h b b m R^{m} i g h t a r r o w m a t h b b m R^{N}

. Compressed sensing methods aim to construct a high quality approximation to any given input vector

using only

as input. In particular, we focus herein on instance optimal nonlinear approximation error bounds for

M

and

m a t h c a l A

of the form

for

, where

is the best possible

k

-term approximation to

. In this paper we develop a compressed sensing method whose associated recovery algorithm,

m a t h c a l A

, runs in

O ((k l o g k) l o g N)

-time, matching a lower bound up to a

O (l o g 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.

Recommendations

Cites work

Cited in

(13)

This page was built for publication: Compressed sensing with sparse binary matrices: instance optimal error guarantees in near-optimal time

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2252137)