Most Tensor Problems Are NP-Hard

2013/11/01 by Christopher J. Hillar, Lek-Heng Lim, Lek‐Heng Lim · 125 citations
Mathematics · Computer Science · #Tensor decomposition and applications #Numerical Methods and Algorithms #Matrix Theory and Algorithms

paper · doi:10.1145/2512329

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\n 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
• No-Rank Tensor Decomposition Using Metric Learning
• When Does Non-Orthogonal Tensor Decomposition Have No Spurious Local\n 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\n 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
• 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\n Problems
• Provable Online CP/PARAFAC Decomposition of a Structured Tensor via\n 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\n analogues
• 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
• 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