Optimization Online


Most tensor problems are NP-hard

Christopher Hillar (chillar***at***msri.org)
Lek-Heng Lim (lekheng***at***galton.uchicago.edu)

Abstract: We show that multilinear (tensor) analogues of many efficiently computable problems in numerical linear algebra are NP-hard. Our list here includes: determining the feasibility of a system of bilinear equations, deciding whether a tensor possesses a given eigenvalue, singular value, or spectral norm; approximating an eigenvalue, eigenvector, singular vector, or spectral norm; determining a best rank-1 approximation to a tensor; and determining the rank of a tensor. Additionally, we prove that some of these problems have no polynomial time approximation schemes, some are undecidable over the rationals, and at least one enumerative version is #P-complete. We also show that restricting these problems to symmetric tensors does not alleviate their NP-hardness and that the problem of deciding nonnegative definiteness of a symmetric 4-tensor is also NP-hard. Except for this nonnegative definiteness problem, all our results apply to 3-tensors. We shall argue that these 3-tensor problems may be viewed as the boundary separating the computational tractability of linear/convex problems from the intractability of nonlinear/nonconvex ones.

Keywords: Numerical multilinear algebra, tensor rank, tensor eigenvalue, tensor singular value, tensor spectral norm, system of multilinear equations, symmetric tensors, nonnegative definite tensors, NP-hardness, #P-completeness, polynomial time approximation schemes

Category 1: Global Optimization (Theory )

Category 2: Combinatorial Optimization (Graphs and Matroids )

Category 3: Applications -- Science and Engineering


Download: [PDF]

Entry Submitted: 11/06/2009
Entry Accepted: 11/07/2009
Entry Last Modified: 04/09/2012

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society