Information Technology Reference
In-Depth Information
In the same way, we get
R
(
T
2
m
+
1
)
∧
R
(
T
m
)
+
2
m
.
It is easy to verify that the bound stated in the theorem is the solution of this recurrence.
We can now extend this to a tensor of size
n
×
(
n
+
1
)
×
n
by extending the slices
above by one column and then add
n
linearly independent slices, which just
have a one in the extra column. These slices can be substituted away and we get a
tensor of size
n
−
(ˇ
+
1
)
m
e
×
(
n
+
1
)
×
n
with rank bounded by 3
n
−
(
log
n
)
.Ifweset
n
=
and add just
m
extra slices, we get a tensor of size
m
e
m
e
m
e
×
(
+
1
)
×
the rank of
2
m
e
which can be lower bounded by 2
n
+
m
−
(
log
n
)
=
+
m
−
(
d
log
m
)
.As
1in
m
e
before, we can interpret this tensor as a tensor of order 2
e
1
the second component disturbs this construction a little bit, to remedy this, we can
start with a tensor of size
+
1. (The
+
+
(
n
−
1
)
×
(
n
−
1
)
×
(
n
−
1
)
and then extend this to a tensor
of size
n
n
by adding zeros.)
If you look at the construction closely, we can view this again as a tensor related
to an algebra, as pointed by Landsberg [
Lan13
]. For simplicity, assume that
n
is a
power of 2. Otherwise, the tensor will just have some additional zeros. It is quite easy
to see, that up to permutations, the tensor
T
n
are just the slices 1
×
n
×
2
i
2
ˇ
,
2
,...,
,...,
X
n
of the tensor of the algebra
k
[
X
]
/(
)
. For instance,
T
8
has the form
⊤
⊝
12 3
4
⊛
⊠
2
3
4
3
4
3
4
T
8
=
4
4
4
4
Looking at this, it is easy to see that we can project away the lower four rows and
four columns to the righthand side. This reduces the rank by 8 (in general by
n
) and
affects only the fourth slice. We can remove this slice and get
T
4
. Using induction,
we get a lower bound of 1
+
2
+
4
+
8
=
15 (in general 2
n
−
1, note that
n
is a
power of 2).
6.5 Conclusions
In the examples we have seen, the bounds on the rank are proven via the substitution
method. The bounds that are achievable with this method are usually limited by the
sum of the dimension of the vector spaces. Up to lower order terms, our constructions
reach this limit. To get better bounds, new lower bound techniques are needed. One
promising approach for this is the geometric complexity approach by Bürgisser and
Ikenmeyer [
BI11
,
BI12
].
