On orthogonal tensors and best rank-one approximation ratio

Zhening Li, Yuji Nakatsukasa, Tasuku Soma, André Uschmajew

Research output: Contribution to journalArticlepeer-review

156 Downloads (Pure)

Abstract

As is well known, the smallest possible ratio between the spectral norm and the Frobenius norm of an m × n matrix with mn is 1/√m and is (up to scalar scaling) attained only by matrices having pairwise orthonormal rows. In the present paper, the smallest possible ratio between spectral and Frobenius norms of n× ··· × nd 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≤ ··· ≤ nd. 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/√n1···nd−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 n1, ..., nd 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 l × m × n is equivalent to the admissibility of the triple [l, m, n] to the Hurwitz problem. Some implications for higher-order tensors are then given. For instance, real orthogonal n × ··· × n tensors of order d ≥ 3 do exist, but only when n = 1, 2, 4, 8. In the complex case, the situation is more drastic: unitary tensors of size l × m × n with lmn exist only when l mn. Finally, some numerical illustrations for spectral norm computation are presented.
Original languageEnglish
Pages (from-to)400-425
JournalSIAM Journal on Matrix Analysis and Applications
Volume39
Issue number1
Early online date8 Mar 2018
DOIs
Publication statusPublished - Mar 2018

Keywords

  • orthogonal tensor
  • rank-one approximation
  • spectral norm
  • nuclear norm
  • Hurwitz problem

Fingerprint

Dive into the research topics of 'On orthogonal tensors and best rank-one approximation ratio'. Together they form a unique fingerprint.

Cite this