{"id":"1db91fb9-53e4-4b0a-aacc-3a9aa816aedf","arxiv_id":"2508.06693","paper_version":1,"verdict":"UNVERDICTED","confidence":"LOW","novelty_score":6.0,"correctness_risk":"unknown","formal_verification":"none","parameter_count":0,"one_line_summary":"HOSVD and related tensor-decomposition algorithms have worst-case approximation ratios that are exactly tight, shown by explicit tensor constructions.","lead":"This paper proves that a standard tensor simplification method cannot guarantee better accuracy than a previously known bound. It constructs a data example where the method is exactly as bad as its worst case.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The lower bound hinges on an exact computation of the optimal rank-(R1,...,RN) error for the constructed tensor; if the best Tucker error is smaller than claimed, the N/(1+ε) ratio is not established.","rationale":"The reader correctly identifies that the construction's prescribed singular-value structure is load-bearing, but the most precise weak point is the computation of the optimal rank-(R1,...,RN) error. Even if a tensor with the required HOSVD singular-vector behavior exists, the lower-bound ratio only follows if the best approximation error is exactly what the paper claims. Because the abstract provides no proof details, the claim remains unverified. My concern does not change the reader's UNVERDICTED verdict, so I recommend UNCHANGED. I marked agreement as partial because the reader's weakest_assumption focuses on existence of the tensor structure, whereas I emphasize the optimal-error computation as the more fragile sub-assumption.","tokens_in":686,"tokens_out":11851,"duration_ms":138793,"concrete_test":"Reproduce the construction for N=3 with a small ε (e.g., ε=0.1) and the specified target ranks (R1,R2,R3). Compute the HOSVD output using the paper's chosen SVD tie-breaking, then independently compute the optimal rank-(R1,R2,R3) approximation error using a numerical optimizer (e.g., Riemannian optimization or brute-force for small dimensions). Verify the ratio is 3/(1+ε) within the claimed tolerance. Additionally, check analytically whether the best Tucker approximation could use off-diagonal core terms to reduce the error below the paper's stated value.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The paper's central claim is that HOSVD can achieve a squared-error approximation ratio of N/(1+ε), matching the classic upper bound. This requires a tensor for which (i) each mode-n unfolding has a prescribed singular-value structure (equal or grouped singular values) so that HOSVD selects a deliberately bad subspace, and (ii) the optimal rank-(R1,...,RN) Tucker approximation error is exactly known and small. The fragile step is (ii). Computing the best rank-(R1,...,RN) approximation of a general third-or-higher-order tensor is NP-hard, so the construction must be specially structured (e.g., orthogonal rank-1 components with equal/grouped singular values) to make the optimal error analytically tractable. A subtle failure mode is that even with orthogonal components, the optimal Tucker approximation can exploit coupling across modes—e.g., by using non-coordinate subspaces or an off-diagonal core—to obtain an error smaller than the authors' claimed value. If the proof of the optimal error implicitly assumes that the best approximation is obtained by mode-wise truncation in the component basis, the lower-bound ratio would be an overestimate. The abstract's mention of 'prescribed singular value structure' is exactly this premise, and its correctness cannot be checked from the abstract alone. The full proof must verify both the HOSVD error and the optimal error with precise inequalities, including the ε-dependence.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":990,"tokens_out":2787,"duration_ms":34039,"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":[{"comment":"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.","section":"Abstract"},{"comment":"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.","section":"Abstract"}],"minor_comments":[{"comment":"Use consistent notation for ε (the abstract mixes ε and \\varepsilon).","section":"Abstract"},{"comment":"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.","section":"Abstract"}],"recommendation":"uncertain","confidential_remarks":"I reviewed only the abstract; the full manuscript is not available. The claimed result is plausible and significant, but a proper verdict requires checking the construction's optimal-error computation and the ε-dependence in detail. The editor should ensure referees receive the full text before a decision is made."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","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.\n\nWhat'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.\n\nThe 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.\n\nI'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.\n\nThe 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.","headline":"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.","tokens_in":1426,"tokens_out":2097,"would_cite":true,"duration_ms":26809,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper constructs tensors that force HOSVD to achieve its worst-case approximation ratio, proving the classic guarantee cannot be improved.","keywords":["higher-order singular value decomposition","HOSVD","approximation ratio","tight lower bound","tensor approximation","ST-HOSVD","HOOI"],"falsifier":"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$.","tokens_in":597,"feed_emoji":"🎯","tokens_out":4698,"duration_ms":48554,"temperature":0.7,"pith_summary":"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.","feed_headline":"HOSVD's worst-case approximation ratio cannot be improved","feed_subtitle":"The classic HOSVD approximation guarantee is proven tight by explicit tensor construction.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[],"fun_headline_variants":["HOSVD bound proven tight: no better ratio exists","Worst-case HOSVD approximation ratio is optimal","Matching construction proves HOSVD guarantee tight","Explicit tensor shows HOSVD can't do better","Tight bounds proven for HOSVD, ST-HOSVD, HOOI"],"cache_read_input_tokens":2816,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["HOSVD bound proven tight: no better ratio exists","Worst-case HOSVD approximation ratio is optimal","Matching construction proves HOSVD guarantee tight","Explicit tensor shows HOSVD can't do better","Tight bounds proven for HOSVD, ST-HOSVD, HOOI"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000489,"raw_usage":{"total_tokens":2211,"prompt_tokens":676,"completion_tokens":1535,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":420,"completion_tokens_details":{"reasoning_tokens":1461}},"tokens_in":420,"tokens_out":1535,"duration_ms":12257,"temperature":1.0,"reasoning_tokens":1461,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-05T22:34:56.940535+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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$.","supporting_citations":[],"review_version":1}