Information Technology Reference
In-Depth Information
6.2 Explicit Tensors of High Rank Imply Circuit Lower Bounds
6.2.1 Higher Order Tensors
We can generalize the concept of tensors of order three to higher orders. Let
V
1
,...,
V
n
be vector spaces, dim
V
i
=
d
i
,1
ↆ
i
ↆ
n
. The tensor product
V
1
≤ ··· ≤
V
n
can be built as follows: Choose bases
v
i
,
j
,1
ↆ
j
ↆ
d
i
, for each
V
i
. Then we formally built the elements
v
1
,
j
1
≤ ··· ≤
v
n
,
j
n
,1
ↆ
j
1
ↆ
d
1
,…,
1
ↆ
j
n
ↆ
d
n
. They form a basis of the vector space
V
1
≤ ··· ≤
V
n
.Ifwehave
arbitrary vectors
x
i
=
˃
i
,
1
v
i
,
1
+···
˃
i
,
d
i
v
i
,
d
i
∗
V
i
,1
ↆ
i
ↆ
d
i
, then
d
1
d
n
x
1
≤···≤
x
n
=
1
···
1
˃
1
,
j
1
···
˃
n
,
j
n
v
1
,
j
1
≤···≤
v
n
,
j
n
.
j
1
=
j
n
=
An element
v
1
≤···≤
v
n
with
v
i
∗
V
i
is a rank-one tensor. As before, the rank of a
tensor
t
∗
V
1
≤···≤
V
n
is minimum number of rank-one tensors
s
1
,...,
s
r
such that
t
=
s
1
+···+
s
r
.
The definition above is a coordinate-free definition of tensor rank. You can also
think in coordinates, if you prefer that:
V
i
is isomorphic to
k
d
i
, simply choose bases.
These isomorphims naturally extend to an isomorphism between
V
1
≤···≤
V
n
and
k
d
1
k
d
n
. There is also a way of defining tensor products without choosing
bases at all by the universal property of turning multilinear mappings into linear ones.
≤···≤
6.2.2 Basic Properties
Let
ʲ
∗
S
n
be a permutation of
{
1
,...,
n
}
.If
v
i
∗
V
i
, then
v
ʲ(
1
)
≤···≤
v
ʲ(
n
)
∗
V
ʲ(
1
)
≤···≤
V
ʲ(
n
)
.So
ʲ
identifies the rank-one tensors of
V
1
≤···≤
V
n
with the
rank-one tensors of
V
ʲ(
1
)
≤ ··· ≤
V
ʲ(
n
)
. We can extend this mapping to a linear
mapping
V
1
≤···≤
V
ʲ(
n
)
. This mapping clearly is surjective
and by comparing dimensions, we see that is is in fact an isomorphism. The image
of any tensor
t
under this mapping is denoted by
t
ʲ
.
If you think in coordinates, then the entries
t
i
1
,...,
i
n
of
t
ʲ
are defined by
t
i
1
,...,
i
n
V
n
≥
V
ʲ(
1
)
≤···≤
=
=
(
t
j
1
,...,
j
n
)
t
i
ʲ
−
1
(
1
)
,...,
i
ʲ
−
1
(
n
)
, where
t
.
t
ʲ
)
Fact 1
R
(
t
)
=
R
(
.
Let
U
1
,...,
U
n
be vector spaces. Let
h
i
:
V
i
≥
U
i
be homomorphism of vector
spaces, 1
ↆ
i
ↆ
n
. We get a mapping that maps the rank-one tensors of
V
1
≤···≤
V
n
to the rank-one tensors of
U
1
≤···≤
U
n
by
v
1
≤···≤
v
n
∩≥
h
1
(v
1
)
≤···≤
h
n
(v
n
).
