Most tensor problems are NP-hard

Abstract

We prove 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 3-tensor possesses a given eigenvalue, singular value, or spectral norm; approximating an eigenvalue, eigenvector, singular vector, or the spectral norm; and determining the rank or best rank-1 approximation of a 3-tensor. Furthermore, we show that restricting these problems to symmetric tensors does not alleviate their NP-hardness. We also explain how deciding nonnegative definiteness of a symmetric 4-tensor is NP-hard and how computing the combinatorial hyperdeterminant of a 4-tensor is NP-, #P-, and VNP-hard. We shall argue that our results provide another view of the boundary separating the computational tractability of linear/convex problems from the intractability of nonlinear/nonconvex ones.

38 pages; to appear in Journal of the ACM

References in corpus (2)

• The Number of Eigenvalues of a Tensor
• The Multivariate Resultant is NP-hard in any Characteristic

Cited by in corpus (9)

• Recovery Guarantees for One-hidden-layer Neural Networks
• Multiarray Signal Processing: Tensor decomposition meets compressed sensing
• Quantum Money from Hidden Subspaces
• Learning Non-overlapping Convolutional Neural Networks with Multiple Kernels
• Decomposing Overcomplete 3rd Order Tensors using Sum-of-Squares Algorithms
• Hypergraph Markov Operators, Eigenvalues and Approximation Algorithms
• Hardness and Approximation Results for $L_p$-Ball Constrained Homogeneous Polynomial Optimization Problems
• Randomized Interpolative Decomposition of Separated Representations
• On best rank one approximation of tensors