A Tight Lower Bound for the Approximation Guarantee of Higher-Order Singular Value Decomposition

Matthew Fahrbach; Mehrdad Ghadiri

A Tight Lower Bound for the Approximation Guarantee of Higher-Order Singular Value Decomposition

T0 review · 2 major / 2 minor · reviewed 2026-08-05 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The paper constructs tensors that force HOSVD to achieve its worst-case approximation ratio, proving the classic guarantee cannot be improved.

desk verdict If the construction's optimal-Tucker-error computation is right, this closes a 20-year gap with a clean tightness result for HOSVD, ST-HOSVD, and HOOI; the proof, not the abstract, is where the work lives. read the letter →

arxiv 2508.06693 v1 pith:JI7FH3XC submitted 2025-08-08 cs.DS cs.LG

Matthew Fahrbach , Mehrdad Ghadiri This is my paper · ORCID

classification cs.DScs.LG

keywords higher-ordersingularvaluedecompositionHOSVDapproximationratiotightlowerboundtensorST-HOSVDHOOI

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper sets out to prove that the classic approximation guarantee of the higher-order singular value decomposition (HOSVD) cannot be improved. It does this by constructing tensors for which HOSVD's approximation ratio is exactly $N/(1+\varepsilon)$ for any desired $\varepsilon>0$, matching the known upper bound. The same construction strategy is then extended to two related algorithms, ST-HOSVD and HOOI, showing their worst-case guarantees are also tight. If the constructions are valid, the decades-old bound is not just an artifact of the proof technique but a fundamental limit of these methods.

What carries the argument

The central object is a carefully chosen tensor whose mode-n unfoldings have a singular-value profile that makes every truncated step of HOSVD lose exactly the right amount of energy. By controlling the singular values to be equal within groups or otherwise clustered, the construction forces the final approximation error to be $N/(1+\varepsilon)$ times the optimal low-multilinear-rank error.

What would settle it

Run HOSVD on a family of tensors with varying rank parameters and find one whose approximation ratio is strictly below $N/(1+\varepsilon)$ for some $\varepsilon>0$ under the same metric, or prove that a tensor family with the required unfolding singular-value structure cannot exist for all $\varepsilon>0$.

Watch

Extended reading notes

Core claim

The central claim is a worst-case lower bound: for any tensor order $N$ and any $\varepsilon>0$, there exists an $N$-way tensor whose HOSVD approximation has ratio at least $N/(1+\varepsilon)$ compared to the best rank-$(R_1,\dots,R_N)$ approximation. Since the upper bound established in earlier work says the ratio never exceeds this value, the matching construction proves the bound is tight. The authors further adapt the construction to show the same worst-case ratio is achieved by ST-HOSVD and HOOI. The construction works by arranging the tensor's mode-n unfoldings so that the truncated HOSVD keeps a specific amount of energy, forcing the error to sit exactly at the desired ratio.

Load-bearing premise

The load-bearing premise is that for every $\varepsilon>0$ there exists a tensor with the required multilinear ranks and mode-n unfolding singular values; if no such tensor exists for some combination of order and target ratio, the lower bound does not follow.

Editorial extensions

If this is right

HOSVD's approximation ratio is tight in the worst case; no algorithm in the same class that relies only on this guarantee can be improved by a constant factor.
ST-HOSVD and HOOI also have tight worst-case guarantees, so their known bounds are optimal.
Any future improvement must either change the algorithm family or exploit structure beyond the worst-case.
Practitioners can expect that for adversarial tensors the error will approach the proven ratio.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The construction likely uses tensors with vanishing gaps between certain singular values, suggesting that slightly perturbed real-world tensors might also approach the bound in practice.
The technique may transfer to other tensor formats, such as Tucker decompositions with different truncation rules, to settle their worst-case ratios.
It raises the question of whether randomized or adaptive HOSVD variants can evade the lower bound in expectation or with high probability.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

You should know this paper claims to close a gap open since 2000: proving that HOSVD's N/(1+ε) approximation guarantee is tight, and extending the same tightness to ST-HOSVD and HOOI. The abstract is the only part I can see, so I can't verify the math, but the claim itself is exactly the sort of result that matters to the tensor approximation community.

What's genuinely new: no one has shown a matching lower bound for these algorithms before. The authors name the prior upper bounds and state they construct tensors that achieve the worst-case ratio for any ε > 0. That's a standard and honest way to prove tightness—no fitted parameters, no circularity. If the construction works, it's a definitive answer to a known theoretical question.

The soft spot, and it's the load-bearing one, is the computation of the optimal rank-(R1,...,RN) Tucker error for the constructed tensor. Computing the best Tucker approximation for a general tensor is NP-hard, so the construction must be special enough to make that error analytically tractable. The stress-test note is right: even with orthogonal rank-1 components, a non-coordinate subspace or an off-diagonal core could potentially beat the claimed error. The proof has to show that the mode-wise truncation is genuinely optimal, not just assume it. The abstract says the construction has a 'prescribed singular value structure,' but gives no details. Also the ε-dependence needs care; the ratio goes to N from below, so you need to show the construction produces a tensor that works for every ε > 0 with dimensions that actually admit the required ranks.

I'm not saying the proof is wrong. The reader's low soundness score is about the lack of evidence, not a detected error—and that's the right reading. The stress-test concern may well dissolve once you see the construction, but you can't tell from the abstract. This is a theorem paper; correctness lives entirely in the inequalities.

The paper is for researchers in tensor decompositions and approximation theory, people who care about worst-case guarantees for HOSVD and its variants. I'd bring it to a theory reading group, and if the result holds up it deserves citation. It absolutely deserves a serious referee: it's a named, open gap, and even a skeptical editor should send it out. The referee should ask for explicit verification of the optimal Tucker error and the ε-scaling; if those are airtight, the result stands.

Referee Report

2 major / 2 minor

Summary. The paper claims to prove that the classical approximation guarantee for the higher-order singular value decomposition (HOSVD) is tight: for any ε>0, it constructs a tensor for which HOSVD attains approximation ratio N/(1+ε), matching the upper bound of De Lathauwer et al. (2000a). The abstract further claims that the same worst-case ratio is achievable for ST-HOSVD (Vannieuwenhoven et al., 2012) and HOOI (De Lathauwer et al., 2000b), thereby showing their guarantees are also tight. The result is presented as a formal theorem, with the proof based on explicit tensor constructions with prescribed singular-value structures.

Significance. If the proof is correct, the paper closes an important gap in tensor approximation theory by showing that the well-known HOSVD approximation ratio cannot be improved in the worst case. The construction-based approach is appropriate for a lower bound, and the reliance on the existing upper bound is non-circular. The extension to ST-HOSVD and HOOI is a valuable addition. However, because only the abstract was available for review, the central proof—especially the exact computation of the optimal rank-(R1,...,RN) error of the constructed tensor—could not be audited. The significance is therefore conditional on the full proof being correct.

major comments (2)

[Abstract] The load-bearing step is the exact computation of the optimal rank-(R1,...,RN) approximation error for the constructed tensor. The abstract states the construction and the resulting ratio N/(1+ε), but it does not provide the precise singular-value structure, the rank parameters, or the error inequalities. Since finding the best Tucker approximation is NP-hard in general, the proof must explicitly show that no non-coordinate Tucker subspace achieves an error smaller than the claimed optimal value. If the proof implicitly assumes that mode-wise truncation in the component basis gives the optimal error without justification, the announced lower bound may overestimate the true worst-case ratio. This step is not auditable from the abstract alone.
[Abstract] The statement 'for any ε>0' is ambiguous. It presumably means that for every ε>0 there exists a tensor for which the HOSVD-to-optimal error ratio is at least N/(1+ε), but the direction of the inequality and the limiting behavior as ε→0 should be stated precisely. The abstract also does not define the error measure (squared Frobenius norm or Frobenius norm) or the rank tuple (R1,...,RN) to which the lower bound applies. These details matter because the known upper bound of De Lathauwer et al. may be stated for a specific measure, and a mismatch would weaken the claimed tightness.

minor comments (2)

[Abstract] Use consistent notation for ε (the abstract mixes ε and \varepsilon).
[Abstract] The acronyms ST-HOSVD and HOOI should be expanded at first use if the abstract is meant to be self-contained, and the rank parameters (R1,...,RN) should be defined.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the lower bound is established by an explicit tensor construction, not by fitting or by self-citation.

full rationale

The paper's central claim is that HOSVD (and ST-HOSVD/HOOI) can achieve approximation ratio N/(1+ε), matching known upper bounds. The method of proof is construction of a tensor with prescribed singular-value structure, then comparison of the HOSVD error to the optimal Tucker error. This is a standard, non-circular tightness argument: the cited upper bounds (De Lathauwer et al. 2000a,b; Vannieuwenhoven et al. 2012) are external results used as benchmarks to be matched, not as premises that define the constructed example. No fitted parameters are used, no known result is merely renamed, and no load-bearing claim is justified solely by a self-citation. Concerns about whether the optimal rank-(R1,...,RN) error is computed correctly for the construction are substantive mathematical correctness questions, not circularity; the abstract alone does not exhibit any equation that reduces to its own input. Therefore the appropriate circularity score is 0.

Assumptions & free parameters 0 free parameters · 2 assumptions · 0 invented entities

No free parameters. The proof depends on the cited upper bound and standard tensor-decomposition definitions. The constructed tensor is an example within the standard setting, not a new entity.

assumptions (2)

domain assumption The N/(1+ε) upper bound on HOSVD approximation ratio from De Lathauwer et al. (2000a) is correct.
The tightness claim is defined relative to this cited upper bound; the paper assumes it holds.
domain assumption Standard definition of HOSVD and the Frobenius-norm approximation ratio are used.
The construction only makes sense under the standard definition; the paper relies on it.

how reviews work

0 comments

Cite this review

Pith. "Pith review of A Tight Lower Bound for the Approximation Guarantee of Higher-Order Singular Value Decomposition." pith.science (2026). https://pith.science/paper/JI7FH3XC

@misc{pith2026250806693,
  author       = {Pith},
  title        = {Pith review of: A Tight Lower Bound for the Approximation Guarantee of Higher-Order Singular Value Decomposition},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/JI7FH3XC}},
  note         = {Machine review of arXiv:2508.06693}
}

abstract

We prove that the classic approximation guarantee for the higher-order singular value decomposition (HOSVD) is tight by constructing a tensor for which HOSVD achieves an approximation ratio of $N/(1+\varepsilon)$, for any $\varepsilon > 0$. This matches the upper bound of De Lathauwer et al. (2000a) and shows that the approximation ratio of HOSVD cannot be improved. Using a more advanced construction, we also prove that the approximation guarantees for the ST-HOSVD algorithm of Vannieuwenhoven et al. (2012) and higher-order orthogonal iteration (HOOI) of De Lathauwer et al. (2000b) are tight by showing that they can achieve their worst-case approximation ratio of $N / (1 + \varepsilon)$, for any $\varepsilon > 0$.

Discussion (0). Continue with ORCID to comment.

Pith tools

Reviewed August 5, 2026 · model on record in the stance chip above.