|
Applied Math Seminar
Some Phase Transitions for Random Convex Polytopes
|
|
Consider the convex hull of $n$ iid Gaussian random vectors $X_i$ in ${\bf R}^d$. In the case where $d$ is fixed and $n$ is large, this is a classical problem. We consider the case where $d$ and $n$ are both large, and proportional to each other. In that case, some counterintuitive things are happening. For example, all the $X_i$ are vertices; none fall in the interior. But more is true: all the line segments $[X_i,X_j]$ are edges, in fact all the simplices spanned by any $k$ of the $X_i$ are $k-1$ faces, for every $k$ up to a certain threshold, which is proportional to $d$. This phenomenon has surprising applications in compressed sensing and error-correcting codes, which I will discuss. I'll also describe several other surprising phase transitions. The basic underlying mathematics concerns evaluation of Grassmann angles in very high-dimensional spaces, which involves some geometry and some large deviations. Part of this work was joint with Jared Tanner. |