The smallest singular value of large random rectangular Toeplitz and circulant matrices

Abstract

Let $x_i$, $i\in \mathbb{Z}$ be a sequence of i.i.d. standard normal random variables. Consider rectangular Toeplitz $\mathbf{X}={\left(x_{j-i}\right)}_{1\le i\le p,1\le j\le n}$ and circulant $\mathbf{X}={\left(x_{(j-i)\mathrm{mod}n}\right)}_{1\le i\le p,1\le j\le n}$ matrices. Let $p,n\to \infty$ so that $p/n\to c\in (0,1]$. We prove that the smallest eigenvalue of $\frac{1}{n}\mathbf{X}{\mathbf{X}}^{\top }$ converges to zero in probability and in expectation. We establish a lower bound on the rate of this convergence. The lower bound is faster than any poly-log but slower than any polynomial rate. For the ``rectangular circulant'' matrices, we also establish a polynomial upper bound on the convergence rate, which is a simple explicit function of $c$.

29 pages including Appendix, 4 figures