  


Most tensor problems are NPhard
Christopher Hillar (chillarmsri.org) Abstract: We show that multilinear (tensor) analogues of many efficiently computable problems in numerical linear algebra are NPhard. 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 rank1 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 #Pcomplete. We also show that restricting these problems to symmetric tensors does not alleviate their NPhardness and that the problem of deciding nonnegative definiteness of a symmetric 4tensor is also NPhard. Except for this nonnegative definiteness problem, all our results apply to 3tensors. We shall argue that these 3tensor 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, NPhardness, #Pcompleteness, polynomial time approximation schemes Category 1: Global Optimization (Theory ) Category 2: Combinatorial Optimization (Graphs and Matroids ) Category 3: Applications  Science and Engineering Citation: Download: [PDF] Entry Submitted: 11/06/2009 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  