- Rating
- 2
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 3
Read review
Paper summary
This paper proposes a lightweight implementation framework for low Tucker rank tensor estimation without changing the underlying optimization objectives or reference algorithms. The approach combines selective extraction of singular components, implicit multilinear contractions that avoid explicit Kronecker products, and compact state representations based on tensor factors and sparse residuals. The experimental results report reduced computational costs and memory consumption while largely maintaining numerical agreement with the original implementations.
Critical strengths
- The paper provides a practical approach to reducing computational and memory overhead without modifying the underlying optimization objectives. The theoretical analysis and numerical validation of trajectory preservation help support the correctness of the proposed computational reformulations.
- The approach is evaluated across five representative tensor estimators, covering different optimization paradigms. The component-wise ablation studies provide useful insights into the computational benefits and limitations of the individual modules.
Critical weaknesses
- The methodological novelty is limited, as the three proposed modules primarily rely on established numerical techniques and algebraic reformulations. Moreover, the experiments mainly compare the proposed implementations with raw baselines and different internal module combinations, without sufficient comparisons against existing efficient implementations. This makes it difficult to establish the additional methodological and computational contributions of the proposed approach.
- The experimental validation is insufficient, as all evaluations are conducted on synthetic datasets without real-world experiments. In addition, several inconsistencies in the experimental settings and reported results raise concerns about the clarity and reproducibility of the evaluation. These limitations weaken the empirical support for the claimed practical effectiveness.
Questions for authors
- The paper only evaluates the proposed approach on synthetic datasets, without providing any validation on real-world data. Although synthetic experiments allow for controlled evaluations, they may not adequately reflect the complexity and characteristics of practical applications. Consequently, it remains unclear whether the reported computational and memory improvements can be achieved on real-world datasets. Could the authors provide experimental results on real-world datasets to demonstrate the practical effectiveness of the proposed approach?
- The methodological novelty of the proposed approach appears somewhat limited. Algorithm 1 employs iterative partial SVD to compute only the required singular components, which is a well-established technique in previous studies. Algorithm 2 mainly rearranges tensor computations through sequential mode-wise contractions to avoid explicitly constructing Kronecker products, while Algorithm 3 reformulates the updates using factorized representations and sparse residuals instead of materializing full tensor iterates. These modules appear to be primarily algebraic reformulations and computational tricks for reducing redundant operations, rather than a fundamentally new algorithmic framework or methodology. Could the authors further clarify the methodological novelty of these modules beyond existing computational techniques?
- The experiments mainly compare different combinations of the authors' three modules and their performance against the raw implementations of existing methods. While these comparisons demonstrate the benefits of the proposed implementation, they do not establish whether it outperforms existing acceleration techniques that employ similar computational strategies. For example, Algorithm 1 is not directly compared with existing efficient partial SVD or Lanczos-based implementations. Could the authors provide comparisons with existing efficient implementations to better demonstrate the advantages of the proposed acceleration techniques?
- There are several inconsistencies in the experimental descriptions and reported results across different sections of the paper. For example, Section 4.1 describes geometrically decaying singular values, whereas Appendix E.2 specifies power-law decay, and the sampling ratios reported in these sections also differ. In addition, the runtime and memory results for ScaledGD in Tables 3 and 9 differ from those in Figure 2 and Table 7, despite apparently similar experimental configurations. The authors should clarify whether these discrepancies arise from differences in experimental settings or errors in reporting the results. Could the authors provide further details on the experimental configurations to explain these inconsistencies?
5 comments
Response to Reviewer yfzF (2/3)
(Part 2 of 3)
Response to Questions
Q1. Real-World Data
Yes. The new Section 4.3 uses two real data sets of a kind often recorded on devices that lack the storage and computation for low-rank recovery. All runs use an A100 in float64 with iterations; we report the median of 3 seeds (Figure 3; Tables 14–15).
- Video: completion of the Airport Hall surveillance video (, , ) with ScaledGD and Frank–Wolfe (HaLRTC in Table 14).
- Cube: denoising of a HYPSO-1 satellite hyperspectral cube (, SNR 20 dB, ) with the subspace norm and HOOI. A second scene gives the same peaks.
Results:
- Same estimates. Ours agrees with Raw to a relative at 512 fixed positions ( for Frank–Wolfe). The PSNR is the same: 33.89 dB (HOOI) and 35.60 dB (subspace norm) on the cube, and 19.40 dB (ScaledGD) on the unobserved video entries.
- Less memory. Peak memory, including the input data, is – lower than that of the public implementations and – lower than that of Raw. For example, the subspace norm needs 2.46 vs. 11.90 GiB, and ScaledGD 0.39 vs. 1.21 GiB.
- Time per iteration. Ours is faster than the public code for ScaledGD (3.7 vs. 5.9 ms), HOOI (81.0 vs. 90.2 ms) and the subspace norm (191 vs. 302 ms).
- Edge-sized devices. Counting the 0.52 GiB held outside the PyTorch allocator, only ours fits a 1 GiB device (video) and a 4 GiB device (cube). Under allocator caps of these sizes, the other implementations run out of memory (Table 15).
- Losses.
- Frank–Wolfe is slower than the public code, whose oracle is inexact.
- HaLRTC is not lighter and is much slower, because its iterates are nearly full rank.
- Among the HOOI-type methods on the cube, ours needs less memory beyond the input than the Tensor Toolbox (
eig), but it is slower. With , ours computes an SVD of an matrix per mode, whereas the Tensor Toolbox applies a symmetric eigensolver to the Gram matrix (Table 8).
Q2. Methodological Novelty
We agree that the modules themselves are established, and we cite each (Sections 1–3):
- Algorithm 1 is a Lanczos partial SVD (ARPACK/PROPACK);
- Algorithm 2 is mode-wise contraction with reuse of partial contractions (dimension trees);
- Algorithm 3 is the sparse-plus-low-rank state of Soft-Impute.
What is new:
- A correctness condition (Definition 1, Theorem 1, Proposition 1): the intertwining relation , the admissible class , and a gap condition that states which triplets an update needs. It tells when combining the modules keeps the iterates of a given estimator unchanged, so that all its guarantees carry over. It also marks the estimators for which the modules would change the result.
- A fixed rule for where Krylov extraction is used (Section 3.1; Q3).
- A measurement of where this pays off against efficient implementations, and why (Figure 1, Table 8).
We also tested the conditions from the five estimators on eight further estimators, with predictions fixed in advance (Appendix J, Table 30).
- As predictors of gains, they failed. At , the memory condition failed in 6 of 16 cases, and only 8 of 16 speed predictions were correct.
- As predictors of losses, they held. Ours was never faster for or for nearly full-rank updates (0 of 28 cases).
- The revision therefore states them as necessary, not sufficient, conditions (Figure 1, Section 5).
- The correctness condition held for all eight: their lightweight versions reproduce the reference iterates.
(Continued in Part 3 of 3.)
Response to Reviewer yfzF (3/3)
(Part 3 of 3)
Q3. Comparison with Efficient Implementations
Yes. Each of the five estimators runs in three implementations of the same iteration, with the same initialization and hyperparameters: Raw (literal), Public (a port of the authors' code or a standard library; Table 6) and ours (one fixed configuration). Every claim in the abstract and the conclusion compares ours with Public (Table 3).
- At , ours is faster and lighter for the subspace norm ( faster, less memory), HOOI (, ) and ScaledGD (–, –).
- It is lighter but slower for Frank–Wolfe (whose public code uses an inexact oracle) and for HaLRTC at .
Similar acceleration techniques are part of the HOOI comparison (Section 4.1, Appendix H): the Tensor Toolbox with an iterative eigensolver (eigs), randomized range finders (RandHOSVD, RandST-HOSVD), sketched ALS (TUCKER-TS, TUCKER-TTMTS), one- and two-pass sketches, and the slice-compressed D-Tucker. Ours needs the least memory of all 15 methods at every size. On tensors, every method that is faster than ours is approximate, with at least the error of HOOI.
Algorithm 1 itself is a standard Lanczos partial SVD (Golub–Kahan–Lanczos bidiagonalization with early stopping, Section 3.1), the method behind svds (ARPACK, PROPACK). We do not claim that it is faster than these routines on the same matrix. Its benefit is that it works on an implicit operator, a sparse residual plus factored terms. Products with this operator cost far less than forming the unfolding that svds would need first (Eq. 3). A benchmark against a dense SVD (Appendix I, Table 29) shows that this pays off only from and only for very few triplets (never ). The fixed rule therefore uses a dense SVD whenever the matrix is small and explicit.
Q4. Experimental Consistency
Thank you for pointing these out. We could not trace the submitted numbers back to raw logs, so we could not find the cause of each discrepancy. Instead, we re-ran every experiment under one protocol and replaced all tables and figures (Appendix F).
- One setup. One A100 GPU (40 GiB; 80 GiB for Appendix J), PyTorch, float64, TF32 disabled, one process per run, and synchronized timing. Memory is the peak GPU memory, including the input data and all workspaces.
- Spectrum. Every synthetic tensor has spectra that decay geometrically from 1 to with , except for a power law in the separate benchmark of Algorithm 1 (Appendix I).
- Sampling rates. Every synthetic completion experiment uses , and denoising uses SNR 20 dB. The real video uses , with and in Appendix G.1.
- ScaledGD. All ScaledGD numbers of one comparison come from the same runs, and scripts generate every number from the raw logs.
- Spread. For synthetic data, absolute values are mean s.e. over 5 seeds (Appendices G and H).
We would be glad to answer further questions.
Response to Reviewer yfzF (1/3)
(Part 1 of 3)
We thank the reviewer for the constructive feedback. We address the critical weaknesses and questions below. All section, figure and table numbers refer to the revised PDF.
Overview of the Revision
This overview is the same for all reviewers.
Changes in the Revised Paper
Where each point is addressed:
Response to Critical Weaknesses
W1. Novelty and Comparisons with Efficient Implementations
W2. Real-World Data and Consistency
(Continued in Part 2 of 3.)