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 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.
Document Details
- Document Type
- Pub Defense Publication
- Publication Date
- Nov 01, 2013
- Source ID
- 10.1145/2512329
Entities
People
- Christopher J. Hillar
- Lek-heng Lim
Organizations
- Air Force Office of Scientific Research
- Mathematical Sciences Research Institute
- National Science Foundation
- National Science Foundation Division of Mathematical Sciences
- University of Chicago