Academy of Mathematics and Systems Science, CAS
Colloquia & Seminars

Speaker:	Prof. Zhening Li, University of Portsmouth
Inviter:	刘歆副研究员
Title:	Orthogonal tensors and best rank one app roximation ratio
Time & Venue:	2019.7.25 11:00-12:00 Z311
Abstract:	As is well known, the minimum ratio between the spectral norm and the Frobenius norm of an $m \times n$ matrix with $m \le n$ is $1/\sqrt{m}$ and is (up to scalar scaling) attained only by matrices having pairwise orthonormal rows. In this work, the minimum ratio between spectral and Frobenius norms of $n_1 \times \dots \times n_d$ tensors of order $d$, also called the best rank-one approximation ratio in the literature, is investigated. The exact value is not known for most configurations of $n_1 \le \dots \le n_d$. Using a natural definition of orthogonal tensors over the real field (resp. unitary tensors over the complex field), it is shown that the obvious lower bound $1/\sqrt{n_1 \cdots n_{d-1}}$ is attained if and only if a tensor is orthogonal (resp. unitary) up to scaling. Whether or not orthogonal or unitary tensors exist depends on the dimensions $n_1, \dots, n_d$ and the field. A connection between the (non)existence of real orthogonal tensors of order three and the classical Hurwitz problem on composition algebras can be established: existence of orthogonal tensors of size $\ell \times m \times n$ is equivalent to the admissibility of the triple $[\ell, m, n]$ to Hurwitz problem. Some implications for higher-order tensors are then given. For instance, real orthogonal $n \times \dots \times n$ tensors of order $d \ge 3$ do exist, but only when $n = 1, 2, 4, 8$. In the complex case, the situation is more drastic: unitary tensors of size $\ell \times m \times n$ with $\ell \le m \le n$ exist only when $\ell m \le n$. Some numerical illustrations for spectral norm computation are presented. This is a joint work with Yuji Nakatsukasa (University of Oxford), Tasuku Soma (University of Tokyo), and André Uschmajew (MPI Leipzig).