The restricted isometry property for time-frequency structured random matrices (Q365713)

The authors investigate a random Gabor system which is a structured \(n\times n^2\) matrix whose columns are obtained by taking all possible time-frequency shifts of a fixed random vector. The random Gabor system has many potential applications including channel identification, underwater communications, high-resolution radar, as well as matrix probing problems. Their approach is related to a recent restricted isometry analysis of the partial random circulant matrix. This approach involves an estimate of the covering numbers of the set of unit-norm \(s\)-spars vectors with respect to two metrics induced by the random process. The main results of this paper is to prove probabilistic estimates for the restricted isometry constants of a matrix whose columns consist of time-frequency shifts of a random vector. Roughly speaking, they show that the \(s\)th-order restricted isometry constant of the associated \(n\times n^2\) Gabor synthesis matrix is small, provided that \(s\leq cn^{2/3}\log^2n\). It is worth to say that the proof depends on an estimate for the expected supremum of a second-order chaos.