acceptodds
Under review as a conference paper at ICLR 2027

Lightweight Representation Learning for Low Tucker Rank Tensors

Abstract

Low Tucker rank tensors provide compact representations of multidimensional dependencies, but standard learning pipelines can incur substantial computational and memory overhead from redundant intermediate quantities. We reduce this overhead without modifying the underlying representation objective or parameterization. Our approach combines three complementary components: (i) sequential extraction of only task-required spectral components, avoiding unnecessary full decompositions; (ii) factor-wise multilinear contractions without materializing large Kronecker operators; and (iii) compact latent-state updates without storing full ambient tensor iterates. These components preserve the algebraic operations and learning trajectories of the original algorithms while reducing their computational and memory footprints. Across five low Tucker rank tensor estimators, our implementations match the original trajectories to numerical precision (relative discrepancies of to ), while reducing per-iteration runtime by up to and resident memory by up to () on the main order-3 benchmark at , with memory reductions exceeding across the full evaluation suite. These results show that substantial computational redundancy can be eliminated from Tucker representation learning without changing the underlying model or learned representation.

Primary area:
unsupervised, self-supervised, semi-supervised, and supervised representation learning
Keywords:
multilinear representation learning, low-rank tensor estimation, Tucker decomposition, computational efficiency

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_yfzFOpenReview ↗
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
  1. 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.
  2. 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
  1. 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.
  2. 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
  1. 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?
  2. 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?
  3. 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?
  4. 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
AuthorsOpenReview ↗

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.

  • Abstract. Rewritten. It drops the ratios against the literal implementation and the exactness range. It now states exactness as an intertwining relation, compares ours with efficient implementations (with the input data counted in the memory), reports two real data sets, and says that memory and time gains need separate conditions.
  • Main text. A new Figure 1 states the conditions for same iterates, less memory and less time. Section 4 now answers three questions: HOOI among 15 HOOI-type methods (4.1), five estimators against efficient public code (4.2), and real data on edge-sized devices (4.3). Section 5 adds "When to use it" and a longer Limitations paragraph. The pseudocode moved to Appendix A.
  • Experiments. Every experiment was re-run on one A100 GPU under one protocol (Appendix F).
  • Ablations. The module-combination ablation of the submitted version (its Table 7) is replaced. Each estimator now runs in one fixed configuration, and we focus the comparison with existing methods on HOOI, which has the most published accelerations: Section 4.1 compares it with 14 other methods, and Table 17 removes one ingredient at a time. The benchmark of Algorithm 1 moved to Appendix I.
  • Supplement. It opens with an Appendix Overview of what each appendix supports. Appendices C.4, F.1, G.1, H, I and J are new; Appendices F and G were rebuilt.

Changes in the Revised Paper

Where each point is addressed:

CommentMain paperSupplement
W1Table 3 (Sec. 4.2); Sec. 4.1 and Figure 2Table 8 (App. G); new App. F.1 (Table 6); new App. H
W2, Q1new Sec. 4.3 and Figure 3new App. G.1 (Tables 14–15)
Q2Contributions (Sec. 1); Definition 1 and Theorem 1; new Figure 1; Sec. 5new App. J (Table 30)
Q3Algorithm 1 and the fixed rule (Sec. 3.1); Sec. 4.1 and Figure 2new App. H; new App. I (Table 29); new App. F.1 (Table 6)
Q4"Protocol" and setup paragraphs (Sec. 4); all tables and figuresrewritten App. F; App. G

Response to Critical Weaknesses

W1. Novelty and Comparisons with Efficient Implementations

  • Novelty. We agree that the three modules rely on established techniques, and the revision no longer claims them as new. Q2 explains what we claim instead.
  • Comparisons. Every estimator is now compared with an efficient public implementation of the same iteration, and HOOI also with 14 other methods, including randomized and sketched ones. Q3 gives the results; the slower cases and their causes are in Section 4.2 and Table 8.

W2. Real-World Data and Consistency

  • Real data. The revision adds a surveillance video and a satellite hyperspectral cube (Section 4.3; Q1).
  • Inconsistencies. We re-ran all experiments under one protocol, and scripts generate every number from the raw logs (Q4).

(Continued in Part 2 of 3.)

AuthorsOpenReview ↗

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 T=20T=20 iterations; we report the median of 3 seeds (Figure 3; Tables 14–15).

  • Video: completion of the Airport Hall surveillance video (144×176×1000144\times176\times1000, p=0.05p=0.05, r=10r=10) with ScaledGD and Frank–Wolfe (HaLRTC in Table 14).
  • Cube: denoising of a HYPSO-1 satellite hyperspectral cube (956×684×120956\times684\times120, SNR 20 dB, r=20r=20) with the subspace norm and HOOI. A second scene gives the same peaks.

Results:

  • Same estimates. Ours agrees with Raw to a relative 2.1×10−122.1\times10^{-12} at 512 fixed positions (4.6×10−74.6\times10^{-7} 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 1.551.55–4.83×4.83\times lower than that of the public implementations and 2.642.64–5.98×5.98\times 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 32×32\times 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 12×12\times less memory beyond the input than the Tensor Toolbox (eig), but it is 2.6×2.6\times slower. With r=20r=20, ours computes an SVD of an nk×400n_k\times400 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 D∘T~=T∘DD\circ\tilde{\mathcal T}=\mathcal T\circ D, the admissible class T\mathfrak T, 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 n=500n=500, 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 n=100n=100 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.)

AuthorsOpenReview ↗

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 n=500n=500, ours is faster and lighter for the subspace norm (3.4×3.4\times faster, 4.0×4.0\times less memory), HOOI (2.4×2.4\times, 2.0×2.0\times) and ScaledGD (1.31.3–3.7×3.7\times, 2.32.3–8.4×8.4\times).
  • It is lighter but slower for Frank–Wolfe (whose public code uses an inexact oracle) and for HaLRTC at p=0.05p=0.05.

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 8003800^3 tensors, every method that is faster than ours is approximate, with at least 7.6×7.6\times 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 n=200n=200 and only for very few triplets (never s>0.05ns > 0.05n). 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 1/κ1/\kappa with κ=100\kappa=100, except for a power law in the separate benchmark of Algorithm 1 (Appendix I).
  • Sampling rates. Every synthetic completion experiment uses p∈0.05,0.2p\in\\{0.05,0.2\\}, and denoising uses SNR 20 dB. The real video uses p=0.05p=0.05, with 0.020.02 and 0.10.1 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 ±\pm s.e. over 5 seeds (Appendices G and H).

We would be glad to answer further questions.

Reviewer_GfecOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
1
Presentation
2
Soundness
1
Read review
Paper summary

The paper is about making existing low Tucker rank tensor estimators cheaper to run, without changing what they compute. Methods such as sum-of-nuclear-norms (SNN), Frank-Wolfe, HOOI, and ScaledGD are often implemented in a direct way. They take full SVDs of every unfolding, build large Kronecker products of the factor matrices, and keep the full tensor iterate in memory at every step. The paper argues that much of this work is redundant.

The method has three parts. First, only the singular vectors that the update actually uses are computed, with a Lanczos (Krylov) partial SVD instead of a full SVD (Algorithm 1). Second, products with Kronecker matrices are done one mode at a time, so the Kronecker matrix is never built (Algorithm 2). Third, the iterate is stored as factors and a core plus a sparse residual on the observed entries, instead of as a full tensor (Algorithm 3). Theorem 1 states that, in exact arithmetic and under spectral gap conditions, the compact iteration gives the same iterates as the reference one. Theorem 2 gives the per-iteration cost and memory of the compact version.

The validation uses synthetic order-3 and order-4 tensors with n up to 120 on one CPU node. Five estimators are compared against a "Raw" implementation that forms full unfoldings and Kronecker operators. The iterates of the two versions agree to near machine precision (Figure 1, Table 5). The best reported gains at n = 100 are about 3x in time per iteration and about 600x in persistent memory, both for HOOI (Table 3). SNN gets no speed-up, and at small n most lightweight variants are slower than Raw.

Critical strengths

S1. A clear, general view of where the cost comes from. The paper separates the cost of one iteration into three sources: unneeded spectral components, Kronecker operators that are built but only applied, and full-size iterates that are fully determined by factors. It then gives one framework (Definition 1 and the intertwining relation in Eq. 1) that covers convex proximal methods, Frank-Wolfe, HOOI, and ScaledGD. The per-estimator states in Appendix C make it easy to see what has to be stored for each method. This is useful for anyone who implements these estimators.

S2. Careful correctness argument and honest discussion of limits. The proofs in Appendix A are complete and easy to follow. The paper states the gap conditions it needs (Proposition 1, Remark 1), explains the finite-precision behavior with Davis-Kahan, and tests exactness directly by running both versions side by side (Section 4.1). Section 5 openly says that SNN gets no speed-up, that the memory gain disappears at high sampling rates, and that the Frank-Wolfe and ADMM states grow over time. This makes it clear when the method helps and when it does not.

Critical weaknesses

W1. The baseline is a deliberately naive implementation, and the components are standard. This is my biggest concern.

  • "Raw" takes a full SVD of each unfolding, forms the Kronecker matrix explicitly, and stores the full iterate (Appendix E.4, Theorem 2). This is not how these estimators are usually implemented. Kolda and Bader (2009), which the paper cites, already compute tensor-times-matrix products mode by mode without forming Kronecker matrices. ScaledGD (Tong et al., 2022) already works on the factors. FFW (Guo et al., 2017) was designed around sparse residuals and rank-one atoms found with power iterations. The sparse-plus-low-rank trick of Algorithm 3 is the Soft-Impute idea of Mazumder et al. (2010), which the paper cites. Partial SVD with Lanczos is what standard routines such as svds or PROPACK provide. So the gains in Table 3 measure the distance from a straw-man version, not from the implementations people actually use.
  • Against this weak baseline the speed-ups are still small. Only HOOI gets a clear gain, Frank-Wolfe is about even, and SNN is slower (Table 3). At n = 50 most lightweight variants are slower than Raw (Table 7).
  • Algorithm 1, one of the three headline components, slows things down in almost every row of Table 7 where it is added. The best runtime configuration is usually "Alg 2 + Alg 3" without it. This conflicts with the claim that the three parts are complementary.
  • The exactness result (Theorem 1) holds by construction. Each step computes the same quantity through a standard algebraic identity, so the decoded iterate must be the same. The proofs are correct, but they do not add new insight beyond these identities. Corollary 1 then restates that the original guarantees still hold, which follows directly.
  • The paper should compare against the efficient public implementations of each estimator (for example the authors' own code for ScaledGD and FFW, or a Tensor Toolbox HOOI with truncated SVD). If the lightweight versions are still clearly faster or smaller than those, the contribution would be much stronger.

W2. The memory and runtime claims are overstated, and the experimental report is not consistent.

  • The headline memory gain counts only the persistent state (Eq. 9, Section 5), not the data or the Krylov workspace. For HOOI in the denoising setting, the input tensor is fully observed and is "not part of the state" (Appendix C.3). That input is the same size as the iterate that Raw stores. So the actual memory needed to run HOOI does not fall by the stated factor. The abstract still calls this "resident memory", while Appendix E.1 says peak memory was measured with getrusage and cudaMemGetInfo. Please report true peak memory including the data and the Krylov scratch, which Appendix B.2 says is not small unless q is much smaller than n.
  • The runtime and memory numbers in the abstract and Table 3 come from different configurations, picked separately for each metric (Table 3 caption, Table 9). For HOOI, the configuration with the best memory is not the one with the best runtime. The headline pair is never achieved by one single method.
  • The Frank-Wolfe atom pool and the HaLRTC multipliers grow with the iteration count (Section 5, Remark 3). The ablation in Table 7 runs only eight iterations, while the protocol in Appendix E.3 allows up to 500. The memory numbers for E1 and E2 are therefore taken before this growth shows.
  • The setup is described in conflicting ways. Appendix E.1 lists an A100 GPU, PyTorch, and CuPy. Section 4.1 mentions single-threaded BLAS, and Table 9 says MATLAB R2025b, single thread. The parameter grids in Section 4.1 and Appendix E.2 also differ (sampling ratios, condition numbers, sizes). Table 6 fits slopes on four sizes and leaves out n = 100. Appendix E.3 says ten seeds with standard errors, but no table or figure shows any spread. Many of the runtime differences are small (for example Frank-Wolfe in Table 3), so without spread it is hard to tell if they are real.
  • The abstract says all five estimators match to the 1e-16 to 1e-13 range. Table 5 marks Frank-Wolfe under the default tolerance as "Fail". The text explains this, but the abstract should state it.
  • The scope is small for the claims. All data are synthetic, n is at most 120, and only one CPU node is used (Section 5). There is no real tensor dataset and no learning task where the "representation" is used. The title and framing as representation learning go beyond what is shown. The work is closer to an efficient numerical implementation of known estimators.
Questions for authors

Clarifications:

Q1. Stronger baselines. Can you compare against efficient existing implementations of each estimator? For example: HOOI with mode-wise products and a truncated SVD, the public ScaledGD code, and the original FFW code. If the lightweight versions still give clear time or memory gains over these, my main concern would be resolved. If the gains disappear, the contribution is mainly the unified framework.

Q2. True peak memory. What is the total peak memory, including the input data (for denoising) and the Krylov workspace, for each estimator in Table 3? How does it compare with Raw on the same terms?

Q3. Single configuration. Can you report one fixed configuration (for example "All") per estimator, with both runtime and memory, instead of picking the best configuration separately for each metric?

Q4. Role of Algorithm 1. In Table 7, adding Algorithm 1 slows down almost every estimator. At what size or spectrum does it start to help? Can you show this with a larger n, or explain why it should be kept as a core component?

Q5. Long runs. How do runtime and memory for Frank-Wolfe and HaLRTC change over the full run up to convergence, not only eight iterations? If periodic re-compression is needed, how much does it change the iterates?

Q6. Experimental setup. Which hardware and software were used for each table: MATLAB single thread, or Python with the GPU listed in Appendix E.1? Please also give one consistent parameter grid, and show the standard errors over the ten seeds mentioned in Appendix E.3.

Minor:

Q7. Section 1 and Theorem 2 say "one polynomial order lower in n", while Section 5 gives a gain of order n squared over q(q + r). Please state clearly which terms dominate for fixed sampling ratio, and why the fitted Raw slopes in Table 6 are well below the predicted exponent.

Q8. The reference list has two entries for the same AAAI 2017 Frank-Wolfe paper (Guo et al., 2017a and 2017b) with different first-author names. Please merge them.

Q9. Will the code be released? The method is an implementation contribution, so the code is central to its value.

3 comments
AuthorsOpenReview ↗

Response to Reviewer Gfec (1/3)

(Part 1 of 3)

We thank the reviewer for the very detailed and 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.

  • Abstract. Rewritten. It drops the ratios against the literal implementation and the exactness range. It now states exactness as an intertwining relation, compares ours with efficient implementations (with the input data counted in the memory), reports two real data sets, and says that memory and time gains need separate conditions.
  • Main text. A new Figure 1 states the conditions for same iterates, less memory and less time. Section 4 now answers three questions: HOOI among 15 HOOI-type methods (4.1), five estimators against efficient public code (4.2), and real data on edge-sized devices (4.3). Section 5 adds "When to use it" and a longer Limitations paragraph. The pseudocode moved to Appendix A.
  • Experiments. Every experiment was re-run on one A100 GPU under one protocol (Appendix F).
  • Ablations. The module-combination ablation of the submitted version (its Table 7) is replaced. Each estimator now runs in one fixed configuration, and we focus the comparison with existing methods on HOOI, which has the most published accelerations: Section 4.1 compares it with 14 other methods, and Table 17 removes one ingredient at a time. The benchmark of Algorithm 1 moved to Appendix I.
  • Supplement. It opens with an Appendix Overview of what each appendix supports. Appendices C.4, F.1, G.1, H, I and J are new; Appendices F and G were rebuilt.

Changes in the Revised Paper

Where each point is addressed:

CommentMain paperSupplement
W1 (baseline, components)Abstract; Contributions (Sec. 1); "Efficient exact HOOI" (Sec. 2); citations (Sec. 3.1)new App. F.1 (Table 6)
W1 (speed-ups)Sec. 4.1 and Figure 2; Table 3 and "Why" (Sec. 4.2); new Figure 1Table 8 (App. G)
W1 (Algorithm 1), Q4fixed rule (Sec. 3.1); Sec. 4.2new App. I (Table 29); Table 17 (new App. H)
W1 (Theorem 1)Definition 1; Theorem 1; Corollary 1; Limitations (Sec. 5)proof of Corollary 1 (App. B.6); App. D; new App. J
W1 (public code), Q1Table 3 (Sec. 4.2); Sec. 4.1 and Figure 2new App. F.1; new App. H
W2 (peak memory), Q2Abstract; Theorem 2 (Sec. 3.2); Table 3; Sec. 4.1memory measurement (App. F); Table 7 (App. G); App. C.2
W2 (one configuration), Q3Abstract; Contributions (Sec. 1); Sec. 3.1Table 6 (App. F.1); Table 17 (App. H)
W2 (state growth), Q5Limitations (Sec. 5)App. D
W2 (setup), Q6"Protocol" (Sec. 4)rewritten App. F; Table 5 (new App. C.4); mean ± s.e. in Apps. G and H
W2 (exactness range)Abstract; Table 2 (Sec. 4)–
W2 (scope and framing)Sec. 1 (after the contributions); new Sec. 4.3 and Figure 3; Sec. 4.1new App. G.1; new App. J
Q7Sec. 3.2 and Theorem 2App. C.1; new App. C.4 (Table 5)
Q8References–
Q9Reproducibility Statement–

Response to Critical Weaknesses

W1. Baseline and Components

  • Baseline. We agree. Every claim in the abstract and the conclusion now compares ours with efficient public implementations (Q1). Ratios against Raw remain in the tables only for reference.
  • Components. We no longer present them as new, and we cite each where we use it: mode-wise products (Kolda and Bader), factor-based ScaledGD, the sparse residual and rank-one atoms of FFW, Soft-Impute, and Lanczos partial SVD (ARPACK/PROPACK). Our contribution is a correctness condition and a measurement of where it pays off (Figure 1).
  • Speed-ups. This is still partly true, and the revision says so: memory is now the main claim. Q1 gives the time results.
  • Algorithm 1. We agree and changed the method. A fixed rule uses Algorithm 1 only for matrices given as implicit operators; explicit matrices get a dense SVD (Section 3.1; Q4). We no longer claim that the three components help in every case.
  • Theorem 1. We agree that each step is a standard identity, and we no longer present the theorem as a deep result.
    • Its role is to state when the combined rewritings keep the whole trajectory (the class T\mathfrak T and the spectral gap of Proposition 1), and where they do not apply.
    • Corollary 1 follows directly. The Limitations paragraph now says that the framework gives no new statistical or convergence result.
    • Corollary 1 (ii) no longer claims that the savings add up with sketching or preconditioning.

(Continued in Part 2 of 3.)

AuthorsOpenReview ↗

Response to Reviewer Gfec (2/3)

(Part 2 of 3)

W2. Claims and Experimental Report

  • Peak memory. We agree. All memory numbers are now measured peak GPU memory, including the input data and the Krylov and cuBLAS/cuSOLVER workspaces (Appendix F). The term "resident memory" is gone.
    • For HOOI denoising, the gain against Raw falls to about 4×4\times at n=500n=500 (3,864 MiB vs. 970 MiB, Table 7). The earlier 616×616\times compared persistent states only.
    • Theorem 2 now says that, at a fixed pp, the sparse state is smaller than an ambient array only if (N+1)p<1(N+1)p < 1, and its peak bound includes the O(N∣Ω∣)O(N|\Omega|) index structures.
    • Our implementation uses about 15 words per observed entry (Appendix C.2), which is why the gain shrinks at p=0.2p=0.2.
  • One configuration. Each estimator uses one fixed configuration, and time and memory come from the same runs (Q3).
  • State growth. We agree; we did not resolve it with experiments (Q5).
  • Setup. We could not match the submitted tables to raw logs, so we re-ran every experiment under one protocol and replaced all tables and figures (Q6, Q7). The parameter grid is:
    • order-3 synthetic tensors with r=5r=5 and spectra decaying geometrically to 1/κ1/\kappa, κ=100\kappa=100 (a power law only in Appendix I);
    • completion at p∈0.05,0.2p\in\\{0.05,0.2\\}, denoising at SNR 20 dB;
    • nn from 100 to 500; up to 1000 for HOOI, and order 4 up to 80480^4 with r=3r=3.
  • Exactness range. The abstract no longer states a range. Section 4 reports the largest difference over the five estimators: 5.2×10−145.2\times10^{-14} with a tight Krylov tolerance and 9.5×10−119.5\times10^{-11} with the default one (Table 2). It also says that the public Frank–Wolfe code follows a different trajectory, because its oracle is an inexact power method.
  • Scope and framing.
    • We added two real data sets (Section 4.3): a surveillance video and a satellite hyperspectral cube. Only ours fits a 1 GiB device (video) and a 4 GiB device (cube). Synthetic tensors now reach 10910^9 entries.
    • The learned representation is the Tucker representation (factor matrices and core), used for completion and denoising. We propose no new model, and Section 1 now says so.
    • By Theorem 1, ours obtains the same representation with less memory and, in some cases, in less time.

Response to Questions

Q1. Stronger Baselines

Yes (Sections 4.1–4.3; Table 6).

  • Comparators. For HOOI: TensorLy, Tensor Toolbox tucker_als (dense eig or iterative eigs on the Gram matrix), HOQRI and nine approximate methods. For the other estimators: ports of the authors' codes for ScaledGD, FFW, HaLRTC and the subspace-norm ADMM.
  • Memory. Clear gains for all five estimators, but not for every further estimator (Appendix J).
  • Time. At n=500n=500, ours is faster than the public code for the subspace norm (3.4×3.4\times), HOOI (2.4×2.4\times) and ScaledGD (1.31.3–3.7×3.7\times). Against the fastest exact HOOI implementations, it is about as fast, and the fastest only on the two largest sizes (1.12×1.12\times and 1.05×1.05\times).
  • Losses. HaLRTC at p=0.05p=0.05, Frank–Wolfe (whose public code uses an inexact oracle) and small problems are slower (Table 8).

Where the gains disappear, we say so, and we present the contribution as the framework and the measurement of where it pays off (Figure 1, Table 8).

Q2. True Peak Memory

Table 3 gives the ratios at n=500n=500, with the input data included, and Table 7 the absolute values.

EstimatorRaw / ours
Subspace norm4.0×4.0\times
HaLRTC1.03×1.03\times (p=0.05p=0.05), 1.96×1.96\times (p=0.2p=0.2)
Frank–Wolfe6.5×6.5\times, 3.3×3.3\times
HOOI4.0×4.0\times
ScaledGD7.2×7.2\times, 2.0×2.0\times

Public / ours: 1.21.2–8.4×8.4\times.

Q3. Single Configuration

Yes. Every table and figure uses one fixed configuration per estimator (Table 6), with runtime and memory from the same runs. The effect of removing one ingredient is reported separately for HOOI (Table 17).

(Continued in Part 3 of 3.)

AuthorsOpenReview ↗

Response to Reviewer Gfec (3/3)

(Part 3 of 3)

Q4. Role of Algorithm 1

We keep Algorithm 1 only where the matrix is an implicit operator, so that a dense SVD would first have to form a large unfolding. A microbenchmark (Appendix I, Table 29; 120 runs) shows the crossover:

  • Size. It beats a dense SVD only from n=200n=200.
  • Required triplets. Only very few: in 30 of the 32 faster cases s≤5s\le5, and never s>0.05ns > 0.05n. At s=1s=1 and n=500n=500, it is 4.44.4–12.7×12.7\times faster, with 5.55.5–8.2×8.2\times less memory. For s≥n/2s\ge n/2, it is 1010–51×51\times slower.
  • Spectrum. It matters less than ss. With a power law, the faster range reaches s=0.05ns=0.05n for the explicit matrix.
  • Small explicit matrices (as in HOOI). The dense SVD is always faster (66–16×16\times; 2.0×2.0\times in the ablation, Table 17).

The Frank–Wolfe oracle (s=1s=1) benefits. HaLRTC at p=0.05p=0.05 needs about 280 of 300 triplets per mode; it is the one case in which the rule picks the slower option.

Q5. Long Runs

We have not run Frank–Wolfe and HaLRTC to convergence; our runs stop after at most 20 iterations, as the Limitations paragraph says.

  • The Frank–Wolfe pool gains one atom per iteration.
  • Our HaLRTC keeps the dual variables in ambient form. This bounds them but costs (N+1)nˉ(N+1)\bar n words from the start.
  • Periodic recompression would change the reference iteration, so we do not use it and did not measure its effect.

Q6. Experimental Setup

One setup is used throughout (Appendix F):

  • Hardware. One NVIDIA A100-SXM4-40GB (A100-SXM4-80GB for Appendix J).
  • Software. PyTorch 2.14.1 (CUDA 13.0), float64, TF32 disabled. The public MATLAB codes were ported.
  • Timing. A fresh process per run, and torch.cuda.synchronize() before every clock reading.
  • Grid. See W2 (Setup).
  • Seeds. For synthetic data, absolute values are mean ±\pm s.e. over 5 seeds, and Table 7 marks differences within two s.e. The real data report the median of 3 seeds. We corrected the statement of ten seeds.

Q7. Dominant Terms and Fitted Slopes

  • Which term dominates. At a fixed pp, the term (q+rN),p,nN(q+r^N)\\,p\\,n^N dominates (Section 3.2, Appendix C.4). One iteration costs Θ((q+rN),p,nN)\Theta((q+r^N)\\,p\\,n^N), against Ω(nN+1)\Omega(n^{N+1}) for the literal baseline.
  • This is one order lower in nn only if qq does not grow with nn, as Theorem 2 now states. HaLRTC at p=0.05p=0.05 has q≈nq\approx n.
  • The gain n2/(q(q+r))n^2/(q(q+r)) needs ∣Ω∣=O(nN−1)|\Omega|=O(n^{N-1}).
  • For denoising, contracting the data (Θ(r,nN)\Theta(r\\,n^N)) dominates. For the subspace norm, HOOI and ScaledGD, every implementation scales as nNn^N, and the gain is a constant factor.
  • Fitted slopes. We could not reproduce the fitted-slope table from raw logs, so we replaced it with local slopes for n=200n=200–700 (Table 5). For Raw HaLRTC and Frank–Wolfe, the slopes rise from 2.2–2.3 (n=200→300n=200\to300) to 3.25–3.28 (500→700500\to700), against an exponent of 4. A fit t=c0+c3n3+c4n4t=c_0+c_3n^3+c_4n^4 explains why: the n4n^4 SVD overtakes the n3n^3 dense operations only at n≈555n\approx555–722. Where the order is lowered, ours has the smaller slope.

Q8. Duplicate Reference

We merged the two entries into one (Guo, Yao and Kwok, AAAI 2017).

Q9. Code Release

Yes. We will release all code upon acceptance (estimators, ports of the public codes, and scripts for measurement and tables), as the Reproducibility Statement says. Scripts generate every number in Section 4 from the raw JSON logs.

We would be glad to answer further questions.

Reviewer_QpPKOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper addresses the computational and memory redundancies inherent in low-Tucker-rank tensor estimation by proposing a lightweight implementation framework. The framework consists of three primary components: selective singular value extraction, implicit multilinear contraction, and compact state storage. The authors further demonstrate the iterative equivalence between this lightweight implementation and the corresponding reference algorithms. Experiments were conducted using five tensor estimation algorithms: Subspace Norm, SNN/HaLRTC, Frank–Wolfe, HOOI, and ScaledGD.

Critical strengths
  1. The paper identifies redundancies—such as full SVD computations, explicit Kronecker operators, and the storage of large intermediate tensors—within low-Tucker-rank tensor estimation, offering valuable insights for large-scale tensor computations.
  2. The authors provide a proof of iterative equivalence, analyze the computational and memory complexity per iteration, and employ ablation studies to evaluate the contribution of each individual module.
Critical weaknesses
  1. The core methodology lacks significant innovation; the primary contribution is more akin to a combination of existing techniques and implementation-level optimizations.
  2. The experiments rely primarily on synthetically generated low-Tucker-rank tensors. The use of third-order tensors in the main experiments is insufficient to fully demonstrate the framework's effectiveness for real-world, large-scale tensor tasks.
  3. Improvements in actual runtime are inconsistent, with the maximum speedup being highly dependent on the specific algorithm.
  4. The "naive" implementation used for comparison may not be the most competitive baseline; benchmarking solely against implementations that explicitly construct large intermediate tensors could exaggerate the perceived performance gains.
Questions for authors
  1. It is unclear which experiments correspond to the various sampling ratios mentioned in the main text versus the appendix. It is recommended to clarify and standardize the experimental configurations and baseline implementations.
  2. Could the framework be evaluated on larger-scale tensors, real-world datasets, and data with varying spectral distributions to further substantiate its benefits?
2 comments
AuthorsOpenReview ↗

Response to Reviewer QpPK (1/2)

(Part 1 of 2)

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.

  • Abstract. Rewritten. It drops the ratios against the literal implementation and the exactness range. It now states exactness as an intertwining relation, compares ours with efficient implementations (with the input data counted in the memory), reports two real data sets, and says that memory and time gains need separate conditions.
  • Main text. A new Figure 1 states the conditions for same iterates, less memory and less time. Section 4 now answers three questions: HOOI among 15 HOOI-type methods (4.1), five estimators against efficient public code (4.2), and real data on edge-sized devices (4.3). Section 5 adds "When to use it" and a longer Limitations paragraph. The pseudocode moved to Appendix A.
  • Experiments. Every experiment was re-run on one A100 GPU under one protocol (Appendix F).
  • Ablations. The module-combination ablation of the submitted version (its Table 7) is replaced. Each estimator now runs in one fixed configuration, and we focus the comparison with existing methods on HOOI, which has the most published accelerations: Section 4.1 compares it with 14 other methods, and Table 17 removes one ingredient at a time. The benchmark of Algorithm 1 moved to Appendix I.
  • Supplement. It opens with an Appendix Overview of what each appendix supports. Appendices C.4, F.1, G.1, H, I and J are new; Appendices F and G were rebuilt.

Changes in the Revised Paper

Where each point is addressed:

CommentMain paperSupplement
W1Contributions (Sec. 1); new Figure 1; "When to use it" (Sec. 5)new App. J (Table 30)
W2new Sec. 4.3 and Figure 3; Sec. 4.1 and Figure 2new App. G.1 (Tables 14–15); new App. H
W3Abstract; Table 3 and "Why" (Sec. 4.2); Figure 1; Sec. 5Table 8 (App. G)
W4Table 3 (Sec. 4.2); Sec. 4.1 and Figure 2new App. F.1 (Table 6); new App. H
Q1"Protocol" and setup paragraphs (Sec. 4)rewritten App. F; new App. C.4
Q2Secs. 4.1 and 4.3; Limitations (Sec. 5)new App. I (Table 29); new App. G.1

Response to Critical Weaknesses

W1. Methodological Novelty

We agree that each component is a known technique. The revision says so and cites each one (Section 1). We claim two other things:

  • A correctness condition (Definition 1, Theorem 1). The intertwining relation D∘T~=T∘DD\circ\tilde{\mathcal T}=\mathcal T\circ D and the class T\mathfrak T tell when these rewritings keep the iterates unchanged. Then all guarantees of the original estimator carry over. The condition also shows where the rewritings do not apply.
  • A measurement against efficient implementations of where this saves memory, where it also saves time, and why (Tables 3 and 8, new Figure 1).

We also tested these conditions on eight further estimators, with predictions fixed in advance (Appendix J). They are necessary but not sufficient for a gain, and the revision now says so. The correctness condition held for all eight: final errors agree to a relative 5.5×10−95.5\times10^{-9}.

W2. Real-World and Large-Scale Evaluation

The revision adds three things:

  • Two real data sets (Section 4.3): completion of a surveillance video (144×176×1000144\times176\times1000, p=0.05p=0.05) and denoising of a satellite hyperspectral cube (956×684×120956\times684\times120). Ours gives the same estimates as Raw, with 1.551.55–4.83×4.83\times less peak memory (input included) than the public implementations. Only ours fits a 1 GiB device (video) and a 4 GiB device (cube).
  • Larger tensors: order 3 up to 100031000^3 (the submitted version stopped at n=120n=120).
  • Order-4 tensors up to 80480^4 (Section 4.1, Appendix H).

W3. Runtime Improvements

We agree, and the revision says so (Section 4.2, Table 8). Memory is now the main claim; the abstract and the conclusion present runtime gains as conditional.

  • Ours is faster when the comparator builds objects that ours never builds: the subspace norm, HOOI and ScaledGD at n=500n=500 (numbers in W4).
  • Ours is slower in four cases:
    • an update needs nearly all singular triplets (HaLRTC at p=0.05p=0.05: 55×55\times);
    • the comparator computes a different iteration (the public Frank–Wolfe code uses an inexact oracle);
    • the problem is small (up to 1.4×1.4\times at n=100n=100);
    • on the cube, the Gram eigensolver of the Tensor Toolbox is faster (2.6×2.6\times).

(Continued in Part 2 of 2.)

AuthorsOpenReview ↗

Response to Reviewer QpPK (2/2)

(Part 2 of 2)

W4. Competitive Baselines

We agree. All headline numbers now compare ours with efficient implementations (Table 3; codes in Table 6).

  • At n=500n=500, ours is faster and lighter for the subspace norm (3.4×3.4\times faster, 4.0×4.0\times less memory), HOOI (2.4×2.4\times, 2.0×2.0\times) and ScaledGD (1.31.3–3.7×3.7\times, 2.32.3–8.4×8.4\times).
  • It is lighter but slower for Frank–Wolfe and for HaLRTC at p=0.05p=0.05.
  • Among 15 HOOI-type methods (Section 4.1), ours needs the least memory at every size: 1.21.2–121×121\times less beyond the input than the lightest exact method. HOQRI is up to 1.5×1.5\times faster on smaller order-3 tensors.

Response to Questions

Q1. Experimental Configurations

We agree that the submitted version was inconsistent (Section 4.1 vs. Appendix E.2), and we could not trace its numbers back to raw logs. We therefore re-ran every experiment under one protocol and replaced all tables and figures (Appendix F): one A100 GPU, float64, and peak memory including the input data. Scripts generate every number from the raw logs.

Experimentpp or noisennSeeds
HOOI vs. 14 other methods (Sec. 4.1)SNR 20 dB100–1000; order 4: 20–805
Five estimators (Sec. 4.2)completion: p∈0.05,0.2p\in\\{0.05,0.2\\}; denoising: SNR 20 dB100–5005
Measured exponents (App. C.4)as in Sec. 4.2200–7003
Algorithm 1 vs. dense SVD (App. I)SNR 20 dB; p∈0.05,0.2p\in\\{0.05,0.2\\}50–5003
Eight further estimators (App. J)p∈0.05,0.2p\in\\{0.05,0.2\\}100–5005
Real data (Sec. 4.3)video: p=0.05p=0.05 (also 0.020.02, 0.10.1 in App. G.1); cube: SNR 20 dB–3
  • Spectra. Synthetic spectra decay geometrically (κ=100\kappa=100), except for a power law in Appendix I.
  • Baselines. In Sections 4.2 and 4.3, Raw, Public and ours run the same iteration with the same initialization and hyperparameters.
  • Spread. For synthetic data, absolute values are mean ±\pm s.e. over seeds (Appendices G and H).

Q2. Additional Evaluations

  • Larger tensors and real data: yes; see W2.
  • Other spectra: partly. Algorithm 1 is the component whose cost depends on the spectrum, and Appendix I also tests it on a power law σi=1/i\sigma_i=1/i. The number ss of needed triplets matters more than the spectrum: with the power law, Algorithm 1 beats a dense SVD up to s=0.05ns=0.05n for the explicit matrix; otherwise only up to s≤5s\le5.
  • Real data have their own spectra, and their gains and losses follow the same pattern (Table 8).
  • A sweep over spectra for whole estimators is left for future work (Limitations, Section 5).

We would be glad to answer further questions.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.