Most Tensor Problems Are NP-Hard
By Christopher J. Hillar, Lek-Heng Lim. 2009
1,392 citations recorded by the source corpus.
We prove that multilinear (tensor) analogues of many efficiently computable problems in numerical linear algebra are NP-hard. Our list 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 is NP-, #P-, and VNP-hard.
Subfields: Computational Mathematics, Computational Theory and Mathematics
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Computational Mathematics
- Anima Anandkumar
- André Uschmajew
- Rong Ge
- Thorsten Rohwedder
- Sham M. Kakade
- Daniel J. Hsu
- Christine Tobler
- Yining Wang
In Computational Theory and Mathematics
- Sham M. Kakade
- Prateek Jain
- Thorsten Rohwedder
- Inderjit S. Dhillon
- André Uschmajew
- Zhao Song
- Jieping Ye
- Qihang Lin
Citations in the corpus
- Learning Discrete Distributions from Untrusted Batches (2017, background): “Both the problems of computing the best low-rank ℓ 1 approximation of a matrix , and the problems of computing the best rank-1 approximation of a k -tensor for k ≥ 3 are NP-hard [GV15, HL13].”
- A deterministic and computable Bernstein-von Mises theorem (2019, background): “Note that it is already NP-hard to compute exactly the max norm of an order 3 tensor (Hillar and Lim [2013]).”
- Recovery Guarantees for One-hidden-layer Neural Networks (2017, background): “It is known that most tensor problems are NP-hard (H˚astad, 1990; Hillar & Lim, 2013) or even hard to approximate (Song et al., 2017b).”
- Tensor decompositions for learning latent variable models (2012, background): “We note that in general, obtaining such approximations for general (symmetric) tensors is NP-hard (Hillar and Lim, 2013).”
- Greedy Algorithms for Structurally Constrained High Dimensional Problems (2011, background): “Indeed, the above problem is closely related to the problem of finding the best rank-one approximLltion to a given tensor which is known to be NP-hard [16] already for order-3 tensors.”
- A tensor approach to learning mixed membership community models (2013, background): “Note that the decomposition of a general tensor into its rank-one components is referred to as its CP decomposition (Kolda and Bader, 2009) and is in general NP-hard (Hillar and Lim, 2013).”
- A Unified Analysis of Stochastic Momentum Methods for Deep Learning (2018, background): “However, it is NP-hard to find the global optimal solution for a general non-convex optimization problem [ Hillar and Lim, 2013 ] .”
- Learning Two Layer Rectified Neural Networks in Polynomial Time (2018, background): “While computing a tensor decomposition is NP-hard in general Hillar and Lim (2013), there is a plethora of work on special cases, where computing such decompositions is tractable”
- Low Rank Language Models for Small Training Sets (2011, background): “When the tensor is order-3 or higher, not only is this problem NP-hard [3], but there are no tractable convex relaxations of the notion of rank in (2).”
- On Local Convergence of Alternating Schemes for Optimization of Convex Problems in the Tensor Train Format (2013, background): “Of course, these points might not be the global minima on the approximation manifold under consideration – it has recently even been shown that the computation of global rank-1-best approximations is an NP-hard problem [20].”