Ph.D Thesis
Ph.D Student Alon Dmitriyuk Asymptotic and Probabilistic Estimates on Distortions of Linear Mappings between Convex Bodies Department of Mathematics Professor Emeritus Gordon Yehoram

Abstract

This thesis is about embeddings of subsets of the Euclidean space into Banach spaces using random mappings. Particular cases were considered by A. Dvoretzky and many other subsequent authors in the case of embedding Euclidean spaces of dimension n into general Banach spaces having higher dimensions.

To follow and expand on these ideas, we consider a subset T of the n-dimensional Euclidean space and a Banach space Y. Assume that a map F from Rn to Y satisfies that for any t1, t2 in T  A|| t1- t2||2<||F(t1)-F(t2)||Y< B|| t1- t2||2.

Then we say F has distance distortion at most B/A on T. Since in this thesis we consider only linear mappings then by putting

S={(t1-t2)/|| t1-t2||2):: t1,t2 in T} we see that a linear map F satisfies for any s in S , A<||F(s)|Y < B.

Hence we may consider subsets S of the n-dimensional unit sphere S n-1 and for D>1 we give conditions on Banach spaces Y for which there are linear maps F from Rn to Y for which Sup||F(s)||Y/Inf||F(s)||Y<D where the infimum and supremum are taken over all s in S.

The methods used in this thesis are probabilistic: We prove that random matrices give the required mappings under certain conditions. A particular case of general results proved in this thesis shows that when the target space is Euclidean we obtain the following result:

Let r>0 and 0< k< n and let {Wl} be p affine subspaces of Rn each of dimension at most k. Let m=O(r-2(k?(p)) if r<1, and m=O(k?(p)/log(1)) if r>1. Then there is a linear map H from Rn to Rm such that for all 0<l<p and x,y in Wl we have

||x-y||2<||H(x)-H(y)||2< (1)||x-y||2  i.e.the distance distortion is at most 1. We prove that the estimate on m is tight in terms of k and p whenever 0<r<1 and is tight on r,k,p whenever r>1. Our general results give random embeddings into Banach spaces Y and involve various parameters concerning Y and probability estimates on the various kinds of random embeddings.