Journal Article

Nuclear norm of higher-order tensors

Lim, Lek-Heng, Friedland, Shmuel

2018

Overview

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 33-tensor depends on whether we regard it as a real 33-tensor or a complex 33-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 33-tensors is NP-hard, as is finding an ε\\varepsilon-approximation of nuclear norm for 33-tensors. In addition, the problem of computing spectral or nuclear norm of a 44-tensor is NP-hard, even if we restrict the 44-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)(p,q)-norm of a matrix is NP-hard in general but polynomial-time if p=1p=1, q=1q = 1, or p=q=2p=q=2, with closed-form expressions for the nuclear (1,q)(1,q)- and (p,1)(p,1)-norms.

• Publisher: American Mathematical Society
• Subject: Research article