Information Technology Reference
In-Depth Information
The sum of
r
generic rank-one tensors is described by
rdn
varibles. Its entries are
multilinear polynomials in these variables. A generic tensor in
V
≤
d
is described by
n
d
variables, all of them begin algebraically independent. Therefore,
rnd
n
d
∧
is
required to write every tensor as a sum of
r
rank-one tensor, that is,
n
d
−
1
d
r
∧
.
This is a very simple argument, but sufficient for our needs and almost optimal. With
more sophisticated ones, we can get tighter bounds, see the work of Lickteig and
Strassen for three-dimensional tensors [
Lic85
,
Str83
], see Landsberg's topic for the
general case [
Lan11
].
From the argument above, it follows that there is a tensor with rank at least
n
d
−
1
d
. But even random tensors have at least this rank with high probability. The
entries of tensors that can be written as the sum of fewer rank-one tensors are alge-
braically dependent, since they can we written as polynomials in less than
n
d
vari-
ables. Therefore, these entries fulfill some polynomial relation. It is well known that
random points do not fufill polynomial relations with high probability. In theoretical
computer science, this fact is known as the Schwartz-Zippel lemma.
2
Lemma 1
/
(Schwartz-Zippel)
Let F be a field. Let p be a nonzero polynomial in
F
[
X
1
,...,
X
n
]
of total degree d. Let S
∃
F . Then
Pr
r
1
,...,
S
[
p
(
r
1
,...,
r
n
)
=
0
]ↆ|
S
|
/
d
.
r
n
∗
Even if we do not know a bound on the polynomial describing the algebraic
dependence, if the underlying field is large enough or even infinite, a random tensor
will have rank
n
d
−
1
d
with high probability.
Although it sounds very simple, it is a major open problem to find a tensor of
high rank that is explicit, i.e., whose entries can be constructed by a
deterministic
polynomial time algorithm.
∧
/
6.3 Explicit Tensors from Bilinear Mappings
This section shows the present (poor) knowledge of how to construct explicit tensors
of high rank.
6.3.1 The Rank of Bilinear Mappings and Algebras
Let
˕
:
W
be a bilinear mapping. Every bilinear map corresponds in a
unique way to a tensor
t
˕
U
×
V
≥
in
U
∈
≤
V
∈
≤
W
,see(
6.1
). Since a vector space and its
2
The name of the lemma is justified because Schwartz and independently Zippel were the
last
to
prove this lemma.
