Nuclear norm of higher-order tensors

• Published in: Mathematics of computation 2018-05, Vol.87 (311), p.1255-1281
• Main Authors: FRIEDLAND, SHMUEL, LIM, LEK-HENG
• Format: Article
• Language: English
• ISSN: 0025-5718; 1088-6842
• DOI: 10.1090/mcom/3239

We establish several mathematical and computational properties of the nuclear norm for higher-order tensors. We show that like tensor rank, tensor nuclear norm is dependent on the choice of base field; the value of the nuclear norm of a real 3-tensor depends on whether we regard it as a real 3-tensor or a complex 3-tensor with real entries. We show that every tensor has a nuclear norm attaining decomposition and every symmetric tensor has a symmetric nuclear norm attaining decomposition. There is a corresponding notion of nuclear rank that, unlike tensor rank, is lower semicontinuous. We establish an analogue of Banach's theorem for tensor spectral norm and Comon's conjecture for tensor rank; for a symmetric tensor, its symmetric nuclear norm always equals its nuclear norm. We show that computing tensor nuclear norm is NP-hard in several ways. Deciding weak membership in the nuclear norm unit ball of 3-tensors is NP-hard, as is finding an \varepsilon -approximation of nuclear norm for 3-tensors. In addition, the problem of computing spectral or nuclear norm of a 4-tensor is NP-hard, even if we restrict the 4-tensor to be bi-Hermitian, bisymmetric, positive semidefinite, nonnegative valued, or all of the above. We discuss some simple polynomial-time approximation bounds. As an aside, we show that computing the nuclear (p,q)-norm of a matrix is NP-hard in general but polynomial-time if p=1, q = 1, or p=q=2, with closed-form expressions for the nuclear (1,q)- and (p,1)-norms.