Most Tensor Problems Are NP-Hard

2013/11/01 by Christopher J. Hillar, Lek-Heng Lim, Lek‐Heng Lim · 1,150 citations
Computer Science · Mathematics · #Algebra over a field #Bilinear form #Bilinear interpolation #Cartesian tensor #Combinatorics #Eigenvalues and eigenvectors #Exact solutions in general relativity #Jordan algebra #Mathematical analysis #Mathematics #Matrix Theory and Algorithms #Matrix norm #Multilinear algebra #Multilinear map #Norm (philosophy) #Numerical Methods and Algorithms #Physics #Pure mathematics #Quantum mechanics #Rank (graph theory) #Singular value #Symmetric tensor #Tensor (intrinsic definition) #Tensor algebra #Tensor decomposition and applications #Tensor density #Tensor field

paper · doi:10.1145/2512329

published in Journal of the ACM 60(6), 1-39 (Association for Computing Machinery)

openalex publication_date 2013/11/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/31

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.

Cited by

• Tensor slice rank and Cayley's first hyperdeterminant
• Line Multigraphs of General Hypergraphs
• An optimal statistical and computational framework for generalized tensor estimation
• A low-rank and sparse enhanced Tucker decomposition approach for tensor completion
• Kernel Regression with Tensor Trains and Hadamard Overparameterization
• Spectral Properties of Hypergraph Laplacian and Approximation Algorithms
• Analysis of the Stochastic Alternating Least Squares Method for the Decomposition of Random Tensors
• Nonnegative Tensor Completion via Integer Optimization
• Structural Loss Metrics for Tensor Approximation via Matrix Low-Rank Approximation
• On decompositions and approximations of conjugate partial-symmetric complex tensors
• Approximation and learning with compositional tensor trains
• Prospects for quantum advantage in machine learning from the representability of functions
• Provably Extracting the Features from a General Superposition
• DynACPD Embedding Algorithm for Prediction Tasks in Dynamic Networks
• Optimal Sparse Singular Value Decomposition for High-dimensional High-order Data
• Waring decompositions of special binomials
• Efficient Tensor Decomposition
• A Random Matrix Perspective on Random Tensors
• Scaling and Scalability: Provable Nonconvex Low-Rank Tensor Estimation from Incomplete Measurements
• A new bound on the rank of tensor product of W-states
• The k-core of a graph and its high-order spectra
• New Identity for Cayley's First Hyperdeterminant with Applications to Symmetric Tensors and Entanglement
• Waring decompositions of the product of two quadrics: the small rank cases
• Semidefinite Relaxations for Best Rank-1 Tensor Approximations
• Efficiently Maximizing a Homogeneous Polynomial over Unit Sphere without Convex Relaxation
• Stochastic Recursive Variance-Reduced Cubic Regularization Methods
• Multi-modal and frequency-weighted tensor nuclear norm for hyperspectral image denoising
• A Sharp Blockwise Tensor Perturbation Bound for Orthogonal Iteration
• Adaptive Low-Rank Factorization to regularize shallow and deep neural networks
• Bayesian Allocation Model: Inference by Sequential Monte Carlo for Nonnegative Tensor Factorizations and Topic Models using Polya Urns
• Stochastic Iterative Hard Thresholding for Low-Tucker-Rank Tensor Recovery
• Near-Efficient and Non-Asymptotic Multiway Inference
• Convex semidefinite tensor optimization and quantum entanglement
• Many (most?) column subset selection criteria are NP hard for a few columns
• No-Rank Tensor Decomposition Using Metric Learning
• When Does Non-Orthogonal Tensor Decomposition Have No Spurious Local Minima?
• Relations of the Nuclear Norms of a Tensor and its Matrix Flattenings
• Tensor Decomposition for Signal Processing and Machine Learning
• Sparse and Low-Rank High-Order Tensor Regression via Parallel Proximal Method
• Tensor Q-Rank: New Data Dependent Definition of Tensor Rank
• Tensor Ring Decomposition with Rank Minimization on Latent Space: An Efficient Approach for Tensor Completion
• Landscape analysis of an improved power method for tensor decomposition
• Solving Systems of Random Quadratic Equations via Truncated Amplitude Flow
• Hierarchical search of tree tensor networks for high-dimensional data
• Incoherent Tensor Norms and Their Applications in Higher Order Tensor Completion
• Kullback-Leibler Principal Component for Tensors is not NP-hard
• Low-Rank High-Order Tensor Completion With Applications in Visual Data
• Tensor Restricted Isometry Property Analysis For a Large Class of Random Measurement Ensembles
• Small-Signal Stability Analysis of Power Systems by Implicit Multilinear Models
• The Real Vanishing Ideals of Nuclear p-Norm Balls
• The injective norm of CSS quantum error-correcting codes
• Continuation Methods for Computing Z-/H-eigenpairs of Nonnegative Tensors
• On isolation of singular zeros of multivariate analytic systems
• Multi-subspace power method for decomposing partially symmetric tensors
• Efficient Tensor Completion Algorithms for Highly Oscillatory Operators
• HOQRI: Higher-order QR Iteration for Low Multilinear Rank Approximation of Large and Sparse Tensors
• On the Identifiability of Tensor Ranks via Prior Predictive Matching
• Data Understanding Survey: Pursuing Improved Dataset Characterization Via Tensor-based Methods
• Multi-Slice Low-Rank Tensor Decomposition Based Multi-Atlas Segmentation: Application to Automatic Pathological Liver CT Segmentation
• Faster Perturbed Stochastic Gradient Methods for Finding Local Minima
• Best approximation on semi-algebraic sets and k-border rank approximation of symmetric tensors
• Rotated Mean-Field Variational Inference and Iterative Gaussianization
• Randomized truncation of quantum states
• Finding Local Minima via Stochastic Nested Variance Reduction
• Tensors, entanglement, separability, and their complexity
• Learning Diagonal Gaussian Mixture Models and Incomplete Tensor Decompositions
• Tensor Full Feature Measure and Its Nonconvex Relaxation Applications to Tensor Recovery
• Streaming Coresets for Symmetric Tensor Factorization
• Functional Tensor Regression
• Optimal Bias-variance Tradeoff in Matrix and Tensor Estimation
• Low Rank Approximation of Tensors via Sparse Optimization
• Low-rank Tensor Estimation via Riemannian Gauss-Newton: Statistical Optimality and Second-Order Convergence
• Multi-View Spectral Clustering Tailored Tensor Low-Rank Representation
• On the tensor nuclear norm and the total variation regularization for image and video completion
• Learning words in groups: fusion algebras, tensor ranks and grokking
• k-Positive Maps: New Characterizations and a Generation Method
• Spectral norm of a symmetric tensor and its computation
• Implicit Regularization in Tensor Factorization
• Provable Adaptation across Multiway Domains via Representation Learning
• CNN inference acceleration using dictionary of centroids
• Calculating the Projective Norm of higher-order tensors using a gradient descent algorithm
• A Tight Lower Bound for the Approximation Guarantee of Higher-Order Singular Value Decomposition
• Composite Fermion Theory of Fractional Chern Insulator Stability
• Subspace power method for symmetric tensor decomposition
• How hard is the tensor rank?
• Generalized Eigenvalue Complementarity Problem for Tensors
• Photon catalysis for general multimode multi-photon quantum state preparation
• General Linear Group Action on Tensors: A Candidate for Post-Quantum Cryptography
• Smoothed Analysis of Tensor Decompositions
• Max vs Min: Tensor Decomposition and ICA with nearly Linear Sample Complexity
• Counting tensor rank decompositions
• Factor Models for High-Dimensional Tensor Time Series
• Tensor Robust Principal Component Analysis with a New Tensor Nuclear Norm
• Further Results on Cauchy Tensors and Hankel Tensors
• A New Class of Positive Semi-definite Tensors
• Hankel tensor decompositions and ranks
• First-order Convergence Theory for Weakly-Convex-Weakly-Concave Min-max Problems
• Provable Online CP/PARAFAC Decomposition of a Structured Tensor via Dictionary Learning
• Tensor-Tensor Products, Group Representations, and Semidefinite Programming
• An adaptive gradient method for computing generalized tensor eigenpairs
• Spectral inequalities for nonnegative tensors and their tropical analogues
• sparseGeoHOPCA: A Geometric Solution to Sparse Higher-Order PCA Without Covariance Estimation
• Blind Multilinear Identification
• Bayesian Tensorized Neural Networks with Automatic Rank Selection
• Normalized Iterative Hard Thresholding for Tensor Recovery
• All Real Eigenvalues of Symmetric Tensors
• Positivity of GCD tensors and their determinants
• Provable Tensor-Train Format Tensor Completion by Riemannian Optimization
• Nondegenerate 2 × k × (k+1) Hypermatrices
• Robust Tensor Completion via Gradient Tensor Nulclear L1-L2 Norm for Traffic Data Recovery
• Disentangling tensor product structures
• The characteristic polynomial of sunflowers
• Higher order Matching Pursuit for Low Rank Tensor Learning
• Convex Optimization For Non-Convex Problems via Column Generation
• Gramian Tensor Decomposition via Semidefinite Programming
• Implicit Regularization and Entrywise Convergence of Riemannian Optimization for Low Tucker-Rank Tensor Completion
• Power Iteration for Tensor PCA
• Tensor Factorization via Matrix Factorization
• Interpolating Convex and Non-Convex Tensor Decompositions via the Subspace Norm
• The number of singular vector tuples and uniqueness of best rank one\n approximation of tensors
• From Symmetry to Geometry: Tractable Nonconvex Problems
• Dictionary Learning with Low-rank Coding Coefficients for Tensor Completion
• Demystifying Tubal Tensor Algebra
• Enhanced image approximation using shifted rank-1 reconstruction
• Tensor SVD: Statistical and Computational Limits
• Sum-of-squares meets square loss: Fast rates for agnostic tensor completion
• Rank-1 Tensor Approximation Methods and Application to Deflation
• Symmetric Tensor Nuclear Norms
• Domain-Aware Tensor Network Structure Search
• Decom-Renorm-Merge: Model Merging on the Right Space Improves Multitasking
• Fourier PCA and Robust Tensor Decomposition
• Copositive Tensor Detection and Its Applications in Physics and Hypergraphs
• Low-Rank and Sparse Enhanced Tucker Decomposition for Tensor Completion
• Polymatrix Competitive Gradient Descent
• Multi-Tensor Network Representation for High-Order Tensor Completion
• Phase transition in random tensors with multiple independent spikes
• A Super-Resolution Framework for Tensor Decomposition
• Adaptive Low-Rank Regularization with Damping Sequences to Restrict Lazy Weights in Deep Networks
• Separability of Hermitian Tensors and PSD Decompositions
• Rank Approximation of a Tensor with Applications in Color Image and Video Processing
• Further results on B-tensors with application to the location of real eigenvalues
• Computing tensor eigenvalues via homotopy methods
• Fast Trainable Multilinear Bases for Image Compression
• Symmetric tensor decomposition on rational varieties
• Tensor Robust Principal Component Analysis: Better recovery with atomic norm regularization
• Beyond Lazy Training for Over-parameterized Tensor Decomposition
• Sharp Analysis for Nonconvex SGD Escaping from Saddle Points
• A Robust and Non-Iterative Tensor Decomposition Method with Automatic Thresholding
• Faster Stochastic Quasi-Newton Methods
• A spectral theory for transverse tensor operators
• The Number of Singular Vector Tuples and Uniqueness of Best Rank-One Approximation of Tensors
• The Computational Complexity of Duality
• New penalized criteria for smooth non-negative tensor factorization with missing entries
• SOS-Hankel Tensors: Theory and Application
• Fast Matrix Multiplication: Limitations of the Laser Method
• Quantum Machine Learning Algorithm for Knowledge Graphs
• Optimal low rank tensor recovery
• Simple Infeasibility Certificates for Attack Trees
• Low-Rank Adaptation Redux for Large Models
• Unifying singular value decompositions of tensors via aligned orthogonality
• Sparse random tensors: Concentration, regularization and applications
• Characterizing Spatiotemporal Transcriptome of Human Brain via Low Rank Tensor Decomposition
• On the Stability of Multilinear Dynamical Systems
• Active Sampling for Accelerated MRI with Low-Rank Tensors
• Efficient Tensor Robust PCA under Hybrid Model of Tucker and Tensor Train
• Community detection in the sparse hypergraph stochastic block model
• Rademacher Random Projections with Tensor Networks
• Renormalization group-like flows in randomly connected tensor networks
• Higher order tensor factorizations for block encoding vibrational and vibronic Hamiltonians
• On Recoverability of Randomly Compressed Tensors With Low CP Rank
• A New Generation of Brain-Computer Interfaces Driven by Discovery of Latent EEG-fMRI Linkages Using Tensor Decomposition. [europepmc]
• Quantum algorithm for multivariate polynomial interpolation. [europepmc]
• Quantum machine learning: a classical perspective. [europepmc]
• Stable Tensor Principal Component Pursuit: Error Bounds and Efficient Algorithms. [europepmc]
• Field Theoretical Approach for Signal Detection in Nearly Continuous Positive Spectra II: Tensorial Data. [europepmc]
• NEWTON CORRECTION METHODS FOR COMPUTING REAL EIGENPAIRS OF SYMMETRIC TENSORS. [europepmc]
• General-Purpose Bayesian Tensor Learning With Automatic Rank Determination and Uncertainty Quantification. [europepmc]
• Dimensionality reduction of longitudinal 'omics data using modern tensor factorizations. [europepmc]
• Discovering faster matrix multiplication algorithms with reinforcement learning. [europepmc]
• Remote Sensing Image of The Landsat 8-9 Compressive Sensing via Non-Local Low-Rank Regularization with the Laplace Function. [europepmc]
• Hypergraph partitioning using tensor eigenvalue decomposition. [europepmc]
• Tensor methods in data analysis of chromatography/mass spectroscopy-based plant metabolomics. [europepmc]
• Spectrum Situation Awareness for Space-Air-Ground Integrated Networks Based on Tensor Computing. [europepmc]
• Efficient enhancement of low-rank tensor completion via thin QR decomposition. [europepmc]
• Continuous sepsis trajectory prediction using tensor-reduced physiological signals. [europepmc]
• A Bayesian Tensor Decomposition Method for Joint Estimation of Channel and Interference Parameters. [europepmc]
• A geometric formulation to measure global and genuine entanglement in three-qubit systems. [europepmc]
• No-rank tensor decomposition via metric learning. [europepmc]
• Covid-19 Analysis Using Tensor Methods [europepmc]

Related

• Most tensor problems are NP-hard
• How hard is the tensor rank?
• Tensor and Its Tucker Core: the Invariance Relationships
• Kullback-Leibler Principal Component for Tensors is not NP-hard
• Bilinear Complexity of 3-Tensors Linked to Coding Theory