REVIEW 2 major objections 3 minor 1 cited by
Wedge Sampling: Efficient Tensor Completion with Nearly-Linear Sample Complexity
T0 review · 2 major / 3 minor · reviewed 2026-08-03 · deepseek-v4-flash
Pith's one-line read A change of sampling scheme — observing length-two wedges rather than single entries — lets polynomial-time algorithms complete low-rank tensors from nearly linear samples, overturning the uniform-sampling barrier.
desk verdict Wedge sampling is a real new idea and the spectral-method results look solid, but the exact-recovery proof (Thm 8) has a load-bearing gap: the leave-one-out estimator in Appendix D.1 is not the wedge estimator. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The wedge estimator: from the wedge set W = {(i,ℓ,j) : 1≤i≤j≤n, ℓ∈[n^{k-1}]}, each triple is kept with probability p and contributes p^{-1} A_iℓ A_jℓ to the (i,j) and (j,i) entries of Z. Because every sampled wedge observes both A_iℓ and A_jℓ, E[Z] = AA^T; incoherence bounds on A make the summands small and independent, so matrix Bernstein concentration holds at roughly n log n samples. A second load-bearing tool is the δ-incoherent tensor norm — a restricted spectral norm that allows only delocalized rank-one test tensors — which gives concentration of sparse random tensors down to sampling rate n^{-(k-1)} and makes the gradient-descent landscape locally strongly convex.
What would settle it
Take T = e_1 ⊗ e_1 ⊗ e_1 for large n, a rank-one tensor with a spiky factor, and run the proposed wedge sampler at the theorem's rate p = Θ(log n/n^3). The only nonzero entry is at (1,1,1); the number of sampled wedges involving the column (1,1) is Bin(n,p), with mean Θ(log n/n^2), so with high probability none are sampled, Z = 0, and the algorithm cannot recover T. This confirms that incoherence is necessary.
Extended reading notes
Core claim
The central claim is that initialization, not refinement, is the bottleneck in efficient tensor completion, and that spending the sampling budget on length-two patterns fixes it. For the mode-1 unfolding A = unfold(T) in R^{n×n^{k-1}}, wedge sampling reveals A_iℓ and A_jℓ together for each sampled triple (i,ℓ,j), then forms a symmetric matrix Z whose expectation is exactly AA^T. The paper proves that Z concentrates around AA^T in operator norm from O(n log n) wedge samples under standard incoherence, and that the top-r eigenvectors recover the left singular subspace with an ℓ_{2,∞}-norm guarantee. These bounds feed a two-stage algorithm: the wedge-based subspace estimate is projected onto a
Load-bearing premise
The tensor must be incoherent in every mode unfolding: no singular-vector factor may concentrate on a few coordinates (informally, each row of the singular matrices has squared norm at most about r/n times a constant). If a factor is spiky, the wedge estimator does not concentrate and the nearly-linear guarantees collapse.
Editorial extensions
If this is right
- Order-k symmetric tensors can be weakly recovered by a polynomial-time spectral method from O(n log n) wedge samples plus O(log n) uniform samples.
- Order-3 CP tensors with incoherent factors can be exactly recovered by wedge-initialized gradient descent from O~(n) total samples.
- For one-sided matrix completion of an n×m matrix, the left singular subspace is recoverable from O~(n) wedge samples, independent of m.
- Existing spectral or gradient refinement procedures can be reused unchanged: only the initialization sampling needs to change.
- The conjectured n^{k/2} sample complexity for efficient tensor completion under uniform sampling is shown to be an artifact of that sampling model.
Reading between the lines
- If the uniform-sampling barrier is indeed an artifact, other non-adaptive designs that make the row graph well connected at near-linear cost — for example entries arranged along random cycles or expander-like patterns — should also bypass the barrier; this is an extrapolation, not proven in the paper.
- For tensors with spiky factors, one could imagine a hybrid design that spends a small wedge budget to detect high-variance coordinates and then concentrates samples there; the paper does not analyze such adaptivity.
- The leave-one-out and δ-incoherent-norm machinery may transfer to sparse hypergraph community detection, where the same wedge-walk statistics arise; the paper does not discuss this connection.
- In practice wedge sampling assumes the sampler can choose which pairs of entries to reveal, which fits experimental or crowdsourced designs but not passive datasets where one only receives a fixed set of observed entries.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper introduces wedge sampling, a non-adaptive sampling scheme for low-rank tensor completion in which the sampler observes pairs of entries sharing a common index (wedges). The authors prove concentration and subspace-recovery guarantees for the resulting wedge matrix (Theorems 5 and 6), and use this as a spectral initializer for two algorithms: a spectral denoising method (Algorithm 2, Theorem 7) and a gradient-descent refinement in the style of Cai et al. (Algorithm 3, Theorem 8). They claim O~(n) sample complexity for both weak and exact recovery of order-k tensors, versus O~(n^{k/2}) under uniform entry sampling, and argue that the statistical-to-computational gap for tensor completion is largely an artifact of the uniform sampling model. Numerical experiments illustrate an advantage over uniform sampling for initialization.
Significance. If the proofs are completed, the paper makes a substantial contribution: one-sided matrix completion with O(n) observed entries under wedge sampling, and polynomial-time tensor completion with near-linear sample complexity via a simple, non-adaptive sampling design. The claim would give a concrete way around the conjectured uniform-sampling barrier. The paper is explicit about its assumptions, has no fitted parameters, and the main spectral concentration results are self-contained given standard inequalities. The numerical experiments are supportive but not the basis of the contribution. However, the exact-recovery proof (Theorem 8) has a load-bearing gap in its leave-one-out argument, so the strong claims are not yet fully supported.
major comments (2)
- [App. D.1, Prop. 31] The leave-one-out initializer \hat U^{(s)} is defined as the top singular space of p^{-1}\tilde T^{(s)}, where \tilde T^{(s)} is built from the uniform subsample \Omega with s-entries set to pT. This is not the wedge-sampling estimator from Algorithm 1/3, and Lemma 17 bounds the wedge leave-one-out matrix Z^{(s)}, not p^{-1}\tilde T^{(s)}. At the rate p \asymp \mu^7 r^4 \log^2 n / n^3, p^{-1}\tilde T^{(s)} has spiky O(n^3) entries on row/column s; no uniform-sampling spectral estimator of an n \times n^2 unfolding can recover U at this sparsity (uniform one-sided completion needs ~ n^{3/2} samples). Thus Prop. 31 is unsupported and likely false as stated. Since Prop. 31 feeds Lemma 35/36 and Cor. 41, the proof of Theorem 8 lacks a valid leave-one-out chain. A wedge-specific leave-one-out analysis (e.g., for Z^{(s)}) is required.
- [App. D.2, Lemma 36] The proof of Lemma 36 invokes Theorem 43 with \delta \equiv \|\hat u_\tau\|_\infty, a random quantity depending on the same data (\Omega and \hat U). Theorem 43 is stated and proved for a fixed \delta \in \prod_i [n_i^{-1/2},1]; no uniform-in-\delta or data-dependent-\delta argument is provided. This is a gap in the \ell_\infty / \ell_{2,\infty} leave-one-out estimate used for the extraction step. A bound with fixed deterministic \delta = \Theta(\sqrt{\mu/n}) and the same conclusion, or a union bound over a \delta-net, would repair it.
minor comments (3)
- [Sec. 1, one-sided matrix completion] The text says the wedge-sampling spectral method achieves O~(m) sample complexity (Theorem 6), but Theorem 6 and the surrounding discussion imply O~(n) observed entries; this is a typo and should be corrected.
- [Algorithm 1 / Thm. 6] The theorems are stated in terms of p, the wedge sampling rate, not the number of observed entries. Each sampled wedge reveals one or two entries. State explicitly that the observed-entry count is O(p n^2 m) (up to a factor of 2), so that the claimed O~(n) sample complexity is unambiguous.
- [App. D] Several propositions are justified by 'the same proof as [Cai et al., 2022]' or 'repeat the analysis of Lemma 17' without verifying that the hypotheses hold under wedge sampling. This is particularly important for the extraction step and the gradient-descent initialization; please expand the derivation or restate the precise conditions.
Circularity Check
No circular derivation: main claims rest on independent concentration and leave-one-out bounds; self-citations are background only. A non-circular proof gap exists in Prop. 31.
full rationale
After walking the derivation chain, I find no circular reduction. Algorithm 1 constructs Z with E[Z]=AA^T by design, but Theorem 5's concentration and Theorem 6's leave-one-out ℓ2,∞ bounds are nontrivial probabilistic statements; nothing is fitted and no claimed recovery rate is used as an assumption. Theorem 7 and Theorem 8 combine these with external refinement frameworks (Montanari-Sun 2018, Cai et al. 2022), and the sparse-regime concentration in Theorem 9 is proved in Appendix E rather than imported from the authors' own prior work. The self-citations (Stephan-Zhu 2024a/b, Zhou-Zhu, etc.) appear in the introduction and comparisons, not as load-bearing premises, and no uniqueness theorem or ansatz is smuggled through self-citation. I do flag a separate, non-circular gap: in Appendix D.1, Proposition 31 defines the leave-one-out initializer Uhat^{(s)} from p^{-1}^tilde T^{(s)}, a uniformly-subsampled tensor object, while Lemma 17's leave-one-out analysis concerns the wedge-sampling matrix Z; the sentence "we can repeat the analysis of Lemma 17" is an unsupported analogy. This is a missing proof step for Theorem 8, but it is not an instance of an output being equivalent to an input by construction, so it does not constitute circularity. The score 2 reflects only the presence of minor, non-load-bearing self-citations; the central derivation is independent.
Assumptions & free parameters
assumptions (3)
- domain assumption The completed tensor is (μ1, μ2)-incoherent in every mode unfolding (Definition 3) or μ-CP incoherent (Lemma 4).
- domain assumption Each wedge triple (i,ℓ,j) is sampled independently with probability p, and each pair of entries sharing ℓ is observed.
- standard math Matrix Bernstein inequality (Lemma 12), Davis-Kahan and Wedin perturbation theorems, and prior spectral/gradient refinement guarantees (Montanari-Sun 2018, Cai et al. 2022) hold as stated.
Cite this review
Pith. "Pith review of Wedge Sampling: Efficient Tensor Completion with Nearly-Linear Sample Complexity." pith.science (2026). https://pith.science/paper/2KVLNWOO
@misc{pith2026260205869,
author = {Pith},
title = {Pith review of: Wedge Sampling: Efficient Tensor Completion with Nearly-Linear Sample Complexity},
year = {2026},
howpublished = {\url{https://pith.science/paper/2KVLNWOO}},
note = {Machine review of arXiv:2602.05869}
}
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.
Figures
Forward citations
Cited by 1 Pith paper
-
Shrinkage priors for Bayesian Substitute Confounders
Bayesian shrinkage priors on factor models produce sparse substitute confounders that support consistent regression-adjusted causal estimates under latent variable identification assumptions.
Reviewed August 3, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.