# Matrix Denoising with Doubly Heteroscedastic Noise: Fundamental Limits and Optimal Spectral Methods arXiv: https://arxiv.org/abs/2405.13912 · HTML: https://mlsanity.com/paper/2405.13912/ ## Key facts - Cited by 5 papers in the map (data through 14 Oct 2026). - Builds on 34 of its 78 references that are in the map. - First posted on arXiv 22 May 2024. ## Builds on (most cited first, 30 of 34) - [Optimal Errors and Phase Transitions in High-Dimensional Generalized Linear Models](https://mlsanity.com/paper/1708.03395/) (2017) - [Confidence Intervals and Hypothesis Testing for High-Dimensional Regression](https://mlsanity.com/paper/1306.3171/) (2013) - [A unifying tutorial on Approximate Message Passing](https://mlsanity.com/paper/2105.02180/) (2021) - [Estimation of Low-Rank Matrices via Approximate Message Passing](https://mlsanity.com/paper/1711.01682/) (2017) - [De-biasing the Lasso: Optimal Sample Size for Gaussian Designs](https://mlsanity.com/paper/1508.02757/) (2015) - [Graph-based Approximate Message Passing Iterations](https://mlsanity.com/paper/2109.11905/) (2021) - [Heteroskedastic PCA: Algorithm, Optimality, and Applications](https://mlsanity.com/paper/1810.08316/) (2018) - [Approximate Message Passing algorithms for rotationally invariant matrices](https://mlsanity.com/paper/2008.11892/) (2020) - [Randomly initialized EM algorithm for two-component Gaussian mixture achieves near optimality in O(√n) iterations](https://mlsanity.com/paper/1908.10935/) (2019) - [MMSE of probabilistic low-rank matrix estimation: Universality with respect to the output channel](https://mlsanity.com/paper/1507.03857/) (2015) - [Hypothesis Testing in High-Dimensional Regression under the Gaussian Random Design Model: Asymptotic Theory](https://mlsanity.com/paper/1301.4240/) (2013) - [Approximate Message Passing for orthogonally invariant ensembles: Multivariate non-linearities and spectral initialization](https://mlsanity.com/paper/2110.02318/) (2021) - [Estimation in Rotationally Invariant Generalized Linear Models via Approximate Message Passing](https://mlsanity.com/paper/2112.04330/) (2021) - [Optimal Combination of Linear and Spectral Estimators for Generalized Linear Models](https://mlsanity.com/paper/2008.03326/) (2020) - [ScreeNOT: Exact MSE-Optimal Singular Value Thresholding in Correlated Noise](https://mlsanity.com/paper/2009.12297/) (2020) - [OptShrink: An algorithm for improved low-rank signal matrix denoising by optimal, data-driven singular value shrinkage](https://mlsanity.com/paper/1306.6042/) (2013) - [PCA Initialization for Approximate Message Passing in Rotationally Invariant Models](https://mlsanity.com/paper/2106.02356/) (2021) - [Entrywise Estimation of Singular Vectors of Low-Rank Matrices with Heteroskedasticity and Dependence](https://mlsanity.com/paper/2105.13346/) (2021) - [Denoising and Covariance Estimation of Single Particle Cryo-EM Images](https://mlsanity.com/paper/1602.06632/) (2016) - [Tackling small eigen-gaps: Fine-grained eigenvector estimation and inference under heteroscedastic noise](https://mlsanity.com/paper/2001.04620/) (2020) - [Information-Theoretic Limits for the Matrix Tensor Product](https://mlsanity.com/paper/2005.11273/) (2020) - [The price of ignorance: how much does it cost to forget noise structure in low-rank matrix estimation?](https://mlsanity.com/paper/2205.10009/) (2022) - [Complex diffusion-weighted image estimation via matrix recovery under general noise models](https://mlsanity.com/paper/1812.05954/) (2018) - [Fundamental limits for rank-one matrix estimation with groupwise heteroskedasticity](https://mlsanity.com/paper/2106.11950/) (2021) - [Optimal Algorithms for the Inhomogeneous Spiked Wigner Model](https://mlsanity.com/paper/2302.06665/) (2023) - [Precise Asymptotics for Spectral Methods in Mixed Generalized Linear Models](https://mlsanity.com/paper/2211.11368/) (2022) - [Deflated HeteroPCA: Overcoming the curse of ill-conditioning in heteroskedastic PCA](https://mlsanity.com/paper/2303.06198/) (2023) - [Fundamental limits of community detection from multi-view data: multi-layer, dynamic and partially labeled block models](https://mlsanity.com/paper/2401.08167/) (2024) - [Matrix denoising for weighted loss functions and heterogeneous signals](https://mlsanity.com/paper/1902.09474/) (2019) - [Adapting to Unknown Noise Distribution in Matrix Denoising](https://mlsanity.com/paper/1810.02954/) (2018) ## Built on by (most cited first, 5 of 5) - [Asymptotics of Linear Regression with Linearly Dependent Data](https://mlsanity.com/paper/2412.03702/) (2024) - [Optimal thresholds and algorithms for a model of multi-modal learning in high dimensions](https://mlsanity.com/paper/2407.03522/) (2024) - [On the phase diagram of extensive-rank symmetric matrix denoising beyond rotational invariance](https://mlsanity.com/paper/2411.01974/) (2024) - [Computational and statistical lower bounds for low-rank estimation under general inhomogeneous noise](https://mlsanity.com/paper/2510.08541/) (2025) - [Heteroskedastic Canonical Polyadic Tensor Decomposition](https://mlsanity.com/paper/2610.00498/) (2026) ## Abstract (arXiv) 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. On top of this, most of the literature has focused on the special case of estimating the left singular vector of the signal when the noise only possesses row correlation (one-sided heteroscedasticity). 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, and design a novel spectral estimator with rigorous optimality guarantees: under a technical condition, 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 theoretically principled method with the state of the art. The proofs draw connections with statistical physics and approximate message passing, departing drastically from standard random matrix theory techniques.