A Randomized Algorithm to Reduce the Support of Discrete Measures
Francesco Cosentino, Harald Oberhauser, Alessandro Abate
Abstract
Given a discrete probability measure supported on $N$ atoms and a set of $n$ real-valued functions, there exists a probability measure that is supported on a subset of $n+1$ of the original $N$ atoms and has the same mean when integrated against each of the $n$ functions. If $ N \gg n$ this results in a huge reduction of complexity. We give a simple geometric characterization of barycenters via negative cones and derive a randomized algorithm that computes this new measure by ``greedy geometric sampling''. We then study its properties, and benchmark it on synthetic and real-world data to show that it can be very beneficial in the $N\gg n$ regime. A Python implementation is available at \url{https://github.com/FraCose/Recombination_Random_Algos}.
BibTeX
@inproceedings{NEURIPS2020_ac4395ad,
author = {Cosentino, Francesco and Oberhauser, Harald and Abate, Alessandro},
booktitle = {Advances in Neural Information Processing Systems},
editor = {H. Larochelle and M. Ranzato and R. Hadsell and M.F. Balcan and H. Lin},
pages = {15100--15110},
publisher = {Curran Associates, Inc.},
title = {A Randomized Algorithm to Reduce the Support of Discrete Measures},
url = {https://proceedings.neurips.cc/paper_files/paper/2020/file/ac4395adcb3da3b2af3d3972d7a10221-Paper.pdf},
volume = {33},
year = {2020}
}