BenOr, Michael ;
Eldar, Lior
A QuasiRandom Approach to Matrix Spectral Analysis
Abstract
Inspired by quantum computing algorithms for Linear Algebra problems [Harrow et al., Phys. Rev. Lett. 2009, TaShma, STOC 2013] we study how simulation on a classical computer of this type of "Phase Estimation algorithms" performs when we apply it to the EigenProblem of Hermitian matrices. The result is a completely new, efficient and stable, parallel algorithm to compute an approximate spectral decomposition of any Hermitian matrix. The algorithm can be implemented by Boolean circuits in O(log^2(n)) parallel time with a total cost of O(n^(\omega+1)) Boolean operations. This Boolean complexity matches the best known O(log^2(n)) parallel time algorithms, but unlike those algorithms our algorithm is (logarithmically) stable, so it may lead to actual implementations, allowing fast parallel computation of eigenvectors and eigenvalues in practice.
Previous approaches to solve the EigenProblem generally use randomization to avoid bad conditions  as we do. Our algorithm makes further use of randomization in a completely new way, taking random powers of a unitary matrix to randomize the phases of its eigenvalues. Proving that a tiny Gaussian perturbation and a random polynomial power are sufficient to ensure almost pairwise independence of the phases (mod 2pi) is the main technical contribution of this work. It relies on the theory of lowdiscrepancy or quasirandom sequences  a theory, which to the best of our knowledge, has not been connected thus far to linear algebra problems. Hence, we believe that further study of this new connection will lead to additional improvements.
BibTeX  Entry
@InProceedings{benor_et_al:LIPIcs:2018:8328,
author = {Michael BenOr and Lior Eldar},
title = {{A QuasiRandom Approach to Matrix Spectral Analysis}},
booktitle = {9th Innovations in Theoretical Computer Science Conference (ITCS 2018)},
pages = {6:16:22},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770606},
ISSN = {18688969},
year = {2018},
volume = {94},
editor = {Anna R. Karlin},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/8328},
URN = {urn:nbn:de:0030drops83288},
doi = {10.4230/LIPIcs.ITCS.2018.6},
annote = {Keywords: linear algebra, eigenvalues, eigenvectors, lowdiscrepancy sequence}
}
12.01.2018
Keywords: 

linear algebra, eigenvalues, eigenvectors, lowdiscrepancy sequence 
Seminar: 

9th Innovations in Theoretical Computer Science Conference (ITCS 2018)

Issue date: 

2018 
Date of publication: 

12.01.2018 