Estimation of Probability Measures in High Dimensions, with Optimal Transport and Fast Algorithms

• Activity Number: 310
• Type: Invited
• Date/Time: Tuesday, August 5, 2014 : 10:30 AM to 12:20 PM
• Sponsor: Section on Statistical Learning and Data Mining
• Author(s): Mauro Maggioni*+
• Companies: Duke University
• Keywords: Multiscale Analysis ; High dimensional probability ; Optimal transport ; Manifold Learning ; Data Sketching ; Dictionary Learning

Abstract

We introduce a novel class of algorithms for the estimation of probability measures in high-dimensional spaces, given a finite number of samples. We are particularly interested in the case when the probability measure is concentrated near a low-dimensional set. These algorithms are based on geometric multiscale decompositions of probability measures, and we prove that with high probability, given a sufficiently large but finite number of samples, the algorithm returns a probability measure which is close, in Wasserstein-Kantorovich distance, to the target probability measure. We discuss applications to modeling high-dimensional noisy data sets, and anomaly detection in time-varying data.