Information Technology Reference
In-Depth Information
so easy to come up with explicit matrices of high rank. We can compute the rank of
a matrix in polynomial time.
For tensors the situation is more complicated. Per se, it is even not clear what
the maximum rank of tensors in
k
ˇ
×
m
×
n
is.
1
We will discuss this briefly in the next
section. How to construct explicit tensors of high rank is a widely open problem.
And finally, computing the rank of a tensor is an
NP
-hard problem.
}
∈
.
Theorem 1
(Håstad [
Hås90
])
Let k be a field that can be represented over
{
0
,
1
k
ˇ
×
m
×
n
Let
Tensor
-
Rank
(over k) be the following problem: Given a tensor T
∗
and a bound b, decide whether R
(
T
)
ↆ
b.
1.
Over finite fields,
Tensor
-
Rank
is
NP
-complete.
2.
,
Tensor
-
Rank
is
NP
-hard.
What does it mean that “a field can be represented over
Over
Q
}
∈
”? Traditional com-
plexity classes like
P
or
NP
are defined over some fixed alphabet, sowe need to be able
to encode the field elements by
{
0
,
1
-strings. For instance, elements fromfinite fields
can be represented in binary and rational numbers by tuples of integers represented in
binary. The actual encoding does not matter as long as it is “reasonably nice”, that is,
all operations like addition, multiplication, etc., can be performed in polynomial time.
The hardness proof is the same over finite fields and over
{
0
,
1
}
. Over finite fields,
the problems is also
NP
-easy; we just have to guess
b
rank-one tensors and check
whether their sum is
T
.Over
Q
, it is not clear whether this is possible, since we do not
know an upper bound on the number of bits of the representation of the entries of the
rank-one tensors. It could be the case that the rank of
T
is
b
, but all sums of
b
rank-
one tensors involve rational numbers with a huge number of bits. (“Huge” means
superpolynomial in the size of the representation of the input tensor.) To the best of
my knowledge, it is even not known whether
Tensor-Rank
over
Q
Q
is decidable.
Over
R
, the situation is somewhat better:
R
itself is not representable over
{
0
,
1
}
,
but since
Q ∃ R
, we can look at tensors
T
over
Q
and ask what is the minimum
number of rank-one tensor with entries from
such that
T
is the sum of these rank-
one tensors. This problem is decidable and even in
PSPACE
, since it can be reduced
to the existential theory over the reals [
Can88
,
Ren92
].
R
Open Problem 1
What can you say about the approximability of
Tensor
-
Rank
?
Is there a constant factor approximation algorithm? A PTAS? As far as I know,
nothing in this direction is known.
Open Problem 2
What is the complexity of
Tensor
-
Rank
over
Q
?
M
i
)
∗
k
n
×
n
is a sequence of matrices that converges to a matrix
M
(componentwisely), then
Another important property of matrix rank is that it is semicontinuous. If
(
R
(
M
i
)
ↆ
r
for all
i
R
(
M
)
ↆ
r
.
1
Of course,
ˇ
mn
is an upper bound. However, it is not clear—and not true—that this is necessary.
