|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'506'133
Articles rated: 2609
26 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
An improved quantum algorithm for A-optimal projection | | Shi-Jie Pan
; Lin-Chun Wan
; Hai-Ling Liu
; Qing-Le Wang
; Su-Juan Qin
; Qiao-Yan Wen
; Fei Gao
; | | Date: |
10 Jun 2020 | | Abstract: | Dimensionality reduction (DR) algorithms, which reduce the dimensionality of
a given data set while preserving the information of original data set as well
as possible, play an important role in machine learning and data mining. Duan
et al. proposed a quantum version of A-optimal projection algorithm (AOP) for
dimensionality reduction [Phys. Rev. A 99, 032311 (2019)] and claimed that the
algorithm has exponential speedups on the dimensionality of the original
feature space $n$ and the dimensionality of the reduced feature space $k$ over
the classical algorithm. In this paper, we correct the complexity of Duan et
al.’s algorithm to $O(frac{kappa^{4s}sqrt{k^s}}
{epsilon^{s}}mathrm{polylog}^s (frac{mn}{epsilon}))$, where $kappa$ is the
condition number of a matrix that related to the original data set, $s$ is the
number of iterations, $m$ is the number of data points and $epsilon$ is the
desired precision of the output state. Since the complexity has an exponential
dependence on $s$, the quantum algorithm can only be beneficial for high
dimensional problems with a small number of iterations $s$. To get a further
speedup, we proposed an improved quantum AOP algorithm with complexity
$O(frac{s kappa^6 sqrt{k}}{epsilon}mathrm{polylog}(frac{nm}{epsilon}) +
frac{s^2 kappa^4}{epsilon}mathrm{polylog}(frac{kappa k}{epsilon}))$. Our
algorithm achieves a nearly exponential speedup if $s$ is large and a
polynomial speedup even if $s$ is a small constant compared with Duan et al.’s
algorithm. Also, our algorithm shows exponential speedups in $n$ and $m$
compared with the classical algorithm when both $kappa$, $k$ and $1/epsilon$
are $O(mathrm{polylog}(nm))$. | | Source: | arXiv, 2006.5745 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; +claudebot@anthropic.com)
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER