Quantum mean centering for block-encoding-based quantum algorithm

Abstract

Mean Centering (MC) is an important data preprocessing technique, which has a wide range of applications in data mining, machine learning, and multivariate statistical analysis. When the data set is large, this process will be time-consuming. In this paper, we propose an efficient quantum MC algorithm based on the block-encoding technique, which enables the existing quantum algorithms can get rid of the assumption that the original data set has been classically mean-centered. Specifically, we first adopt the strategy that MC can be achieved by multiplying by the centering matrix $C$, i.e., removing the row means, column means and row-column means of the original data matrix $X$ can be expressed as $XC$, $CX$ and $CXC$, respectively. This allows many classical problems involving MC, such as Principal Component Analysis (PCA), to directly solve the matrix algebra problems related to $XC$, $CX$ or $CXC$. Next, we can employ the block-encoding technique to realize MC. To achieve it, we first show how to construct the block-encoding of the centering matrix $C$, and then further obtain the block-encodings of $XC$, $CX$ and $CXC$. Finally, we describe one by one how to apply our MC algorithm to PCA and other algorithms.

References in corpus (24)

• Quantum Machine Learning
• Quantum Mechanics helps in searching for a needle in a haystack
• Quantum algorithm for solving linear systems of equations
• Quantum support vector machine for big data classification
• Kernel methods in machine learning
• Quantum principal component analysis
• Quantum algorithms: an overview
• Hamiltonian Simulation by Qubitization
• Optimal Hamiltonian Simulation by Quantum Signal Processing
• Simulating Hamiltonian dynamics with a truncated Taylor series
• Efficient quantum algorithms for simulating sparse Hamiltonians
• Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics
• Quantum Data Fitting
• A quantum linear system algorithm for dense matrices
• Quantum Algorithm for Linear Regression
• Quantum Discriminant Analysis for Dimensionality Reduction and Classification
• q-means: A quantum algorithm for unsupervised machine learning
• Quantum Analog-Digital Conversion
• Quantum Fourier Transform in Computational Basis
• Asymptotic Quantum Algorithm for the Toeplitz Systems
• Quantum speedup for twin support vector machines
• Quantum spectral clustering algorithm for unsupervised learning
• An eigenanalysis of data centering in machine learning
• The Double-Constant Matrix, Centering Matrix and Equicorrelation Matrix: Theory and Applications

Cited by in corpus (2)

• Quantum Dimensionality Reduction by Linear Discriminant Analysis
• Quantum Alternating Operator Ansatz for Solving the Minimum Exact Cover Problem