Timeline for Intuitive explanation of Dvoretzky's theorem
Current License: CC BY-SA 3.0
19 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 10, 2013 at 7:56 | comment | added | Mark Meckes | @Bill: Indeed, I once showed two proofs (Milman's and Gordon's) of Dvoretzky's theorem to an audience of probabilists. The point of the talk was the probabilistic tools, so I stated D-R without proof and said something like "There has to be some geometry in the proof somewhere. This is where it's hidden, but of course there'd be no result without it." | |
| Sep 30, 2013 at 15:31 | comment | added | Bill Johnson | Sure, Mark; I explained the conceptual framework (which is used e.g. also to get embeddings of subspaces of $L_p$ into $\ell_p^n$) and how the approach is used to get Dvoretzkys theorem. Concentration is "obvious" if you are a geometer with the classical approach and to probabilists if you use the random gaussian approach, but you still need the D-R lemma to estimate the mean. | |
| Sep 30, 2013 at 14:57 | comment | added | Mark Meckes | @Bill: Isn't that what Terry and I said? (Well, okay, we left out Dvoretzky-Rogers.) | |
| Sep 30, 2013 at 14:04 | comment | added | Bill Johnson | ...But this is just an outline of one standard proof of Dvoretzky's theorem rather than an intuitive explanation. | |
| Sep 30, 2013 at 14:01 | comment | added | Bill Johnson | ....or, if you know something $F$ (such as cotype), you can use the properties of $F$ to get a better lower estimate. The concentration around the mean is good enough that a union bound argument allows you to conclude that there is a $U$ s.t. $\|TUx\|$ is close to the mean for all $x$ in an $\epsilon$-net of the unit sphere of $E_k$, where $E_k$ is the span of the first $k$ ON basis vectors for $E$ and $k $ is at least $C_\epsilon \log n$ (or better when you have a better estimate on the mean of $\|TUx\|$ from cotype).... | |
| Sep 30, 2013 at 13:55 | comment | added | Bill Johnson | When $F$ has dimension $n$, the classical way of getting Euclidean sections is to let $E$ be the $n$ dimensional Hilbert space and let $S$ be the operator that makes $SB_E$ the ellipsoid of maximal volume contained in $B_F$. Randomize $S$ by considering $SU$ as $U$ varies over the orthogonal group or unitary group, depending on the scalar field. Then $\Bbb{E}\|SUx\|$ is independent of $x$ in the unit sphere of $E$ and has good concentration around the mean, but you need to get a lower on $\Bbb{E}\|SUx\|$--that uses the D-R lemma..... | |
| Sep 30, 2013 at 13:35 | comment | added | Bill Johnson | Well, if you accept concentration of measure, then of course Dvoretzky's theorem is clear. A way of getting an embedding of a finite dimensional normed space $E$ into another space $F$ is to define a random linear operator $T_\omega$ from $E$ into $F$ that is, on the average, an isometry or good isomorphism. If you have enough concentration around the mean, then for some $\omega$ the operator $T_\omega$ will be a good isomorphism. | |
| Sep 30, 2013 at 11:59 | comment | added | Mark Meckes | Incidentally, I recommend Keith Ball's article, already mentioned below by Carlo Beenakker, for a presentation of Milman's proof that highlights the big ideas without getting as bogged down in the technicalities as many writers. | |
| Sep 30, 2013 at 11:53 | comment | added | Mark Meckes | Personally, my take is that measure concentration is initially decidedly unintuitive, because it's an intrinsically high-dimensional phenomenon, and our intuition is trained by two- and three-dimensional experience. You could say the same thing about Dvoretzky's theorem itself. Working in high dimensions requires (in part) retraining your intuition to encompass measure concentration. Once you've done that, Terry's one-line summary gives you most of Milman's proof: the norm corresponding to your convex body is almost constant on most of the sphere. | |
| Sep 30, 2013 at 4:44 | comment | added | Igor Rivin | @TerryTao I certainly do not deny concentration of measure, the question is whether it is intuitive (or can be made intuitive). What's your take on this? | |
| Sep 30, 2013 at 4:20 | comment | added | Terry Tao | Do you accept concentration of measure (and specifically, Levy's theorem that Lipschitz functions on a high-dimensional sphere are almost constant outside of a set of very small measure) as intuitive? From that theorem it is not hard to show that if a convex body is somewhat round, then most of its low-dim slices will be very round, which is already a large part of Milman's proof of Dvoretzky's thm. | |
| Sep 30, 2013 at 3:55 | history | edited | Bill Johnson | CC BY-SA 3.0 |
Corrected spelling
|
| Sep 29, 2013 at 20:41 | answer | added | Carlo Beenakker | timeline score: 4 | |
| Sep 29, 2013 at 20:26 | answer | added | Bill Johnson | timeline score: 9 | |
| Sep 29, 2013 at 19:22 | comment | added | Igor Rivin | Arelated question in $\mathbb{R}^3$ ($3$ is not usually viewed as close to infinity, but...) is: given two concentric ellipsoids $E_1, E_2,$ and letting $\chi(E)$ be the excentricity of the ellipse $E,$ what is $\min_P \max_{i=1, 2} \chi(P\cap E_i),$ where the min is taken over all planes through the origin [think of $E_1, E_2$ as the John ellipsoids of some $K$] | |
| Sep 29, 2013 at 19:17 | comment | added | Joseph O'Rourke | It is at least suggestive that every ellipsoid in $\mathbb{R}^3$ has a planar section that is a circle. | |
| Sep 29, 2013 at 19:15 | history | edited | Igor Rivin | CC BY-SA 3.0 |
added 8 characters in body
|
| Sep 29, 2013 at 19:08 | history | edited | Igor Rivin | CC BY-SA 3.0 |
fixed title
|
| Sep 29, 2013 at 19:00 | history | asked | Igor Rivin | CC BY-SA 3.0 |