A SEMIDEFINITE PROGRAM FOR LEAST DISTORTION EMBEDDINGS OF FLAT TORI INTO HILBERT SPACES ARNE HEIMENDAHL MORITZ L UCKE FRANK VALLENTIN

2025-04-30 0 0 545.31KB 23 页 10玖币

侵权投诉

A SEMIDEFINITE PROGRAM FOR LEAST DISTORTION

EMBEDDINGS OF FLAT TORI INTO HILBERT SPACES

ARNE HEIMENDAHL, MORITZ L¨

UCKE, FRANK VALLENTIN,

AND MARC CHRISTIAN ZIMMERMANN

Abstract. We derive and analyze an inﬁnite-dimensional semideﬁnite pro-

gram which computes least distortion embeddings of ﬂat tori Rn/L, where L

is an n-dimensional lattice, into Hilbert spaces.

This enables us to provide a constant factor improvement over the pre-

viously best lower bound on the minimal distortion of an embedding of an

n-dimensional ﬂat torus.

As further applications we prove that every n-dimensional ﬂat torus has a

ﬁnite dimensional least distortion embedding, that the standard embedding of

the standard tours is optimal, and we determine least distortion embeddings

of all 2-dimensional ﬂat tori.

1. Introduction

Lattices (discrete subgroups of n-dimensional Euclidean spaces) are central to the

geometry of integer programming. One good way to describe geometric properties

of a given lattice Lare fundamental domains of Rnwith respect to translations by

L. The quotient Rn/L is itself a metric space; a ﬂat torus.

Approximating metric spaces by Euclidean spaces to design eﬃcient approxima-

tion algorithms has been a central theme in theoretical computer science in the last

two decades. There the starting point is computing a least distortion embedding

of a “diﬃcult” metric spaces into an “easy” normed space.

Least distortion embeddings of ﬂat tori into Hilbert spaces were ﬁrst studied

by Khot and Naor [12] in 2006. One motivation is that studying the Euclidean

distortion of ﬂat tori might have applications to the complexity of lattice problems,

like the closest vector problem, and might also lead to more eﬃcient algorithms for

lattice problems through the use of least distortion embeddings. Another motiva-

tion comes from comparing the Riemannian setting to the bi-Lipschitz setting we

are discussing here. On the one hand, by the Nash embedding theorem, ﬂat tori

can be embedded isometrically as Riemannian submanifolds into Euclidean space;

we refer to [4] for spectacular visualizations of such an isometric embedding in the

case of the two-dimensional square ﬂat torus. On the other hand, Khot and Naor

showed that ﬂat tori can be highly non-Euclidean in the bi-Lipschitz setting.

1.1. Notation and review of the relevant literature. We review the relevant

results of the literature which appeared since the pioneering work of Khot and Naor.

At the same time we set the notation for this paper.

Date: November 22, 2023.

2020 Mathematics Subject Classiﬁcation. 46B85, 52C07, 90C22.

arXiv:2210.11952v2 [math.OC] 21 Nov 2023

2 A. Heimendahl, M. L¨ucke, F. Vallentin, and M.C. Zimmermann

A ﬂat torus is the metric space given by the quotient Rn/L with some n-

dimensional lattice L⊆Rnand with metric

dRn/L(x, y) = min

v∈L|x−y−v|.

An n-dimensional lattice is a discrete subgroup of (Rn,+) consisting of all integral

linear combinations of a basis of Rn. Furthermore, | · | denotes the standard norm

of Rngiven by |x|=√xTx.

A Euclidean embedding of Rn/L is an injective function φ:Rn/L →Hmapping

the ﬂat torus Rn/L into some (complex) Hilbert space H. The distortion of φis

dist(φ) = sup

x,y∈Rn/L

x̸=y

∥φ(x)−φ(y)∥

dRn/L(x, y)·sup

x,y∈Rn/L

x̸=y

dRn/L(x, y)

∥φ(x)−φ(y)∥,

where ∥·∥is the norm of the Hilbert space H. Here the ﬁrst supremum is called

the expansion of φand the second supremum is the contraction of φ. When we

minimize the distortion of φover all possible embeddings of Rn/L into Hilbert

spaces we speak of the least (Euclidean) distortion of the ﬂat torus; it is denoted

c2(Rn/L) = inf{dist(φ) : φ:Rn/L →Hfor some Hilbert space H, φ injective}.

Similarly one can deﬁne c1(Rn/L) by replacing the Hilbert space by some L1space.

Khot and Naor showed (see [12, Corollary 4]) that ﬂat tori can be highly non-

Euclidean in the sense that there is a family of ﬂat tori Rn/Lnwith

(1) c2(Rn/Ln) = Ω(√n).

On the other hand, they noticed (see [12, Remark 5]) that the standard embedding

of the standard ﬂat torus Rn/Znembeds into R2nwith distortion O(1)1. The

standard embedding is given by

(2) φ(x1, . . . , xn) = (cos 2πx1,sin 2πx1,...,cos 2πxn,sin 2πxn).

In fact, Khot and Naor are mainly concerned with bounding c1(Rn/L), which

immediately provides bounds for c2(Rn/L) because c1(Rn/L)≤c2(Rn/L). To state

their main result, leading to (1), we make use of the Voronoi cell of L, which is an

n-dimensional polytope deﬁned as

V(L) = {x∈Rn:|x|≤|x−v|for all v∈L}.

The Voronoi cell is a fundamental domain of Rn/L under the action of L. We

denote the volume of V(L) by vol L. Clearly, |x|=dRn/L(x, 0) for all x∈V(L).

The covering radius of Lis µ(L) = max{|x|:x∈V(L)}, which is the circumradius

of V(L). The length of a shortest vector of Lis λ(L) = min{|v|:v∈L\ {0}} that

is two times the inradius of V(L). Now the main result (see [12, Theorem 5]) is

(3) c1(Rn/L)=Ωλ(L∗)√n

µ(L∗).

Here, as usual, L∗={u∈Rn:uTv∈Zfor all v∈L}denotes the dual lattice of

L. They also give an alternative proof of their main result for c2(Rn/L) (see [12,

Lemma 11]). The main result leads to the lower bound (1) when plugging in duals

of lattices which simultaneously provide dense packings and economical coverings.

Such a family of lattices exist by a theorem of Butler [5].

1In fact, we have dist(φ) = π/2 and φis an optimal embedding, see Theorem 6.1.

A semideﬁnite program for least distortion embeddings of ﬂat tori into Hilbert spaces 3

Using Korkine-Zolotarev reduction Khot and Naor determine an embedding of

Rn/L into R2nwith distortion O(n3n/2) (see [12, Theorem 6]).

Haviv and Regev [11, Theorem 1.3] found an improved embedding that yields

c2(Rn/L) = O(n√log n). They also improved on (3) and showed in [11, Theorem

1.5] that for any n-dimensional lattice Lwe have

(4) c2(Rn/L)≥λ(L∗)µ(L)

4√n,

which improves on (3) because µ(L)µ(L∗)≥Ω(n) holds for every n-dimensional

lattice. This follows from a simple volume argument giving µ(L) = Ω(√n(vol L)1/n)

and vol L∗= (vol L)−1.

Recently, Agarwal, Regev, Tang [2] constructed excellent embeddings of ﬂat tori

having low distortion and showed that the lower bound (1) is nearly tight: For

every lattice L⊆Rnthere exists an embedding of Rn/L into Hilbert space with

distortion O(√nlog n).

1.2. Aim and method. In this paper we want to add a semideﬁnite optimization

perspective to this story.

For ﬁnite metric spaces it is known that one can compute least distortion Eu-

clidean embeddings via a semideﬁnite program (SDP), which is linear optimization

over the cone of positive semideﬁnite matrices. We want to extend this result from

ﬁnite metric spaces to ﬂat tori. This will yield, via semideﬁnite programming du-

ality, an algorithmic method for proving nonembeddability results. In particular,

this leads to a new, simple proof of (4). In fact we even get a constant factor

improvement that is tight in the case of the standard torus.

First we recall the semideﬁnite program for ﬁnding least Euclidean distortion

embeddings of ﬁnite metric spaces. Suppose we consider a ﬁnite metric space Xwith

distance function d. Then, as ﬁrst observed by Linial, London, Rabinovich [16], we

can ﬁnd a least distortion embedding of (X, d) into a Hilbert space algorithmically

by solving the following semideﬁnite program

min{C:C∈R+, Q ∈ SX

d(x, y)2≤Qxx −2Qxy +Qyy ≤Cd(x, y)2for all x, y ∈X},

(5)

where SX

+denotes the convex cone of positive semideﬁnite matrices whose rows

and columns are indexed by the elements of X. The optimal solution Cof this

semideﬁnite program equals c2(X, d)2and if Qattains the optimal solution, then

we can determine a least distortion embedding φ:X→RXwith the property

φ(x)·φ(y) = Qxy by considering a Cholesky decomposition of Q.

This shows how to compute (in fact in polynomial time) an optimal Euclidean

embedding of a ﬁnite metric space. Another beneﬁt of this formulation is that we

can apply duality theory of semideﬁnite programs. Then the dual maximization

problem will play a key role to determine lower bounds for c2(X, d). By using strong

duality we arrive at the following result: The least distortion of a ﬁnite metric space

(X, d), with X={x1, . . . , xn}, into Euclidean space is given by

(6) c2(X, d)2= max (Pn

i,j=1:Yij >0Yij d(xi, xj)2

−Pn

i,j=1:Yij <0Yij d(xi, xj)2:Y∈ Sn

+, Y e= 0).

The condition Ye= 0 says that the all-ones vector elies in the kernel of Y. A

proof of this result is detailed in Matouˇsek [19] or in Laurent, Vallentin [15].

4 A. Heimendahl, M. L¨ucke, F. Vallentin, and M.C. Zimmermann

This lower bound has been extensively used to determine the least distortion

Euclidean embeddings of the shortest path metric of several graph classes. Linial,

Magen [17] computed least distortion embeddings of products of cycles and of ex-

pander graphs. Least distortion Euclidean embeddings of strongly regular graphs

and of more general distance regular graphs were ﬁrst considered by Vallentin [22].

This was further extended by Kobayashi, Kondo [13], Cioab˘a, Gupta, Ihringer,

Kurihara [6]. Linial, Magen, Naor [18] considered graphs of high girth using this

approach.

To apply the bound (6) one has to construct a matrix Y, which sometimes

appears to come out of the blue. By complementary slackness, which is the same

as analyzing the case of equality in the proof of weak duality, we get hints where to

search for an appropriate matrix Y: If Yis an optimal solution of the maximization

problem (6), then Yij >0 only for the most contracted pairs. These are pairs

(xi, xj) for which d(xi,xj)

∥f(xi)−f(xj)∥is maximized. Similarly, then Yij <0 only for the

most expanded pairs, maximizing ∥f(xi)−f(xj)∥

d(xi,xj).

Linial, Magen [17] realized that for graphs most expanded pairs are simply ad-

jacent vertices. However, most contracted pairs are more mysterious and there is

no characterization known. The ﬁrst intuition that the largest contraction occurs

at pairs at maximum distance is wrong in general.

1.3. Contribution and structure of the paper. In Section 2of this paper

we derive a new inﬁnite-dimensional semideﬁnite program for determining a least

distortion embedding of ﬂat tori into Hilbert spaces which is analogous to (5). It is

given in Theorem 2.1 where we additionally apply symmetry reduction techniques

in the spirit of [3] to reduce the original inﬁnite-dimensional SDP into an inﬁnite-

dimensional linear program that involves Fourier analysis. Then we realize that

in a Euclidean embedding of a ﬂat torus there are no most expanded pairs: The

expansion is only attained in the limit by pairs whose distance tends to zero. This is

in perfect analogy to the graph case where the most expanded pairs are also attained

at minimal distance. This insight has the advantage that in the inﬁnite dimensional

linear program some of the inﬁnitely many constraints can be replaced by only one

ﬁnite-dimensional semideﬁnite constraint. This is the content of Theorem 2.4. Its

dual program is derived in Theorem 2.5 which is analogous to (6).

In Section 3we further investigate the properties of the optimization problems

given in Theorem 2.4 and Theorem 2.5. These properties will be used in the next

sections.

In the last sections we apply our new methodology. In Section 4we prove that

an n-dimensional ﬂat torus always admits a ﬁnite dimensional least distortion em-

bedding, a space of (complex) dimension 2n−1 suﬃces. Section 5contains a new

and simple proof of our constant factor improvement of the lower bound given

in (4). In Section 6we show that the standard embedding (2) of the standard torus

is indeed optimal and has distortion π/2. We give an optimal embedding of the

lattices D∗

nin Section 7. In Section 8we determine least distortion embeddings of

all two-dimensional ﬂat tori. Open questions are discussed in Section 9.

2. An infinite-dimensional SDP

Starting from (5) we want to derive a similar, but now inﬁnite-dimensional,

semideﬁnite program which can be used to determine c2(Rn/L).

A semideﬁnite program for least distortion embeddings of ﬂat tori into Hilbert spaces 5

2.1. Primal program. The ﬁrst step is to apply a classical theorem of Moore [20]

which enables us to optimize over all embeddings φ:Rn/L →Hinto some Hilbert

space H. In our situation Moore’s theorem says that there exists a (complex)

Hilbert space Hand a map φ:Rn/L →Hif and only if there is a positive deﬁnite

kernel2

Q:Rn/L ×Rn/L →Csuch that Q(x, y)=(φ(x), φ(y)) for all x, y ∈Rn/L,

where (·,·) denotes the inner product of H. Therefore we get

c2(Rn/L)2= inf{C:C∈R+, Q positive deﬁnite,

dRn/L(x, y)2≤Q(x, x)−2ℜ(Q(x, y)) + Q(y, y)

≤CdRn/L(x, y)2for all x, y ∈Rn/L}.

Here we scaled the embedding φwhich is deﬁned through Qso that the contraction

of φequals 1. The real part ℜ(Q) of a positive deﬁnite kernel is positive deﬁnite

again and we can restrict to real-valued positive deﬁnite kernels for determining

c2(Rn/L).

For the second step we apply a standard group averaging argument. If Qis a

feasible solution for the minimization problem above, so is its group average

Q(x, y) = 1

vol(Rn/L)ZRn/L

Q(x−z, y −z)dz.

By this averaging the kernel Qbecomes continuous and only depends on the diﬀer-

ence x−y. Thus, instead of minimizing over positive deﬁnite kernels Qit suﬃces to

minimize over continuous, real functions f:Rn/L →Rwhich are of positive type,

i.e. the kernel (x, y)7→ f(x−y) is positive deﬁnite; see also the proof of Theorem

3.1 in the paper [1] by Aharoni, Maurey, Mityagin.

For the convenience of the reader we provide the argument why the positive type

function f(x) = Q(x, 0) is continuous: For every x,ythe matrix





f(0) f(x)f(x+y)

f(x)f(0) f(y)

f(x+y)f(y)f(0) 



is positive semideﬁnite and it is congruent (simultaneously subtract the second

row/column of the third row/column) to the positive semideﬁnite matrix





f(0) f(x)f(x+y)−f(x)

f(x)f(0) f(y)−f(0)

f(x+y)−f(x)f(y)−f(0) 2f(0) −2f(y)



Taking the minor of the ﬁrst and third row/column gives

2f(0)(f(0) −f(y)) ≥(f(x+y)−f(x))2.

This inequality implies that fis continuous at every xif and only if fis continuous

at 0. Then fis continuous at 0 because it satisﬁes the constraint

dRn/L(0, y)2≤Q(0,0) −2Q(0, y) + Q(y, y) = 2(f(0) −f(y)) ≤CdRn/L(0, y)2

for every y.

2A kernel Qis called positive deﬁnite if and only if for all N∈Nand for all x1,...,xN∈Rn/L

the matrix (Q(xi, xj))1≤i,j≤N∈CN×Nis Hermitian and positive semideﬁnite. This naming

convention is unfortunate but for historical reasons unavoidable.

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

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

10 玖币 0人已下载

立即下载

摘要：

ASEMIDEFINITEPROGRAMFORLEASTDISTORTIONEMBEDDINGSOFFLATTORIINTOHILBERTSPACESARNEHEIMENDAHL,MORITZL¨UCKE,FRANKVALLENTIN,ANDMARCCHRISTIANZIMMERMANNAbstract.Wederiveandanalyzeaninfinite-dimensionalsemidefinitepro-gramwhichcomputesleastdistortionembeddingsofflattoriRn/L,whereLisann-dimensionallattice,int...

展开>> 收起<<

A SEMIDEFINITE PROGRAM FOR LEAST DISTORTION EMBEDDINGS OF FLAT TORI INTO HILBERT SPACES ARNE HEIMENDAHL MORITZ L UCKE FRANK VALLENTIN.pdf

共23页,预览5页

还剩页未读，继续阅读

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

A SEMIDEFINITE PROGRAM FOR LEAST DISTORTION EMBEDDINGS OF FLAT TORI INTO HILBERT SPACES ARNE HEIMENDAHL MORITZ L UCKE FRANK VALLENTIN

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: