跳到正文
研踪PaperTrail
← 研踪 PaperTrail

arXiv:2602.05869 · v4

Wedge Sampling: Efficient Tensor Completion with Nearly-Linear Sample Complexity

首次提交 2026-02-06 00:47
版本更新 2026-11-19 04:19
雷达观测 2026-11-21 12:18
arXiv ↗PDF ↗

摘要

We introduce wedge sampling, a non-adaptive sampling scheme for recovering an order-kk low-rank tensor of side length nn 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 nn. The spectral initializer can be combined with existing refinement procedures using only an additional O~(n)\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 O~(nk/2)\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.

作者备注:87 pages, 5 figures. Includes sharpened noiseless guarantees

AI 论文解读

基于摘要 · 非全文审阅

此版本尚未生成 AI 解读。解读由后台任务生成并按论文版本保存,登录后共享已有结果。

版本差异

本站首次收录为 v4,暂无更早版本可对照。

观测到的版本

相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。

v4 · 2026-11-19 04:19 · 最新观测版本

Wedge Sampling: Efficient Tensor Completion with Nearly-Linear Sample Complexity

We introduce wedge sampling, a non-adaptive sampling scheme for recovering an order-kk low-rank tensor of side length nn 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 nn. The spectral initializer can be combined with existing refinement procedures using only an additional O~(n)\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 O~(nk/2)\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.

查看此版本解读 →查看此版本原文 ↗