You are currently browsing the tag archive for the ‘L_2’ tag.

A regular tetrahedron (in \mathbb{R}^3) can be thought of as the convex hull of four pairwise non-adjacent vertices of a regular cube. A bisecting plane parallel to a face of the cube intersects the tetrahedron in a square (one can think of this as the product of two intervals, contained as the middle slice of the join of two intervals). A plane bisecting the long diagonal of a regular cube intersects the cube in a regular hexagon. In each case, the “slice”  one obtains is “rounder” (in some sense) than the original pointy object.

The unit ball in the L_1 norm on \mathbb{R}^n is a “diamond”, the dual polyhedron to an n-cube (which is the unit ball in the L_\infty norm). In three dimensions, the unit cube is an octahedron, the dual of an (ordinary) cube. This is certainly a very pointy object — in fact, for very large n, almost all the mass of such an object is arbitrarily close to the origin (in the ordinary Euclidean norm). Suppose one intersects such a diamond with a “random” m-dimensional linear subspace V. The intersection is a polyhedron, which is the unit ball in the restriction of the L_1 norm to the subspace V. A somewhat surprising phenomenon is that when n is very big compared to m, and V is chosen “randomly”, the intersection of V with this diamond is very round — i.e. a “random” small dimensional slice of L_1 looks like (a scaled copy of) L_2. In fact, one can replace L_1 by L_p here for any p (though of course, one must be a bit more precise what one means by “random”).

We can think of obtaining a “random” m-dimensional subspace of n-dimensional space by choosing n linear maps L_i \in (\mathbb{R}^m)^*:= \text{Hom}(\mathbb{R}^m,\mathbb{R}) and using them as the co-ordinates of a linear map L = \oplus_i L_i:\mathbb{R}^m \to \mathbb{R}^n. For a generic choice of the L_i, the image has full rank, and defines an m-dimensional subspace. So let \mu be a probability measure on (\mathbb{R}^m)^*, and let L define a random embedding of \mathbb{R}^m into \mathbb{R}^n. The co-ordinates of L determine a finite subset of (\mathbb{R}^m)^* of cardinality n; the uniform probability measure with this subset as support is itself a measure \nu, and we can easily compute that \|L(v)\|_p = \left( \int_{\pi \in (\mathbb{R}^m)^*} |\pi(v)|^p d\nu \right)^{1/p}. For n big compared to m, the measure \nu is almost surely very close (in the weak sense) to \mu.  If we choose \mu to be \text{O}(m)-invariant, it follows that the pullback of the L_p norm on \mathbb{R}^n to \mathbb{R}^m under a random L is itself almost \text{O}(m)-invariant, and is therefore very nearly propotional to the L_2 norm. In particular, the pullback of the L_2 norm on \mathbb{R}^n is very nearly equal to (a multiple of) the L_2 norm on \mathbb{R}^m, so (after rescaling), L is very close to an isometry, and the intersection of L(\mathbb{R}^m) with the unit ball in \mathbb{R}^n in the L_p norm is very nearly round.

Dvoretzky’s theorem says that any infinite dimensional Banach space contains finite dimensional subspaces that are arbitrarily close to L_2 in given finite dimension m. In fact, any symmetric convex body in \mathbb{R}^n for large n depending only on m,\epsilon, admits an m-dimensional slice which is within \epsilon of being spherical. On the other hand, Pelczynski showed that any infinite dimensional subspace of \ell_1 contains a further subspace which is isomorphic to \ell_1, and is complemented in \ell_1; in particular, \ell_1 does not contain an isometric copy of \ell_2, or in fact of any infinite dimensional Banach space with a separable dual (I learned these facts from Assaf Naor).


Get every new post delivered to your Inbox.

Join 156 other followers