# Computational and statistical lower bounds for low-rank estimation under general inhomogeneous noise

arXiv: https://arxiv.org/abs/2510.08541 · HTML: https://mlsanity.com/paper/2510.08541/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 22 of its 71 references that are in the map.
- First posted on arXiv 9 Oct 2025.

## Builds on (most cited first, 22 of 22)

- [Notes on Computational Hardness of Hypothesis Testing: Predictions using the Low-Degree Likelihood Ratio](https://mlsanity.com/paper/1907.11636/) (2019)
- [The power of sum-of-squares for detecting hidden structures](https://mlsanity.com/paper/1710.05017/) (2017)
- [Optimality and Sub-optimality of PCA I: Spiked Random Matrix Models](https://mlsanity.com/paper/1807.00891/) (2018)
- [Mutual information for symmetric rank-one matrix estimation: A proof of the replica formula](https://mlsanity.com/paper/1606.04142/) (2016)
- [MMSE of probabilistic low-rank matrix estimation: Universality with respect to the output channel](https://mlsanity.com/paper/1507.03857/) (2015)
- [Computational Complexity of Statistics: New Insights from Low-Degree Polynomials](https://mlsanity.com/paper/2506.10748/) (2025)
- [Fundamental limits of detection in the spiked Wigner model](https://mlsanity.com/paper/1806.09588/) (2018)
- [Spectral Planting and the Hardness of Refuting Cuts, Colorability, and Communities in Random Graphs](https://mlsanity.com/paper/2008.12237/) (2020)
- [Rank-one matrix estimation: analysis of algorithmic and information theoretic limits by the spatial coupling method](https://mlsanity.com/paper/1812.02537/) (2018)
- [Statistical and Computational Phase Transitions in Group Testing](https://mlsanity.com/paper/2206.07640/) (2022)
- [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)
- [Information-theoretic limits of a multiview low-rank symmetric spiked matrix model](https://mlsanity.com/paper/2005.08017/) (2020)
- [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)
- [Tensor cumulants for statistical inference on invariant distributions](https://mlsanity.com/paper/2404.18735/) (2024)
- [Detection of Dense Subhypergraphs by Low-Degree Polynomials](https://mlsanity.com/paper/2304.08135/) (2023)
- [Information limits and Thouless-Anderson-Palmer equations for spiked matrix models with structured noise](https://mlsanity.com/paper/2405.20993/) (2024)
- [Spectral Detection in the Censored Block Model](https://mlsanity.com/paper/1502.00163/) (2015)
- [Matrix Denoising with Doubly Heteroscedastic Noise: Fundamental Limits and Optimal Spectral Methods](https://mlsanity.com/paper/2405.13912/) (2024)
- [Near-optimal fitting of ellipsoids to random points](https://mlsanity.com/paper/2208.09493/) (2022)
- [Low coordinate degree algorithms I: Universality of computational thresholds for hypothesis testing](https://mlsanity.com/paper/2403.07862/) (2024)

## Abstract (arXiv)

Recent work has generalized several results concerning the well-understood spiked Wigner matrix model of a low-rank signal matrix corrupted by additive i.i.d. Gaussian noise to the inhomogeneous case, where the noise has a variance profile. In particular, for the special case where the variance profile has a block structure, a series of results identified an effective spectral algorithm for detecting and estimating the signal, identified the threshold signal strength required for that algorithm to succeed, and proved information-theoretic lower bounds that, for some special signal distributions, match the above threshold. We complement these results by studying the computational optimality of this spectral algorithm. Namely, we show that, for a much broader range of signal distributions, whenever the spectral algorithm cannot detect a low-rank signal, then neither can any low-degree polynomial algorithm. This gives the first evidence for a computational hardness conjecture of Guionnet, Ko, Krzakala, and Zdeborov'a (2023). With similar techniques, we also prove sharp information-theoretic lower bounds for a class of signal distributions not treated by prior work. Unlike all of the above results on inhomogeneous models, our results do not assume that the variance profile has a block structure, and suggest that the same spectral algorithm might remain optimal for quite general profiles. We include a numerical study of this claim for an example of a smoothly-varying rather than piecewise-constant profile. Our proofs involve analyzing the graph sums of a matrix, which also appear in free and traffic probability, but we require new bounds on these quantities that are tighter than existing ones for non-negative matrices, which may be of independent interest.