{"id":"arxiv/2602.05869","url":"https://arxiv.org/abs/2602.05869","tags":["stat.ML","cs.LG","math.NA","math.PR","math.ST"],"score":0,"title":"Wedge Sampling: Efficient Tensor Completion with Nearly-Linear Sample Complexity","domain":"stat.ML","source":"arxiv","authors":["Hengrui Luo","Anna Ma","Ludovic Stephan","Yizhe Zhu"],"reviews":0,"subject":"stat.ML","summary":"We introduce Wedge Sampling, a new non-adaptive sampling scheme for low-rank tensor completion. We study recovery of an order-$k$ low-rank tensor of dimension $n\\times\\cdots\\times n$ from structured observations of its entries. Unlike the standard uniform entry model (i.e., i.i.d. samples from $[n]^k$), wedge sampling allocates observations to structured length-two patterns (wedges) in an associated bipartite sampling graph. By directly promoting these length-two connections, the sampling design strengthens the spectral signal that underlies efficient initialization, in regimes where uniform…","category":"research","comments":0,"disputed":false,"division":"stat","mentions":0,"discussed":0,"published":"2026-02-05","reactions":{}}