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?)

  • [1] S. Banach, Uber homogene Polynome in ($ L^2$), Studia Math. 7 (1938), 36-44.
  • [2] Jean-Luc Brylinski, Algebraic measures of entanglement, Mathematics of quantum computation, Comput. Math. Ser., Chapman & Hall/CRC, Boca Raton, FL, 2002, pp. 3-23. MR 2007941
  • [3] Pierre Comon, Gene Golub, Lek-Heng Lim, and Bernard Mourrain, Symmetric tensors and symmetric tensor rank, SIAM J. Matrix Anal. Appl. 30 (2008), no. 3, 1254-1279. MR 2447451, https://doi.org/10.1137/060661569
  • [4] Vin de Silva and Lek-Heng Lim, Tensor rank and the ill-posedness of the best low-rank approximation problem, SIAM J. Matrix Anal. Appl. 30 (2008), no. 3, 1084-1127. MR 2447444, https://doi.org/10.1137/06066518X
  • [5] Andreas Defant and Klaus Floret, Tensor norms and operator ideals, North-Holland Mathematics Studies, vol. 176, North-Holland Publishing Co., Amsterdam, 1993. MR 1209438
  • [6] Harm Derksen, On the nuclear norm and the singular value decomposition of tensors, Found. Comput. Math. 16 (2016), no. 3, 779-811. MR 3494510, https://doi.org/10.1007/s10208-015-9264-x
  • [7] H. Derksen, S. Friedland, L.-H. Lim, and L. Wang, Theoretical and computational aspects of entanglement, preprint (2017), arXiv:1707.02569.
  • [8] Shmuel Friedland, Best rank one approximation of real symmetric tensors can be chosen symmetric, Front. Math. China 8 (2013), no. 1, 19-40. MR 3010470, https://doi.org/10.1007/s11464-012-0262-x
  • [9] Shmuel Friedland, Matrices--algebra, analysis and applications, World Scientific Publishing Co. Pte. Ltd., Hackensack, NJ, 2016. MR 3467205
  • [10] Shmuel Friedland, Variation of tensor powers and spectra, Linear and Multilinear Algebra 12 (1982/83), no. 2, 81-98. MR 670715, https://doi.org/10.1080/03081088208817475
  • [11] Shmuel Friedland and Lek-Heng Lim, The computational complexity of duality, SIAM J. Optim. 26 (2016), no. 4, 2378-2393. MR 3566920, https://doi.org/10.1137/16M105887X
  • [12] Alexandre Grothendieck, Produits tensoriels topologiques et espaces nucléaires, Mem. Amer. Math. Soc. No. 16 (1955), 140. MR 0075539
  • [13] Julien M. Hendrickx and Alex Olshevsky, Matrix $ p$-norms are NP-hard to approximate if $ p\neq1,2,\infty$, SIAM J. Matrix Anal. Appl. 31 (2010), no. 5, 2802-2812. MR 2740634, https://doi.org/10.1137/09076773X
  • [14] Christopher J. Hillar and Lek-Heng Lim, Most tensor problems are NP-hard, J. ACM 60 (2013), no. 6, Art. 45, 39. MR 3144915, https://doi.org/10.1145/2512329
  • [15] F. L. Hitchcock, The expression of a tensor or a polyadic as a sum of products, J. Math. Phys. 6 (1927), no. 1, 164-189.
  • [16] Richard M. Karp, Reducibility among combinatorial problems, Complexity of computer computations (Proc. Sympos., IBM Thomas J. Watson Res. Center, Yorktown Heights, NY, 1972) Plenum, New York, 1972, pp. 85-103. MR 0378476
  • [17] L.-H. Lim, Tensors and hypermatrices, Handbook of Linear Algebra, 2nd Ed., CRC Press, Boca Raton, FL, 2013.
  • [18] L.-H. Lim and P. Comon, Multiarray signal processing: Tensor decomposition meets compressed sensing, C. R. Acad. Sci. Paris, Series IIB - Mechanics 338 (2010), no. 6, 311-320.
  • [19] Lek-Heng Lim and Pierre Comon, Blind multilinear identification, IEEE Trans. Inform. Theory 60 (2014), no. 2, 1260-1280. MR 3164974, https://doi.org/10.1109/TIT.2013.2291876
  • [20] A. Pappas, Y. Sarantopoulos, and A. Tonge, Norm attaining polynomials, Bull. Lond. Math. Soc. 39 (2007), no. 2, 255-264. MR 2323457, https://doi.org/10.1112/blms/bdl033
  • [21] Yang Qi, Pierre Comon, and Lek-Heng Lim, Semialgebraic geometry of nonnegative tensor rank, SIAM J. Matrix Anal. Appl. 37 (2016), no. 4, 1556-1580. MR 3565551, https://doi.org/10.1137/16M1063708
  • [22] T. S. Motzkin and E. G. Straus, Maxima for graphs and a new proof of a theorem of Turán, Canad. J. Math. 17 (1965), 533-540. MR 0175813
  • [23] Raymond A. Ryan, Introduction to Tensor Products of Banach Spaces, Springer Monographs in Mathematics, Springer-Verlag London, Ltd., London, 2002. MR 1888309
  • [24] Robert Schatten, A Theory of Cross-Spaces, Annals of Mathematics Studies, no. 26, Princeton University Press, Princeton, NJ, 1950. MR 0036935
  • [25] D. Steinberg, Computation of Matrix Norms with Applications to Robust Optimization, M.Sc. thesis, Technion Israel Institute of Technology, Haifa, Israel, 2005.
  • [26] Angus E. Taylor, The norm of a real linear transformation in Minkowski space, Enseignement Math. (2) 4 (1958), 101-107. MR 0096687
  • [27] Yau Chuen Wong, Schwartz Spaces, Nuclear Spaces and Tensor Products, Lecture Notes in Mathematics, vol. 726, Springer, Berlin, 1979. MR 541034
  • [28] K. Ye and L.-H. Lim, Fast structured matrix computations: Tensor rank and Cohn-Umans method, Found. Comput. Math. (2016), DOI 10.1007/s1020, to appear.
  • [29] Fyodor L. Zak, Determinants of projective varieties and their degrees, Algebraic Transformation Groups and Algebraic Varieties, Encyclopaedia Math. Sci., vol. 132, Springer, Berlin, 2004, pp. 207-238. MR 2090676, https://doi.org/10.1007/978-3-662-05652-3_11
  • [30] Tong Zhang and Gene H. Golub, Rank-one approximation to high order tensors, SIAM J. Matrix Anal. Appl. 23 (2001), no. 2, 534-550. MR 1871328, https://doi.org/10.1137/S0895479899352045

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