AI & ML
Wedge Sampling: Efficient Tensor Completion with Nearly-Linear Sample Complexity
arXiv stat.ML0 views
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.
Source:https://arxiv.org/abs/2602.05869PreviousAnytime-Valid Conformal Risk ControlNextContinuous-time learning of probability distributions: a case study in a digital trial of young children with type 1 diabetes
Related posts

Serving Qwen3.5-0.8B with a 0.016% weight edit: measure the loops, pin the sampling on the server
0dev.to
Design Tokens for AI: Extract a Website's Real Colours, Fonts, Shadows and Icons So an LLM Builds On Brand
0dev.to
Trying to get our Arms around AI efficiency
0Stack Overflow Blog
Why an Embedded Game Fails on Some Phones, and How to Debug It
0dev.to
Microsoft 365 vs Office 2024: The Break-Even Math
0dev.to
Master AI Evals: Build Reliable, Scalable Model Evaluation Pipelines
0dev.to