{"id":"a7268322-6e05-40ac-bf18-d7ba2abeb310","arxiv_id":"2412.02597","paper_version":3,"verdict":"REJECT","confidence":"MODERATE","novelty_score":4.0,"correctness_risk":"high","formal_verification":"none","parameter_count":4,"one_line_summary":"Randomized SVD is substituted for deterministic SVD inside the TTr1SVD algorithm to obtain a faster Kronecker tensor decomposition, with an unproven recursive error bound.","lead":"This paper replaces the slow, exact singular value decompositions used in Kronecker tensor decomposition with randomized, approximate versions, cutting computing time by about an order of magnitude in tests on images, videos, and synthetic tensors. The authors claim a formal error bound for the approximation, but the proof is only sketched with no derivation.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 4's proof is one sentence and never composes randomized-SVD errors through the TTr1SVD tree; the stated additive bound against a single tail-energy term is unsupported and likely false.","rationale":"The reader's weakest assumption identifies the same load-bearing defect I see: Theorem 4 asserts an error bound for the full randomized TTr1SVD pipeline without deriving how per-SVD randomized errors compose through the tree. The one-sentence proof is not a proof of the composition step, and the stated form of the bound—a sum of per-step epsilon_i multiplied by a single tail energy—is not what a standard recursive argument would deliver. This is not merely a stylistic gap: the intermediate matrices in Algorithm 3 are random and depend on previous errors, so their tail energies and spectral gaps differ from the fixed quantities in Theorem 3. The empirical results show plausible speedups (roughly an order of magnitude in the reported synthetic tests, not the abstract's 'several orders of magnitude'), and they support the practical algorithm as an engineering contribution, but they do not substantiate the theoretical theorem. Since the advertised contribution includes 'a detailed theoretical analysis' and 'recursive error bound,' the unsupported Theorem 4 warrants rejection of the paper in its current form. A revised version with a genuine composition proof, a corrected statement of the tail term, and released code would merit reconsideration. I therefore see no reason to change the reader's REJECT verdict.","tokens_in":15379,"tokens_out":5554,"duration_ms":63302,"concrete_test":"Independently derive a recursive error expression for Algorithm 3 on a third-order tensor: let Delta_i be the randomized-SVD error at step i and express the final reconstruction error in terms of Delta_i and the exact/unperturbed intermediate SVD bases. Then implement Algorithm 3 on a small known-rank example (e.g., 12x12x12, exact KTD rank R=6, approximation rank R'=4, q=0, several oversampling values) and compare the Monte Carlo empirical E||X - X_hat||_F^2 against the right-hand side of (16). If the recursive derivation contains extra amplification terms, or if the empirical mean exceeds the claimed bound, Theorem 4 fails as stated. If the bound is nevertheless satisfied across many instances, the missing proof is an exposition gap rather than a substantive error.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The advertised theoretical contribution is Theorem 4, but its proof is only 'Using Theorem 3, the proof is straightforward.' This skips the entire composition argument. Theorem 3 bounds the Frobenius error of one randomized SVD on one fixed matrix in terms of that matrix's own singular-value tail. In Algorithm 3, however, the second and later randomized SVDs operate on reshaped right-singular vectors produced by the previous randomized SVDs. Those intermediate matrices are random perturbations of the exact unfoldings of X, so their singular values, spectral gaps tau_i, and tail sums are not the same as the quantities appearing on the right-hand side of (16). No argument is given that per-step errors add, that intermediate perturbations are not amplified by subsequent truncations, or that a sum of epsilon_i times a single tail energy controls the final reconstruction error. A rigorous recursive bound would need to track how each Delta_i propagates through the remaining SVD tree, typically producing products or compounded terms and intermediate tail energies; it would not obviously reduce to the stated linear sum over epsilon_i times a fixed (sigma^2_{R'+1}+...+sigma^2_R). Because this unproven composition step is the bridge from a standard one-matrix randomized-SVD bound to the paper's advertised KTD guarantee, it is the load-bearing weakness of the central claim.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes randomized algorithms for computing the Kronecker Tensor Decomposition (KTD), replacing the deterministic SVDs in the TTr1SVD pipeline with randomized SVDs that use oversampling and power iterations. Three variants are presented: R-KTD (randomized SVD), RF-KTD (pass-efficient randomized SVD), and PT-KTD (randomized Tucker compression followed by randomized KTD). The manuscript claims a theoretical guarantee in Theorem 4 that the expected Frobenius-norm error of the randomized KTD is bounded by a product of per-step factors times a single tail-energy term, with exponential decay in the number of power iterations. Extensive experiments on synthetic tensors, images, and videos report substantial speedups over the deterministic baseline while maintaining comparable accuracy in compression, completion, denoising, and super-resolution applications.","tokens_in":15643,"tokens_out":2172,"duration_ms":21460,"significance":"If the theoretical guarantee were established, the paper would provide a valuable practical contribution: randomized KTD with controlled expected error and large speedups would make KTD scalable to large tensors. The empirical results, particularly the order-of-magnitude speedups in the larger synthetic and video experiments, are plausible and potentially useful to practitioners. The paper also demonstrates that power iterations improve reconstruction quality, and it ships a pass-efficient variant that permits flexible pass budgets, which is a practically relevant design choice. However, the advertised theoretical contribution is not proven as written: the proof of Theorem 4 is a single sentence that does not address error propagation through the recursive TTr1SVD tree, and the stated bound is therefore unsupported. The empirical claims, while suggestive, are not presented with error bars or statistical significance tests, and some runtime comparisons are on small tensors where the speedups are modest.","major_comments":[{"comment":"The proof of Theorem 4, stated as 'Using Theorem 3, the proof is straightforward,' does not justify the bound. Theorem 3 applies to a single randomized SVD of one fixed matrix and bounds its error by that matrix's own singular-value tail. In Algorithm 3, however, the second and subsequent randomized SVDs operate on matrices produced by the previous randomized SVDs; those intermediate matrices are random perturbations of the exact unfoldings of X. Their singular values, spectral gaps tau_i, and tail sums are not the same as the fixed (sigma^2_{R'+1}+...+sigma^2_R) appearing on the right-hand side of (16). The manuscript gives no argument that per-step errors combine additively, that perturbations are not amplified by subsequent truncations, or that the final reconstruction error is controlled by the sum of per-step factors times a single tail energy. A rigorous recursive bound would need to track how each intermediate error propagates through the remaining SVD tree, typically producing compounded or multiplicative terms and multiple tail energies. This missing composition argument is the load-bearing step for the paper's advertised theoretical contribution and, as written, the claim is unsupported.","section":"Section 5, Eq. (16)"},{"comment":"The complexity comparison is not sufficiently substantiated. The paper states that the deterministic KTD complexity is O(I^{N+1}) and the randomized KTD is O(I^N R), but no derivation is given for either expression, and the dependence on the oversampling parameter P, the power iteration q, and the intermediate tensor shapes is omitted. In particular, the randomized algorithm performs T = R^(N-2) types of randomized SVDs on reshaped right-singular vectors, and the sizes of these matrices depend on the block dimensions J_n^{(m)}; the stated complexity O(I^N R) does not transparently follow. Since the speedup claim is central to the paper, this complexity comparison needs a clearer derivation or at least a precise reference to the operations counted.","section":"Section 6"},{"comment":"The claim that 'similar upper bounds as in Theorem (4) can be straightforwardly estimated for this new strategy' is not supported. The pass-efficient algorithm of Bjarkason [40] is cited for matrix approximation, but no adaptation to the tensor tree is described, and the error analysis of that algorithm is not coupled to the TTr1SVD recursion. Given that Theorem 4 itself is not proven, the extension to RF-KTD is even less justified, yet the simulations use RF-KTD as one of the proposed methods. Please provide either a derivation or explicitly mark this as an empirical heuristic.","section":"Section 5, 'It is also known...' paragraph"}],"minor_comments":[{"comment":"The abstract says the error is bounded by 'a sum of tail energies multiplied by factors that decay exponentially,' while Theorem 4 states a sum of epsilon_i multiplied by a single tail energy. These formulations are inconsistent: the abstract implies multiple tail energies, the theorem has one. Please reconcile.","section":"Abstract"},{"comment":"Equation (13) contains a typo in the denominator: it reads ||sigma^2_{R'+1}+...+sigma^2_R||_F, which is a scalar and not a Frobenius norm of a matrix; it should be sqrt(sigma^2_{R'+1}+...+sigma^2_R) divided by the appropriate norm of X. Also, the text refers to 'relative approximation error (16)' when the displayed equation is (13); please fix the cross-reference.","section":"Section 3"},{"comment":"In Algorithm 1, the input dimensions are denoted J_n^{(m)} but the reshape on line 1 uses these dimensions without specifying the ordering; also the permutation vector p is not defined in this algorithm. For reproducibility, please define p explicitly.","section":"Section 3, Algorithm 1"},{"comment":"The theorem assumes X has exact KTD rank R, but the bound is stated for an approximation with KTD rank R' (presumably R' < R). The relationship between R, R', and the truncation ranks used in the inner SVDs of Algorithm 3 is not specified. The notation 'sigma_{R'+1}+...+sigma_R' also reuses R in two roles (the true KTD rank and the intermediate SVD rank). This ambiguity makes the theorem hard to parse.","section":"Section 5, Theorem 4"},{"comment":"The running-time comparisons in Figure 2 are reported for only a single run or the mean of 100 runs? The text says 100 Monte Carlo simulations for the errors, but the running-time figure is not described as averaged. Please clarify the variance of the timings; a speedup claim of 'several orders of magnitude' is not supported by Figure 2, which shows roughly one order of magnitude in the displayed range.","section":"Section 7, Example 1"},{"comment":"The statement 'a single image is not a large tensor' conflicts with the earlier claim that the randomized KTD gives several orders of magnitude speedup on large tensors. For the Kodak image, the reported speedup is about 4.5x (14.45 vs 3.10 seconds), not orders of magnitude. Please adjust the language to match the reported numbers.","section":"Section 7, Example 2"},{"comment":"In the video compression experiment, the text says patches of size 16x12x30 and 11x12x10, but the frame count is 300; the relationship between these patch sizes and the video dimensions 176x144x300 is not explained. Also, Figure 5 (left) is labeled 'Aikyo' while the text says 'Foreman'; please correct the labels.","section":"Section 7, Example 3"},{"comment":"The denoising and super-resolution experiments are presented without comparison to a baseline or to the deterministic KTD, so the reader cannot judge whether the proposed method is competitive in quality. Also, the PSNR gains are not reported numerically; please add quantitative metrics.","section":"Section 7, Example 5"},{"comment":"The notation for the tensor Kronecker product is introduced, but the paper also uses the standard Kronecker product symbol in the preliminaries; the notation for the tensor Kronecker product (same symbol) may cause confusion. Consider using a distinct symbol or explicitly noting the difference in each use.","section":"Section 2"}],"recommendation":"major_revision","confidential_remarks":"The paper's empirical contribution is potentially useful, but the central theoretical claim (Theorem 4) is not proven, and the complexity analysis is not derived. The gap in Theorem 4 is not a minor omission; it is the advertised core contribution. I recommend major revision rather than reject because the empirical results and the algorithmic idea are plausible, and a rigorous error-propagation analysis, while nontrivial, may be within reach if the authors can establish a recursive perturbation bound. If the authors cannot supply that analysis, the paper should be reframed as an empirical study without the unsupported Theorem 4, in which case its significance would be considerably lower."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The thing to know: this is a straightforward, plausible randomized version of the TTr1SVD algorithm for Kronecker tensor decomposition, and the experiments support maybe a 10x speedup, not the 'several orders of magnitude' promised in the abstract. The bigger problem is that the advertised theoretical guarantee, Theorem 4, is essentially unproved.\n\nWhat is genuinely new: the authors are, as far as I can tell, the first to propose randomized SVD inside the TTr1SVD pipeline for KTD. Replacing deterministic truncated SVDs with randomized SVDs plus oversampling and power iteration is a natural move, but natural moves still need to be tested, and they did test it. The experiments span synthetic tensors, image/video compression, completion, denoising, and super-resolution. The ablations over power iteration q and the inclusion of a pass-efficient variant and a Tucker-compressed variant are useful. The empirical performance looks credible and roughly an order of magnitude faster than deterministic KTD on the reported cases.\n\nThe soft spots are real and load-bearing. Theorem 4 claims an expected Frobenius error bound that is a sum of per-step factors times a single tail energy of the original tensor. The proof is one sentence: 'Using Theorem 3, the proof is straightforward.' That is not a proof. Theorem 3 is a standard one-matrix randomized-SVD bound, but in Algorithm 3 the second and later randomized SVDs operate on reshaped right-singular vectors that are random perturbations of the exact unfoldings. The singular values, spectral gaps, and tail energies of those intermediate matrices are not the same as the quantities on the right-hand side of (16). No argument shows the per-step errors add, or that perturbations are not amplified by later truncations. A recursive bound would likely produce compounded terms and intermediate tail energies, not a simple linear sum against one fixed tail. I suspect the stated bound is false as written.\n\nThere are also smaller but telling slips. The sentence after Theorem 3 says a smaller spectral gap gives better approximation, which is backwards—the factor depends on the ratio sigma_{R+1}/sigma_R, so a larger gap helps. And the citation for Theorem 3 points at a tensor-ring paper, not the usual randomized-SVD source, which is sloppy. No code is released, despite the text referencing a GitHub repository for the deterministic baseline.\n\nBottom line: the algorithmic contribution is reasonable and worth engaging with, but the theoretical centerpiece is not there. A revised version with either a real recursive error analysis or an explicit retreat to a heuristic claim, plus code, would deserve another look. I would send this to a serious referee: the problem is meaningful and the empirical work is useful, but the referee should be told to focus on Theorem 4 and the overclaiming.","headline":"A sensible randomized-TTr1SVD combination with useful experiments, but the advertised error bound in Theorem 4 is not proved and the paper overstates its speedups.","tokens_in":16174,"tokens_out":1956,"would_cite":false,"duration_ms":23398,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["15A69","46N40","15A23"],"pacs":[],"model":"deepseek-v4-flash","headline":"Randomized SVDs with oversampling and power iterations can replace the SVD chain in TTr1SVD, giving a Kronecker tensor decomposition with expected error bounded by tail energy times exponentially decaying factors and order-of-magnitude…","keywords":["Kronecker tensor decomposition","randomized SVD","power iteration","oversampling","TTr1SVD","tensor completion","tensor compression","tensor approximation"],"falsifier":"Run R-KTD on a synthetic tensor with known KTD rank and known singular spectra, over many random trials and for increasing numbers of SVD steps $T$, and compare the empirical mean-squared error with the Theorem 4 bound $(\\sum_i\\epsilon_i)(\\sigma_{R'+1}^2+\\cdots+\\sigma_R^2)$; if the observed error grows faster than the bound as $T$ increases, the additive error-propagation assumption is false.","tokens_in":15138,"feed_emoji":"🧮","tokens_out":14877,"duration_ms":129444,"temperature":0.7,"pith_summary":"Kronecker tensor decomposition (KTD) writes a large tensor as a short sum of Kronecker products of smaller normalized tensors, and the standard TTr1SVD method computes it by a chain of truncated SVDs that is too slow for large data. The paper's central claim is that each deterministic SVD in that chain can be replaced by a randomized SVD with oversampling and power iterations, producing a randomized KTD algorithm (R-KTD) with a controlled expected error and much lower cost. The advertised guarantee is Theorem 4: the expected squared Frobenius error of the randomized approximation is bounded by the tail singular-value energy (the squared norm of the singular values omitted by truncation) times a sum of factors, one per SVD step, each decaying exponentially with the number of power iterations. If the bound is right, large-scale tensor compression, completion, denoising, and super-resolution become practical without the deterministic algorithm's $O(I^{N+1})$ cost. The paper also gives pass-efficient and Tucker-compressed variants and reports several orders of magnitude acceleration on synthetic and real datasets.","feed_headline":"Randomized SVDs keep tensor decomposition accurate and fast","feed_subtitle":"The paper gives an error bound for randomized Kronecker tensor decomposition and shows order-of-magnitude speedups.","key_machinery":"The load-bearing object is the randomized SVD used as a drop-in replacement at every node of the TTr1SVD tree (the chain of truncated SVDs on successive unfoldings and reshaped singular vectors). On an unfolding matrix $X$, the algorithm draws a Gaussian sketch $\\Omega$ of width $R+P$, forms $Y=(XX^T)^q X\\Omega$ for $q$ power iterations, orthonormalizes $Y$ to get $Q$, and then computes the SVD of the small matrix $Q^T X$. The error analysis is carried by the per-matrix bound $E\\|X-QQ^TX\\|_F^2 \\le (1+\\frac{R}{P-1}\\tau^{4q})\\sum_{j>R}\\sigma_j^2$; Theorem 4 assembles these per-step bounds along the chain of unfoldings into a single inequality with tail energy $\\sigma_{R'+1}^2+\\cdots+\\sigma_R^2$. The reshaping-and-permutation equivalence between KTD and CPD with orthonormal rank-1 terms is what makes a chain of matrix SVDs produce the tensor factors in the first place.","core_discovery":"On the paper's own terms, the discovery is a drop-in randomization of TTr1SVD: at every node of the sequential SVD tree, the deterministic truncated SVD is replaced by a randomized SVD with oversampling $P$ and power iterations $q$. The resulting rank-$R'$ approximation satisfies the expected-error inequality $$E\\|X - \\sum_{r=1}^{R'} \\sigma_r $X_r^{{(1)}}$\\otimes\\cdots\\otimes $X_r^{{(M)}}$\\|$_F^{2}$ \\le \\left(\\sum_{i=1}^T \\epsilon_i\\right)(\\sigma_{R'+1}^2+\\cdots+\\$sigma_R^{2}$),$$ with $\\epsilon_i = 1 + \\frac{R}{P-1}\\tau_i^{4q}$, where $\\tau_i$ is the spectral gap at the $i$-th SVD step and $T$ is the number of randomized SVDs. The factors $\\tau_i^{4q}$ decay exponentially with $q$, so the expected error stays within a modest multiple of the optimal tail energy. The paper claims this makes randomized KTD a near-optimal approximation in expectation, and the experiments show the same reconstruction quality as the deterministic KTD at a fraction of the runtime.","pith_inferences":["Editorial inference: Theorem 4's additive form suggests the early SVD steps dominate the error, so spending more power iterations on early tree levels could improve accuracy per pass; the paper does not test this adaptive allocation.","Editorial inference: because TTr1SVD is a sequential-unfolding scheme, the same randomized replacement should transfer to tensor-train and other hierarchical SVD decompositions, although the paper only claims it for KTD.","Editorial inference: the guarantee depends on per-step spectral gaps $\\tau_i$, so tensors with slowly decaying singular values will need larger $q$; a gap-free bound based on stable rank would be a natural extension."],"forward_implications":["If Theorem 4 is correct, the randomized KTD error is controlled by a known tail-energy term, so a user can choose KTD rank and power iteration before running the algorithm and have an expected-error guarantee.","The reported experiments show about an order of magnitude speedup on a $100\\times100\\times100\\times100$ synthetic tensor and larger gains on a $1000\\times1000\\times1000$ tensor, making KTD practical for tensors that require gigabytes of memory.","In iterative tensor completion, replacing the deterministic low-rank operator with R-KTD reduced video-completion time from 235 seconds to 70 seconds on the Akiyo test while maintaining PSNR.","Compressing the full Kodak dataset dropped from 14.45 seconds to 3.10 seconds with $q=1$ at nearly identical PSNR, so batch image compression becomes much faster."],"supporting_citations":[{"why":"Supplies the randomized-SVD error bound (Theorem 3) that the paper's Theorem 4 builds on.","marker":"[12]"},{"why":"Introduces the TTr1SVD-based KTD algorithm and its error analysis, the deterministic baseline the randomized algorithms replace.","marker":"[17]"},{"why":"Provides the constructive orthonormal rank-1 decomposition (TTr1SVD) whose sequence of truncated SVDs is randomized here.","marker":"[29]"},{"why":"Provides the pass-efficient low-rank approximation scheme used by the RF-KTD variant.","marker":"[40]"},{"why":"Provides the randomized Tucker/HOSVD algorithm used for the two-stage PT-KTD variant.","marker":"[25]"},{"why":"Defines the tensor Kronecker product and the KTD model that the algorithms compute.","marker":"[16]"},{"why":"Supplies the tensor-completion iterative scheme used in the completion experiments.","marker":"[5]"}],"fun_headline_variants":["Randomize to speed up tensor decomposition without accuracy loss","Proven-error randomized tensor decomposition is orders faster","Kronecker tensor decomposition: randomization yields big speedups","Randomized SVDs accelerate Kronecker tensor decomposition","Error-bounded random tensor decomposition is fast"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing assumption is that the errors from the successive randomized SVDs in the TTr1SVD tree combine additively into a single tail-energy term; the paper's proof of Theorem 4 says only 'using Theorem 3, the proof is straightforward' and does not show how one step's error flows into the next, so if errors amplify multiplicatively along the tree instead of adding, the advertised bound does not follow.","fun_headline_variants_meta":{"raw":{"variants":["Randomize to speed up tensor decomposition without accuracy loss","Proven-error randomized tensor decomposition is orders faster","Kronecker tensor decomposition: randomization yields big speedups","Randomized SVDs accelerate Kronecker tensor decomposition","Error-bounded random tensor decomposition is fast"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00063,"raw_usage":{"total_tokens":2914,"prompt_tokens":954,"completion_tokens":1960,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":570,"completion_tokens_details":{"reasoning_tokens":1899}},"tokens_in":570,"tokens_out":1960,"duration_ms":16449,"temperature":1.0,"reasoning_tokens":1899,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T23:16:53.745527+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run R-KTD on a synthetic tensor with known KTD rank and known singular spectra, over many random trials and for increasing numbers of SVD steps $T$, and compare the empirical mean-squared error with the Theorem 4 bound $(\\sum_i\\epsilon_i)(\\sigma_{R'+1}^2+\\cdots+\\sigma_R^2)$; if the observed error grows faster than the bound as $T$ increases, the additive error-propagation assumption is false.","supporting_citations":[{"cited_title":"Batselier, N","cited_arxiv_id":null,"evidence_quote":"Introduces the TTr1SVD-based KTD algorithm and its error analysis, the deterministic baseline the randomized algorithms replace."},{"cited_title":"Batselier, H","cited_arxiv_id":null,"evidence_quote":"Provides the constructive orthonormal rank-1 decomposition (TTr1SVD) whose sequence of truncated SVDs is randomized here."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the pass-efficient low-rank approximation scheme used by the RF-KTD variant."},{"cited_title":"Ahmadi-Asl, S","cited_arxiv_id":null,"evidence_quote":"Provides the randomized Tucker/HOSVD algorithm used for the two-stage PT-KTD variant."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines the tensor Kronecker product and the KTD model that the algorithms compute."},{"cited_title":"Ahmadi-Asl, M","cited_arxiv_id":null,"evidence_quote":"Supplies the tensor-completion iterative scheme used in the completion experiments."}],"review_version":1}