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

  1. Anima Anandkumar
  2. André Uschmajew
  3. Rong Ge
  4. Thorsten Rohwedder
  5. Sham M. Kakade
  6. Daniel J. Hsu
  7. Christine Tobler
  8. Yining Wang

In Computational Theory and Mathematics

  1. Sham M. Kakade
  2. Prateek Jain
  3. Thorsten Rohwedder
  4. Inderjit S. Dhillon
  5. André Uschmajew
  6. Zhao Song
  7. Jieping Ye
  8. Qihang Lin

Citations in the corpus