|
abstract:
Compressive sensing predicts that sufficiently sparse
vectors can be recovered from highly incomplete information. Efficient
recovery methods such as L1-minimization find the sparsest
solution to certain systems of equations. Random matrices have
become a popular choice for the measurement matrix. Indeed,
near-optimal uniform recovery results have been shown for such
matrices. In this note we focus on nonuniform recovery using
Gaussian random matrices and `1-minimization. We provide a
condition on the number of samples in terms of the sparsity
and the signal length which guarantees that a fixed sparse signal
can be recovered with a random draw of the matrix using L1-
minimization. The constant 2 in the condition is optimal, and the
proof is rather short compared to a similar result due to Donoho
and Tanner.
This is joint work with Holger Rauhut. |
