Rank and optimal computation of generic tensors

DOI10.1016/0024-3795(83)80041-XzbMath0514.15018WikidataQ60307007 ScholiaQ60307007MaRDI QIDQ1051066

Volker Strassen

Publication date: 1983

Published in: Linear Algebra and its Applications (Search for Journal in Brave)

zbMATH Keywords

computational complexityrank of tensorsoptimal bilinear computationsoptimal computation of generic tensorsperfect shape

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Vector and tensor algebra, theory of invariants (15A72) Quadratic and bilinear forms, inner products (15A63) Multilinear algebra, tensor calculus (15A69)

Related Items

Border rank of m\(\times n\times (mn-q)\) tensors, Tensor decomposition for learning Gaussian mixtures from moments, A lower bound for the border rank of a bilinear map, On the spectral problem for trivariate functions, A very brief introduction to nonnegative tensors from the geometric viewpoint, Smoothed analysis for tensor methods in unsupervised learning, Generic Uniqueness Conditions for the Canonical Polyadic Decomposition and INDSCAL, Maximal bilinear complexity and codes, Segre Functions in Multiprojective Spaces and Tensor Analysis, A probabilistic algorithm for the secant defect of Grassmann varieties, Abelian tensors, On the geometry of geometric rank, Equations for secant varieties of Veronese and other varieties, Communication complexity of multi-processor systems, Fundamental invariants for the action of $SL_3(\mathbb {C}) \times SL_3(\mathbb {C}) \times SL_3(\mathbb {C})$ on $3 \times 3 \times 3$ arrays, Symmetric tensor decomposition, An introduction to the computational complexity of matrix multiplication, Condition numbers for the tensor rank decomposition, The subbundles of decomposable vector bundles over an elliptic curve, Tensor decomposition and homotopy continuation, The rank of \(n \times n\) matrix multiplication is at least \(3n^2 - 2\sqrt{2}n^{\frac{3}{2}} - 3n\), Algebraic geometry and representation theory in the study of matrix multiplication complexity and other problems in theoretical computer science, On the Geometry of Border Rank Decompositions for Matrix Multiplication and Other Tensors with Symmetry, Ranks of tensors and a generalization of secant varieties, On tensors of border rank \(l\) in \({\mathbb C}^{m\times n\times l}\), Typical ranks for \(m\times n\times (m-1)n\) tensors with \(m \leq n\), Effective Criteria for Specific Identifiability of Tensors and Forms, Geometry and the complexity of matrix multiplication, A generalization of Kruskal’s theorem on tensor decomposition, On the structure tensor of \(\mathfrak{sl}_n\), Identifiability of an X-Rank Decomposition of Polynomial Maps, Tensor rank: matching polynomials and Schur rings, Tensor surgery and tensor rank, Real and complex rank for real symmetric tensors with low ranks, Concise tensors of minimal border rank, Bad and good news for Strassen's laser method: border rank of \(\mathrm{Perm}_3\) and strict submultiplicativity, Identifiability of large phylogenetic mixture models, New lower bounds for matrix multiplication and, Estimation under group actions: recovering orbits from invariants, On Uniqueness and Computation of the Decomposition of a Tensor into Multilinear Rank-$(1,L_r,L_r)$ Terms, Tensor rank is not multiplicative under the tensor product, Hadamard products of linear spaces, Tensor decompositions and rank increment conjecture, Bilinear complexity of algebras and the Chudnovsky-Chudnovsky interpolation method, Fast structured matrix computations: tensor rank and Cohn-Umans method, Unnamed Item, On Waring's problem for systems of skew-symmetric forms, On generic identifiability of symmetric tensors of subgeneric rank, Vanishing Hessian, wild forms and their border VSP, Plücker varieties and higher secants of Sato's Grassmannian, An upper bound for the tensor rank, Unnamed Item, On the \(X\)-rank with respect to linearly normal curves, Bounded-rank tensors are defined in bounded degree, Hyperdeterminants of polynomials, On the generic and typical ranks of 3-tensors, Higher secant varieties of \(\mathbb P^n \times \mathbb P^n\) embedded in bi-degree \((1,d)\), An asymptotic bound for secant varieties of Segre varieties, Inequalities for the ranks of multipartite quantum states, The \(3\times 3\times 3\) hyperdeterminant as a polynomial in the fundamental invariants for \(\mathrm{SL}_3(\mathbb C)\times\mathrm{SL}_3(\mathbb C)\times\mathrm{SL}_3(\mathbb C)\), Refined methods for the identifiability of tensors, Algebraic geometry of Bayesian networks, Fast bilinear algorithms for symmetric tensor contractions, Fundamental invariants of orbit closures, Phylogenetic ideals and varieties for the general Markov model, Toward a Salmon Conjecture, Ranks derived from multilinear maps, Typical ranks ofm×n× (m− 1)ntensors with 3 ≤m≤nover the real number field, Beyond the Alder-Strassen bound., A proof of the set-theoretic version of the salmon conjecture, On the generic rank of matrices composed of Kronecker products, Induction for secant varieties of Segre varieties, Subtracting a best rank-1 approximation may increase tensor rank, The border rank of the multiplication of $2\times 2$ matrices is seven, Generic and typical ranks of multi-way arrays, On the Geometry of Border Rank Algorithms for n × 2 by 2 × 2 Matrix Multiplication, Rank and border rank of Kronecker powers of tensors and Strassen's laser method, Efficient parallel linear programming, Fiber Sampling Approach to Canonical Polyadic Decomposition and Application to Tensor Completion, Homotopy techniques for tensor decomposition and perfect identifiability, Border Rank Nonadditivity for Higher Order Tensors, Semialgebraic Geometry of Nonnegative Tensor Rank, Grothendieck constant is norm of Strassen matrix multiplication tensor, The Hitchhiker guide to: secant varieties and tensor decomposition, A note on border rank, Coupled Canonical Polyadic Decompositions and (Coupled) Decompositions in Multilinear Rank-$(L_r,n,L_r,n,1)$ Terms---Part I: Uniqueness, Nontriviality of equations and explicit tensors in \(\mathbb{C}^m \otimes \mathbb{C}^m \otimes \mathbb{C}^m\) of border rank at least \(2m - 2\), Ranks of tensors, secant varieties of Segre varieties and fat points, Unnamed Item, Guarantees for Existence of a Best Canonical Polyadic Approximation of a Noisy Low-Rank Tensor, Typical tensorial rank, Unifying known lower bounds via geometric complexity theory

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the maximal multiplicative complexity of a family of bilinear forms
• On varieties of optimal algorithms for the computation of bilinear mappings. I. The isotropy group of a bilinear mapping
• On varieties of optimal algorithms for the computation of bilinear mappings. II. Optimal algorithms for \(2\times 2\)-matrix multiplication
• Bounds on the ranks of some 3-tensors
• On varieties of optimal algorithms for the computation of bilinear mappings. III. Optimal algorithms for the computation of \(xy\) and \(yx\) where \(x,y\in M_2(K)\)
• Relations between exact and approximate bilinear algorithms. Applications
• On the algorithmic complexity of associative algebras
• Base tensorielle des matrices de Hankel (ou de Toeplitz). Applications
• Three-way arrays: rank and uniqueness of trilinear decompositions, with application to arithmetic complexity and statistics
• Global properties of tensor rank
• \(0(n^{2.7799})\) complexity for \(n\times n\) approximate matrix multiplication
• Sur le calcul des produits de matrices. (Calculation of the product of matrices.)
• The Computational Complexity of Continued Fractions
• Characterization of Division Algebras of Minimal Rank and the Structure of their Algorithm Varieties
• A remark on certain matrix varieties
• Some bilinear forms whose multiplicative complexity depends on the field of constants
• Universality of iterated networks
• Optimal evaluation of pairs of bilinear forms
• Introduction to Lie Algebras and Representation Theory
• Further Pathologies in Algebraic Geometry