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.