提出可自适应调整复杂度的矩阵与张量去噪方法,实现最优偏差-方差权衡。
Optimal Bias-variance Tradeoff in Matrix and Tensor Estimation
- 基于高阶SVD改进,通过设定秩参数自动平衡拟合误差与噪声敏感度。
- 理论证明在任意信号下均达到最小可能误差上限,且误差由偏差与方差共同决定。
- 适用于无低秩假设的通用信号,尤其适合未知结构的数据去噪任务。
研究当潜在信号不一定是低秩时的矩阵与张量去噪问题。在张量情形下,观测模型为 $ Y = X^ op + Z \in \mathbb{R}^{p_1 \times p_2 \times p_3} $,其中 $X^ op$ 为未知信号张量,$Z$ 为噪声张量。本文提出一种高阶SVD(HOSVD)的一步变体估计器 $\widetilde X$,并证明:对任意用户指定的Tucker秩 $(r_1,r_2,r_3)$,以高概率有 $$ \|\widetilde X - X^\ast\|_{\mathrm F}^2 = O\Big( κ^2\Big\{r_1r_2r_3 + \sum_{k=1}^3 p_k r_k\Big\} + ξ_{(r_1,r_2,r_3)}^2 \Big) $$ 其中,$ξ_{(r_1,r_2,r_3)}$ 表示 $X^\ast$ 在Tucker秩 $(r_1,r_2,r_3)$ 下的最优逼近误差(偏差),$κ^2$ 衡量噪声水平,$κ^2\{r_1r_2r_3+\sum_{k=1}^3 p_k r_k\}$ 为随有效自由度变化的方差项。该结果实现了秩自适应的偏差-方差权衡:增大秩可降低偏差但增加方差。在矩阵情形下,我们进一步证明截断SVD对任意信号矩阵也能实现类似权衡,且无需任何关于信号矩阵的假设(如有限秩或谱隙)。最后,我们给出了匹配的信息论下界,表明该偏差-方差权衡在矩阵与张量情形下均达到极小最大误差意义下的最优性,仅差常数因子。
原文摘要 · Abstract (English)
We study matrix and tensor denoising when the underlying signal is \textbf{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 $\widetilde X$, and show that, uniformly over any user-specified Tucker ranks $(r_1,r_2,r_3)$, with high probability, \[ \|\widetilde X - X^\ast\|_{\mathrm F}^2 = O\Big( κ^2\Big\{r_1r_2r_3 + \sum_{k=1}^3 p_k r_k\Big\} + ξ_{(r_1,r_2,r_3)}^2 \Big). \] Here, $ξ_{(r_1,r_2,r_3)}$ is the best achievable Tucker rank-$(r_1,r_2,r_3)$ approximation error of $X^\ast$ (bias), $κ^2$ quantifies the noise level, and $κ^2\{r_1r_2r_3+\sum_{k=1}^3 p_k r_k\}$ is the variance term scaling with the effective degrees of freedom of $\widetilde X$. This yields a rank-adaptive bias-variance tradeoff: increasing $(r_1,r_2,r_3)$ decreases the bias $ξ_{(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 \textbf{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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。