A uniform uncertainty principle for Gaussian circulant matrices

This paper considers the problem of estimating a discrete signal from its convolution with a pulse consisting of a sequence of independent and identically distributed Gaussian random variables. We derive lower bounds on the length of a random pulse needed to stably reconstruct a signal supported on [1, n]. We will show that a general signal can be stably recovered from convolution with a pulse of length m gsim n log⁵ n, and a sparse signal which can be closely approximated using s lsim n/log⁵ n terms can be stably recovered with a pulse of length n.