NOTIONS OF TENSOR RANK MANDAR JUVEKAR AND ARIAN NADJIMZADAH Abstract. Tensors or multi-linear forms are important objects

2025-05-02 0 0 408.91KB 19 页 10玖币

侵权投诉

NOTIONS OF TENSOR RANK

MANDAR JUVEKAR AND ARIAN NADJIMZADAH

Abstract. Tensors, or multi-linear forms, are important objects

in a variety of areas from analytics, to combinatorics, to compu-

tational complexity theory. Notions of tensor rank aim to quan-

tify the “complexity” of these forms, and are thus also important.

While there is one single deﬁnition of rank that completely cap-

tures the complexity of matrices (and thus linear transformations),

there is no deﬁnitive analog for tensors. Rather, many notions of

tensor rank have been deﬁned over the years, each with their own

set of uses. In this paper we survey the popular notions of ten-

sor rank. We give a brief history of their introduction, motivating

their existence, and discuss some of their applications in computer

science. We also give proof sketches of recent results by Lovett,

and Cohen and Moshkovitz, which prove asymptotic equivalence

between three key notions of tensor rank over ﬁnite ﬁelds with at

least three elements.

1. Introduction

We ﬁrst come across the notion of rank in a course on linear algebra.

If Ais an m×nmatrix over a ﬁeld F, the rank of Ais the dimension

of the space spanned by its rows (or columns). To help generalize this

deﬁnition, it will be useful to reinterpret the matrix Aas a bilinear

form T:Fm×Fn→Fby the natural correspondence

(x, y)∈Fm×Fn7→ T(x, y) = X

i,j

Ai,jxiyj.

As a notational convention, here and elsewhere in this paper we will use

superscripts to index coordinates of a vector, and subscripts to index

over diﬀerent vectors. For example, if x1, x2, . . . are vectors, x7

5would

be the seventh coordinate of the ﬁfth vector. Getting back to ranks,

using this correspondence, we can formulate an alternative deﬁnition

of rank where the rank of Tis the minimal natural number rsuch that

Tcan be written as a sum of rbilinear forms of “lowest” complexity,

or rank 1 matrices. The natural objects of lowest complexity are the

linear 1-forms, i.e., the dot product with a ﬁxed vector. Products of

Date: September 2022; Revised June 2023.

arXiv:2210.01183v2 [cs.CC] 14 Jun 2023

2 MANDAR JUVEKAR AND ARIAN NADJIMZADAH

1-forms T1(x)T2(y) are then bilinear forms. Since every bilinear form

can be written as a ﬁnite sum of forms of this type, we set them to

be our rank 1 bilinear forms (matrices). Putting everything together,

our alternative deﬁnition then says that the rank of a matrix Ais the

minimum natural number rsuch that the bilinear form Tcorresponding

to Acan be written as the sum of rbilinear forms each of the type

T1(x)T2(y) where T1and T2are 1-forms. This alternative deﬁnition

agrees with the usual linear algebra deﬁnition of rank (see for instance

[Hal58, Sections 32 and 51]).

In this paper we focus on generalizing the notion of rank to higher-

dimensional analogs of matrices. What are these higher-dimensional

matrices? The analogs in higher dimensions that we will look at are

the d-tensors.

Deﬁnition 1.1 (d-tensor).Let Fbe a ﬁeld. A d-tensor Ton Fn1× · · ·×

Fndis a multilinear map T:Fn1× · · · × Fnd→F.

Note that a d-tensor T:Fn1× · · · × Fnd→Fcan naturally be iden-

tiﬁed with a d-dimensional array Msuch that

T(x1,...xd) = X

i1∈[n1],...,id∈[nd]

Mi1,...,idxi1

1· · · xid

So, following the convention for matrices, we will often denote the space

of d-tensors on Fn1× · · · × Fndby Fn1×···×nd.1

The deﬁnition of rank given above generalizes well to arbitrary d-

tensors. Setting the rank 1 d-tensors to products of dlinear 1-forms

(or, since linear 1-forms are the same as 1-tensors, d1-tensors) leads

to the notion of rank that is traditionally associated with tensors. We

call it traditional rank, or TR for short.

Deﬁnition 1.2 (Traditional Rank).Ad-tensor Thas traditional rank

1if we can write

T(x1, . . . , xd) = T1(x1)T2(x2)· · · Td(xd),

where each Tjis a 1-tensor.

The traditional rank of an arbitrary d-tensor T, TR(T), is the mini-

mum number rsuch that we can write

T(x) =

i=1

Ti(x)

where each Tiis a d-tensor with traditional rank 1.

1Here and elsewhere in the paper we will use [n] to denote the set {1,2, . . . , n}.

NOTIONS OF TENSOR RANK 3

While this deﬁnition does generalize matrix rank it turns out that

there are also other, non-equivalent generalizations of matrix rank to

arbitrary tensors that characterize the combinatorial, analytic, and geo-

metric properties of tensors. Each of these notions is useful in its own

way. Finding tight relationships between these notions remains an open

research question.

One disadvantage of the traditional notion of tensor rank is that

it is prohibitively hard to compute in general. Since H˚astad’s work

in 1989 [H˚as89] it has been known that computing traditional tensor

rank over ﬁnite ﬁelds is NP-complete, and over Qis NP-hard. In 2013,

Hillar and Lim [HL13] showed that H˚astad’s proof could be modiﬁed to

show that traditional rank is NP-hard over Rand Cas well. Traditional

rank also turns out to be NP-hard to approximate with arbitrarily small

error bounds [Swe18]. The non-traditional notions we will discuss are

less “stringent” than traditional rank, so it is possible that they are

easier to compute. Showing (exact or approximate) hardness results

for those notions, however, is still an open problem.

In this paper we introduce the landscape of notions of tensor rank,

motivating their existence (Section 2). We then give examples of ap-

plications of these notions in computational complexity theory (Sec-

tion 3). In Section 4 we give a rundown of the trivial relationships

between the notions that come from their deﬁnitions. Sections 5 and

6 give proof sketches for results by Lovett [Lov19] and Cohen and

Moshkovitz [CM21] respectively which, put together, prove asymptotic

equivalence between three key notions of rank over ﬁnite ﬁelds with

three or more elements.

2. Tensor Rank Through the Ages

The oldest non-traditional notion of tensor rank is the so-called an-

alytic rank.

Deﬁnition 2.1 (Analytic Rank).Let Fbe a ﬁnite ﬁeld. The bias of a

d-tensor T∈Fn1×···×ndis given by

bias(T) = E(x1,...,xd)∈Fn1×···×Fndχ(T(x1, . . . , xd)),

where χis a nontrivial additive character which, in the case that F=

Fp, can be taken to be χ(x) = e2πix/p.

The analytic rank of T, denoted by AR(T), is then given by

AR(T) = −log|F|bias(T).

4 MANDAR JUVEKAR AND ARIAN NADJIMZADAH

This measure of the complexity of a tensor was ﬁrst introduced

by Gowers and Wolf in the context of higher-order Fourier analy-

sis [GW11]. In Section 5 we will see the connection between the ana-

lytic rank and the other combinatorial and geometric notions described

below.

Going back to the traditional deﬁnition of tensor rank, there is no

reason why one cannot use other kinds of tensors as rank 1 tensors, as

long as the new notion agrees with the old in the case of matrices (in

order to be a true generalization). Doing so, it turns out, is useful for

a whole host of applications. The ﬁrst such “alternative” notion was

introduced in 2016 in the context of the so-called “capset problem.”

Acapset in F3is a subset of F3with no non-trivial three-term arith-

metic progressions. That is, a capset is a set A⊆F3that does not

contain {x, x +r, x + 2r}for any x, r ∈F3with r̸= 0. The capset

problem asks what the maximum size of a capset in F3can be. In

the spring of 2016, Croot, Lev, and Pach [CLP17] proved a break-

through result for a similar problem in the additive group Z/4Z. They

showed that if A⊆(Z/4Z)ncontains no non-trivial three-term arith-

metic progressions, then |A| ≤ 3.60172n. Soon after, Ellenberg and Gi-

jswijt [EG17] generalized the Croot-Lev-Pach argument to show that

any progression-free set A⊆(Z/pZ)n, where pis a prime, satisﬁes

|A| ≤ (J(p)p)nwhere J(p) is an explicit constant less than 1. This ex-

ponentially improved the known bound for the capset problem, bring-

ing it down from O(3n/n1+c) (where cis some absolute constant) to

O(2.756n). Tao [Tao16] reformulated the Ellenberg-Gijswijt argument

in terms of tensors, introducing what is now known as the slice rank of

a tensor.

Deﬁnition 2.2 (Slice Rank).Ad-tensor Thas slice rank 1 if we can

write

T(x1, . . . , xd) = T1(xi)T2(xj:j̸=i),

where i∈[d], T1is a 1-tensor, and T2is a (d−1)-tensor.

The slice rank of an arbitrary d-tensor T, SR(T), is the minimum

number rsuch that we can write

T(x) =

i=1

Ti(x)

where each Tiis a d-tensor with slice rank 1.

Notice that in essence this deﬁnition just modiﬁes Deﬁnition 1.2 so

that our rank 1 tensors go from being products of d1-tensors to being

the product of two tensors: one of order 1 and one of order d−1. Also

notice that in the case of matrices (which are 2-tensors), Deﬁnitions 2.2

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

NOTIONSOFTENSORRANKMANDARJUVEKARANDARIANNADJIMZADAHAbstract.Tensors,ormulti-linearforms,areimportantobjectsinavarietyofareasfromanalytics,tocombinatorics,tocompu-tationalcomplexitytheory.Notionsoftensorrankaimtoquan-tifythe“complexity”oftheseforms,andarethusalsoimportant.Whilethereisonesingledefinit...

展开>> 收起<<

NOTIONS OF TENSOR RANK MANDAR JUVEKAR AND ARIAN NADJIMZADAH Abstract. Tensors or multi-linear forms are important objects.pdf

共19页,预览4页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

NOTIONS OF TENSOR RANK MANDAR JUVEKAR AND ARIAN NADJIMZADAH Abstract. Tensors or multi-linear forms are important objects

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: