Most tensor problems are NP-hard
From MaRDI portal
\#P-hardnessbivariate matrix polynomialshyperdeterminantsnonnegative definite tensorsNP-hardnessnumerical multilinear algebrapolynomial time approximation schemessymmetric tensorssystem of multilinear equationstensor eigenvaluetensor ranktensor singular valuetensor spectral normundecidabilityVNP-hardness
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.
Recommendations
Cited in
(only showing first 100 items - show all)- Convergence rate analysis for the higher order power method in best rank one approximations of tensors
- A very brief introduction to nonnegative tensors from the geometric viewpoint
- Continuation methods for computing Z-/H-eigenpairs of nonnegative tensors
- On the rank of a Latin tensor
- Completely positive tensor recovery with minimal nuclear value
- Accurate calculation of the geometric measure of entanglement for multipartite quantum states
- Self-concordance is NP-hard
- Orthogonal and unitary tensor decomposition from an algebraic perspective
- Effective identifiability criteria for tensors and polynomials
- The generalized inverses of tensors and an application to linear models
- The numerical approximation of nonlinear functionals and functional differential equations
- Higher-order principal component analysis for the approximation of tensors in tree-based low-rank formats
- Calculating entanglement eigenvalues for nonsymmetric quantum pure states based on the Jacobian semidefinite programming relaxation method
- Cross: efficient low-rank tensor completion
- Some criteria for identifying strong \(\mathcal{H}\)-tensors
- Alternating iterative methods for solving tensor equations with applications
- Tensor completion using total variation and low-rank matrix factorization
- Real eigenvalues of nonsymmetric tensors
- Block tensors and symmetric embeddings
- Monotonically convergent algorithms for symmetric tensor approximation
- Principal eigenvector of the signless Laplacian matrix
- Parallel tensor methods for high-dimensional linear PDEs
- On polynomial time methods for exact low-rank tensor completion
- Spectral inequalities for nonnegative tensors and their tropical analogues
- Tensor \(N\)-tubal rank and its convex relaxation for low-rank tensor recovery
- Tensor train rank minimization with nonlocal self-similarity for tensor completion
- The characteristic polynomial of the complete 3-uniform hypergraph
- Computing tensor Z-eigenvalues via shifted inverse power method
- Sparse random tensors: concentration, regularization and applications
- Spectra of random regular hypergraphs
- Tensor theta norms and low rank recovery
- Reshaped tensor nuclear norms for higher order tensor completion
- Hyperdeterminants from the E₈ discriminant
- Tensor Q-rank: new data dependent definition of tensor rank
- Community detection on mixture multilayer networks via regularized tensor decomposition
- Sharp bounds on the minimum \(M\)-eigenvalue and strong ellipticity condition of elasticity \(Z\)-tensors-tensors
- A Krylov-Schur-like method for computing the best rank-\((r_1,r_2,r_3)\) approximation of large and sparse tensors
- Tensor slice rank and Cayley's first hyperdeterminant
- A new tensor multi-rank approximation with total variation regularization for tensor completion
- A tensor regularized nuclear norm method for image and video completion
- Computing the largest C-eigenvalue of a tensor using convex relaxation
- Robust and resource-efficient identification of two hidden layer neural networks
- An optimal statistical and computational framework for generalized tensor estimation
- Tensor clustering with planted structures: statistical optimality and computational limits
- Inference for low-rank tensors -- no need to debias
- Learning diagonal Gaussian mixture models and incomplete tensor decompositions
- A globally convergent method for solving a quartic generalized Markowitz portfolio problem
- Further results on eigenvalues of symmetric decomposable tensors from multilinear dynamical systems
- Adjacency energy of hypergraphs
- Spectra of weighted uniform hypertrees
- On the optimization landscape of tensor decompositions
- The signless Laplacian matrix of hypergraphs
- Tensor completion via fully-connected tensor network decomposition with regularized factors
- Fast multidimensional completion and principal component analysis methods via the cosine product
- The set of orthogonal tensor trains
- Nonlinear transform induced tensor nuclear norm for tensor completion
- Several approximation algorithms for sparse best rank-1 approximation to higher-order tensors
- Riemannian conjugate gradient methods for computing the extreme eigenvalues of symmetric tensors
- On norm compression inequalities for partitioned block tensors
- A bound for the Waring rank of the determinant via syzygies
- High-order tensor estimation via trains of coupled third-order CP and Tucker decompositions
- General linear group action on tensors: a candidate for post-quantum cryptography
- Enhanced image approximation using shifted rank-1 reconstruction
- High-order sum-of-squares structured tensors: theory and applications
- Matrix factorization for low-rank tensor completion using framelet prior
- \(p\)-norm \(B\)-tensors and \(p\)-norm \(B_0\)-tensors
- Symmetric matrices whose entries are linear functions
- Adaptive total variation and second-order total variation-based model for low-rank tensor completion
- On the spectrum of hypergraphs
- On decompositions and approximations of conjugate partial-symmetric tensors
- Phase transition in random tensors with multiple independent spikes
- Programmable sufficient conditions for the strong ellipticity of partially symmetric tensors
- Behavior of the Fréchet mean and central limit theorems on spheres
- Learning with tensors: a framework based on convex optimization and spectral regularization
- Tensor completion based on triple tubal nuclear norm
- M-eigenvalues-based sufficient conditions for the positive definiteness of fourth-order partially symmetric tensors
- An iterative algorithm based on strong \(\mathcal{H} \)-tensors for identifying positive definiteness of irreducible homogeneous polynomial forms
- CP decomposition and weighted clique problem
- On the tensor spectral p-norm and its dual norm via partitions
- An inexact augmented Lagrangian method for computing strongly orthogonal decompositions of tensors
- SDP relaxation algorithms for \(\mathbf{P(P}_0)\)-tensor detection
- Iterative methods for computing U-eigenvalues of non-symmetric complex tensors with application in quantum entanglement
- Low-rank tensor completion via smooth matrix factorization
- Exclusion sets in the \({\Delta}\)-type eigenvalue inclusion set for tensors
- Solving equations of random convex functions via anchored regression
- Three-way clustering of multi-tissue multi-individual gene expression data using semi-nonnegative tensor decomposition
- Pseudospectra localizations for generalized tensor eigenvalues to seek more positive definite tensors
- Low-rank tensor completion using matrix factorization based on tensor train rank and total variation
- Solving tensor E-eigenvalue problem faster
- Relations of the nuclear norm of a tensor and its matrix flattenings
- An adaptive gradient method for computing generalized tensor eigenpairs
- A note on the gap between rank and border rank
- High-dimensional change-point estimation: combining filtering with convex optimization
- Generating polynomials and symmetric tensor decompositions
- Computing extreme eigenvalues of large scale Hankel tensors
- On probabilistic algorithm for solving almost all instances of the set partition problem
- Low rank tensor recovery via iterative hard thresholding
- Maximization of homogeneous polynomials over the simplex and the sphere: structure, stability, and generic behavior
- Bounded-rank tensors are defined in bounded degree
- Distribution of the eigenvalues of a random system of homogeneous polynomials
This page was built for publication: Most tensor problems are NP-hard
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5395740)
