Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 
 

 

Nuclear norm of higher-order tensors


Authors: Shmuel Friedland and Lek-Heng Lim
Journal: Math. Comp. 87 (2018), 1255-1281
MSC (2010): Primary 15A69, 90C60; Secondary 47B10, 68Q25
DOI: https://doi.org/10.1090/mcom/3239
Published electronically: September 19, 2017
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: 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.


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 15A69, 90C60, 47B10, 68Q25

Retrieve articles in all journals with MSC (2010): 15A69, 90C60, 47B10, 68Q25


Additional Information

Shmuel Friedland
Affiliation: Department of Mathematics, Statistics and Computer Science, University of Illinois at Chicago, 851 S. Morgan Street, Chicago, Illinois 60607
Email: friedlan@uic.edu

Lek-Heng Lim
Affiliation: Computational and Applied Mathematics Initiative, Department of Statistics, University of Chicago, 5747 S. Ellis Avenue, Chicago, Illinois 60637
Email: lekheng@galton.uchicago.edu

DOI: https://doi.org/10.1090/mcom/3239
Keywords: Tensor nuclear norm, tensor spectral norm, tensor rank, nuclear rank, nuclear decomposition, NP-hard, dual norm
Received by editor(s): May 28, 2016
Received by editor(s) in revised form: November 2, 2016
Published electronically: September 19, 2017
Additional Notes: The first author was partially supported by NSF DMS-1216393
The second author was partially supported by AFOSR FA9550-13-1-0133, DARPA D15AP00109, NSF IIS 1546413, DMS 1209136, DMS 1057064
Article copyright: © Copyright 2017 American Mathematical Society

American Mathematical Society