Quantum discriminant analysis for dimensionality reduction and classification
In: New Journal of Physics, Jg. 18 (2016), Heft 7, S. 073011-73011
Online
academicJournal
Zugriff:
We present quantum algorithms to efficiently perform discriminant analysis for dimensionality reduction and classification over an exponentially large input data set. Compared with the best-known classical algorithms, the quantum algorithms show an exponential speedup in both the number of training vectors M and the feature space dimension N . We generalize the previous quantum algorithm for solving systems of linear equations (2009 Phys. Rev. Lett. http://dx.doi.org/10.1103/PhysRevLett.103.150502 103 http://dx.doi.org/10.1103/PhysRevLett.103.150502 ) to efficiently implement a Hermitian chain product of k trace-normalized N × N Hermitian positive-semidefinite matrices with time complexity of $O(\mathrm{log}(N))$ . Using this result, we perform linear as well as nonlinear Fisher discriminant analysis for dimensionality reduction over M vectors, each in an N -dimensional feature space, in time $O(p\;\mathrm{polylog}({MN})/{\epsilon }^{3})$ , where ϵ denotes the tolerance error, and p is the number of principal projection directions desired. We also present a quantum discriminant analysis algorithm for data classification with time complexity $O(\mathrm{log}({MN})/{\epsilon }^{3})$ .
Titel: |
Quantum discriminant analysis for dimensionality reduction and classification
|
---|---|
Autor/in / Beteiligte Person: | Cong, Iris ; Duan, Luming |
Link: | |
Zeitschrift: | New Journal of Physics, Jg. 18 (2016), Heft 7, S. 073011-73011 |
Veröffentlichung: | IOP Publishing, 2016 |
Medientyp: | academicJournal |
ISSN: | 1367-2630 (print) |
DOI: | 10.1088/1367-2630/18/7/073011 |
Schlagwort: |
|
Sonstiges: |
|