In this paper, we investigate extreme singular values of the analysis matrix of a Gabor frame @math with a random window @math . Columns of such matrices are time and frequency shifts of @math , and @math is the set of time-frequency shift indices. Our aim is to obtain bounds on the singular values of such random time-frequency structured matrices for various choices of the frame set @math , and to investigate their dependence on the structure of @math , as well as on its cardinality. We also compare the results obtained for Gabor frame analysis matrices with the respective results for matrices with independent identically distributed entries.
Before we study the case when @math is a Gabor frame, we include here a short overwiew of the results on the singular values for random frames with independent entries, such as Gaussian matrices. The largest singular value of the analysis matrix @math of a random frame with independent entries can be estimated using Latala’s theorem @cite_8 . The following result implies that, with high probability, @math .
@cite_8
2031213242
Let @math denote a random symmetric @math matrix whose upper diagonal entries are independent and identically distributed Bernoulli random variables (which take values @math and @math with probability @math each). It is widely conjectured that @math is singular with probability at most @math . On the other hand, the best known upper bound on the singularity probability of @math , due to Vershynin (2011), is @math , for some unspecified small constant @math . This improves on a polynomial singularity bound due to Costello, Tao, and Vu (2005), and a bound of Nguyen (2011) showing that the singularity probability decays faster than any polynomial. In this paper, improving on all previous results, we show that the probability of singularity of @math is at most @math for all sufficiently large @math . The proof utilizes and extends a novel combinatorial approach to discrete random matrix theory, which has been recently introduced by the authors together with Luh and Samotij. An approximate Spielman-Teng theorem for the least singular value @math of a random @math square matrix @math is a statement of the following form: there exist constants @math such that for all @math , @math . The goal of this paper is to develop a simple and novel framework for proving such results for discrete random matrices. As an application, we prove an approximate Spielman-Teng theorem for @math -valued matrices, each of whose rows is an independent vector with exactly @math zero components. This improves on previous work of Nguyen and Vu, and is the first such result in a truly combinatorial' setting. The classical random matrix theory is mostly focused on asymptotic spectral properties of random matrices as their dimensions grow to infinity. At the same time many recent applications from convex geometry to functional analysis to information theory operate with random matrices in fixed dimensions. This survey addresses the non-asymptotic theory of extreme singular values of random matrices with independent entries. We focus on recently developed geometric methods for estimating the hard edge of random matrices (the smallest singular value). We prove an optimal estimate of the smallest singular value of a random sub- Gaussian matrix, valid for all dimensions. For an Nn matrix A with inde- pendent and identically distributed sub-Gaussian entries, the smallest singular value of A is at least of the order p Np n � 1 with high probability. A sharp