Most Tensor Problems Are NP-Hard

DOI10.1145/2512329zbMath1281.68126arXiv0911.1393OpenAlexW2079705627WikidataQ60307003 ScholiaQ60307003MaRDI QIDQ5395740

Lek-Heng Lim, Christopher J. Hillar

Publication date: 17 February 2014

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/0911.1393

zbMATH Keywords

undecidabilitysymmetric tensorsNP-hardnesshyperdeterminantstensor ranktensor eigenvaluepolynomial time approximation schemes\#P-hardnessnumerical multilinear algebratensor spectral normtensor singular valuebivariate matrix polynomialsnonnegative definite tensorssystem of multilinear equationsVNP-hardness

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

Robust Eigenvectors of Symmetric Tensors, Tensors in computations, Separability of Hermitian tensors and PSD decompositions, Orthogonal decomposition of tensor trains, Unnamed Item, The Geometry of Rank-One Tensor Completion, Half-quadratic alternating direction method of multipliers for robust orthogonal tensor approximation, Iterative hard thresholding for low CP-rank tensor models, Nonlinear Perron--Frobenius Theorems for Nonnegative Tensors, Low-rank tensor methods for partial differential equations, Some new \(Z\)-eigenvalue localization sets for even-order tensors and their application in the geometric measure of entanglement, Community detection in the sparse hypergraph stochastic block model, Alternating Mahalanobis Distance Minimization for Accurate and Well-Conditioned CP Decomposition, Fully-connected tensor network decomposition for robust tensor completion problem, Partially symmetric tensor structure preserving rank-\(R\) approximation via BFGS algorithm, Low tubal rank tensor completion based on singular value factors, Approximate real symmetric tensor rank, On the stability of discrete-time homogeneous polynomial dynamical systems, Tensor completion via multi-directional partial tensor nuclear norm with total variation regularization, Adaptive tensor networks decomposition for high-order tensor recovery and compression, Some properties on eccentricity matrices of uniform hypertrees, Some bounds on spectral radius of signless Laplacian matrix of k-graphs, The low-rank approximation of fourth-order partial-symmetric and conjugate partial-symmetric tensor, A complex-valued gradient flow for the entangled bipartite low rank approximation, Spectral theory of weighted hypergraphs via tensors, On Best Low Rank Approximation of Positive Definite Tensors, A Learnable Group-Tube Transform Induced Tensor Nuclear Norm and Its Application for Tensor Completion, TR-STF: a fast and accurate tensor ring decomposition algorithm via defined scaled tri-factorization, Feasible Newton methods for symmetric tensor Z-eigenvalue problems, A Corrected Tensor Nuclear Norm Minimization Method for Noisy Low-Rank Tensor Completion, Approximating Tensor Norms via Sphere Covering: Bridging the Gap between Primal and Dual, Tensor decompositions on simplicial complexes with invariance, More on Tensors with Different Rank and Symmetric Rank, Approximating Higher-Order Derivative Tensors Using Secant Updates, Factor Models for High-Dimensional Tensor Time Series, Symmetric Tensor Nuclear Norms, Hankel Tensor Decompositions and Ranks, Analytical expressions of copositivity for fourth-order symmetric tensors, On the irregularity of uniform hypergraphs, Low-Rank Tensor Recovery using Sequentially Optimal Modal Projections in Iterative Hard Thresholding (SeMPIHT), The Sup-norm Perturbation of HOSVD and Low Rank Tensor Denoising, Computing Tensor $Z$-Eigenvectors with Dynamical Systems, On isolation of simple multiple zeros and clusters of zeros of polynomial systems, Optimal Sparse Singular Value Decomposition for High-Dimensional High-Order Data, Approximating the existential theory of the reals, Approximating the existential theory of the reals, ${}_{\delta}^{\gamma}\!\mathbf{\Phi}$-type inclusion set for eigenvalues of a tensor, Rigid continuation paths I. Quasilinear average complexity for solving polynomial systems, A TT-Based Hierarchical Framework for Decomposing High-Order Tensors, A Unifying Perron--Frobenius Theorem for Nonnegative Tensors via Multihomogeneous Maps, Positive contraction mappings for classical and quantum Schrödinger systems, Hardness and Approximation Results for L_p-Ball Constrained Homogeneous Polynomial Optimization Problems, Nonlocal robust tensor recovery with nonconvex regularization ^*, Tensor Spaces and Hierarchical Tensor Representations, Guarantees for Existence of a Best Canonical Polyadic Approximation of a Noisy Low-Rank Tensor, Robust Tensor Completion: Equivalent Surrogates, Error Bounds, and Algorithms, A generalization of inverse power method for computing eigenpairs of symmetric tensors, A Semidefinite Relaxation Method for Partially Symmetric Tensor Decomposition, Tensor Regression Using Low-Rank and Sparse Tucker Decompositions, Ergodicity Coefficients for Higher-Order Stochastic Processes, Further results on sum-of-squares tensors, A public key cryptosystem based on data complexity under quantum environment, An adaptive gradient method for computing generalized tensor eigenpairs, On $\ell_p$-Support Vector Machines and Multidimensional Kernels, The Optimization Landscape for Fitting a Rank-2 Tensor with a Rank-1 Tensor, Newton Correction Methods for Computing Real Eigenpairs of Symmetric Tensors, Successive Rank-One Approximations for Nearly Orthogonally Decomposable Symmetric Tensors, An Adaptive Correction Approach for Tensor Completion, How to iron out rough landscapes and get optimal performances: averaged gradient descent and its application to tensor PCA, Tensor Completion in Hierarchical Tensor Representations, A Counterexample to Comon's Conjecture, Rank-1 Tensor Properties with Applications to a Class of Tensor Optimization Problems, Quantum machine learning: a classical perspective, Quantum algorithm for multivariate polynomial interpolation, A General Theory of Singular Values with Applications to Signal Denoising, 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, Unnamed Item, 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, Statistically optimal and computationally efficient low rank tensor completion from noisy entries, Nonconvex Low-Rank Tensor Completion from Noisy Data, Generalized notions of sparsity and restricted isometry property. II: Applications, Statistical thresholds for tensor PCA, When does OMP achieve exact recovery with continuous dictionaries?, Robust low transformed multi-rank tensor methods for image alignment, An approximation method of CP rank for third-order tensor completion, Optimization on the Euclidean Unit Sphere, Recognition of absolutely irreducible matrix groups that are tensor decomposable or induced, The symmetric rank and decomposition of \(m\)-order \(n\)-dimensional \((n = 2,3,4)\) symmetric tensors over the binary field, Unnamed Item, Kronecker-structured covariance models for multiway data, The average number of critical rank-one approximations to a tensor, Generalized eigenvalue for even order tensors via Einstein product and its applications in multilinear control systems, Maximization of homogeneous polynomials over the simplex and the sphere: structure, stability, and generic behavior, Rapid solution of problems by quantum computation, Rank properties and computational methods for orthogonal tensor decompositions, Randomized algorithms in numerical linear algebra, $N$-Dimensional Tensor Completion for Nuclear Magnetic Resonance Relaxometry, Low Rank Symmetric Tensor Approximations, The location of H-eigenvalues of real even order symmetry tensors, Spectral norm of a symmetric tensor and its computation, Enhancing low-rank tensor completion via first-order and second-order total variation regularizations, Singular vectors of orthogonally decomposable tensors, Mixed membership Gaussians, New \(Z\)-eigenvalue inclusion theorem of tensors with application to the geometric measure of entanglement, Nuclear norm of higher-order tensors, Unnamed Item, T-product factorization based method for matrix and tensor completion problems, Structured Matrix Problems from Tensors, Lower bounds on the rank and symmetric rank of real tensors, On some general operators of hypergraphs, Bounded-rank tensors are defined in bounded degree, Non-degenerate 2 × k × (k + 1) hypermatrices, The Power of Tensor-Based Approaches in Cardiac Applications, Synthetic Aperture Imaging and Motion Estimation Using Tensor Methods, The Epsilon-Alternating Least Squares for Orthogonal Low-Rank Tensor Approximation and Its Global Convergence, Tensor Train Construction From Tensor Actions, With Application to Compression of Large High Order Derivative Tensors, Estimating Higher-Order Moments Using Symmetric Tensor Decomposition, HIGH-ORDER COPOSITIVE TENSORS AND ITS APPLICATIONS, Algebraic Methods for Tensor Data, On the equivalence between low-rank matrix completion and tensor rank, Behavior of the Fréchet mean and central limit theorems on spheres, Deterministic Tensor Completion with Hypergraph Expanders, Learning with tensors: a framework based on convex optimization and spectral regularization, Computing Tensor Eigenvalues via Homotopy Methods, Tensor completion based on triple tubal nuclear norm, \(M\)-eigenvalues-based sufficient conditions for the positive definiteness of fourth-order partially symmetric tensors, Matrix completion and tensor rank, Random Projections for Low Multilinear Rank Tensors, An iterative algorithm based on strong \(\mathcal{H} \)-tensors for identifying positive definiteness of irreducible homogeneous polynomial forms, Inverse Optimization with Noisy Data, Resonator Networks, 2: Factorization Performance and Capacity Compared to Optimization-Based Methods, 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, Low-Rank Approximation and Completion of Positive Tensors, Bounds on the Spectral Norm and the Nuclear Norm of a Tensor Based on Tensor Partitions, Exclusion sets in the \({\Delta}\)-type eigenvalue inclusion set for tensors, The Computational Complexity of Duality, Solving equations of random convex functions via anchored regression, Computing Eigenvalues of Large Scale Sparse Tensors Arising from a Hypergraph, Comon's Conjecture, Rank Decomposition, and Symmetric Rank Decomposition of Symmetric Tensors, 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, Incremental CP Tensor Decomposition by Alternating Minimization Method, Systems of Polynomial Equations, Higher-order Tensor Decompositions, and Multidimensional Harmonic Retrieval: A Unifying Framework. Part I: The Canonical Polyadic Decomposition, Low-rank tensor completion using matrix factorization based on tensor train rank and total variation, Solving tensor E-eigenvalue problem faster, A Higher Order Unscented Transform, Unnamed Item, Unnamed Item, Relations of the nuclear norm of a tensor and its matrix flattenings, Three Hypergraph Eigenvector Centralities, An optimal statistical and computational framework for generalized tensor estimation, Tensor clustering with planted structures: statistical optimality and computational limits, Convergence rate analysis for the higher order power method in best rank one approximations of tensors, A note on Banach's results concerning homogeneous polynomials associated with nonnegative tensors, Inference for low-rank tensors -- no need to debias, Tensor norm and maximal singular vectors of nonnegative tensors -- a Perron-Frobenius theorem, a Collatz-Wielandt characterization and a generalized power method, Learning diagonal Gaussian mixture models and incomplete tensor decompositions, On the nuclear norm and the singular value decomposition of tensors, A very brief introduction to nonnegative tensors from the geometric viewpoint, Numerical ranges of tensors, Continuation methods for computing Z-/H-eigenpairs of nonnegative tensors, On the rank of a Latin tensor, 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, Completely positive tensor recovery with minimal nuclear value, 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, On tensor completion via nuclear norm minimization, The set of orthogonal tensor trains, Bounding the equivariant Betti numbers of symmetric semi-algebraic sets, Checking strict positivity of Kraus maps is NP-hard, 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, Accurate calculation of the geometric measure of entanglement for multipartite quantum states, Self-concordance is NP-hard, High-order sum-of-squares structured tensors: theory and applications, Eigenvectors of tensors and algorithms for Waring decomposition, Block tensors and symmetric embeddings, Monotonically convergent algorithms for symmetric tensor approximation, Orthogonal and unitary tensor decomposition from an algebraic perspective, Effective identifiability criteria for tensors and polynomials, Matrix factorization for low-rank tensor completion using framelet prior, \(p\)-norm \(B\)-tensors and \(p\)-norm \(B_0\)-tensors, An efficient tree decomposition method for permanents and mixed discriminants, The generalized inverses of tensors and an application to linear models, Symmetric matrices whose entries are linear functions, The numerical approximation of nonlinear functionals and functional differential equations, Deterministic approximation algorithms for sphere constrained homogeneous polynomial optimization problems, Adaptive total variation and second-order total variation-based model for low-rank tensor completion, Higher-order principal component analysis for the approximation of tensors in tree-based low-rank formats, A spectral theory for tensors, Calculating entanglement eigenvalues for nonsymmetric quantum pure states based on the Jacobian semidefinite programming relaxation method, Cross: efficient low-rank tensor completion, On the spectrum of hypergraphs, The number of singular vector tuples and uniqueness of best rank-one approximation of tensors, Some criteria for identifying strong \(\mathcal{H}\)-tensors, Alternating iterative methods for solving tensor equations with applications, Further results on Cauchy tensors and Hankel tensors, Principal eigenvector of the signless Laplacian matrix, On decompositions and approximations of conjugate partial-symmetric tensors, Phase transition in random tensors with multiple independent spikes, Tensor networks and hierarchical tensors for the solution of high-dimensional partial differential equations, Programmable sufficient conditions for the strong ellipticity of partially symmetric tensors, Semidefinite approximations of conical hulls of measured sets, Operator norm inequalities between tensor unfoldings on the partition lattice, Copositive tensor detection and its applications in physics and hypergraphs, Tensor completion using total variation and low-rank matrix factorization, Finding a low-rank basis in a matrix subspace, Real eigenvalues of nonsymmetric tensors, On cones of nonnegative quartic forms, 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, Rank-\(r\) decomposition of symmetric tensors, Tensor convolutions and Hankel tensors, Further results on \(B\)-tensors with application to location of real eigenvalues, The complexity of tensor rank, Dynamic background modeling using tensor representation and ant colony optimization, 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_8\) discriminant, Tensor Q-rank: new data dependent definition of tensor rank, Community detection on mixture multilayer networks via regularized tensor decomposition, A new class of positive semi-definite tensors, Algorithmic thresholds for tensor PCA, 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, A locally convergent Jacobi iteration for the tensor singular value problem, Tensor slice rank and Cayley's first hyperdeterminant, A new tensor multi-rank approximation with total variation regularization for tensor completion, Distribution of the eigenvalues of a random system of homogeneous polynomials, 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