{"id":"44ca6910-4564-4605-957a-f49a4b51b544","arxiv_id":"1908.02721","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"FastTT converts large sparse tensors to tensor-train format with the same accuracy and TT ranks as TT-SVD but with large speedups, by constructing an exact low-rank representation from nonzero fibers and applying specialized rounding.","lead":"This paper introduces FastTT, a faster method for converting large sparse data tensors into compact tensor-train form by building an exact representation from the data's nonzero fibers and then rounding it down efficiently. It reports speedups of up to 240x over the standard method on image, equation, and network data, while keeping the same accuracy and ranks.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"FastTT's rank guarantee is false as stated: in Table 3, N=10^4, eps=1e-2, TT-SVD ranks are 28,1390,70 while FastTT returns 28,1395,70.","rationale":"The reader's conditions included verifying the rank-equality claim for general p, but their weakest_assumption focused on the density/sparsity assumption behind the speedup. My stress-test identifies a sharper, load-bearing problem: the rank-equality assertion is not merely missing a proof; the algorithm's threshold allocation makes it internally unlikely, and the paper's own experimental data contradicts it. Table 3, row N=10^4, eps=1e-2, shows FastTT returning rank 1395 where TT-SVD returns 1390 at the same eps. This directly falsifies the strongest_claim as formulated by the reader. The error-bound part of the paper (Theorem 9) and the empirical speedups are not called into question by this concern; the core algorithm may still be valuable. Therefore I would keep the reader's CONDITIONAL verdict but add an explicit mandatory condition: either prove a correct rank-comparison statement under the actual thresholds of Algorithm 6, or revise the abstract/introduction and the strongest-claim-level language to drop the unconditional 'no increase of TT ranks' assertion. If the authors choose the latter, the paper can likely be accepted after that revision and a small amount of additional experimental reporting of ranks for each p.","tokens_in":18686,"tokens_out":12378,"duration_ms":139625,"concrete_test":"Re-run the roadNet-PA experiment of Table 3 (N=10^4, eps=1e-2) with Algorithm 7's static Algorithm 6, forcing p=1 and then each p=2,...,d, and record the resulting TT-ranks against TT-SVD. Also run a small synthetic sparse tensor sweep (e.g., d=4, n_k around 10-20, random fiber values with a known singular-value gap) for every p. If any p>1 case yields a rank strictly larger than TT-SVD's at the same eps, then Section 3.3's 'similar results' claim is disproved and the rank-comparison part of the strongest claim must be withdrawn or replaced with a weaker statement.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The strongest claim includes 'TT ranks not larger than those of TT-SVD for the same eps.' The paper's Section 3.3 argument for rank equality is only given for p=1 and for eps=0, and then asserts 'similar results' for general p without proof. For 1 sqrt(d-1) for interior p, FastTT's thresholds are strictly smaller than TT-SVD's. Smaller thresholds cannot be expected to yield equal or smaller ranks; they tend to retain more singular values. The paper's own Table 3 provides a concrete counterexample: for roadNet-PA with N=10^4 and eps=1e-2, TT-SVD returns TT-ranks 28,1390,70, while FastTT (static Algorithm 6) returns 28,1395,70. Thus the advertised rank guarantee is empirically false as stated, not merely unproven. This is load-bearing because the paper motivates FastTT partly as avoiding the exaggerated ranks of randomized TT-SVD; the speed advantage may survive, but the central claim as formulated does not.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes FastTT, an algorithm for computing a tensor-train (TT) decomposition of a large sparse tensor. It first constructs an exact TT whose initial rank is the number R of nonzero p-fibers (Algorithm 4), then applies a parallel-vector rounding procedure and a two-sided TT-rounding procedure (Algorithm 6) to reduce the rank while satisfying a prescribed relative error bound. A dynamic truncation variant (Algorithm 8) is also proposed. The authors prove an error bound (Theorem 9), give FLOP-based complexity estimates, and report speedups on image/video inpainting, finite-difference matrices, and a road-network adjacency matrix.","tokens_in":18965,"tokens_out":5918,"duration_ms":63912,"significance":"The core algorithmic idea is attractive: by rearranging a sparse tensor as a sum of rank-one tensors and exploiting the resulting quasi-permutation structure, FastTT avoids forming dense unfolded matrices and can be much faster than TT-SVD on data with few nonzero fibers. The code is publicly available, and the main error-bound proof is mostly self-contained. However, the paper's advertised rank guarantee relative to TT-SVD is contradicted by its own experiments, and one auxiliary proof is incomplete. These issues do not invalidate the speed advantage, but they materially affect what the paper can honestly claim.","major_comments":[{"comment":"The claim that FastTT yields TT ranks no larger than those of TT-SVD for the same tolerance is contradicted by Table 3. For N=10^4 and ε=1e-2, TT-SVD returns ranks (28,1390,70) while FastTT returns (28,1395,70). The supporting paragraph only proves rank equality for ε=0 and p=1, then asserts 'similar results' without a proof. For 1p with 'the same line of reasoning can be used.' The two cases are not symmetric in an obvious way because the contraction order differs (G^{(k-1)} ×3 T^T versus G^{(k+1)} ×1 T) and the unfolding is transposed. Since Corollary 7 and hence Theorem 9 rely on Theorem 5, the correctness proof for general p is not fully rigorous as written. Please supply the complete argument for k>p.","section":"Section 3.2, Theorem 5"}],"minor_comments":[{"comment":"The displayed chain of equalities in the proof of Theorem 9 writes ||A-C||_F^2 = δ_p^2 + ... as an equality. Because the SVD truncation only guarantees ||E_p||_F ≤ δ_p, this should be an inequality (≤). The final error bound is unaffected, but the current presentation is misleading.","section":"Section 3.3, proof of Theorem 9"},{"comment":"The sentence 'it can be used to decomposes arbitrary high-dimensional tensor' contains a grammatical error ('decomposes' should be 'decompose').","section":"Abstract"},{"comment":"The complexity estimates in Eqs. (1) and (13) rely on an unspecified constant C_SVD in f_SVD(m,n)=C_SVD mn min(m,n). It would be helpful to state explicitly that C_SVD is implementation-dependent and to explain how the FLOP comparisons should be interpreted across different SVD routines.","section":"Section 3.3 and Section 4"},{"comment":"The table would be easier to interpret if the difference between the FastTT and TT-SVD ranks were explicitly highlighted, especially for the ε=1e-2, N=10^4 case, since it directly contradicts the stated rank-guarantee claim.","section":"Table 3"}],"recommendation":"major_revision","confidential_remarks":"The rank discrepancy in Table 3 is the strongest evidence against the paper's central claim and should be addressed head-on. The authors should either adjust their truncation strategy to enforce the rank guarantee or clearly qualify the claim. The incomplete proof of Theorem 5 is also a correctness gap that must be closed before the paper can be accepted."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Here's my honest take. FastTT is a real algorithm, not a repackaging. The two genuinely new pieces are the quasi-permutation deparallelization (Algorithm 5) and the middle-out orthogonal rounding (Algorithm 6). The error bound in Theorem 9 is carefully argued, and Algorithm 8's adaptive thresholds are a sensible improvement with its own proof. The experiments are the strongest part: C++ code and data are on GitHub, and the speedups over TT-SVD, up to 240x for the FDM matrix conversion, are consistent with the complexity analysis: the cost scales with the number of nonzero fibers, not the full tensor size. That is the paper's real contribution.\n\nThe soft spot is the rank claim. The abstract and intro say the algorithm produces the same compact TT representation as TT-SVD, and the paper states that TT ranks are not larger. That is false as stated. Table 3 is a concrete counterexample: for roadNet-PA with N=10^4 and eps=1e-2, TT-SVD gives ranks 28,1390,70 while FastTT with static rounding gives 28,1395,70. This is not a fluke of the experiment; it follows from the thresholds. For interior p, FastTT's delta is smaller than TT-SVD's, so the truncated SVD retains more singular values. The proof in Section 3.3 only covers p=1 and eps=0, and the extension to general p is asserted. The dynamic variant (FastTT+) actually returns smaller ranks in that same table, so the story can likely be repaired, but the claim as printed should not stand.\n\nTwo smaller issues. Theorem 5's k>p case is hand-waved with 'the same line of reasoning'—likely fillable, but it should be written out. And the TT-cross timing comparison is cross-language (MATLAB vs C++), so those speedup ratios are indicative, not exact. The 'previously unachievable/unimaginable' language in the abstract and conclusion is marketing; tone it down.\n\nWho is this for? Anyone doing TT decompositions of large sparse tensors—inpainting, PDE/MPO conversion, graph data—will get value from the algorithm and the experiments. It deserves a serious referee: send it out, but require the rank claim to be corrected and, ideally, a real bound for positive eps. This is a useful paper with an overstatement, not a weak paper.","headline":"FastTT is a genuinely useful sparse TT algorithm with proven error bounds and big speedups, but its advertised 'ranks not larger than TT-SVD' claim is false as stated and needs fixing.","tokens_in":19479,"tokens_out":3421,"would_cite":true,"duration_ms":34528,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["15A69","65F55"],"pacs":[],"model":"deepseek-v4-flash","headline":"A sparse tensor can be TT-decomposed in time set by its nonzero fibers, not its full size.","keywords":["tensor train decomposition","sparse tensor","TT-rounding","parallel-vector rounding","quasi-permutation matrix","matrix product operator","low-rank approximation"],"falsifier":"Construct a sparse tensor with a known exact TT decomposition of small rank, run FastTT with a tolerance near machine precision, and check whether the returned TT ranks equal those from TT-SVD and the relative error stays below the tolerance; any mismatch would refute the central correctness and rank claims.","tokens_in":18490,"feed_emoji":"🧮","tokens_out":11270,"duration_ms":113285,"temperature":0.7,"pith_summary":"This paper proposes an algorithm, FastTT, for computing a tensor-train (TT) decomposition of a large sparse tensor. The claim is that runtime is driven by the number $R$ of nonzero one-dimensional fibers rather than by the product of the tensor's dimensions, while the error bound and the final TT ranks match those of the standard TT-SVD algorithm. The construction writes the sparse tensor exactly as a TT of rank $R$ using its nonzero fibers, then lowers the ranks with a lossless quasi-permutation-aware rounding step followed by a revised TT-rounding that carries a proven error bound. Experiments report speedups over TT-SVD from about 2x to 240x depending on sparsity, and one matrix-conversion case where TT-SVD could not finish at all. The significance is that TT-based methods become usable for sparse high-dimensional tensors that dense or randomized SVD routes cannot handle.","feed_headline":"FastTT cuts tensor-train cost to the number of nonzero fibers","feed_subtitle":"Error bound and final ranks match the standard method, while runtime scales with sparsity, not tensor size.","key_machinery":"A $p$-fiber is a one-dimensional slice of a tensor obtained by fixing all indices except the $p$-th. The load-bearing construction is Theorem 3: a sparse tensor with $R$ nonzero $p$-fibers is exactly a sum of $R$ rank-1 tensors, hence an exact TT of rank $R$ whose cores are sparse and have quasi-permutation unfoldings (each column contains a single 1). Parallel-vector rounding eliminates duplicate columns of these quasi-permutation matrices in roughly linear time and without floating-point arithmetic, and the revised TT-rounding replaces the standard right-to-left/left-to-right sweeps with two sweeps starting from the fiber direction $p$, using the orthonormality of the outer cores to keep the error budget clean.","core_discovery":"On its own terms, the paper establishes Theorem 9: for a sparse $d$-way tensor $A$ and any tolerance $\\varepsilon$, the FastTT algorithm returns a TT-format tensor $B$ with $\\|A-B\\|_F \\le \\varepsilon \\|A\\|_F$, and when $\\varepsilon$ is near machine precision the TT ranks of $B$ are exactly those produced by TT-SVD. The exact rank match follows because the initial TT built from nonzero $p$-fibers has rank $R$, and the later rounding steps reduce ranks without exceeding the allocated error budget. The complexity claim is expressed in the FLOP estimate (13): the dominant cost is a small number of SVDs whose smaller dimension is bounded by $R$ and by the prefix or suffix dimension products, so sparsity, not tensor volume, controls the running time. This is what lets the algorithm decompose tensors that TT-SVD cannot handle and convert large sparse matrices into matrix product operators.","pith_inferences":["Because the nonzero-fiber representation is just a sum of rank-1 terms, the same construction could plausibly be carried over to tensor-ring or hierarchical Tucker formats; the paper develops it only for TT.","A probabilistic extension that samples a subset of nonzero fibers first and then corrects by a residual sweep could trade a small accuracy loss for still lower initial ranks on extremely sparse, high-dimensional tensors; the paper does not explore this.","The quasi-permutation observation may apply beyond sparse fibers: any TT core whose unfoldings are quasi-permutation matrices could be rounded by the same duplicate-column elimination, which might speed up other structured tensor computations."],"forward_implications":["Tensors with many dimensions but few nonzero entries can be decomposed without ever forming a dense unfolding, so TT-based methods become practical for very high-order sparse data.","Sparse matrices can be converted to matrix product operators with the same speed-up, allowing larger linear systems to be solved by alternating least squares or related TT-iterative methods.","Setting the tolerance near zero makes the final TT ranks identical to TT-SVD's ranks, so existing pipelines can substitute FastTT without changing downstream behavior.","The proven error bound, including the dynamic parameter variant, means the algorithm does not require per-mode truncation parameters to be hand-tuned."],"supporting_citations":[{"why":"Defines the TT format, the TT-SVD algorithm and TT-rounding that FastTT extends, including the lemma on sums of TT cores.","marker":"[3]"},{"why":"Supplies the parallel-vector rounding and Deparallelisation procedure that Algorithm 4 adapts for quasi-permutation cores.","marker":"[23]"},{"why":"Contains the orthonormal-core lemma used in the proof of Theorem 9.","marker":"[14, Appendix B]"},{"why":"The randomized TT-SVD algorithm that FastTT is compared against and claimed to outperform in speed and accuracy.","marker":"[20]"},{"why":"The TT-cross approximation algorithm used as a comparative baseline in the experiments.","marker":"[18]"},{"why":"Provides the randomized SVD procedure that underlies the randomized TT-SVD baseline, relevant to the accuracy comparison.","marker":"[21]"}],"fun_headline_variants":["Sparse tensor train: cost now tracks nonzero entries, not size","New TT algorithm matches accuracy, runs in sparsity time","FastTT: decomposition speed set by nonzero fibers, not dimensions","Tensor-train decomposition that scales with sparsity, not size","FastTT beats SVD-based TT on sparse data, proven bounds"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The runtime advantage, though not the correctness guarantee, rests on the number $R$ of nonzero fibers being small compared with the full tensor size; if $R$ approaches the total number of entries, the initial TT rank grows and the speedup over TT-SVD mostly disappears.","fun_headline_variants_meta":{"raw":{"variants":["Sparse tensor train: cost now tracks nonzero entries, not size","New TT algorithm matches accuracy, runs in sparsity time","FastTT: decomposition speed set by nonzero fibers, not dimensions","Tensor-train decomposition that scales with sparsity, not size","FastTT beats SVD-based TT on sparse data, proven bounds"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000414,"raw_usage":{"total_tokens":2139,"prompt_tokens":947,"completion_tokens":1192,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":563,"completion_tokens_details":{"reasoning_tokens":1105}},"tokens_in":563,"tokens_out":1192,"duration_ms":8622,"temperature":1.0,"reasoning_tokens":1105,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T14:37:17.845787+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Construct a sparse tensor with a known exact TT decomposition of small rank, run FastTT with a tolerance near machine precision, and check whether the returned TT ranks equal those from TT-SVD and the relative error stays below the tolerance; any mismatch would refute the central correctness and rank claims.","supporting_citations":[{"cited_title":"Tensor-train decomposition","cited_arxiv_id":null,"evidence_quote":"Defines the TT format, the TT-SVD algorithm and TT-rounding that FastTT extends, including the lemma on sums of TT cores."},{"cited_title":"Generic construction of efficient matrix product operators","cited_arxiv_id":null,"evidence_quote":"Supplies the parallel-vector rounding and Deparallelisation procedure that Algorithm 4 adapts for quasi-permutation cores."},{"cited_title":"A randomized tensor train singular value decomposition","cited_arxiv_id":null,"evidence_quote":"The randomized TT-SVD algorithm that FastTT is compared against and claimed to outperform in speed and accuracy."},{"cited_title":"TT-cross approximation for mul- tidimensional arrays","cited_arxiv_id":null,"evidence_quote":"The TT-cross approximation algorithm used as a comparative baseline in the experiments."},{"cited_title":"Finding struc- ture with randomness: Probabilistic algorithms for constructing approxi- mate matrix decompositions","cited_arxiv_id":null,"evidence_quote":"Provides the randomized SVD procedure that underlies the randomized TT-SVD baseline, relevant to the accuracy comparison."}],"review_version":1}