Probabilistic bounds on best rank-1 approximation ratio (Q6649813)

Let \(\mathbb{K}^{\mathbf{n}}=\mathbb{K}^{n_1}\otimes \ldots \otimes \mathbb{K}^{ n_d}\) represent the \(\mathbb{K}^{\mathbf{n}}\)-vector space of \({\mathbf{n}}\)-tensors with \({\mathbf{n}}=(n_1,\ldots,n_d)\), here \(\mathbb{K}\) denotes the field of real or complex numbers. A tensor \(W\in \mathbb{K}^{\mathbf{n}}\) is called rank-1, if it can be expressed as the tensor product of \(d\) vectors. The problem of best rank-1 approximation of an arbitrary tensor \(T\in \mathbb{K}^{\mathbf{n}}\) involves identifying the closest rank-1 tensor to \(T\). It is known that this problem is essentially equivalent to computing the spectral norm of \(T\),\N\[\N{\left\| T \right\|_\infty }: = \mathop {\max }\limits_{{x^j} \in \mathbb{S}({{\mathbb{K}}^{{n_j}}})} \left| {\left\langle {T,{x^1} \otimes \cdots \otimes {x^d}} \right\rangle } \right|,\N\]\Nwhich is known to be NP-hard [\textit{C. J. Hillar} and \textit{L.-H. Lim}, J. ACM 60, No. 6, Article No. 45, 39 p. (2013; Zbl 1281.68126)]. If \(\lambda {x^1} \otimes \cdots \otimes {x^d}\) is a best rank-1 approximation of \(T\), then (the square of) the relative best rank-1 approximation error equals\N\[\N\frac{{{{\left\| {T - \lambda {x^1} \otimes \cdots \otimes {x^d}} \right\|}^2}}}{{{{\left\| T \right\|}^2}}} = 1 - \frac{{\left\| T \right\|_\infty ^2}}{{{{\left\| T \right\|}^2}}}.\N\]\NThus, finding the largest (worst) relative best rank-1 error is equivalent to determining \[{\min _{T \in \mathbb{K}^{\mathbf{n}}}}{\left\| T \right\|_\infty }/\left\| T \right\|.\] In general, the best rank-1 approximation ratio of a tensor subspace \(V \subseteq \mathbb{K}^{\mathbf{n}}\) can be defined as follows: \[\mathcal{A}(V):={\min _{T \in V}}{\left\| T \right\|_\infty }/\left\| T \right\|.\]\N\NIn [\textit{Z. Li} et al., SIAM J. Matrix Anal. Appl. 39, No. 1, 400--425 (2018; Zbl 1390.15081)] it is shown that the right inequality in\N\[\N\frac{1}{{\sqrt {{{\min }_{i = 1, \ldots, d}}\prod\nolimits_{j \ne i} {{n_j}} } }} \le \mathcal{A}({\mathbb{R}^n}) \le \frac{{{{\left\| T \right\|}_\infty }}}{{\left\| T \right\|}} \le \frac{{C\sqrt {d\ln d} }}{{\sqrt {{{\min }_{i = 1, \ldots, d}}\prod\nolimits_{j \ne i} {{n_j}} } }}\N\]\Nholds with positive probability in \(T\), where \(C\) is some constant and the entries of \(T\) are independent standard Gaussians. In the current work, the authors reprove these probabilistic upper bounds giving explicit values for the constant \(C\) for tensors of arbitrary order \(d\).\N\NFor symmetric tensors, the problem of estimating the ratio \(\mathcal{A}(\cdot)\) remains largely open. In this work, the primary result improves upon the upper bound established in [\textit{Z. Li} and \textit{Y.-B. Zhao}, Calcolo 57, No. 1, Paper No. 11, 27 p. (2020; Zbl 1436.15027)] for the case \(d=3\). For any fixed \(d \ge 3\), the main theorem demonstrates that the lower bound for general tensors is also asymptotically optimal (up to a constant factor) for symmetric tensors of order \(d\). More generally, new upper and lower bounds are derived for \(\mathcal{A}(V)\), where \(V\) is a space of (partially) symmetric tensors over \(\mathbb{K}\). The authors also provides insights into the growth and scaling properties of the bounds as the tensor order \(d\) increases.