Optimal Bias-variance Tradeoff in Matrix and Tensor Estimation

We study matrix and tensor denoising when the underlying signal is $\mathbf{\text{not}}$ necessarily low-rank. In the tensor setting, we observe $$Y=X^{\ast }+Z\in {\mathbb{R}}^{p_1\times p_2\times p_3},$$ 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 $\tilde{X}$, and show that, uniformly over any user-specified Tucker ranks $(r_1,r_2,r_3)$, with high probability, $$\mathrm{\parallel }\tilde{X}-X^{\ast }{\mathrm{\parallel }}_{\mathrm{F}}^2=O\left({\kappa }^2\right\{r_1{r}_2{r}_3+\sum _{k=1}^3{p}_k{r}_k\}+{\xi }_{(r_1,r_2,r_3)}^2)\mathrm{.}$$ Here, ${\xi }_{(r_1,r_2,r_3)}$ is the best achievable Tucker rank-$(r_1,r_2,r_3)$ approximation error of $X^{\ast }$ (bias), ${\kappa }^2$ quantifies the noise level, and ${\kappa }^2\{r_1{r}_2{r}_3+{\sum }_{k=1}^3{p}_k{r}_k\}$ is the variance term scaling with the effective degrees of freedom of $\tilde{X}$. This yields a rank-adaptive bias-variance tradeoff: increasing $(r_1,r_2,r_3)$ decreases the bias ${\xi }_{(r_1,r_2,r_3)}$ 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 $\mathbf{\text{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.