{"id":"a5c54934-2e20-45e6-8575-69395a22bd88","arxiv_id":"2602.05869","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Wedge sampling gives polynomial-time low-rank tensor completion with nearly linear sample complexity O~(n), bypassing the O~(n^{k/2}) barrier of uniform entry sampling.","lead":"This paper introduces wedge sampling, a non-adaptive scheme that observes pairs of tensor entries sharing a coordinate, and proves that polynomial-time tensor completion then needs only ~n log n observed entries rather than ~n^{k/2}. If the proofs hold, the widely conjectured statistical-to-computational gap in tensor completion is an artifact of uniform entry sampling.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Exact-recovery proof (Thm 8) uses a leave-one-out spectral estimator defined from uniform sampling, not from wedge sampling; at the stated rates this estimator cannot be accurate, so Prop. 31 lacks support.","rationale":"The central claim — near-linear sample complexity for tensor completion under wedge sampling — is plausible and the matrix concentration arguments in Theorems 5–7 are detailed. However, the exact-recovery result (Theorem 8) is the other half of the headline claim, and its proof depends on a leave-one-out analysis in Section D.1. There, the auxiliary estimator \\hat U^{(s)} is defined from a uniformly subsampled tensor at rate p, whereas Algorithm 3 obtains its initializer from wedge sampling. At the rates used in Theorem 8 (p n^3 = polylog), no uniform-sampling spectral estimator can be accurate, so the stated Proposition 31 cannot be a consequence of the wedge-sampling Lemma 17. This is an internal inconsistency in the proof, not merely a disagreement with prior consensus. The reader's weakest_assumption focused on incoherence, which is a standard and necessary condition; I do not see it as the most load-bearing issue. I would keep the verdict CONDITIONAL: the paper should not be accepted without either correcting Proposition 31 or adding a genuine wedge-sampling leave-one-out proof. The concrete test — re-deriving the bound for the wedge leave-one-out matrix, or numerically testing the uniform estimator at the stated sparsity — would settle whether the gap is real.","tokens_in":45665,"tokens_out":37630,"duration_ms":374163,"concrete_test":"Re-derive Proposition 31 by constructing the leave-one-out wedge matrix Z^{(s)} (zero out row and column s of the wedge estimator Z) and bounding ||\\hat U\\hat U^T - \\hat U^{(s)}\\hat U^{(s)T}|| via Lemma 17. If this derivation does not reproduce the claimed bound, numerically evaluate the uniform estimator p^{-1}\\tilde T^{(s)} for n=10^3, p=1/n^3 (or polylog), rank r=1; its subspace error will be ~1, contradicting Proposition 31's claimed O(1/√n) bound.","verdict_should_be":"UNCHANGED","load_bearing_attack":"In Appendix D.1, Proposition 31 defines the leave-one-out initializer \\hat U^{(s)} as the top singular space of p^{-1}\\tilde T^{(s)}, where \\tilde T^{(s)} is a uniformly subsampled tensor (entries involving s are set to pT; other entries from Ω are set to T). This is not the wedge-sampling estimator used in Algorithm 3. For the rates in Theorem 8, p ≈ μ^7 r^4 log^2 n / n^3, so p n^3 = O(polylog); no uniform-sampling spectral estimator of an n × n^2 unfolding can recover U with the claimed error at this sparsity — uniform one-sided matrix completion requires ~ n^{3/2} samples. Proposition 31 therefore cannot follow from Lemma 17, which is a wedge-sampling leave-one-out bound, and the subsequent leave-one-out bounds for extraction (Prop. 33) and initialization (Cor. 41) are not tied to the actual wedge initializer. Unless a wedge-specific leave-one-out analysis is supplied, Theorem 8, the main exact-recovery result, has a missing proof step.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":45961,"tokens_out":10513,"duration_ms":104360,"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":[{"comment":"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.","section":"App. D.1, Prop. 31"},{"comment":"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.","section":"App. D.2, Lemma 36"}],"minor_comments":[{"comment":"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.","section":"Sec. 1, one-sided matrix completion"},{"comment":"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.","section":"Algorithm 1 / Thm. 6"},{"comment":"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.","section":"App. D"}],"recommendation":"major_revision","confidential_remarks":"The central idea is interesting and the weak-recovery part (Theorems 5--7) appears solid. The exact-recovery proof of Theorem 8 has a genuine gap: Proposition 31 uses the wrong leave-one-out object, and the random-\\delta use of Theorem 43 is not justified. If the authors can supply a wedge-specific leave-one-out analysis and fix the \\delta issue, the paper would likely be publishable. I do not recommend rejection because the missing step is a proof gap, not a demonstrated counterexample to the main claim."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The thing to know up front: the wedge-sampling idea is genuinely new, and Theorems 5–7 look like real contributions. But Theorem 8's proof, as written, has a serious gap in the leave-one-out analysis.\n\nThe stress-test is right. In Appendix D.1, Proposition 31 defines \\hat U^{(s)} as the top singular space of p^{-1}\\tilde T^{(s)}, where \\tilde T^{(s)} is a uniformly subsampled tensor with a full slice set to pT. That is not the wedge matrix Z from Algorithm 1, so Lemma 17's wedge leave-one-out bound cannot be applied to it. At the stated rates, p n^3 is polylogarithmic, and no uniform-sampling spectral estimator of an n-by-n^2 unfolding can recover the left singular subspace with that little information. Proposition 31 is therefore unsupported, and the later leave-one-out steps (Prop. 33 and Cor. 41) inherit the problem. Theorem 8 may be true, but the proof as written does not establish it. This needs a proper wedge-specific leave-one-out analysis, not a sentence saying the previous argument repeats.\n\nWhat is genuinely good: the sampling scheme is clever and non-adaptive; Theorem 5 gives concentration of the wedge matrix; Theorem 6 provides ℓ_{2,∞} subspace recovery with near-linear samples for one-sided matrix completion; Theorem 7 gives a clean spectral tensor completion bound; Theorem 9's incoherent-norm concentration is new and likely useful. The framing of the Barak–Moitra gap as an artifact of uniform sampling is thought-provoking, and the paper is honest that spiky tensors break the approach. The appendix is serious, though not machine-checked.\n\nMinor issues: the introduction says \"O~(m)\" for one-sided completion while Theorem 6 implies O~(n) observed entries; that looks like a typo. The experiments have no error bars and use small n, but that is a minor concern.\n\nBottom line: this paper deserves peer review. The wedge-sampling idea and Theorem 7 are significant enough to warrant referee time. But I would not cite Theorem 8 until the leave-one-out gap is fixed. A referee should focus on Appendix D.1.","headline":"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.","tokens_in":46415,"tokens_out":6588,"would_cite":false,"duration_ms":68701,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["15A69","60B20","62H12"],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["tensor completion","wedge sampling","low-rank tensor","spectral initialization","sample complexity","one-sided matrix completion","incoherence","statistical-to-computational gap"],"falsifier":"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.","tokens_in":45598,"feed_emoji":"📐","tokens_out":6460,"duration_ms":68710,"temperature":0.7,"pith_summary":"The paper sets out to establish that the sample barrier for polynomial-time tensor completion — roughly n^{k/2} observations under uniform entry sampling — disappears when observations are drawn as 'wedges': pairs of entries that share a common index. It introduces a non-adaptive wedge-sampling scheme and proves that the resulting spectral estimator concentrates around the second-moment matrix of the unfolded tensor with only O(n log n) samples, provided the tensor is incoherent. From that initialization, the paper shows both weak recovery by spectral denoising and exact recovery by gradient descent, with total sample complexity O~(n) rather than O~(n^{k/2}). A sympathetic reader would care because the result suggests the widely believed statistical-to-computational gap in tensor completion is an artifact of uniform sampling, not an intrinsic algorithmic obstruction, and because the initialization is plug-and-play with existing refinement methods. The guarantees also improve one-sided matrix completion, recovering the left singular subspace of an n×m matrix from O~(n) samples.","feed_headline":"Nearly linear samples finish low-rank tensor completion","feed_subtitle":"Sampling length-two wedges instead of single entries powers spectral initialization and bypasses the uniform-sampling barrier.","key_machinery":"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.","core_discovery":"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","pith_inferences":["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."],"forward_implications":["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."],"fun_headline_variants":["Wedge sampling cracks tensor completion with nearly linear samples","Length-two wedges beat uniform sampling for tensor recovery","Tensor completion: wedge sampling hits nearly linear complexity","New wedge sampling scheme outruns uniform entry sampling","Wedge sampling: efficient tensor completion from fewer entries"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Wedge sampling cracks tensor completion with nearly linear samples","Length-two wedges beat uniform sampling for tensor recovery","Tensor completion: wedge sampling hits nearly linear complexity","New wedge sampling scheme outruns uniform entry sampling","Wedge sampling: efficient tensor completion from fewer entries"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000729,"raw_usage":{"total_tokens":3131,"prompt_tokens":802,"completion_tokens":2329,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":546,"completion_tokens_details":{"reasoning_tokens":2254}},"tokens_in":546,"tokens_out":2329,"duration_ms":16317,"temperature":1.0,"reasoning_tokens":2254,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-03T04:04:29.017372+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[],"review_version":1}