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

arXiv:2602.05869v3 Announce Type: replace-cross Abstract: 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 sampling is too sparse to generate enough informative correlations. Our main result shows that this change in sampling paradigm enables polynomial-time algorithms to achieve both weak and exact recovery with nearly linear sample complexity in $n$. The approach is also plug-and-play: wedge-sampling-based spectral initialization can be combined with existing refinement procedures (e.g., spectral or gradient-based methods) using only an additional $\tilde O(n)$ uniformly sampled entries, substantially improving over the $\tilde O(n^{k/2})$ sample complexity typically required under uniform entry sampling for efficient methods. We also formulate a noisy wedge-sampling extension for additive Gaussian observations and analyze both the spectral and gradient-descent procedures under suitable signal-to-noise conditions. Thus, the computational barrier in tensor completion is sensitive to the observation model: while it persists under uniform entry sampling, it can be bypassed by non-adaptive structured designs that provide a stronger initialization.

Abstract: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 sampling is too sparse to generate enough informative correlations. Our main result shows that this change in sampling paradigm enables polynomial-time algorithms to achieve both weak and exact recovery with nearly linear sample complexity in $n$. The approach is also plug-and-play: wedge-sampling-based spectral initialization can be combined with existing refinement procedures (e.g., spectral or gradient-based methods) using only an additional $\tilde O(n)$ uniformly sampled entries, substantially improving over the $\tilde O(n^{k/2})$ sample complexity typically required under uniform entry sampling for efficient methods. We also formulate a noisy wedge-sampling extension for additive Gaussian observations and analyze both the spectral and gradient-descent procedures under suitable signal-to-noise conditions. Thus, the computational barrier in tensor completion is sensitive to the observation model: while it persists under uniform entry sampling, it can be bypassed by non-adaptive structured designs that provide a stronger initialization.

88 pages, 5 figures. Includes new results on noisy tensor completion

Machine Learning (stat.ML); Machine Learning (cs.LG); Numerical Analysis (math.NA); Probability (math.PR); Statistics Theory (math.ST)

arXiv:2602.05869 [stat.ML]

(or arXiv:2602.05869v3 [stat.ML] for this version)

https://doi.org/10.48550/arXiv.2602.05869 Focus to learn more arXiv-issued DOI via DataCite

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.

analiza aiqbench

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

Subiecte conexe