Estimating the Norms of Random Circulant and Toeplitz Matrices and Their Inverses
arXiv:1311.3730
Abstract
We estimate the norms of standard Gaussian random Toeplitz and circulant matrices and their inverses, mostly by means of combining some basic techniques of linear algebra. In the case of circulant matrices we obtain sharp probabilistic estimates, which show that these matrices are expected to be very well conditioned. Our probabilistic estimates for the norms of standard Gaussian random Toeplitz matrices are within a factor of 1.4143 from those in the circulant case. We also achieve partial progress in estimating the norms of Toeplitz inverses. Namely we yield reasonable probabilistic upper estimates for these norms assuming certain bounds on the absolute values of two corner entries of the inverse. Empirically we observe that the condition numbers of random Toeplitz and general matrices tend to be of the same order. As the matrix size grows, these numbers grow equally slowly, although faster than for random circulant matrices.
10.3 pages. arXiv admin note: substantial text overlap with arXiv:1212.4551
Cited by in corpus (4)
- Numerically Safe Gaussian Elimination with No Pivoting
- Inversion of the Toeplitz-block Toeplitz matrices and the structure of the corresponding inverse matrices
- Random Multipliers Numerically Stabilize Gaussian and Block Gaussian Elimination: Proofs and an Extension to Low-rank Approximation
- New Structured Matrix Methods for Real and Complex Polynomial Root-finding