  As a general framework, Matrix Exponential Dimensionality Reduction (MEDR)
deals with the small-sample-size problem that appears in linear Dimensionality
Reduction (DR) algorithms. High complexity is the bottleneck in this type of DR
algorithm because one has to solve a large-scale matrix exponential
eigenproblem. To address it, here we design a general quantum algorithm
framework for MEDR based on the block-encoding technique. This framework is
configurable, that is, by selecting suitable methods to design the
block-encodings of the data matrices, a series of new efficient quantum
algorithms can be derived from this framework. Specifically, by constructing
the block-encodings of the data matrix exponentials, we solve the eigenproblem
and then obtain the digital-encoded quantum state corresponding to the
compressed low-dimensional dataset, which can be directly utilized as input
state for other quantum machine learning tasks to overcome the curse of
dimensionality. As applications, we apply this framework to four linear DR
algorithms and design their quantum algorithms, which all achieve a polynomial
speedup in the dimension of the sample over their classical counterparts.
