Treffer: A Randomized Algorithm to Reduce the Support of Discrete Measures

Title:
A Randomized Algorithm to Reduce the Support of Discrete Measures
Authors:
Cosentino, F, Oberhauser, H, Abate, A
Publication Status:
Preprint
Publisher Information:
arXiv, 2020.
Publication Year:
2020
Subject Terms:
FOS: Computer and information sciences, Computer Science - Machine Learning, Statistics - Machine Learning, Probability (math.PR), FOS: Mathematics, Machine Learning (stat.ML), 0101 mathematics, 01 natural sciences, Mathematics - Probability, Machine Learning (cs.LG)
Document Type:
Fachzeitschrift Article<br />Conference object
DOI:
10.48550/arxiv.2006.01757
Access URL:
http://arxiv.org/abs/2006.01757
https://ora.ox.ac.uk/objects/uuid:6a32a4f2-c8c9-4af5-9007-de93bc09dbc3
Rights:
arXiv Non-Exclusive Distribution
Accession Number:
edsair.doi.dedup.....11ec2e9bae52f1c059bf36a764d3df5f
Database:
OpenAIRE

Weitere Informationen

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}.