Improve the worst-case approximation factor for prescribed tensor-train ranks
Let $d \ge 3$, $n_1, \dots, n_d \ge 2$ and positive integers $r = (r_1, \dots, r_{d-1})$ be given, and let $S_r \subseteq \mathbb{R}^{n_1 \times \cdots \times n_d}$ be the set of tensors whose unfolding separating modes $1, \dots, j$ from modes $j + 1, \dots, d$ has rank at most $r_j$, for every $1 \le j \le d - 1$. For $A \in \mathbb{R}^{n_1 \times \cdots \times n_d}$ let $$E_*(A, r) = \min_{Y \in S_r} \|A - Y\|_F^2,$$ a minimum that is attained. The TT-SVD algorithm of Oseledets, which truncates the unfoldings in turn by singular value decompositions, returns $X \in S_r$ with $\|A - X\|_F^2 \le (d - 1)\,E_*(A, r)$.
Problem. Find an algorithm that, given $r$ and the entries of any $A \in \mathbb{R}^{n_1 \times \cdots \times n_d}$, returns $X \in S_r$ with $$\|A - X\|_F^2 < (d - 1)\,E_*(A, r) \quad \text{whenever } E_*(A, r) > 0,$$ and $X = A$ whenever $E_*(A, r) = 0$, in time polynomial in the dense input size $n_1 \cdots n_d$ and in $r_1, \dots, r_{d-1}$, in the idealised model of exact real arithmetic and comparisons, with exact singular value decompositions, used for TT-SVD; or establish a complexity obstruction to such a guarantee.
Source: Stated by OpenProblemsInNLA for tensor trains, after Amsel et al. (2026), Problem 6.1, proposed by Mehrdad Ghadiri, which asks it for every tree tensor network.
Imported from github.com/ajt60gaibb/OpenProblemsInNLA.
Imported from github.com/MColbrook/AIM.
Classification
- Primary
- NA — Numerical Analysis
- Keywords
- approximation algorithms, low-rank approximations, OpenProblemsInNLA, tensor-train decompositions
- Literature checked
- Oct. 8, 2026 by clemens-admin
References
@misc{amsel2026,
author = {Amsel, Noah and Baumann, Yves and Beckman, Paul and B{\"u}rgisser, Peter and Cama{\~n}o, Chris and Chen, Tyler and Chow, Edmond and Damle, Anil and Derezinski, Michal and Embree, Mark and Epperly, Ethan N. and Falgout, Robert and Fornace, Mark and Greenbaum, Anne and Greif, Chen and Halikias, Diana and Huang, Zhen and Jarlebring, Elias and Koutis, Yiannis and Kressner, Daniel and Kyng, Rasmus and Liesen, J{\"o}rg and Lok, Jackie and Meyer, Raphael A. and Nakatsukasa, Yuji and Pearce, Kate and Peng, Richard and Persson, David and Rebrova, Eliza and Schneider, Ryan and Shah, Rikhav and Solomonik, Edgar and Srivastava, Nikhil and Townsend, Alex and Webber, Robert J. and Williams, Jess},
title = {Linear Systems and Eigenvalue Problems: Open Questions from a {S}imons Workshop},
year = {2026},
eprint = {2602.05394},
archivePrefix = {arXiv},
}
@article{oseledets2011,
author = {Oseledets, I. V.},
title = {Tensor-Train Decomposition},
journal = {SIAM J. Sci. Comput.},
volume = {33},
number = {5},
year = {2011},
pages = {2295--2317},
doi = {10.1137/090752286},
}
@misc{openproblemsinnla-tr04,
author = {Townsend, Alex},
title = {{TR-04}: Improve the worst-case approximation factor for prescribed tensor-train ranks},
howpublished = {Open Problems in Numerical Linear Algebra, GitHub repository},
year = {2026},
url = {https://github.com/ajt60gaibb/OpenProblemsInNLA/blob/main/tensor-computations/TR-04/README.md},
note = {Read at commit eb7c9d6, 2026-10-07},
}
Resolution claims
For prescribed tensor-train rank bounds, a deterministic algorithm in the exact arithmetic/SVD model returns an approximation with squared error strictly smaller than $(d - 1)$ times the optimal squared error whenever that optimum is positive, and reconstructs exactly at zero optimum. It performs at most $n_1$ tensor-train SVD completions. The only modification to the standard construction is to test a …
Status history
| When | Change | By | Reason |
|---|---|---|---|
| 2026-10-08 | Needs verification → Solution claimed | clemens-admin | Listed with the record of its solution, unreviewed. |
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00207, "Improve the worst-case approximation factor for prescribed tensor-train ranks", clopen.solutions.