Random Toeplitz Matrices: The Condition Number under High Stochastic Dependence

Paulo Manrique--Mirón

Published 2020-05-19Version 1

In this paper, we study the condition number of a random Toeplitz matrix. Since a Toeplitz matrix is a diagonal constant matrix, its rows or columns cannot be stochastically independent. This situation does not permit us to use the classic strategy to analyze its minimum singular value when all the entries of a random matrix are stochastically independent. Using Cauchy Interlacing Theorem as a decoupling technique, we can break the stochastic dependence of the structure of the Toeplitz matrix and reduce the problem to analyze the extreme singular values of a random circulant matrix. Among our results, we show the condition number of non--symmetric random Toeplitz matrix of dimension $n$ under the existence of moment generating function of the random entries is $\kappa\left(\mathcal{T}_n\right) = \mbox{O}\left( \frac{1}{\varepsilon} n^{\rho+1/2} \left(\log n\right)^{1/2} \right)$ with probability $1-\mbox{O}\left((\varepsilon^2 + \varepsilon) n^{-2\rho} + n^{-1/2+\scriptstyle{o}(1)}\right)$ for any $\varepsilon >0$, $\rho\in(0,1/4)$. Moreover, if the random entries only have the second moment, we have $\kappa\left(\mathcal{T}_n\right) = \mbox{O}\left( \frac{1}{\varepsilon} n^{\rho+1/2} \log n\right)$ with probability $1-\mbox{O}\left((\varepsilon^2 + \varepsilon) n^{-2\rho} + \left(\log n\right)^{-1/2}\right)$. Also, Cauchy Interlacing Theorem permits to analyze the condition number of a symmetric random Toeplitz matrix. In this case, the condition number $\kappa\left( \mathcal{T}^{sym}_n\right) = \mbox{O}\left(\frac{1}{\varepsilon} n^{1.01} \left(\log n\right)^{1/2}\right)$ with probability $1- \mbox{O}\left( \varepsilon n^{-1/10} + n^{-77/300+\scriptstyle{o}(1)}\right)$, when the random entries have moment generating function. Additionally, we show that the results on the random Toeplitz matrices hold for random Hankel matrices.