Access Restriction

Author Hillar, Christopher J ♦ Lim, Lek-Heng
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©2013
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword #P-hardness ♦ NP-hardness ♦ Numerical multilinear algebra ♦ VNP-hardness ♦ Bivariate matrix polynomials ♦ Hyperdeterminants ♦ Nonnegative definite tensors ♦ Polynomial time approximation schemes ♦ Symmetric tensors ♦ System of multilinear equations ♦ Tensor eigenvalue ♦ Tensor rank ♦ Tensor singular value ♦ Tensor spectral norm ♦ Undecidability
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.
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2013-11-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 60
Issue Number 6
Page Count 39
Starting Page 1
Ending Page 39

Open content in new tab

   Open content in new tab
Source: ACM Digital Library