Robust Low-Rank Correlation Fitting

Thu Ha Phi, Alexandre Hippert-Ferrer, Florent Bouchard, Arnaud BreloyICASSP 2024 · DOI

TL;DR

This paper introduces a robust method for fitting low-rank correlation matrices, which are crucial in various data analysis tasks. By employing the Huber loss function, their approach is less susceptible to outliers than traditional methods, and they develop efficient algorithms using the block majorization-minimization (MM) framework to solve it.

What Problem Does This Paper Address?

In many fields like signal processing and machine learning, understanding the relationships between variables is key. This is often captured by a correlation matrix. However, the standard way to estimate this matrix (the sample correlation matrix) can be heavily influenced by a few unusual data points (outliers). This can lead to a distorted view of the true underlying relationships. Furthermore, for datasets with many variables, storing and processing the full correlation matrix can be computationally expensive.

This paper addresses two main issues:

  1. Robustness to Outliers: How to estimate a correlation matrix that accurately reflects the general trend of the data, even when some observations are erroneous.
  2. Low-Rank Approximation: How to find a simplified, lower-dimensional representation of the correlation matrix that is computationally efficient and can still capture the essential structure.

Traditional methods like least-squares fitting for low-rank correlation matrices are sensitive to outliers. This paper aims to provide a more robust alternative that can better identify the true low-rank structure.

Methods

The core of the paper's contribution lies in its novel methodology for robust low-rank correlation fitting. Here's a breakdown:

  • Robust Cost Function: Instead of the standard least-squares (LS) approach, which uses the squared error, the authors propose using the Huber loss function. The Huber loss is a hybrid function that behaves like a quadratic loss for small errors but like a linear loss for large errors. This makes it less sensitive to extreme values (outliers) compared to the purely quadratic LS loss.
  • Low-Rank Parameterization: To enforce the low-rank structure, the correlation matrix $C$ is parameterized as $C = WW^T$, where $W$ is a tall matrix of size $p \times k$ (with $k \ll p$). This parameterization ensures that the rank of $C$ is at most $k$. Additionally, for $C$ to be a valid correlation matrix, the rows of $W$ (representing individual variables) must have unit norm.
  • Block Majorization-Minimization (MM) Framework: Directly minimizing the Huber loss with the low-rank constraint is challenging. The authors leverage the block MM framework, a powerful iterative optimization technique. This framework works by iteratively finding a "surrogate function" that is an upper bound of the objective function and is easier to minimize. The algorithm cyclically updates blocks of variables (in this case, the rows of $W$) by solving sub-problems.
  • Key Propositions for MM:
    • Proposition 1: Provides a weighted least-squares surrogate function for the Huber loss, making the problem more tractable.
  • Proposition 2: Further refines the surrogate function by linearizing it on the unit k-sphere (where the rows of $W$ reside), leading to a more efficient update.
  • Proposition 3: Solves a simple linear minimization problem on the unit k-sphere, which is the final step in updating the blocks of $W$.
  • Algorithmic Options: The paper explores different choices within the MM framework, such as how to compute upper bounds (using SVD or a simpler constant) and whether to update blocks "in" or "out" of the Huber cost calculation. These choices impact convergence speed and computational cost.

Datasets

The paper evaluates its proposed method using:

  • Simulated Data: They generate synthetic data based on a probabilistic PCA model and then intentionally corrupt a percentage of the entries to test the robustness of their algorithm against outliers.
  • CuMiDa Microarray Dataset: This dataset is used for a real-world application in dimension reduction for gene expression data. The authors note that this dataset is "extensively curated" and suitable for benchmarking machine learning approaches in cancer research.

Key Insights and Ideas

  • Huber Loss is Key for Robustness: The most significant insight is that simply switching from a least-squares objective to the Huber loss function dramatically improves the ability to recover the true low-rank correlation structure when outliers are present.
  • MM Framework Enables Efficient Optimization: The block MM framework is crucial for making the robust fitting problem computationally feasible. Without it, solving the complex optimization problem would be much harder.
  • Trade-offs in Algorithmic Choices: The paper highlights that there are practical trade-offs in choosing different MM options. For instance, using a tighter upper bound (like SVD) can speed up convergence but increases per-iteration cost, while a looser bound (like $\lambda_{max} = p$) is computationally cheaper per iteration but may require more iterations.
  • Correlation Fitting as an Alternative to PCA: The application to microarray data suggests that using low-rank correlation fitting can be a competitive, and sometimes superior, alternative to Principal Component Analysis (PCA) for linear dimension reduction, especially when the underlying correlation structure is important.

Key Results

  • Robustness Demonstrated: Figure 2 clearly shows that their proposed Huber fitting method (CorFit-Hub) significantly outperforms the standard LS fitting (CorFit-LS) in terms of Mean Squared Error (MSE) for recovering the true low-rank correlation matrix, especially as the percentage of corrupted entries increases. The Huber method with a low threshold $c$ is particularly resilient.
  • Scalability: Figure 1 demonstrates that the MM algorithms scale well for high dimensions ($p=1000, k=100$), indicating their practical applicability.
  • Microarray Clustering Performance: Table 1 shows that embedding data using their correlation fitting method (CorFit-Hub) can lead to lower clustering errors compared to PCA on several CuMiDa microarray datasets. The Huber fitting generally slightly outperforms LS fitting in this application.

Limitations and Future Work

  • Tuning the Huber Threshold ($c$): While the paper proposes a method for adaptively tuning $c$ (using 85% of entries treated with $\ge c$ as in (2)), the optimal choice of $c$ can still influence performance. The paper mentions that a low $c$ is beneficial for robustness.
  • Computational Cost of SVD: The paper acknowledges that the SVD computation for the tight upper bound can be a bottleneck. While they suggest using a universal upper bound ($\lambda_{max} = p$) to avoid this, it comes at the cost of slower convergence.
  • Future Work: The paper implicitly suggests that further exploration of adaptive thresholding strategies for $c$ could be beneficial. Additionally, investigating the theoretical properties of the Huber fitting in more detail and exploring its application to other domains where robust correlation estimation is important would be valuable future directions.

Summary updated

BibTeX
@inproceedings{phi2024robust,
  author = {Thu Ha Phi and Alexandre Hippert-Ferrer and Florent Bouchard and Arnaud Breloy},
  title = {{Robust Low-Rank Correlation Fitting}},
  booktitle = {IEEE International Conference on Acoustics, Speech and Signal Processing},
  year = {2024},
  doi = {10.1109/icassp48485.2024.10446634},
}
Figure