Sufficient Coherence Conditions for Sparse Signal Recovery


Event Speaker: 

Alexander Barg (U. Maryland)

Event Location: 


Event Date/Time: 

Tuesday, March 19, 2013 - 4:00pm

Reception to follow.
The most frequently used condition for sampling matrices employed in compressive sampling is the restricted isometry property of the matrix when restricted to sparse signals. At the same time, imposing this condition makes it difficult to find explicit matrices that support recovery of signals from sketches of the optimal (smallest possible) dimension. A number of attempts have been made to relax or replace the RIP property in sparse recovery algorithms. We focus on the relaxation under which the near-isometry property holds for most rather than for all submatrices of the sampling matrix, known as statistical RIP or StRIP condition. We show that sampling matrices of dimensions m x N with maximum coherence mu=O((k\log^3 N)^{-1/4}) and mean square coherence \bar\mu^2=O(1/(k\log N)) support stable recovery of k-sparse signals using Basis Pursuit. These assumptions are satisfied in many examples. As a result, we are able to construct sampling matrices that support recovery with low error for sparsity k higher than \sqrt m, which exceeds the range of parameters of the known classes of RIP matrices.
Joint work with Arya Mazumdar and Rongrong Wang.
Alexander Barg received the M.Sc. degree in applied
mathematics and the Ph.D. degree in electrical engineering (information
 theory) from the Institute for Information Transmission Problems
(IPPI) Moscow, Russia. He has been a Senior Researcher at the
IPPI since 1988. During 1997–2002, he was Member of Technical Staff of Bell Labs, Lucent Technologies. Since 2003 he has been a Professor in the Department of Electrical and Computer Engineering and Institute for Systems Research, University of Maryland, College Park. His research interests include coding and information theory and its links with
 computer science and mathematics.