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

Let {xi}i∈Z be a sequence of i.i.d. standard normal random variables. We consider two classes of rectangular random matrices: ToeplitzX=(xj−i)1≤i≤p,1≤j≤n and circulantX=(x(j−i)modn)1≤i≤p,1≤j≤n. We let p,n→∞ so that p∕n→c∈(0,1]. Our main result is that, for any c∈(0,1], the smallest eigenvalue of 1nXX⊤ converges to zero both in probability and in expectation. We further establish a lower bound on the rate of this convergence, showing it is faster than any poly-logarithmic rate yet slower than any polynomial rate. In the “rectangular circulant” setting, we additionally derive a simple, explicit upper bound on the convergence rate in terms of c. This upper bound implies that, for sufficiently small c, the decay of the smallest eigenvalue to zero can be made arbitrarily slow on a polynomial scale.