Optimal Bias-variance Tradeoff in Matrix and Tensor Estimation

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.