Source-linked AI summary
Symmetric tensors and symmetric tensor rank
Pierre Comon, Gene Golub, Lek-Heng Lim, Bernard Mourrain
TL;DR
The paper examines how symmetric tensors decompose into symmetric rank-1 outer products and how their rank notions behave. It develops algebraic-geometric results on existence, equality cases, generic rank, and rank-bounded sets, while focusing mainly on complex tensors. The results establish broad rank relationships and characterize generic symmetric rank, alongside scope limitations for real-field and unresolved maximal-rank questions.
Problem
Symmetric tensor decomposition is insufficiently addressed, while computing or bounding symmetric rank remains far from resolved and rank-bounded sets can be ill-posed because they are not closed.
Method
The paper studies symmetric outer-product decompositions using multilinear algebra and algebraic geometry, including Veronese secant varieties and polynomial representations.
Results
The decomposition exists over any field; rank and symmetric rank coincide in several cases, generic symmetric rank is characterized by the Alexander-Hirschowitz theorem, and rank-at-most-r sets are not closed unless r = 1.
Takeaways & Limitations
Symmetric tensor rank has a developed generic theory, but practical determination of individual or maximal symmetric ranks remains unresolved.
Takeaways & Limitations
Most results concern complex-field decompositions; real-field decompositions require different techniques, and maximal symmetric rank remains unresolved.
Abstract
from arXiv · showhide
A symmetric tensor is a higher order generalization of a symmetric matrix. In this paper, we study various properties of symmetric tensors in relation to a decomposition into a sum of symmetric outer product of vectors. A rank-1 order-k tensor is the outer product of k non-zero vectors. Any symmetric tensor can be decomposed into a linear combination of rank-1 tensors, each of them being symmetric or not. The rank of a symmetric tensor is the minimal number of rank-1 tensors that is necessary to reconstruct it. The symmetric rank is obtained when the constituting rank-1 tensors are imposed to be themselves symmetric. It is shown that rank and symmetric rank are equal in a number of cases, and that they always exist in an algebraically closed field. We will discuss the notion of the generic symmetric rank, which, due to the work of Alexander and Hirschowitz, is now known for any values of dimension and order. We will also show that the set of symmetric tensors of symmetric rank at most r is not closed, unless r = 1.
1. Introduction.
The paper studies symmetric outer-product decompositions, their rank notions, and foundational properties of symmetric tensors. It addresses applications, unresolved computation questions, field restrictions, and geometric behavior of rank-bounded sets.
- Decomposition and rank: Symmetric tensors are decomposed into minimal linear combinations of symmetric outer products, generalizing eigenvalue decomposition for symmetric matrices.This defines symmetric tensor rank, which reduces to matrix rank for order-2 symmetric tensors.
- Applications: The symmetric outer-product decomposition is important for blind identification of under-determined mixtures and applications including signal processing, machine learning, and factor analysis.
- Open problem: The topic remains inadequately addressed in the literature, while fitting symmetric tensors of rank at most r is generally ill-posed because these sets are not closed unless r = 1.
- Contributions: The paper develops algebraic-geometric results on maximal and generic rank, equality of rank notions in specific cases, and the existence and non-maximality of generic rank.These results are presented after background material in multilinear algebra and algebraic geometry.
- Scope: The analysis focuses mostly on complex-field decompositions; corresponding real-field results require substantially different techniques.
2. Arrays and tensors.
This section establishes the relationship between tensors and their array representations, then introduces outer products, multilinear transforms, contractions, and basis changes.
- Array notation: A k-way array of complex numbers is a multidimensional array whose entries form a complex vector space under entry-wise addition and scalar multiplication.The space has dimension n1 · · · nk.
- Outer products: The outer product combines k vectors into an order-k array, and more generally combines arrays of orders k and ℓ into an array of order k + ℓ.For example, two vectors produce a matrix, while three vectors produce a 3-way array.
- Arrays and tensors: A k-way array represents an order-k tensor in a tensor-product space, with the identification depending on the chosen basis.The tensor-product and array spaces have the same dimension and are related by an isomorphism.
- Multilinear transforms: Multilinear transforms apply one matrix to each mode, and nonsingular square transforms can be interpreted as changes of basis.For three modes, the transformed array can be written using contractions as A′ = A•1L•2M•3N.
- Contraction products: The mode-p inner product contracts two arrays by summing over their shared pth index, producing an array of order k + ℓ − 2.
3. Symmetric arrays and symmetric tensors.
The section characterizes symmetric arrays and tensors through permutation invariance, symmetrization, and polynomial correspondence. It also introduces a non-degenerate bilinear form for homogeneous polynomials.
- Symmetric arrays: A cubical k-way array has equal dimensions, and it is symmetric when its entries remain unchanged under every permutation of its k indices.
- Symmetric tensors: Symmetrization projects the tensor-product space onto the subspace of symmetric tensors, which are precisely the tensors fixed by all permutation operators.The symmetrization operator satisfies S^2 = S.
- Basis: The symmetric basis consists of symmetrized tensor products with nondecreasing indices and spans the symmetric tensor space.Its elements are linearly independent and indexed by multiplicities of basis vectors.
- Polynomial correspondence: Every order-k symmetric tensor corresponds bijectively to a homogeneous polynomial of degree k in n variables, also called a quantic.This identification supports the use of algebraic geometry to study symmetric tensor rank.
- Bilinear form: The polynomial pairing is a symmetric, non-degenerate bilinear form but is not an inner product because ⟨F, F⟩ can be complex-valued.When G is a kth power of a linear form, a dedicated lemma describes the resulting pairing with any F.
- Equivalence: The paper proves that tensor symmetry and permutation invariance of the corresponding coordinate array are equivalent.
4. Notions of rank for symmetric tensors.
The paper distinguishes unrestricted tensor rank from symmetric rank, establishes when symmetric decompositions exist, and connects symmetric tensors with homogeneous polynomials and Veronese secant varieties.
- Rank comparison: The paper notes that rank and symmetric rank are equal in several regimes, but equality for all symmetric tensors remains unresolved.The stated cases include generic tensors with symmetric rank at most n, sufficiently large order, and symmetric rank 1 or 2.
- Rank definitions: Tensor rank is the smallest number of arbitrary rank-1 outer products needed to represent a tensor, while symmetric rank imposes identical vectors within each term.For symmetric tensors, the constrained decomposition defines rankS(A).
- Existence: Symmetric rank always exists for complex symmetric tensors because kth powers of linear forms span the symmetric-tensor space.The proof uses the fact that a nonzero degree-k polynomial cannot vanish on every linear form.
- Veronese geometry: A symmetric tensor has symmetric rank at most r exactly when it lies in the linear span of r points of the Veronese variety.The closure of these spans forms the (r−1)th secant variety.
- Independence: r pairwise non-collinear linear forms have linearly independent kth powers whenever k ≥ r − 1.The proof constructs a degree-k polynomial vanishing on r−1 selected points but not the remaining one.
- Polynomial viewpoint: Symmetric tensor rank corresponds to expressing a homogeneous degree-k polynomial as a sum of kth powers of linear forms.This correspondence identifies symmetric rank with membership in spans of points on the Veronese variety.
5. Rank and symmetric rank.
This section analyzes when ordinary rank and symmetric rank coincide, proving generic equality in key regimes and exact equality for symmetric rank 1 or 2, while exhibiting high-rank binary tensors.
- Generic equality: The paper asks whether ordinary rank and symmetric rank are always equal, and proves equality generically when rankS(A) ≤ n.For generic A with symmetric rank at most the dimension, the two ranks coincide.
- Proof strategy: The paper’s span arguments show that a decomposition with s generically independent symmetric factors cannot use fewer than s arbitrary rank-1 terms.Contraction places the symmetric factors in the span of the arbitrary decomposition’s factors, yielding r ≥ s, while the reverse inequality is immediate.
- Large-order equality: For pairwise linearly independent constituting vectors, ordinary and symmetric rank are generically equal when the tensor order k is sufficiently large.The proof contracts decompositions and compares spans of linearly independent tensor factors.
- Low symmetric rank: rank(A) = rankS(A) whenever rankS(A) is 1 or 2.The rank-2 case reduces to the generic span argument after showing the two constituting vectors must be linearly independent.
- Explicit construction: For any k > 1, the symmetric tensor formed by summing the k placements of v1 among k−1 copies of v2 has symmetric rank k.Here v1 and v2 are linearly independent.
- Binary tensors: The maximal symmetric rank for binary symmetric tensors is RS(k, 2) = k.These tensors lie on tangent lines to the Veronese variety, and examples exceed the range handled by a cited decomposition algorithm.
6. Generic symmetric rank and typical symmetric ranks.
The paper establishes how typical and generic symmetric ranks arise over C and characterizes the closure behavior of tensors with bounded symmetric rank. It also shows that symmetric-rank decompositions are generally non-closed for ranks above one, with consequences for Euclidean-density and random-data settings.
- Typical and generic rank: A generic symmetric rank always exists in Sk(Cn), and it is bounded above by the maximal symmetric rank.The generic rank is defined as the least r for which Yr equals the full symmetric-tensor space.
- Typical and generic rank: A typical rank r is one whose exact-rank set Zr is Zariski dense; over C, at most one such rank exists and is therefore generic.This follows because two dense algebraic sets over C must intersect, whereas a tensor cannot have two different ranks.
- Algebraic structure: The sets Yr of symmetric tensors with symmetric rank at most r are irreducible algebraic varieties and are ordered by inclusion.Their irreducibility follows from their construction as closures of parameterized images.
- Non-closed bounded-rank sets: For k > 2, Yr is not closed in several regimes: in particular, Y2 is not closed for n ≥ 2, and Yr is not closed for 1 < r ≤ n.Sequences can have symmetric rank r for every nonzero ε while converging to a tensor of rank r + 1; for r = 2, the limit can have rank k.
- Topological and probabilistic consequences: Over C, the unique generic-rank stratum is also dense in the Euclidean topology and has probability 1 under absolutely continuous random sampling, but these results do not generally hold over R.The probabilistic statement is relevant when tensor entries are sampled from distributions such as Gaussian laws.
7. Values of the generic symmetric rank.
The paper reports that the generic symmetric rank is known for all orders and dimensions over C through the Alexander–Hirschowitz theorem. It also examines when symmetric outer-product decompositions are finite or infinite by studying the dimension of their solution fibers.
- Alexander–Hirschowitz theorem: The generic symmetric rank problem was completely settled by Alexander and Hirschowitz in 1995 after earlier bounds and special-case results.The theorem is presented in the symmetric-tensor setting, although the original proof used multivariate polynomials and interpolation theory.
- Alexander–Hirschowitz theorem: For k > 2 over C, the generic symmetric rank equals the lower bound except for (k, n) ∈ {(3, 5), (4, 3), (4, 4), (4, 5)}, where it is increased by 1.These four cases are the exceptions specified by the Alexander–Hirschowitz theorem.
- Tables: The paper summarizes generic symmetric-rank values in Table 7.1 and generic fiber dimensions in Table 7.2.Table 7.1 marks the Alexander–Hirschowitz exceptions, while Table 7.2 records F(k, n).
- Uniqueness and solution fibers: The generic dimension of the decomposition fiber determines whether a generic symmetric outer-product decomposition has finitely many or infinitely many solutions.A nonzero fiber dimension corresponds to infinitely many decompositions.
8. Examples.
The examples show that symmetric-rank sets need not be closed, that real and complex symmetric ranks can differ, and that real tensors may have multiple typical ranks.
- RS(3, 3) = 4 while the maximal rank is 5; only Z4 is dense in Y5, whereas Z3 and Z5 are not closed.Z1 is closed.
- 8.1. Lack of closeness: A sequence of symmetric-rank-2 tensors can converge to a tensor of symmetric rank 3, demonstrating non-closure for r > 1 and k > 2.The construction uses two non-collinear vectors and a parameter ε ≠ 0.
- 8.1. Lack of closeness: A dimension-4 construction gives symmetric-rank-4 tensors converging to a limit of symmetric rank 6.
- 8.1. Lack of closeness: The order-3 dimension-3 example converges to a tensor of symmetric rank 5, the maximal rank for k = 3 and n = 3.The limiting tensor is represented as a sum of six asymmetric rank-1 terms and has symmetric rank 5.
- 8.2. Symmetric outer product decomposition over the real field: Real decompositions generally require more terms than complex decompositions; an example has symmetric rank 3 over R but 2 over C.For matrices, equality always holds, while strict inequality can occur for k > 2.
- 8.2. Symmetric outer product decomposition over the real field: For 2 × 2 × 2 symmetric tensors, the generic symmetric rank over C is 2, while the two typical symmetric ranks over R are 2 and 3.A matrix-pencil eigenvalue decomposition computes the symmetric outer product decomposition in this case; simulations produce real eigenvalues in 52% of cases and real symmetric rank 3 in 48%.
- 8.3. Open questions: The examples illustrate that real symmetric tensors are more complicated to analyze, while maximal symmetric rank remains known only for particular orders and dimensions.Explicit decomposition can also be computationally expensive, and polynomial-time conditions are not clearly known.