Tensor rank is NP-complete

DOI10.1016/0196-6774(90)90014-6zbMATH Open0716.65043OpenAlexW2106221905WikidataQ56959220 ScholiaQ56959220MaRDI QIDQ3203928FDOQ3203928

Authors: Johan Hastad 

Publication date: 1990

Published in: Journal of Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0196-6774(90)90014-6

Recommendations

• The complexity of tensor rank
• On the complexity of finding tensor ranks
• Tensor rank is hard to approximate
• scientific article; zbMATH DE number 7387190
• Bounds on the tensor rank
• An upper bound for the tensor rank
• Tensor decompositions and rank increment conjecture
• Tensor decompositions in rank \(+1\)
• Matrix completion and tensor rank
• Most tensor problems are NP-hard

zbMATH Keywords

finite fieldNP-complete problemsNP-hard problemstensor rank

Mathematics Subject Classification ID

Complexity and performance of numerical algorithms (65Y20) Analysis of algorithms and problem complexity (68Q25) Vector and tensor algebra, theory of invariants (15A72) Complexity of computation (including implicit computational complexity) (03D15)

Cited In (only showing first 100 items - show all)

• Robust and resource-efficient identification of two hidden layer neural networks
• Tensor representation of rank-metric codes
• Well-posedness of convex maximization problems on Stiefel manifolds and orthogonal tensor product approximations
• Low permutation-rank matrices: structural properties and noisy completion
• Title not available (Why is that?)
• On decompositions of complete hypergraphs
• Partition arguments in multiparty communication complexity
• Computing dense tensor decompositions with optimal dimension trees
• A randomized algorithm for a tensor-based generalization of the singular value decomposition
• Cayley's hyperdeterminant: A combinatorial approach via representation theory
• Title not available (Why is that?)
• Parallel Candecomp/Parafac decomposition of sparse tensors using dimension trees
• On the optimization landscape of tensor decompositions
• The tensor rank of semifields of order 16 and 81
• Pencil-based algorithms for tensor rank decomposition are not stable
• Tensor theta norms and low rank recovery
• Tensor network alternating linear scheme for MIMO Volterra system identification
• Constructive representation of functions in low-rank tensor formats
• A note on the ranks of \(2\times 2\times 2\) and \(2\times 2\times 2\times 2\) tensors
• Entanglement transformation between ensembles of three-qubit GHZ-type states by LOCC
• A numerical solver for high dimensional transient Fokker-Planck equation in modeling polymeric fluids
• The complexity of tensor rank
• Tucker tensor analysis of Matérn functions in spatial statistics
• On the rank of a Latin tensor
• Smoothed analysis for tensor methods in unsupervised learning
• On the nuclear norm and the singular value decomposition of tensors
• Tensor surgery and tensor rank
• An introduction to the computational complexity of matrix multiplication
• Bounding the separable rank via polynomial optimization
• Solution of linear systems in high spatial dimensions
• An iterative algorithm for third-order tensor multi-rank minimization
• The complexity of counting edge colorings and a dichotomy for some higher domain Holant problems
• Low rank tensor recovery via iterative hard thresholding
• A fast alternating least squares method for third-order tensors based on a compression procedure
• Entanglement manipulation beyond local operations and classical communication
• Tensor rank is hard to approximate
• Tucker factorization with missing data with application to low-\(n\)-rank tensor completion
• Numerical tensor techniques for multidimensional convolution products
• Logic minimization techniques with applications to cryptology
• Comon's conjecture, rank decomposition, and symmetric rank decomposition of symmetric tensors
• Barriers for rank methods in arithmetic complexity
• Optimization on the Euclidean unit sphere
• Robust tensor recovery with nonconvex and nonsmooth regularization
• Low rank interpolation of boundary spline curves
• Tensor completion in hierarchical tensor representations
• Random arithmetic formulas can be reconstructed efficiently
• A splitting augmented Lagrangian method for low multilinear-rank tensor recovery
• Numerical solution of high dimensional stationary Fokker-Planck equations via tensor decomposition and Chebyshev spectral differentiation
• Truncation of tensors in the hierarchical format
• Monotonically convergent algorithms for symmetric tensor approximation
• An adaptive prefix-assignment technique for symmetry reduction
• The LSQR method for solving tensor least-squares problems
• The asymptotic induced matching number of hypergraphs: balanced binary strings
• On the complexity of finding tensor ranks
• Learning with tensors: a framework based on convex optimization and spectral regularization
• Rank properties and computational methods for orthogonal tensor decompositions
• Best nonnegative rank-one approximations of tensors
• Tensor Q-rank: new data dependent definition of tensor rank
• The average number of critical rank-one approximations to a tensor
• Ranks of tensors, secant varieties of Segre varieties and fat points
• Tripartite-to-bipartite entanglement transformation by stochastic local operations and classical communication and the structure of matrix spaces
• A spectral theory for tensors
• Rapid solution of problems by quantum computation
• Tripartite Entanglement Transformations and Tensor Rank
• Finding a low-rank basis in a matrix subspace
• Hankel Tensor Decompositions and Ranks
• Numerical tensor calculus
• An inexact augmented Lagrangian method for computing strongly orthogonal decompositions of tensors
• A note on the gap between rank and border rank
• Matrix pencils and entanglement classification
• Tensorized low-rank circulant preconditioners for multilevel Toeplitz linear systems from high-dimensional fractional Riesz equations
• An inexact continuation accelerated proximal gradient algorithm for low \textit{n}-rank tensor recovery
• Nonnegative tensor decomposition with custom clustering for microphase separation of block copolymers
• The border support rank of two-by-two matrix multiplication is seven
• A general theory of singular values with applications to signal denoising
• On the equivalence between low-rank matrix completion and tensor rank
• On the Compressibility of Tensors
• Classifying entanglement by algebraic geometry
• Improved method for finding optimal formulas for bilinear maps in a finite field
• Strassen's rank additivity for small tensors, including tensors of rank less or equal 7
• Rank of a tensor and quantum entanglement
• Title not available (Why is that?)
• Augmented Lagrangian method for tensor low-rank and sparsity models in multi-dimensional image recovery
• On the representation of symmetric and antisymmetric tensors
• Interpolatory tensorial reduced order models for parametric dynamical systems
• An Adaptive Sampling Strategy for Online Monitoring and Diagnosis of High-Dimensional Streaming Data
• Algebraic methods for tensor data
• Non-minimum tensor rank Gabidulin codes
• Tensor representation of non-linear models using cross approximations
• An approximation method of CP rank for third-order tensor completion
• More on Tensors with Different Rank and Symmetric Rank
• Tensor networks for MIMO LPV system identification
• Tensor Mixed Effects Model With Application to Nanomanufacturing Inspection
• The \(G\)-stable rank for tensors and the cap set problem
• Practical post-quantum signature schemes from isomorphism problems of trilinear forms
• General linear group action on tensors: a candidate for post-quantum cryptography
• Average-case linear matrix factorization and reconstruction of low width algebraic branching programs
• Generating hidden Markov models from process models through nonnegative tensor factorization
• \((L_r,L_r,1)\)-decompositions, sparse component analysis, and the blind separation of sums of exponentials
• Imbalanced low-rank tensor completion via latent matrix factorization

This page was built for publication: Tensor rank is NP-complete

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3203928)