Restricted isometries for partial random circulant matrices (Q412402)

The theory of compressed sensing, e.g.[\textit{J.-M. Azais} and \textit{M. Wschebor}, Level sets and extrema of random processes and fields. Hoboken, NJ: John Wiley \& Sons (2009; Zbl 1168.60002)] predicts that a small number of linear samples suffice to capture all the information in a sparse vector and that it is possible to recover the sparse vector from these samples using efficient algorithm. The linear data acquisition process is described by a measurement matrix. The restricted isometry property [\textit{E. J. Candès, J. K. Romberg} and \textit{T. Tao}, Commun. Pure Appl. Math. 59, No. 8, 1207--1223 (2006; Zbl 1098.94009)] is a standard tool for studying how efficiently this matrix captures information about sparse signals. Many potential applications of compressed sensing involve sampling processes that can be modeled by convolution with a random pulse. This random process can be modeled using a random circulant matrix. When only a limited number of samples from the output of the convolution is retained then the measurement process is described by a partial random circulant matrix. So far, the best available analysis of a partial random circulant matrix suggests that its restricted isometry constants do not exhibit optimal scaling. This work describes a new analysis that dramatically improves the previous estimates. It is shown that the \(s\)th-order restricted isometry constant is small when the number \(m\) of samples satisfies the condition \(m > \sim(s \text{log}n)^{3/2}\), where \(n\) is the length of the pulse.