The Quasi-Random Perspective on Matrix Spectral Analysis with Applications.
Michael Ben-Or, Lior Eldar · arXiv (Cornell University) · 2015
Computing the eigenvectors and eigenvalues of a given Hermitian matrix is arguably one of the most well-studied computational problems. Yet despite its immense importance, and a vast array of heuristic techniques, there is no algorithm that can provably approximate the spectral decomposition of any Hermitian matrix in asymptotic bit-complexity o(n^3). Inspired by the quantum computing paradigm, we introduce a new perspective on this problem that draws from the theory of quasi-random, or low-discrepancy sequences - a theory which has been unconnected to linear-algebra problems thus far. We analyze the discrepancy of an n-dimensional sequence formed by taking the fractional part of integer multiples of the vector of eigenvalues of the input matrix. This analysis gives rise to a conceptually new algorithm to compute an approximate spectral decomposition of any n x n Hermitian matrix. This algorithm can be implemented by (randomized) circuits of bit-complexity at most O(n^{\omega+ u}) for any u> 0. Because it is disjoint from previous algorithms, we hope it sheds new light on the complexity of approximate spectral decomposition, in terms of run-time, space complexity, and the number of random bits required.