Exact best-rank-one approximation ratios for general tensor formats
For $d \ge 3$ and $2 \le n_1 \le \cdots \le n_d$, let $\|T\|_F$ be the Frobenius norm of a real tensor $T \in \mathbb{R}^{n_1 \times \cdots \times n_d}$ and $\|T\|_\sigma$ its spectral norm, the maximum of $|\langle T, x_1 \otimes \cdots \otimes x_d \rangle|$ over unit vectors $x_j \in \mathbb{R}^{n_j}$. Let $$\tau(n_1, \dots, n_d) = \min_{T \ne 0} \frac{\|T\|_\sigma}{\|T\|_F},$$ the largest $\tau$ with $\tau \|T\|_F \le \|T\|_\sigma$ for every $T$ of this format. Qi showed that $\tau(n_1, \dots, n_d) \ge 1/\sqrt{n_1 \cdots n_{d-1}}$, and Li, Nakatsukasa, Soma and Uschmajew that equality holds exactly when the format admits an orthogonal tensor in their sense; for $n_1 = \cdots = n_d = n$ such tensors exist exactly when $n \in \{2, 4, 8\}$. Kühn and Peetre determined $\tau(n_1, n_2, n_3)$ for $n_3 \le 4$ except $\tau(3, 3, 3)$, which is $1/\sqrt{7}$ (Agrachev, Kozhasov and Uschmajew).
Problem. Determine $\tau(n_1, \dots, n_d)$ exactly, as a function of the dimensions, for every $d \ge 3$ and all $2 \le n_1 \le \cdots \le n_d$.
Source: Qi (2011), §7, open question 2; in this form, Li and Zhao (2020), §5.
Imported from github.com/ajt60gaibb/OpenProblemsInNLA.
Classification
- Primary
- NA — Numerical Analysis
- Secondary
- FA
- Keywords
- OpenProblemsInNLA, orthogonal tensors, rank-one approximations, spectral norms
- Literature checked
- Oct. 6, 2026 by clemens-admin
References
@article{qi2011,
author = {Qi, Liqun},
title = {The best rank-one approximation ratio of a tensor space},
journal = {SIAM J. Matrix Anal. Appl.},
volume = {32},
number = {2},
year = {2011},
pages = {430--442},
doi = {10.1137/100795802},
}
@article{li2020,
author = {Li, Zhening and Zhao, Yun-Bin},
title = {On norm compression inequalities for partitioned block tensors},
journal = {Calcolo},
volume = {57},
number = {1},
year = {2020},
pages = {11},
doi = {10.1007/s10092-020-0356-x},
}
@article{li2018,
author = {Li, Zhening and Nakatsukasa, Yuji and Soma, Tasuku and Uschmajew, Andr{\'e}},
title = {On orthogonal tensors and best rank-one approximation ratio},
journal = {SIAM J. Matrix Anal. Appl.},
volume = {39},
number = {1},
year = {2018},
pages = {400--425},
doi = {10.1137/17M1144349},
eprint = {1707.02569},
archivePrefix = {arXiv},
}
@article{kuhn2006,
author = {K{\"u}hn, Thomas and Peetre, Jaak},
title = {Embedding constants of trilinear {S}chatten--von {N}eumann classes},
journal = {Proc. Est. Acad. Sci. Phys. Math.},
volume = {55},
number = {3},
year = {2006},
pages = {174--181},
doi = {10.3176/phys.math.2006.3.08},
}
@article{agrachev2020,
author = {Agrachev, Andrei and Kozhasov, Khazhgali and Uschmajew, Andr{\'e}},
title = {Chebyshev polynomials and best rank-one approximation ratio},
journal = {SIAM J. Matrix Anal. Appl.},
volume = {41},
number = {1},
year = {2020},
pages = {308--331},
doi = {10.1137/19M1269713},
eprint = {1904.00488},
archivePrefix = {arXiv},
}
@misc{openproblemsinnla-tr19,
author = {Townsend, Alex},
title = {{TR-19}: Exact best-rank-one approximation ratios for general tensor formats},
howpublished = {Open Problems in Numerical Linear Algebra, GitHub repository},
year = {2026},
url = {https://github.com/ajt60gaibb/OpenProblemsInNLA/blob/main/tensor-computations/TR-19/README.md},
note = {Read at commit e375a6f, 2026-09-30},
}
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00131, "Exact best-rank-one approximation ratios for general tensor formats", clopen.solutions.