  Neighborhood Preserving Embedding (NPE) is an important linear dimensionality
reduction technique that aims at preserving the local manifold structure. NPE
contains three steps, i.e., finding the nearest neighbors of each data point,
constructing the weight matrix, and obtaining the transformation matrix. Liang
et al. proposed a variational quantum algorithm (VQA) for NPE [Phys. Rev. A
101, 032323 (2020)]. The algorithm consists of three quantum sub-algorithms,
corresponding to the three steps of NPE, and was expected to have an
exponential speedup on the dimensionality $n$. However, the algorithm has two
disadvantages: (1) It is incomplete in the sense that the input of the third
sub-algorithm cannot be obtained by the second sub-algorithm. (2) Its
complexity cannot be rigorously analyzed because the third sub-algorithm in it
is a VQA. In this paper, we propose a complete quantum algorithm for NPE, in
which we redesign the three sub-algorithms and give a rigorous complexity
analysis. It is shown that our algorithm can achieve a polynomial speedup on
the number of data points $m$ and an exponential speedup on the dimensionality
$n$ under certain conditions over the classical NPE algorithm, and achieve
significant speedup compared to Liang et al.'s algorithm even without
considering the complexity of the VQA.
