{"id":"7818d565-fe7a-4016-96bf-d8c255dd538f","arxiv_id":"2412.06111","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"TTNN and STTNN compute streaming low-rank approximations of tensors in any tree tensor network format in a single pass, with deterministic and Gaussian expectation error bounds.","lead":"This paper presents TTNN and STTNN, randomized single-pass algorithms for approximating large tensors directly in a tree tensor network format, with error bounds and numerical tests. A smart generalist should read it because streaming low-rank tensor approximation is a practical bottleneck in quantum chemistry and data science, and these methods unify existing approaches for Tucker and tensor-train formats.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The STTNN error guarantee in Theorem 6.7 is not a minor adaptation: sequential projectors built from contracted tensors can discard dominant directions, and a 2x2 example violates the claimed bound.","rationale":"The paper's substantive contribution is the TTNN algorithm and its deterministic/probabilistic error bounds, which appear internally consistent modulo fixable issues in the cited matrix bounds. The weakest point is exactly what the reader identified: the STTNN guarantee in Theorem 6.7 is asserted without proof and is not a direct corollary of the TTNN analysis. I went further and found a concrete 2x2 instance where the claimed STTNN bound fails, because the sequential contraction can project out the dominant component before a later projector is formed. This is not a disagreement with consensus; it is a correctness failure of a stated theorem. The right response is conditional: the authors must either prove Theorem 6.7 under explicit nondegeneracy or structural assumptions, or remove the STTNN error guarantee and clearly state that STTNN is only supported empirically. The TTNN results can stand independently, which is why outright rejection is not warranted. The reader's conditional verdict is therefore appropriate.","tokens_in":22734,"tokens_out":23901,"duration_ms":215791,"concrete_test":"Implement the STTNN construction of Section 5 for T = diag(10,1) with the two-leaf tree, target ranks R=(2,2), and comparison ranks pR=(1,1). Use sketchings X_{1,1} = Y_{1,1} = [e_2, 2e_2], then for the second leaf set X_{1,2} = [0;1] and Y_{1,2} = e_2, so that (5.4) is well-defined. Compute the STTNN approximant via (5.5) and its Frobenius error, and compare it with the right-hand side of Theorem 6.7 evaluated with the same sketchings. If the error is about 10.01 while the claimed bound is about 2.62, Theorem 6.7 is refuted; repeating with small generic perturbations of these sketchings should still produce violations whenever Y_{1,1} is nearly orthogonal to the dominant left singular vector of T.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The load-bearing gap is Theorem 6.7. Section 6.3 asserts the TTNN analysis adapts to STTNN 'with minimal modifications' (Eq. 5.4), but the STTNN projector P_{\\ell,k} is built from A = T^S_{\\ell,k}, a tensor already contracted with previously drawn Y's, not from T_{\\ell,k}. The TTNN proof bounds ||(I-P_{\\ell,k})T_{\\ell,k}|| using the generalized Nystr\\\"om bounds (2.1)-(2.2), which apply when the target matrix and the matrix defining the sketch coincide. In STTNN the target is T_{\\ell,k} while the sketch is Y_S^T T_{\\ell,k}; the contraction Y_S can remove singular directions needed by later projectors. Additionally, the quantities in Theorem 6.7 are dimensionally inconsistent: \\hat V_{\\ell,k} has n_{D\\setminus I_{\\ell,k}} rows, whereas X_{\\ell,k} in (5.4) acts on the contracted T^S and has fewer rows. A concrete falsification: take T = diag(10,1), two-leaf tree, R=(2,2), pR=(1,1); choose X_1 = Y_1 = [e_2, 2e_2], X_2 = [0;1], Y_2 = e_2. Then both projectors select the small singular direction, the STTNN output is [[0,0],[0.5,1]], and the Frobenius error is about 10.01, while ||T-T_{(1,1)}|| = 1 and the bound in (6.11) is approximately 2.62. Thus Theorem 6.7 is false as stated; the theoretical claims should either be restricted to TTNN or supplemented by explicit assumptions on the contracted sketches.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes two randomized algorithms for streaming low-rank approximation of tensors in a general tree tensor network format. The tree tensor network Nystrom (TTNN) method applies generalized Nystrom oblique projectors built from two-sided sketches at every non-root node of the index tree; the sequential variant STTNN reuses contractions with previously drawn sketches to reduce cost. The paper proves a deterministic error bound for TTNN (Theorem 6.4), a Gaussian expectation bound (Theorem 6.6), and states a deterministic bound for STTNN (Theorem 6.7). The final sections discuss structured Khatri-Rao sketchings for TTN rounding and present numerical experiments on dense and structured tensors.","tokens_in":23087,"tokens_out":35115,"duration_ms":316386,"significance":"If the TTNN analysis is correct, the paper gives a genuinely unifying framework: it contains the multilinear Nystrom and streaming tensor-train approximation as special cases, retains single-pass/streamable features, and provides explicit deterministic and Gaussian bounds. The release of code for the experiments is a concrete strength. The STTNN result, however, is a major unresolved problem: Theorem 6.7 is not a minor adaptation of the TTNN proof, and as stated it is ill-posed. Since STTNN is one of the two headline algorithms, the current theoretical contribution is only partial.","major_comments":[{"comment":"The claim in Section 6.3 that the TTNN deterministic analysis can be adapted to STTNN with minimal modifications is not supported. In STTNN the projector in (5.4) is built from A = T^S_(l,k), the tensor already contracted along previously processed indices, while the error term that must be controlled involves the original T_(l,k). The generalized Nystrom bounds (2.1)-(2.2) apply when the sketch and the target coincide; they do not control (I-P)B when P is constructed from a matrix different from B. The theorem is also not well-formed: after a contraction, X_(l,k) has fewer rows than n_(D\\I_(l,k)), so the product Vbar_(l,k)^T X_(l,k) in the definition of rho_(l,k) is dimensionally incompatible with Vbar_(l,k) being a right singular vector matrix of the original T_(l,k). Concretely, for T = diag(10,1,0.1) with two leaves, R = (2,2), pR = (1,1), and the full-column-rank choices X1 = Y1 = [e2,e3], X2 = I2, Y2 = [e2,e3], the STTNN approximant is diag(0,1,0.1), whose Frobenius error is 10, while ||T - T_pR||_F is approximately 1.005. The theorem cannot even be applied to this example because Vbar_(1,2)^T X_(1,2) is undefined; the dimensional mismatch is therefore not a cosmetic issue. Theorem 6.7 should be removed or replaced by a statement with a proof and with definitions compatible with the contracted sketch dimensions.","section":"6.3, Theorem 6.7 and Eq. (5.4)"},{"comment":"The statement of Theorem 6.4 does not include the full-column-rank hypothesis under which Lemma 6.1 is proved. The proof of the theorem uses the identity P = Q(Y^T Q)^+ Y^T and the inequality (6.1), both of which require Y^T_(l,k) T_(l,k) X_(l,k) to have full column rank. Without this hypothesis the deterministic bound need not hold for arbitrary user-supplied DRMs. Please state the rank condition explicitly in Theorems 6.4 and 6.7, or treat the rank-deficient case separately.","section":"6.1, Theorem 6.4 and Lemma 6.1"}],"minor_comments":[{"comment":"The displayed bounds for HMT and GN omit the square-root factors that are present in the correct statements and that are used later in the definitions of rho_(l,k) and tau_(l,k); please update the display.","section":"2, Eqs. (2.1)-(2.2)"},{"comment":"The paragraph beginning with In the second experiment is repeated verbatim; remove the duplicate.","section":"8, second experiment"},{"comment":"The contraction convention for T times Y^T_(l,k) is introduced informally; a formal definition of the contracted tensor T^S_(l,k) and of the row count of X_(l,k) would prevent dimension errors such as the one affecting Theorem 6.7.","section":"5, Eqs. (5.1)-(5.4)"},{"comment":"The use of the same symbol I for the index tree and its extension is confusing; please use a different notation for the extended tree.","section":"3, Definition 3.4"}],"recommendation":"major_revision","confidential_remarks":"The STTNN theorem is the main obstacle. If the authors cannot provide a proof, the paper could be revised by removing Theorem 6.7 and presenting STTNN as an empirical/heuristic acceleration; the abstract and title would need adjustment accordingly. I would not accept the manuscript while Theorem 6.7 stands as stated. Several references by the first author are cited; this is not improper, but the new contribution relative to [28] and [29] should be made explicit."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things to know. First, TTNN is a genuine step forward: it is the first single-pass streaming low-rank approximation for the general tree tensor network format, and it reduces to MLN for Tucker and STTA for tensor-train as special cases. The index-tree formulation (Section 3) and the telescoping bound (Lemma 6.2) are new, and the deterministic error bound for TTNN (Theorem 6.4) and the Gaussian expectation bound (Theorem 6.6) are correctly adapted from the STTA template. I checked the details: the definitions of ρ, τ, η match the proof, there is no circularity, and the experiments support the claims for TTNN.\n\nSecond, the STTNN part is in trouble. Section 6.3 asserts Theorem 6.7, a deterministic bound for STTNN, but only says the TTNN analysis 'can be adapted with minimal modifications.' It cannot. In STTNN the projector Pℓ,k is built from T^Sℓ,k, a version of T that has already been contracted with previously drawn sketches, not from Tℓ,k itself. The generalized Nyström bounds used in TTNN crucially require the matrix defining the sketch and the matrix being approximated to be the same. That assumption is violated, and there is a simple 2x2 counterexample: take T = diag(10,1) with a two-leaf tree; choose sketches so both projectors select the small singular direction. The STTNN output has Frobenius error ≈ 10.01, while the bound in (6.11) is ≈ 2.62. Theorem 6.7 is false as stated. The authors need to supply a correct proof with explicit assumptions on the contracted sketches, or restrict the theoretical claims to TTNN and present STTNN as an empirical method. I suspect the latter is more honest.\n\nMinor issues: equations (2.1)-(2.2) misquote the matrix bounds from [24], omitting the sqrt(1+||·||²) factors that appear later in ρ and τ; it's a display error, not fatal. And the experiments report means over 30 trials but no variance; for a randomized method, that's a notable omission but doesn't change the main conclusion.\n\nWho should read this: anyone working on streaming tensor approximations or randomized tensor network rounding. The TTNN result is worth knowing, and the paper should be circulated. It deserves a serious referee: the TTNN contribution is new and essentially correct, and the STTNN overclaim should be fixed or removed. I'd send it to review with a clear request to resolve Theorem 6.7.","headline":"TTNN is a solid new streaming method for tree tensor networks; the STTNN error bound is false as stated.","tokens_in":23671,"tokens_out":3327,"would_cite":true,"duration_ms":29337,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["15A69","65F55","68W20"],"pacs":[],"model":"deepseek-v4-flash","headline":"Randomized Nyström sketching gives single-pass low-rank tree tensor network approximation with error controlled by the best lower-rank fit.","keywords":["tree tensor network","Nyström approximation","streaming algorithm","single-pass","randomized low-rank approximation","tensor rounding","Gaussian dimension reduction maps","Khatri-Rao embeddings"],"falsifier":"Compute the STTNN approximant for a concrete tensor such as a 6D Hilbert tensor with mode size 20, evaluate the right-hand side of (6.11) exactly from the definitions of $\\hat{V}$, $Q$, $X$, and $Y$ for many Gaussian draws, and compare it with the actual $\\|T-\\hat{T}\\|_F$; a single draw violating the inequality would falsify Theorem 6.7 as stated.","tokens_in":22493,"feed_emoji":"🧮","tokens_out":7762,"duration_ms":75338,"temperature":0.7,"pith_summary":"This paper introduces two streaming, single-pass algorithms—tree tensor network Nyström (TTNN) and its sequential counterpart (STTNN)—for low-rank approximation of tensors in any tree tensor network format. The method applies a generalized Nyström projection at every node of an index tree, drawing two random dimension-reduction maps per node and forming oblique projectors from the unfoldings. The main theoretical result is a deterministic error bound: for any smaller target rank, the Frobenius error of the TTNN output is bounded by the error of the best lower-rank tree tensor network approximation times a sum of node-dependent factors measuring how well the sketches capture dominant singular subspaces. For Gaussian sketches, a bound in expectation is also proved. The same construction performs rounding of tensors already in TTN format, and the sequential variant cuts cost on dense tensors by reusing contracted pieces; a deterministic bound for STTNN is stated by adapting the TTNN analysis.","feed_headline":"One pass sketches tree tensor networks into low rank","feed_subtitle":"Nyström-style random projections deliver streamable tree-network fits whose error tracks the best smaller-rank approximation.","key_machinery":"The central object is the per-node oblique Nyström projector $P_{\\ell,k} = T_{\\ell,k}X_{\\ell,k}(Y_{\\ell,k}^T T_{\\ell,k}X_{\\ell,k})^+ Y_{\\ell,k}^T$, built from one unfolding $T_{\\ell,k}$ of the tensor and two random dimension-reduction maps per node of the index tree. The approximant is the Kronecker product of these projectors acting on the vectorized tensor, level by level from leaves to root. This object carries the argument because the error telescopes into a sum of terms $(I-P_{\\ell,k})T_{\\ell,k}$, each bounded by the generalized Nyström matrix bounds; the recovery phase never forms the pseudoinverse explicitly, instead QR-factorizing the small sketch $Y_{\\ell,k}^T T_{\\ell,k} X_{\\ell,k}$ and solving least-squares problems. For STTNN, the same projectors are built from pre-contracted tensors $T^S_{\\ell,k}$, which is what lowers the cost on dense inputs.","core_discovery":"At the paper's core is the claim that the matrix generalized Nyström framework transfers to an arbitrary tree tensor network without losing its streaming property. For each node $I_{\\ell,k}$ of the extended index tree, the algorithm defines an oblique projector $P_{\\ell,k} = T_{\\ell,k}X_{\\ell,k}(Y_{\\ell,k}^T T_{\\ell,k}X_{\\ell,k})^+ Y_{\\ell,k}^T$ and applies all such projectors level by level, forming $\\hat{T}^D = (\\otimes_j P_{L,j})\\cdots(\\otimes_j P_{1,j})T^D$. Theorem 6.4 asserts that for any rank $\\tilde{R}