Quadratic Matrix Factorization with Applications to Manifold Learning

Zheng Zhai, Hengchao Chen, Qiang SunIEEE TPAMI 2023 · DOI · OpenReview

TL;DR

This paper introduces Quadratic Matrix Factorization (QMF), a novel matrix factorization technique that can capture the curved structure of underlying data manifolds, going beyond traditional linear methods. They propose an alternating minimization algorithm for QMF, establish its convergence properties, and introduce a regularized version with an adaptive tuning method to prevent overfitting, demonstrating its effectiveness on synthetic and real-world datasets.

What Problem Does This Paper Address?

Matrix factorization is a powerful tool for modeling low-rank data. However, many real-world datasets lie on complex, curved manifolds, which standard linear matrix factorization methods struggle to represent accurately. Existing manifold learning techniques often focus on preserving local geometric structures or finding low-dimensional embeddings, but they don't explicitly aim to recover the underlying manifold structure itself. This paper addresses this gap by proposing a method that can learn the curved manifold structure directly, offering a more faithful representation of the data's underlying geometry.

Methods

The core contribution is the Quadratic Matrix Factorization (QMF) framework. Unlike linear matrix factorization (LMF) which assumes a linear relationship between latent variables and observed data, QMF allows for quadratic relationships. This is achieved by modeling the data matrix $X$ as $X \approx R\mathcal{T}(\Phi)$, where $\mathcal{T}(\Phi)$ includes quadratic terms of the latent variables $\Phi$.

Key methodological aspects include:

  • Quadratic Function Class: The paper defines a specific class of quadratic functions to model the mapping from latent space to data space.
  • Alternating Minimization Algorithm: To optimize the QMF objective function, an alternating minimization approach is used. This involves iteratively optimizing for the factors $R$ (which represents the quadratic function) and $\Phi$ (the latent variables).
  • Optimizing for $R$ with fixed $\Phi$ is a linear regression problem.
  • Optimizing for $\Phi$ with fixed $R$ is a "quadratic projection problem," which is solved using an iterative approach (Algorithm 1).
  • Regularized QMF (RQMF): To combat overfitting, a regularization term ($\lambda ||RJ||_F$) is added to the QMF objective. This encourages simpler quadratic functions.
  • Adaptive Tuning Method: A novel method is proposed to automatically tune the regularization parameter $\lambda$ by analyzing the sensitivity of the regularization term.
  • Kernelized RQMF (RQMF-K): For manifold learning applications, a kernelized version is introduced to assign different weights to data points based on their proximity, allowing for more flexible local modeling.

Datasets

The paper evaluates its methods on:

  • Synthetic manifold learning dataset: Used to illustrate the advantages of quadratic fitting over linear fitting and to analyze the impact of parameters.
  • MNIST handwritten digit dataset: Used to demonstrate the ability to recover underlying manifold structures (principal curves) from image data.
  • Cryogenic Electron Microscopy (Cryo-EM) dataset: A real-world dataset used to showcase the method's performance in denoising and manifold reconstruction.

Key Insights and Ideas

  • Curvature Matters: The paper convincingly demonstrates that for datasets lying on curved manifolds, quadratic models (QMF) capture the underlying structure significantly better than linear models (LMF). This is crucial for accurate manifold representation.
  • Overfitting is a Concern: The proposed regularization (RQMF) is essential for preventing QMF from fitting noisy data too closely, leading to better generalization.
  • Adaptive Tuning is Key: The adaptive tuning method for the regularization parameter $\lambda$ is a significant practical contribution, as it automates a critical hyperparameter selection process.
  • Divide-and-Conquer for Manifold Learning: The application of RQMF to manifold learning uses a "divide-and-conquer" strategy, treating each data point's local neighborhood as a sub-problem, which improves accuracy and robustness.

Key Results

  • Superiority over LMF: Experiments show that QMF and RQMF consistently outperform linear matrix factorization (LMF) in reconstructing manifold structures, especially on datasets with significant curvature.
  • Competitive Performance: RQMF (both RQMF-E and RQMF-K) demonstrates competitive or superior performance compared to established manifold learning methods like Local PCA, KDE, LOG-KDE, Mfit, and Moving LS on synthetic, MNIST, and Cryo-EM datasets, particularly in terms of Mean Squared Error (MSE) and Standard Deviation (SD).
  • Improved Denoising: RQMF methods produce smoother denoised images while better preserving the original contours compared to other methods on the MNIST dataset.
  • Parameter Sensitivity: The paper highlights that the choice of regularization parameter $\lambda$ is crucial, with the proposed adaptive tuning method providing a robust way to select it.

Limitations and Future Work

  • Intrinsic Dimension: The paper assumes the intrinsic dimension $d$ of the manifold is known a priori. Estimating $d$ automatically is suggested as a future research direction.
  • Noise Models: The current work assumes Gaussian noise. Developing robust algorithms for heavy-tailed or adversarial noise is mentioned as future work.
  • Computational Cost: While alternating minimization is proposed, the quadratic projection sub-problem can still be computationally intensive.
  • Non-negativity Constraints: The paper briefly mentions that non-negative constraints could be explored in QMF for enhanced performance.

Summary updated

Abstract

Matrix factorization is a popular framework for modeling low-rank data matrices. Motivated by manifold learning problems, this paper proposes a quadratic matrix factorization (QMF) framework to learn the curved manifold on which the dataset lies. Unlike local linear methods such as the local principal component analysis, QMF can better exploit the curved structure of the underlying manifold. Algorithmically, we propose an alternating minimization algorithm to optimize QMF and establish its theoretical convergence properties. Moreover, to avoid possible over-fitting, we then propose a regularized QMF algorithm and discuss how to tune its regularization parameter. Finally, we elaborate how to apply the regularized QMF to manifold learning problems. Experiments on a synthetic manifold learning dataset and two real datasets, including the MNIST handwritten dataset and a cryogenic electron microscopy dataset, demonstrate the superiority of the proposed method over its competitors.
BibTeX
@article{zhai2023quadratic,
  author = {Zheng Zhai and Hengchao Chen and Qiang Sun},
  title = {{Quadratic Matrix Factorization with Applications to Manifold Learning}},
  journal = {IEEE TPAMI},
  year = {2023},
  doi = {10.1109/tpami.2024.3380568},
}
Figure