{"id":"0cf139e3-1399-4f86-81fc-7a9df13d5e7a","arxiv_id":"2502.09534","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A lifting trick plus an approximate Richardson analysis turns fast tensor-decomposition algorithms into sublinear-per-round tensor-completion algorithms with a (1+O(1))-approximation guarantee.","lead":"This paper converts tensor completion, the problem of filling missing entries in a multidimensional array, into a structured regression that fast tensor-decomposition algorithms can solve. The method comes with convergence guarantees and reports 100x speedups on real-world datasets.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Sublinear-time claim depends on small beta and b_epsilon < 1/beta^2; the CP speedup is measured with exact mini-ALS, not the approximate-mini-ALS the theory justifies.","rationale":"The reader's weakest_assumption correctly identifies the spectral upper bound as the load-bearing point. My reading of the proof of Theorem 3.7 found no algebraic error: the recurrence in Section B.4 is valid, and the final error bound follows from the induction with alpha = 1 - 1/beta + sqrt(b_epsilon). The issue is not internal inconsistency but whether the condition A^T A ⪯ beta P^T P is actually satisfied with a moderate beta in the intended use. The paper's two supporting arguments are (i) Cohen et al.'s uniform-sampling bound with beta = 2/p and (ii) empirical speedups. (i) is only as good as the incoherence of the evolving ALS design matrices, which is not shown; (ii) uses b_epsilon = 0 mini-ALS and so does not exercise the theorem's approximate regime. Because the reader's CONDITIONAL verdict already flags this gap and asks for verification, my stress-test does not move the verdict; it sharpens the condition to a concrete reproducibility check and notes a possible missing beta factor in Corollary 4.1. If the check fails, the central claim would need to be weakened to exact-mini-ALS speedups plus a conditional sublinear guarantee under verified incoherence.","tokens_in":21222,"tokens_out":28107,"duration_ms":272466,"concrete_test":"Re-run the CARDIAC-MRI and HYPERSPECTRAL CP experiments (Section 5.2, p=0.1, R=16) using approximate-mini-als with leverage-score sampling, at both the theory-prescribed b_epsilon = eps1/beta^2 and at a practical fixed sampling rate, and record total wall-clock time and train/test RRE over 10 ALS rounds. At the same time, compute beta_t = lambda_max((P_t^T P_t)^{-1/2} A_t^T A_t (P_t^T P_t)^{-1/2}) after each ALS step. If approximate-mini-als does not attain the same RRE as mini-als, or if its time exceeds direct while beta_t is far above 2/p, then the sublinear-time guarantee and the 100x speedup claim are not supported for the proposed approximate method.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim is Theorem 3.7, and its efficiency hinges on the spectral ratio beta in eP^T eP ⪯ A^T A ⪯ beta eP^T eP. Section 3.3 derives beta = 2/p from uniform random row selection plus an incoherence condition on the lifted design matrix A, citing Cohen et al. (2015, Lemma 4). Two things are load-bearing. First, in each ALS step A is a Khatri-Rao/Kronecker/TT-structured matrix built from the current factor matrices; the paper does not establish that these evolving matrices remain coherent with a small parameter as ALS progresses, and the suggested ridge-regularization fix is not analyzed for Theorem 3.7. For high-order tensors or non-uniform missing patterns, beta can be much larger than 2/p, and if an unobserved direction exists then P^T P is singular and no finite beta exists. Second, when beta is large the requirement b_epsilon < 1/beta^2 forces very small inner-solve errors; leverage-score sampling needs at least O(R/b_epsilon) or O(R/b_epsilon^2) samples per solve, and Theorem 3.7's iteration count scales with beta. Combining these gives a total cost polynomial in beta with an extra factor beyond the stated Corollaries (e.g., Corollary 4.1 states beta^2/eps1 while Theorem 3.7's beta iterations times T ~ beta^2/eps1 yields beta^3/eps1). The CP experiments do not test this regime: they compare direct, parafac, mini-als (b_epsilon = 0), and accelerated-mini-als, while approximate-mini-als with actual leverage-score sampling appears only in the coupled-matrix warm-up. Thus the reported 100x speedup is evidence for exact mini-ALS, not for the sublinear approximate method that Theorem 3.7 is meant to justify.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes a lifting method for tensor completion (TC) least-squares subproblems. Instead of solving the masked regression min_x ||Px - q||^2 directly, it introduces the unobserved entries as free variables, obtaining min_x,b ||Ax - b||^2 with a structured full design matrix A. The alternating minimization over x and the missing entries is shown to be equivalent to a preconditioned Richardson iteration (Lemma 3.5). The main theoretical result, Theorem 3.7, gives a convergence guarantee for an approximate version of this iteration, where each structured regression is solved only to multiplicative error (1 + b_epsilon). This is then combined with leverage-score sampling algorithms for CP, Tucker, and tensor-train decompositions to obtain sampling-based TC algorithms. Experiments on a coupled matrix problem and on CP completion of real-world tensors are reported.","tokens_in":21549,"tokens_out":10049,"duration_ms":103435,"significance":"If the main theorem is correct, the paper makes a useful conceptual contribution: it gives a principled way to convert an unstructured TC regression into a sequence of structured TD regressions, so that future fast TD solvers can be plugged into TC. The proof of Theorem 3.7 is self-contained and the iteration count is consistent with the contraction rate up to the stated constants. The paper also releases code and tests the lifting idea on real-world tensors, and the exact-mini-ALS variant shows substantial speedups over direct solves. The main caveats are that the spectral-ratio assumption beta is not shown to hold for the evolving ALS matrices, that the CP running-time corollary appears to miss a factor of beta, and that the CP experiments do not exercise the approximate-mini-ALS with leverage-score sampling that the theory is designed to justify.","major_comments":[{"comment":"The sublinear-time claim depends on the existence of a small spectral ratio beta satisfying eP^T eP <= A^T A <= beta eP^T eP. The paragraph in Section 3.3 derives beta = 2/p from uniform row sampling and an incoherence condition on A, but A is built from the current ALS factor matrices and changes at every outer iteration. The paper does not prove that these evolving Khatri-Rao, Kronecker, or TT-structured matrices remain coherent with a controlled parameter, nor does it handle the case where an entire direction is unobserved, in which case P^T P is singular and no finite beta exists. The ridge-regularization fix mentioned in the same paragraph is not analyzed for Theorem 3.7. A concrete test would be to track the empirical beta (or the leverage scores) over ALS iterations in the experiments; without this, the statement that beta = O(1) is an assumption rather than a derived consequence.","section":"Section 3.3, 'Bounding beta'"},{"comment":"The claimed CP completion running time appears to be off by a factor of beta. The text before Eq. (10) sets b_epsilon = Theta(epsilon_1 / beta^2), so each approximate structured regression costs T_{b_epsilon} = O~(beta^2 / epsilon_1 * sum_n (I_n R^2 + N R^3)). Theorem 3.7 then requires O(beta / (1 - sqrt(b_epsilon) beta)) = O(beta) Richardson iterations per factor update, giving a total of O~(beta^3 / epsilon_1 * sum_n (I_n R^2 + N R^3) log(1/epsilon_2)) for one round, not the stated O~(beta^2 / epsilon_1 ...). If 'one round' is intended to mean something different, the terminology should be clarified; otherwise the corollary should be corrected. The corrected bound is still sublinear in |Omega|, but the advertised exponent changes.","section":"Section 4.1, Corollary 4.1"},{"comment":"The CP experiments compare direct, parafac, mini-als, and accelerated-mini-als, where mini-als and accelerated-mini-als use exact inner solves (b_epsilon = 0). The approximate-mini-ALS algorithm with actual leverage-score sampling, which is the algorithm needed to realize the sublinear-time guarantee of Theorem 3.7, appears only in the coupled-matrix warm-up of Section 5.1. Consequently, the reported 100x speedup for CP completion on real-world tensors validates the lifting/Richardson idea but not the sampling-based approximate method that is the paper's principal theoretical contribution. Adding CP experiments with approximate-mini-ALS, or qualifying the empirical claim, is needed.","section":"Section 5.2, CP completion experiments"},{"comment":"Theorem 3.7 requires b_epsilon < 1/beta^2 and the iteration count grows linearly with beta. The paragraph on bounding beta does not discuss the interaction between the observation rate p and this requirement: for small p, beta = 2/p is large, and the inner solver must be extremely accurate, which increases the sampling cost through the 1/b_epsilon factor. The paper should state explicitly that the sublinear-time guarantee degrades polynomially in beta and should give the resulting total cost as a function of p, not only of the fixed parameters R and epsilon_1.","section":"Section 3.3, spectral condition and Theorem 3.7"}],"minor_comments":[{"comment":"The loop bound in Algorithm 1 and the time expression in Theorem 3.7 use two equivalent forms of the iteration count; please align the notation so the reader can easily match the pseudocode to the theorem.","section":"Theorem 3.7 / Algorithm 1"},{"comment":"The text says 'Applying Bharadwaj et al. (2023, Corollary 3.3), one round of ALS runs in time O~(epsilon^{-1} sum(...))' but does not state which epsilon parameter of that corollary is being used and how it maps to b_epsilon; making this mapping explicit would help verify Corollary 4.1.","section":"Section 4.1, CP completion"},{"comment":"The warm-up reports that approximate-mini-als samples 1% of rows per iteration, but it does not report the failure probability or the number of trials for the stochastic variant; adding this information would strengthen the comparison.","section":"Section 5.1, coupled matrix problem"},{"comment":"The figure captions do not specify the exact epsilon values used for the mini-als and accelerated-mini-als curves, nor whether the reported times include the cost of computing the full tensor or only observed entries; these details are needed to interpret the '100x faster' claim.","section":"Section 5.2, experiments"},{"comment":"The sentence about alpha zeta^2-ridge leverage scores is telegraphic; it should state how alpha is chosen from the observation rate p and how the regularization term is incorporated into the lifted problem (5).","section":"Section 3.3, 'Bounding beta'"}],"recommendation":"major_revision","confidential_remarks":"The paper is within scope for a theory/systems venue and the central Richardson-equivalence idea is sound. My main reservations are the unproven spectral-ratio assumption for evolving ALS matrices, the apparent missing beta factor in Corollary 4.1, and the gap between the theoretical algorithm and the CP experiments. These are fixable within the manuscript's scope, so I recommend major revision rather than rejection."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nThe paper is worth reading. The clean observation is that the old lifting trick for missing-data regression, iterated to convergence, is exactly preconditioned Richardson iteration (Lemma 3.5). That equivalence is new and clearly stated, and the approximate-error analysis (Theorem 3.7) is the right abstraction: it tells you how accurate the inner structured solver must be so the outer iteration still converges. I believe the theorem is correct; the proof splits the error into a contraction term and a noise term, and the iteration count matches the contraction rate. The CP, Tucker, and TT corollaries are straightforward applications of existing fast TD ALS algorithms as blackboxes.\n\nThe soft spots are real but not fatal. First, Corollary 4.1 reports a per-round complexity of O~(β^2/ε1 · Σ(...)). But using their own setting bε=Θ(ε1/β^2), and that the inner solve time T scales as 1/bε, Theorem 3.7 gives β iterations times T, which is β^3/ε1, not β^2/ε1. There is a missing factor of β. This does not kill the sublinear-time claim, but it should be corrected.\n\nSecond, the spectral condition eP^T eP ⪯ A^T A ⪯ β eP^T eP is load-bearing. The paper justifies it only for a fixed A under incoherence and uniform random observations, giving β=2/p. In ALS, A changes every iteration, and the paper does not prove that incoherence propagates. The ridge-regularization fix is mentioned but not analyzed. So the theory is conditional on an assumption that is not shown to hold dynamically.\n\nThird, the headline 100x speedup is for exact mini-ALS (bε=0) and an accelerated variant. Approximate-mini-ALS with actual row sampling appears only in the coupled-matrix warm-up. So the sublinear-time method is not demonstrated on the real tensors; the experiments support the structured-solver speedup, not the sampling speedup.\n\nOverall, the central idea is solid and Theorem 3.7 is a genuine contribution. The missing β factor and the dynamic incoherence gap are fixable in revision, and the experiment/theory mismatch should be explicitly acknowledged. I would send this to a serious referee; it deserves a careful read.\n\nRecommendation: engage with the paper, but require a revision that fixes the complexity statement and clarifies the spectral condition.","headline":"Genuinely new theoretical framework for tensor completion, but the claimed running time has a missing β factor and the experiments test the exact solver, not the sublinear approximate one.","tokens_in":22146,"tokens_out":5755,"would_cite":true,"duration_ms":54223,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["15A69","65F10","68W20"],"pacs":[],"model":"deepseek-v4-flash","headline":"Tensor completion can be made fast by lifting the problem so that missing entries become free variables, then solving via approximate Richardson iteration with fast tensor-decomposition solvers as black boxes.","keywords":["tensor completion","tensor decomposition","alternating least squares","Richardson iteration","leverage score sampling","Kronecker regression","Khatri-Rao product","sublinear-time algorithm"],"falsifier":"Construct a rank-$R$ tensor with a missing pattern that is not uniformly random, for instance observing only entries in a small set of slices or fibers, compute $\\mathbf{P}^\\top\\mathbf{P}$ and $\\mathbf{A}^\\top\\mathbf{A}$, and measure the iteration count of approximate-mini-ALS; the theorem predicts iteration count growing linearly in $\\beta/(1-\\sqrt{\\hat\\varepsilon}\\,\\beta)$, so a demonstration where measured iterations grow faster than $\\beta$, or where leverage-score sampling with $\\hat\\varepsilon < 1/\\beta^2$ fails to produce a $(1+\\hat\\varepsilon)$-optimal inner solve, would falsify the central convergence claim.","tokens_in":1917,"feed_emoji":"🧩","tokens_out":1969,"duration_ms":69694,"temperature":0.7,"pith_summary":"This paper argues that tensor completion is slow because the partially observed design matrix loses the Kronecker, Khatri-Rao, or tensor-train structure that makes tensor decomposition fast, and that this obstacle can be removed by a lifting trick. The unobserved entries are treated as free variables, restoring the full structured matrix, and the lifted least-squares problem is solved by alternating between filling in missing values and running a fast structured regression solver. The authors prove that this alternation is exactly a preconditioned Richardson iteration on the original problem, and that running the inner regression approximately with leverage-score sampling still converges at essentially the same rate provided a spectral ratio is small and the inner solver error is below a threshold. The payoff is concrete: CP, Tucker, and tensor-train completion algorithms whose per-round cost is sublinear in the number of observed entries, with empirical 100x speedups over direct ALS on real tensors.","feed_headline":"Missing entries become free variables to make tensor completion fast","feed_subtitle":"Reuses fast tensor-decomposition solvers, hitting 100x speedups on CP completion.","key_machinery":"The machinery is the lifted problem plus the mini-ALS iteration: with $\\mathbf{A}$ the full structured design matrix and $\\mathbf{P}$ the row-restricted observed matrix, each outer step sets $\\hat{\\mathbf{q}}^{(k)} = \\hat{\\mathbf{q}} + (\\mathbf{A} - \\tilde{\\mathbf{P}})\\mathbf{x}^{(k)}$ and then approximately solves $\\min_{\\mathbf{x}} \\|\\mathbf{A}\\mathbf{x} - \\hat{\\mathbf{q}}^{(k)}\\|^2$ using a fast tensor-decomposition solver. The identity carrying the argument is Lemma 3.5: this alternation is exactly Richardson iteration preconditioned by $\\mathbf{A}^\\top\\mathbf{A}$ on the original regression. The convergence engine is the spectral sandwich $\\mathbf{P}^\\top\\mathbf{P} \\preceq \\mathbf{A}^\\top\\mathbf{A} \\preceq \\beta \\mathbf{P}^\\top\\mathbf{P}$ together with the inner-solver tolerance $\\hat\\varepsilon < 1/\\beta^2$, which says how much approximation error the outer iteration can absorb before the speedup degrades.","core_discovery":"The paper establishes that the unstructured least-squares problems arising in ALS for tensor completion can be solved by solving a larger, structured problem instead. Lifting introduces the missing entries as free response variables, so the design matrix becomes the same Kronecker, Khatri-Rao, or tensor-train product matrix as in the fully observed decomposition problem, and the original solution is recovered exactly (Lemma 3.1). Alternating minimization on the lifted problem, called mini-ALS, is shown in Lemma 3.5 to reproduce the preconditioned Richardson iteration for the original regression. The main theorem, Theorem 3.7, quantifies the permitted sloppiness: if the observed design $\\mathbf{P}$ satisfies $\\mathbf{P}^\\top\\mathbf{P} \\preceq \\mathbf{A}^\\top\\mathbf{A} \\preceq \\beta \\mathbf{P}^\\top\\mathbf{P}$ and the inner structured solver returns a $(1+\\hat\\varepsilon)$-approximate solution with $\\hat\\varepsilon < 1/\\beta^2$, then the outer loop reaches relative error $1 + O(\\hat\\varepsilon/\\beta^2)$ plus an $\\varepsilon$-term in $O\\!\\left(\\frac{\\beta}{1-\\sqrt{\\hat\\varepsilon}\\,\\beta} \\cdot T \\log(\\beta/\\varepsilon)\\right)$ time. Under uniform random observation and an incoherence condition, $\\beta = 2/p$, yielding CP, Tucker, and TT completion algorithms whose per-round cost is sublinear in the number of observed entries and, on the paper's CP experiments, roughly 100x faster than direct ALS.","pith_inferences":["Editorial: the same lifting-plus-approximate-Richardson wrapper should apply to any tensor-network decomposition with a sampling-based ALS solver, such as tensor ring, tensor wheel, or t-SVD, even though the paper only works out CP, Tucker, and TT.","Editorial: the acceleration heuristic, which extrapolates collinear iterates by a geometric series, is essentially heavy-ball momentum for a convex quadratic; a provable momentum variant may exist, and the paper leaves the analysis of the speedup open.","Editorial: a direct experimental test of the theory would measure the ratio $\\beta$ from the observed mask and factors and check the predicted iteration count; the reported speedups on random masks suggest $\\beta$ is small when missingness is benign.","Editorial: treating missing values as free variables connects tensor completion to missing-data imputation; the paper's guarantee shows when iterative imputation is safe, but adversarial missingness remains the practical danger zone where the spectral condition fails."],"forward_implications":["Every sampling-based fast TD ALS algorithm becomes a tensor-completion algorithm, so future improvements in TD solvers transfer to completion automatically.","The per-round cost for CP, Tucker, and TT completion is independent of $|\\Omega|$, giving sublinear-time ALS updates in the number of observed entries.","A smaller sample ratio $p$ means a larger $\\beta$ and more outer iterations, while $p \\to 1$ drives $\\beta \\to 1$ and the method reduces to ordinary fast tensor decomposition.","The Tomasi-Bro imputation method is recovered as a single mini-ALS step; running the loop to convergence, as here, gives Richardson-type guarantees rather than uncontrolled EM drift.","The required inner tolerance $\\hat\\varepsilon < 1/\\beta^2$ is an explicit accuracy budget, quantifying when leverage-score sampling is safe to use as a blackbox."],"supporting_citations":[{"why":"Origin of the lifting idea: treating missing values as free parameters in least-squares problems.","marker":"Healy & Westmacott (1956)"},{"why":"Supplies the spectral approximation bound that gives $\\beta = 2/p$ under uniform row sampling and incoherence.","marker":"Cohen et al. (2015, Lemma 4)"},{"why":"States the preconditioned Richardson iteration contraction used as the exact-iteration baseline in Lemma 3.4.","marker":"Lee & Vempala (2024, Lemma 6.1)"},{"why":"Fast exact leverage-score sampling for Khatri-Rao products; the CP inner solver in Corollary 4.1.","marker":"Bharadwaj et al. (2023)"},{"why":"Subquadratic Kronecker regression algorithms; the Tucker core and factor update solvers in Corollaries 4.2 and 4.3.","marker":"Fahrbach et al. (2022)"},{"why":"Leverage-score sampling for tensor-train cores; the TT inner solver in Corollary 4.4.","marker":"Bharadwaj et al. (2024)"},{"why":"The one-iteration EM-style PARAFAC completion baseline that mini-ALS generalizes.","marker":"Tomasi & Bro (2005)"}],"fun_headline_variants":["Lifting missing entries makes tensor completion 100x faster","Free variables unlock fast tensor-decomposition solvers","Sublinear tensor completion via approximate Richardson","Mini-ALS: reuse structured solvers for 100x speedup","Tensor completion: lift, solve, and speed up 100x"],"cache_read_input_tokens":24192,"weakest_assumption_plain":"The whole speed guarantee rests on the observed rows giving a good spectral approximation of the full tensor's design matrix; if missing data is adversarial or concentrated where the factors are small, the ratio $\\beta$ is large and the inner solver must be so accurate that the sublinear-time guarantee collapses.","fun_headline_variants_meta":{"raw":{"variants":["Lifting missing entries makes tensor completion 100x faster","Free variables unlock fast tensor-decomposition solvers","Sublinear tensor completion via approximate Richardson","Mini-ALS: reuse structured solvers for 100x speedup","Tensor completion: lift, solve, and speed up 100x"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000195,"raw_usage":{"total_tokens":1366,"prompt_tokens":965,"completion_tokens":401,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":581,"completion_tokens_details":{"reasoning_tokens":335}},"tokens_in":581,"tokens_out":401,"duration_ms":4279,"temperature":1.0,"reasoning_tokens":335,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T21:07:19.047685+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Construct a rank-$R$ tensor with a missing pattern that is not uniformly random, for instance observing only entries in a small set of slices or fibers, compute $\\mathbf{P}^\\top\\mathbf{P}$ and $\\mathbf{A}^\\top\\mathbf{A}$, and measure the iteration count of approximate-mini-ALS; the theorem predicts iteration count growing linearly in $\\beta/(1-\\sqrt{\\hat\\varepsilon}\\,\\beta)$, so a demonstration where measured iterations grow faster than $\\beta$, or where leverage-score sampling with $\\hat\\varepsilon < 1/\\beta^2$ fails to produce a $(1+\\hat\\varepsilon)$-optimal inner solve, would falsify the central convergence claim.","supporting_citations":[{"cited_title":"and Westmacott, M","cited_arxiv_id":null,"evidence_quote":"Origin of the lifting idea: treating missing values as free parameters in least-squares problems."},{"cited_title":"B., Lee, Y","cited_arxiv_id":null,"evidence_quote":"Supplies the spectral approximation bound that gives $\\beta = 2/p$ under uniform row sampling and incoherence."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"States the preconditioned Richardson iteration contraction used as the exact-iteration baseline in Lemma 3.4."},{"cited_title":"A., Murray, R., Grigori, L., Buluc, A., and Demmel, J","cited_arxiv_id":null,"evidence_quote":"Fast exact leverage-score sampling for Khatri-Rao products; the CP inner solver in Corollary 4.1."},{"cited_title":"Subquadratic K ronecker regression with applications to tensor decomposition","cited_arxiv_id":null,"evidence_quote":"Subquadratic Kronecker regression algorithms; the Tucker core and factor update solvers in Corollaries 4.2 and 4.3."},{"cited_title":"T., Malik, O","cited_arxiv_id":null,"evidence_quote":"Leverage-score sampling for tensor-train cores; the TT inner solver in Corollary 4.4."},{"cited_title":"and Bro, R","cited_arxiv_id":null,"evidence_quote":"The one-iteration EM-style PARAFAC completion baseline that mini-ALS generalizes."}],"review_version":1}