Name
Abstract | ||
|---|---|---|
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+nu}) for any nuu003e 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. |
Year | Venue | DocType |
|---|---|---|
2015 | arXiv: Data Structures and Algorithms | Journal |
Volume | Citations | PageRank |
abs/1505.08126 | 0 | 0.34 |
References | Authors | |
4 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Michael Ben-Or | 1 | 2008 | 420.97 |
| Lior Eldar | 2 | 19 | 4.02 |