Jared Tanner (joint work with David Donoho, Stanford University)

Title: The surprising structure of Gaussian point clouds and its implications for signal processing

Abstract: We will explore connections between the structure of high-dimensional convex polytopes and information acquisition for compressible signals. A classical result in the field of convex polytopes is that if N points are distributed Gaussian i.i.d. at random in dimension n<<N, then only order (log N)^n of the points are vertices of their convex hull.  Recent results show that provided n grows slowly with N, then with high probability all of the points are vertices of its convex hull.  More surprisingly, a rich "neighborliness" structure emerges in the faces of the convex hull.  One implication of this phenomenon is that an N-vector with k non-zeros can be recovered computationally efficiently from only n random projections with n=2e k log(N/n). Alternatively, the best k-term approximation of a signal in any basis can be recovered from 2e k log(N/n) non-adaptive measurements, which is within a log factor of the optimal rate achievable for adaptive sampling.