楔形采样:近线性样本复杂度的高效张量补全
Wedge Sampling: Efficient Tensor Completion with Nearly-Linear Sample Complexity
Hengrui Luo · Anna Ma · Ludovic Stephan · Yizhe Zhu
中文摘要
提出一种非自适应采样方案——楔形采样(wedge sampling),用于从张量元素的结构化观测中恢复边长为 n 的 k 阶低秩张量。该方案在张量展开的同一列中采样元素对,在关联的二部采样图中形成长度为 2 的路径(楔形)。成对元素的乘积提供了谱初始化所需的相关性,适用于均匀采样产生楔形过少的场景。在秩、非相干性、张量阶数和条件数固定时,楔形采样以关于 n 的近线性样本复杂度实现多项式时间恢复。谱初始化器可结合现有精化过程,仅需额外 Õ(n) 个均匀采样元素。谱精化达到任意固定相对 Frobenius 误差的弱恢复。对于具有非相干 CANDECOMP/PARAFAC(CP)因子的对称三阶张量,梯度下降在无噪声设置下实现精确恢复,误差几何递减。相比均匀元素采样下高效方法典型的 Õ(n^{k/2}) 样本复杂度,该改进表明猜想中的计算壁垒依赖于观测模型。梯度下降分析的关键要素是非相干谱范数下稀疏随机张量的集中不等式。还给出了两种过程在加性高斯噪声下的误差界及显式信噪比条件。除张量补全外,同一采样方案还改进了单边矩阵补全的样本复杂度,其目标是恢复列数远多于行数的矩阵的左奇异子空间。
关键要点
- 01楔形采样在张量展开同列采样元素对形成楔形,为谱初始化提供相关性。
- 02固定秩等参数下以近线性样本复杂度实现多项式时间张量恢复。
- 03对称三阶张量梯度下降无噪声精确恢复,误差几何递减。
- 04给出加性高斯噪声下误差界与显式信噪比条件。
- 05同一方案改进单边矩阵补全的样本复杂度。
解读
本篇暂无解读 — S2 无结论/局限章节正文(Q7 无素材)
原始英文摘要
arXiv:2602.05869v4 Announce Type: replace Abstract: We introduce wedge sampling, a non-adaptive sampling scheme for recovering an order-$k$ low-rank tensor of side length $n$ from structured observations of its entries. The scheme samples pairs of entries in the same column of a tensor unfolding, forming length-two paths (wedges) in the associated bipartite sampling graph. The products of the paired entries supply the row correlations needed for spectral initialization in regimes where uniform sampling yields too few wedges. For fixed rank, incoherence, tensor order, and condition number, wedge sampling enables polynomial-time recovery with nearly linear sample complexity in $n$. The spectral initializer can be combined with existing refinement procedures using only an additional $\tilde O(n)$ uniformly sampled entries. Spectral refinement achieves weak recovery to any fixed relative Frobenius error. For symmetric third-order tensors with incoherent canonical polyadic factors, gradient descent achieves exact recovery in the noiseless setting, with error decreasing geometrically. The improvement over the $\tilde O(n^{k/2})$ sample complexity typical of efficient methods under uniform entry sampling shows how the conjectured computational barrier depends on the observation model. A key ingredient for the gradient descent analysis is a concentration bound for sparse random tensors in an incoherent spectral norm. We also give error bounds for both procedures under additive Gaussian noise and explicit signal-to-noise conditions. Beyond tensor completion, the same sampling scheme improves the sample complexity of one-sided matrix completion, where the goal is to recover the left singular subspace of a matrix with many more columns than rows.