Abstract: Structure recovery is at the heart of modern Data Science. Roughly put, the goal in structure recovery problems is to identify (or at least approximate) an unknown object using limited, random information – e.g., a random sample of the unknown object.
As it happens, key questions on recovery are fundamental (open) problems in Asymptotic Geometric Analysis and High Dimensional Probability. In this talk I will give one example (out of many) that exhibits the rather surprising ties between those seemingly unrelated areas.
I will explain why noise-free recovery is dictated by the geometry of natural random sets: for a class of functions F and n i.i.d random variables σ = (X_1,…,X_n), the random sets are P_σ (F) = { (f(X_1),….,f(X_n)) : f ∈ F }.
I will outline a (sharp) estimate on the structure of a typical P_σ (F) that leads to the solution of the noise-free recovery problem under minimal assumptions. I will explain why the same estimate resolves various questions in high dimensional probability (e.g., the smallest singular values of certain random matrices) and high dimensional geometry (e.g., the Gelfand width of a convex body).
The optimality of the solution is implied by a exposing a “hidden extremal structure” contained in P_σ (F), which in turn is based on a complete answer to Talagrand’s celebrated entropy problem.