Statistical Spectral Analysis of Random
Davide Macagnano, Giuseppe Thadeu, Freitas de Abreu · 2010
In this paper we perform the statistical analysis on the spectrum of random N × N Gramian matrices of the form G ∗ T V T · GT · V, where G and GT are themselves Gramian matrices with subspace distance Δ(G, GT ) and V is the diagonalizer of G. In particular, we employ an extreme- value and asymptotic take on the theory of Gershgorin spectrum bounds to characterize the statistical structure of G ∗ T. The results reveal that even for relatively large Δ(G, GT ), the matrix G ∗ T is, with a high probability, brought to such a structure that can it be quickly diagonalized. This feature is exploited to design a statistically optimized and truncated variation of the Jacobi algorithm which is found to converge to the dominant eigenspace of G ∗ T as fast as the deterministic optimal sweeping strategy but without requiring its typical exhaustive search.