How many entries of a typical orthogonal matrix can be approximated by independent normals?

Abstract

We solve an open problem of Diaconis that asks what are the largest orders of $p_n$ and $q_n$ such that $Z_n,$ the $p_n\times q_n$ upper left block of a random matrix ${\mathbf{\Gamma }}_n$ which is uniformly distributed on the orthogonal group O(n), can be approximated by independent standard normals? This problem is solved by two different approximation methods. First, we show that the variation distance between the joint distribution of entries of $Z_n$ and that of $p_n{q}_n$ independent standard normals goes to zero provided $p_n=o(\sqrt{n})$ and $q_n=o(\sqrt{n})$. We also show that the above variation distance does not go to zero if $p_n=[x\sqrt{n}]$ and $q_n=[y\sqrt{n}]$ for any positive numbers $x$ and $y$. This says that the largest orders of $p_n$ and $q_n$ are $o(n^{1/2})$ in the sense of the above approximation. Second, suppose ${\mathbf{\Gamma }}_n=({\gamma }_{ij}{)}_{n\times n}$ is generated by performing the Gram--Schmidt algorithm on the columns of ${\mathbf{Y}}_n=(y_{ij}{)}_{n\times n}$, where $\{y_{ij};1\le i,j\le n\}$ are i.i.d. standard normals. We show that ${\epsilon }_n(m):={\max }_{1\le i\le n,1\le j\le m}|\sqrt{n}\cdot {\gamma }_{ij}-y_{ij}|$ goes to zero in probability as long as $m=m_n=o(n/\log n)$. We also prove that ${\epsilon }_n(m_n)\to 2\sqrt{\alpha }$ in probability when $m_n=[n\alpha /\log n]$ for any $\alpha >0.$ This says that $m_n=o(n/\log n)$ is the largest order such that the entries of the first $m_n$ columns of ${\mathbf{\Gamma }}_n$ can be approximated simultaneously by independent standard normals.

Published at http://dx.doi.org/10.1214/009117906000000205 in the Annals of Probability (http://www.imstat.org/aop/) by the Institute of Mathematical Statistics (http://www.imstat.org)

Cited by in corpus (39)

• Phase-Programmable Gaussian Boson Sampling Using Stimulated Squeezed Light
• Computational advantage of quantum random sampling
• Multivariate normal approximation using exchangeable pairs
• Quantum Computational Advantage via High-Dimensional Gaussian Boson Sampling
• Random quantum circuits are approximate unitary $t$-designs in depth $O\left(n{t}^{5+o(1)}\right)$
• Sample complexity of device-independently certified "quantum supremacy"
• The Complexity of Bipartite Gaussian Boson Sampling
• Deflation as a Method of Variance Reduction for Estimating the Trace of a Matrix Inverse
• Analogies between random matrix ensembles and the one-component plasma in two-dimensions
• The Golden-Thompson inequality --- historical aspects and random matrix applications
• Generalized Dirichlet distributions on the ball and moments
• Moments of traces of circular beta-ensembles
• On Random Matrix Averages Involving Half-Integer Powers of GOE Characteristic Polynomials
• Fermionic eigenvector moment flow
• Quantum State Tomography for Matrix Product Density Operators
• Distances between Random Orthogonal Matrices and Independent Normals
• Properties of Uniform Doubly Stochastic Matrices
• Random matrices: Universal properties of eigenvectors
• A comparison principle for functions of a uniformly random subspace
• A geometrical triumvirate of real random matrices
• Any Orthonormal Basis in High Dimension is Uniformly Distributed over the Sphere
• Strong asymptotic freeness for independent uniform variables on compact groups associated to non-trivial representations
• How to reduce dimension with PCA and random projections?
• Eigenvectors of random matrices: A survey
• De Finetti-Style Results for Wishart Matrices: Combinatorial Structure and Phase Transitions
• Eigenvectors of Wigner matrices: universality of global fluctuations
• Limit Theorems for Beta-Jacobi Ensembles
• Universality for the Toda algorithm to compute the largest eigenvalue of a random matrix
• Euclidean distance between Haar orthogonal and gaussian matrices
• Guaranteed Simultaneous Asymmetric Tensor Decomposition via Orthogonalized Alternating Least Squares
• Eigenvectors of Sample Covariance Matrices: Universality of global fluctuations
• Transition of Anticoncentration in Gaussian Boson Sampling
• Classes of non-Gaussian random matrices: long-range eigenvalue correlations and non-ergodic extended eigenvectors
• Fast Regression with an ${\ell }_{\infty }$ Guarantee
• Total variation approximation of random orthogonal matrices by Gaussian matrices
• The Product of Gaussian Matrices is Close to Gaussian
• Polytopes, lattices, and spherical codes for the nearest neighbor problem
• Limiting Laws of Coherence of Random Matrices with Applications to Testing Covariance Structure and Construction of Compressed Sensing Matrices
• The Distribution of Permutation Matrix Entries Under Randomized Basis