# Optimal Bias-variance Tradeoff in Matrix and Tensor Estimation

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

## Key facts

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

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

- [Community Detection and Stochastic Block Models](https://mlsanity.com/paper/1703.10146/) (2017)
- [Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview](https://mlsanity.com/paper/1809.09573/) (2018)
- [TensorLy: Tensor Learning in Python](https://mlsanity.com/paper/1610.09555/) (2016)
- [Tensor SVD: Statistical and Computational Limits](https://mlsanity.com/paper/1703.02724/) (2017)
- [Rate-Optimal Perturbation Bounds for Singular Subspaces with Applications to High-Dimensional Statistics](https://mlsanity.com/paper/1605.00353/) (2016)
- [An Optimal Statistical and Computational Framework for Generalized Tensor Estimation](https://mlsanity.com/paper/2002.11255/) (2020)
- [Generative modeling via tensor train sketching](https://mlsanity.com/paper/2202.11788/) (2022)
- [Homotopy Analysis for Tensor PCA](https://mlsanity.com/paper/1610.09322/) (2016)
- [Generative Modeling via Hierarchical Tensor Sketching](https://mlsanity.com/paper/2304.05305/) (2023)
- [Implicit High-Order Moment Tensor Estimation and Learning Latent Variable Models](https://mlsanity.com/paper/2411.15669/) (2024)
- [Moment Estimation for Nonparametric Mixture Models Through Implicit Tensor Decomposition](https://mlsanity.com/paper/2210.14386/) (2022)

## Abstract (arXiv)

We study matrix and tensor denoising when the underlying signal is not necessarily low-rank. In the tensor setting, we observe [ Y = X^ast + Z ∈ ℝp1 × p2 × p3, ] where X^ast is an unknown signal tensor and Z is a noise tensor. We propose a one-step variant of the higher-order SVD (HOSVD) estimator, denoted widetilde X, and show that, uniformly over any user-specified Tucker ranks (r1,r2,r3), with high probability, [ |widetilde X - X^ast|mathrm F2 = OBig( kappa2Bigr1r2r3 + sumk=13 pk rkBig + xi(r1,r2,r3)2 Big). ] Here, xi(r1,r2,r3) is the best achievable Tucker rank-(r1,r2,r3) approximation error of X^ast (bias), kappa2 quantifies the noise level, and kappa2r1r2r3+sumk=13 pk rk is the variance term scaling with the effective degrees of freedom of widetilde X. This yields a rank-adaptive bias-variance tradeoff: increasing (r1,r2,r3) decreases the bias xi(r1,r2,r3) while increasing variance. In the matrix setting, we show that truncated SVD achieves an analogous bias-variance tradeoff for arbitrary signal matrices. Notably, our matrix result requires no assumptions on the signal matrix, such as finite rank or spectral gaps. Finally, we complement our upper bounds with matching information-theoretic lower bounds, showing that the resulting bias-variance tradeoff is minimax optimal up to universal constants in both the matrix and tensor settings.