Tensor rank is NP-complete
From MaRDI portal
Publication:3203928
DOI10.1016/0196-6774(90)90014-6zbMath0716.65043OpenAlexW2106221905WikidataQ56959220 ScholiaQ56959220MaRDI QIDQ3203928
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
Analysis of algorithms and problem complexity (68Q25) Vector and tensor algebra, theory of invariants (15A72) Complexity of computation (including implicit computational complexity) (03D15) Complexity and performance of numerical algorithms (65Y20)
Related Items
More on Tensors with Different Rank and Symmetric Rank, Unnamed Item, The tensor rank of semifields of order 16 and 81, Numerical solution of high dimensional stationary Fokker-Planck equations via tensor decomposition and Chebyshev spectral differentiation, Low Permutation-rank Matrices: Structural Properties and Noisy Completion, A public key cryptosystem based on data complexity under quantum environment, MIONet: Learning Multiple-Input Operators via Tensor Product, On the nuclear norm and the singular value decomposition of tensors, Numerical tensor techniques for multidimensional convolution products, Logic minimization techniques with applications to cryptology, On the rank of a Latin tensor, The complexity of counting edge colorings and a dichotomy for some higher domain Holant problems, Bounding the separable rank via polynomial optimization, Smoothed analysis for tensor methods in unsupervised learning, On the optimization landscape of tensor decompositions, Interpolatory tensorial reduced order models for parametric dynamical systems, Tensor Completion in Hierarchical Tensor Representations, Non-minimum tensor rank Gabidulin codes, Tucker factorization with missing data with application to low-\(n\)-rank tensor completion, Quantum algorithm for multivariate polynomial interpolation, A randomized algorithm for a tensor-based generalization of the singular value decomposition, A General Theory of Singular Values with Applications to Signal Denoising, A note on the gap between rank and border rank, The \(G\)-stable rank for tensors and the cap set problem, Low rank tensor recovery via iterative hard thresholding, Practical post-quantum signature schemes from isomorphism problems of trilinear forms, An inexact continuation accelerated proximal gradient algorithm for lown-rank tensor recovery, An approximation method of CP rank for third-order tensor completion, Optimization on the Euclidean Unit Sphere, General linear group action on tensors: a candidate for post-quantum cryptography, $(L_r,L_r,1)$-Decompositions, Sparse Component Analysis, and the Blind Separation of Sums of Exponentials, An introduction to the computational complexity of matrix multiplication, Low rank interpolation of boundary spline curves, On the complexity of finding tensor ranks, Tensorized low-rank circulant preconditioners for multilevel Toeplitz linear systems from high-dimensional fractional Riesz equations, Tripartite-to-bipartite entanglement transformation by stochastic local operations and classical communication and the structure of matrix spaces, Tensor network alternating linear scheme for MIMO Volterra system identification, Monotonically convergent algorithms for symmetric tensor approximation, Solution of linear systems in high spatial dimensions, The average number of critical rank-one approximations to a tensor, Rapid solution of problems by quantum computation, Rank properties and computational methods for orthogonal tensor decompositions, Tensor surgery and tensor rank, Constructive representation of functions in low-rank tensor formats, Cayley's hyperdeterminant: A combinatorial approach via representation theory, Quantum \(k\)-uniform states for heterogeneous systems from irredundant mixed orthogonal arrays, Parallel Candecomp/Parafac Decomposition of Sparse Tensors Using Dimension Trees, Entanglement transformation between ensembles of three-qubit GHZ-type states by LOCC, Unnamed Item, The average condition number of most tensor rank decomposition problems is infinite, On the Representation of Symmetric and Antisymmetric Tensors, Hankel Tensor Decompositions and Ranks, Barriers for Rank Methods in Arithmetic Complexity, A spectral theory for tensors, The Power of Tensor-Based Approaches in Cardiac Applications, Entanglement manipulation beyond local operations and classical communication, Random arithmetic formulas can be reconstructed efficiently, Algebraic Methods for Tensor Data, On the equivalence between low-rank matrix completion and tensor rank, Computing dense tensor decompositions with optimal dimension trees, Tensor Rank is Hard to Approximate, Finding a low-rank basis in a matrix subspace, Learning with tensors: a framework based on convex optimization and spectral regularization, Well-posedness of convex maximization problems on Stiefel manifolds and orthogonal tensor product approximations, Partition arguments in multiparty communication complexity, Improved method for finding optimal formulas for bilinear maps in a finite field, Numerical tensor calculus, On the complexity of noncommutative polynomial factorization, The complexity of tensor rank, Average-case linear matrix factorization and reconstruction of low width algebraic branching programs, An adaptive prefix-assignment technique for symmetry reduction, A numerical solver for high dimensional transient Fokker-Planck equation in modeling polymeric fluids, An iterative algorithm for third-order tensor multi-rank minimization, Best Nonnegative Rank-One Approximations of Tensors, Tensor Representation of Rank-Metric Codes, Matrix completion and tensor rank, Tensor theta norms and low rank 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, Tensor networks for MIMO LPV system identification, The LSQR method for solving tensor least-squares problems, An inexact augmented Lagrangian method for computing strongly orthogonal decompositions of tensors, Truncation of tensors in the hierarchical format, Unnamed Item, Pencil-Based Algorithms for Tensor Rank Decomposition are not Stable, Comon's Conjecture, Rank Decomposition, and Symmetric Rank Decomposition of Symmetric Tensors, Tensor Q-rank: new data dependent definition of tensor rank, Tripartite Entanglement Transformations and Tensor Rank, Tucker tensor analysis of Matérn functions in spatial statistics, On decompositions of complete hypergraphs, Incremental CP Tensor Decomposition by Alternating Minimization Method, The asymptotic induced matching number of hypergraphs: balanced binary strings, A Splitting Augmented Lagrangian Method for Low Multilinear-Rank Tensor Recovery, A fast alternating least squares method for third-order tensors based on a compression procedure, Tensor representation of non-linear models using cross approximations, Matrix pencils and entanglement classification, Robust tensor recovery with nonconvex and nonsmooth regularization, On the Compressibility of Tensors, Ranks of tensors, secant varieties of Segre varieties and fat points, A note on the ranks of 2 × 2 × 2 and 2 × 2 × 2 × 2 tensors, Robust and resource-efficient identification of two hidden layer neural networks
