Ery Arias-Castro
Stanford University

Multiscale detection of geometric ojects: We study the problem of detecting geometric objects in very noisy data, from a rigorous asymptotic decision theoretic viewpoint. Along the way, we pay careful attention to creating fast algorithms. We introduce a family of new multiscale algorithms which are optimally sensitive detectors - outperforming traditional approaches - and use near-minimal flops. Connect-The-Dots: Points a thrown at random in the unit square. We show that, restricting ourselves to Lipschitz curves with bounded Lipschitz constant, a curve can contain at most $O(\sqrt{n})$ data points. We give explicit lower and upper bounds, and extend to other smoothness classes and classes of higher dimensional smooth objects. We use Dynamic Programming to numerically solve the problem for graphs, and include some simulations.

Back to Multiscale Geometric Analysis: Theory, Tools, and Applications