Quantum algorithm for marginal Fisher analysis

Abstract Marginal Fisher analysis (MFA) stands out as a prominent dimensionality reduction algorithm, striving to minimize within-class scatter while maximizing the separability between marginal data points. However, MFA and its variants require substantial computational resources when dealing with large-scale data. To address this, we propose quantum algorithms for MFA (called QMFA). QMFA is composed of two core processes: the first is the efficient construction of the weight matrices for the intrinsic and penalty graphs, and the second is solving the generalized eigenvalue problem (GEP) using the block-encoding technique. Compared to classical MFA, the proposed QMFA achieves a polynomial acceleration in the number of samples and exponential acceleration in the dimensionality. Additionally, we investigate quantum algorithms for different variants of MFA. Specifically, for enhanced MFA and multiple MFA, we address the construction of the related weight matrix, which differs from that in standard MFA. For kernel MFA, we solve the GEP associated with the corresponding kernel matrix. The proposed quantum algorithms achieve a speedup equivalent to that of QMFA.