Rectangular Rotational Invariant Estimator for General Additive Noise Matrices

Farzad Pourkamali, Nicolas Macris

Introduction

In modern data science, high-dimensional rectangular matrices are ubiquitous. Whether analyzing gene expression profiles in genomics or asset returns in finance, researchers frequently encounter datasets where the number of features $M$ differs significantly from the number of observations $N$. A fundamental challenge in these domains is matrix denoising: the task of recovering a hidden signal matrix from an observation corrupted by noise.

While denoising techniques for square, symmetric matrices have matured significantly, the rectangular case presents unique mathematical hurdles. This paper introduces a novel framework for denoising rectangular matrices subject to general additive, rotationally invariant noise. By leveraging advanced tools from Random Matrix Theory (RMT) and statistical mechanics, the authors derive a "miracle" estimator that achieves Bayes-optimal performance without requiring prior knowledge of the signal's distribution.

The Problem: Denoising Under Structured Noise

The standard model for matrix denoising assumes an observed matrix $Y$ is the sum of a signal matrix $X$ and a noise matrix $W$: $$Y = X + W$$ In many classical applications, $W$ is assumed to be i.i.d. Gaussian noise (white noise). However, real-world noise often possesses complex correlations. This research focuses on rotationally invariant noise, a broader class where the statistical properties of the noise remain unchanged under orthogonal transformations. This setting is significantly more difficult because the noise can be highly structured, yet its rotational symmetry allows for the application of powerful mathematical symmetries.

Methodology: The Rectangular RIE

The authors propose the Rectangular Rotational Invariant Estimator (RIE). The estimator is built upon the Singular Value Decomposition (SVD) of the observed matrix $Y = U \Sigma V^T$. For rotationally invariant noise, the optimal estimate of the signal shares the same left and right singular vectors ($U$ and $V$) as the observation. The denoising task thus reduces to finding the optimal transformation of the singular values—essentially determining how to "shrink" or "stretch" the observed spectrum to filter out the noise.

To derive the optimal singular value transformation, the researchers employed three primary mathematical pillars:

  1. The Replica Trick: Borrowed from the physics of disordered systems, this technique allows for the calculation of averages over random configurations in the high-dimensional limit.
  2. Free Probability Theory: Specifically, the Rectangular R-transform was used to describe the addition of random rectangular matrices, providing a way to predict the singular value distribution of the sum $X + W$.
  3. Symmetrization: The authors utilized a mathematical mapping to transform the rectangular problem into a larger, symmetric square matrix problem, making it compatible with existing RMT tools.

The "Miracle" Property

The most significant theoretical contribution of this work is the discovery of the "miracle" property of the RIE. In Bayesian estimation, achieving the Minimum Mean Squared Error (MMSE) typically requires an "Oracle" that knows the prior distribution of the signal $X$.

However, the authors prove that for rotationally invariant noise in high dimensions, the RIE is Bayes-optimal even when the signal prior is unknown. The estimator only requires knowledge of the noise distribution and the singular values of the observed matrix. This makes the RIE exceptionally practical, as the underlying structure of the signal is rarely known in real-world applications.

Experimental Validation

As this is a theoretical advancement, the authors validated their findings using synthetic datasets designed to test the limits of the high-dimensional $(N, M \to \infty)$ predictions.

Signal and Noise Profiles

  • Signal Types: The estimator was tested against both i.i.d. Gaussian signals and sparse signals (where most entries are zero).
  • Noise Types: Beyond standard Gaussian noise, the researchers tested uniform noise distributions to demonstrate the estimator's versatility across different noise statistics.

Key Results

  • Oracle Matching: Numerical simulations with $1000 \times 1000$ matrices demonstrated that the proposed RIE's performance is indistinguishable from an Oracle estimator that has full knowledge of the signal's prior.
  • Asymptotic Convergence: The experiments confirmed that as matrix dimensions increase, the empirical Mean Squared Error converges exactly to the theoretical MMSE predicted by the authors' formulas.
  • Information-Theoretic Links: The paper establishes a formal connection between Mutual Information and the log-spherical integral (a complex object in high-energy physics), providing a new computational pathway for these integrals via denoising theory.

Limitations and Future Outlook

While the Rectangular RIE represents a major step forward, certain constraints remain:

  • Dimensionality: The "miracle" property is an asymptotic result. While it performs well at $N=1000$, its efficacy on very small matrices (e.g., $10 \times 10$) requires further investigation.
  • Coordinate-Dependent Noise: The estimator relies on rotational invariance. If the noise is aligned with specific coordinates (such as "salt and pepper" noise in imaging), the RIE may not be the optimal choice.
  • Numerical Implementation: At very low Signal-to-Noise Ratios (SNR), approximating the Stieltjes transform (a key component of the R-transform) can become numerically unstable. Future work will likely focus on more robust numerical methods for these transforms.

Conclusion

The Rectangular RIE provides a robust, mathematically grounded framework for denoising complex datasets. By proving that optimal denoising is possible without knowing the signal's prior, the authors have provided a powerful tool for high-dimensional data analysis, bridging the gap between theoretical physics and practical statistical estimation.

Summary updated

Abstract

We propose a rectangular rotational invariant estimator to recover a real matrix from noisy matrix observations coming from an arbitrary additive rotational invariant perturbation, in the large dimension limit. Using the Bayes-optimality of this estimator, we derive the asymptotic minimum mean squared error (MMSE). For the particular case of Gaussian noise, we find an explicit expression for the MMSE in terms of the limiting singular value distribution of the observation matrix. Moreover, we prove a formula linking the asymptotic mutual information and the limit of log-spherical integral of rectangular matrices. We also provide numerical checks for our results, which match our theoretical predictions and known Bayesian inference results.
BibTeX
@inproceedings{pourkamali2023rectangular,
  author = {Farzad Pourkamali and Nicolas Macris},
  title = {{Rectangular Rotational Invariant Estimator for General Additive Noise Matrices}},
  booktitle = {ISIT},
  year = {2023},
  url = {https://openreview.net/forum?id=FJtzIjoOuY},
}
Figure