Abstract
We study the matrix denoising problem of estimating the singular vectors of a rank-1 signal corrupted by noise with both column and row correlations. Existing works are either unable to pinpoint the exact asymptotic estimation error or, when they do so, the resulting approaches (e.g., based on whitening or singular value shrinkage) remain vastly suboptimal. In contrast, our work establishes the information-theoretic and algorithmic limits of matrix denoising with doubly heteroscedastic noise. We characterize the exact asymptotic minimum mean square error (MMSE) and design a novel spectral estimator with rigorous optimality guarantees: it attains positive correlation with the signals whenever information-theoretically possible and, for one-sided heteroscedasticity, it also achieves the Bayes-optimal error. Numerical experiments demonstrate the significant advantage of our method over the state of the art.
Introduction
In many scientific and engineering fields—ranging from cryo-electron microscopy to financial modeling—the primary objective is to recover a low-rank signal matrix buried within high-dimensional noise. While standard denoising models often assume independent and identically distributed (i.i.d.) Gaussian noise, real-world data typically exhibits complex correlations. When noise variance or correlation varies across rows or columns, the noise is termed heteroscedastic.
Previous research has largely focused on "one-sided" heteroscedasticity, where noise is correlated only along one dimension. This paper addresses the more challenging doubly heteroscedastic case, where noise possesses both row and column correlations simultaneously. A critical finding of this work is that the conventional engineering approach—whitening the noise followed by singular value shrinkage—is fundamentally suboptimal and fails to reach the Bayes-optimal theoretical performance.
Methodology
The authors derive the fundamental limits of recovery using a combination of high-dimensional statistics and tools from statistical physics:
- Information-Theoretic Analysis: Using the interpolation method from spin glass theory, the authors calculate the asymptotic Minimum Mean Square Error (MMSE), identifying the precise signal-to-noise ratio (SNR) threshold where recovery becomes possible.
- Optimal Spectral Estimator: The paper introduces a pre-processed spectral method. Instead of performing a standard Singular Value Decomposition (SVD) on the raw noisy data, the matrix is transformed using the known noise covariance structures. This transformation ensures that the signal's singular vectors are optimally aligned with the true signal components.
- Approximate Message Passing (AMP): The theoretical analysis is supported by a Bayes-AMP algorithm, which provides a benchmark for optimal performance in high-dimensional regimes.
Key Insights: The Failure of Whitening and Spectral Gap Emergence
A major takeaway is that whitening is suboptimal for Bayesian estimation in this context. While whitening makes noise look i.i.d., it can destroy essential signal structure or fail to account for the coupling between row and column correlations.
The proposed pre-processing step is designed to create a "spectral gap." By transforming the data, the signal's top singular value is pushed out of the noise "bulk," making it detectable via SVD. This phenomenon is illustrated in the behavior of singular values relative to the signal strength $\lambda$. Below the threshold $\lambda^*$, the signal is indistinguishable from the noise bulk.
Numerical Results and Performance
The theoretical predictions are validated through extensive simulations on high-dimensional synthetic datasets (e.g., $4000 \times 2000$ matrices) with structured noise covariances like Toeplitz and circulant matrices.
The proposed spectral estimator significantly outperforms state-of-the-art methods, including HeteroPCA, OptShrink, and ScreeNOT. As shown in the performance metrics below, the advantage is most pronounced at low SNRs, where competing methods often fail to achieve any positive correlation with the true signal. The experimental results for both overlap (correlation with the true signal) and Mean Square Error (MSE) align perfectly with the theoretical "State Evolution" predictions.
Limitations and Future Work
While this work establishes a new state-of-the-art, several avenues for future research remain:
- Covariance Estimation: The current framework assumes noise covariances are known. Future work will address scenarios where these must be estimated from data.
- Higher-Rank Signals: The current proofs focus on rank-1 signals. Extending these results to general rank-$r$ signals is a natural next step.
- Non-Gaussian Priors: Optimality for non-Gaussian signal priors (e.g., sparse signals) would require the development of more complex AMP-based denoisers.
Summary updated