Explicit measurements with almost optimal thresholds for compressed sensing

Abstract

We consider the deterministic construction of a measurement matrix and a recovery method for signals that are block sparse. A signal that has dimension N = nd, which consists of n blocks of size d, is called (s, d)-block sparse if only s blocks out of n are nonzero. We construct an explicit linear mapping Ω that maps the (s, d)-block sparse signal to a measurement vector of dimension M, where s | d < N (1 - (1 - M/N)d/d+1) - o(1). We show that if the (s, d)-block sparse signal is chosen uniformly at random then the signal can almost surely be reconstructed from the measurement vector in O(N3) computations. ©2008 IEEE.