fracose / recombination_random_algos

Cosentino, Oberhauser, Abate - A randomized algorithm to reduce the support of discrete measures

---

This Repository contains the Algorithms explained in
Cosentino, Oberhauser, Abate
"A randomized algorithm to reduce the support of discrete measures "
NeurIPS 2020

The files are divided in the following way:

• The ipython notebooks contain the experiments to be run.
  
• recombination.py is the library with all the code of the Algorithms presented in
  the cited work.
  

Some general notes:

• The names of the ipynb files refer directly to the experiments in the cited work.
  
• The last cells of the notebooks produce the pictures of the pdf.
  
• To reduce the running time the parameters can be easily changed, e.g. decreasing N, n or sample.
  

---

Library - recombination.py

It contains the algorithms relative to the reduction of the measure presented in this work,
see the pdf for more details. In recombination.py we have rewritten in Python the algorithm presented
in Tchernychova, Lyons "Caratheodory cubature measures", PhD thesis, University of Oxford, 2016.
Note that we do not consider their studies relative to different trees/data structure,
read the cited work for more details.

---

Special Note to run the experiments

The notebooks "Comparison_random_algos.ipynb", "Comparison_literature_algos.ipynb", "Running_time_ratio.ipynb"
and "Running_times_vs_n.ipynb" contain multiple experiments: symmetric vs non-symmetric.
You have to comment/uncomment the respective parts of the code as indicated to reproduce the
wanted experiments.

---

To Run the Experiments - Requested file

To run the comparisons, please download the following file and name it "Maalouf_Jubran_Feldman.py".
"Fast and Accurate Least-Mean-Squares Solvers"
(NIPS19' - Oral presentation + Outstanding Paper Honorable Mention) by Alaa Maalouf and Ibrahim
Jubran and Dan Feldman”, which you can also find here
https://github.com/ibramjub/Fast-and-Accurate-Least-Mean-Squares-Solvers

---

To Run the Experiments - Datasets

To run the experiments, the following dataset need to be donwloaded and saved in the /Datasets folder:

• 3D_spatial_network.txt -
  https://archive.ics.uci.edu/ml/machine-learning-databases/00246/3D_spatial_network.txt
  
• household_power_consumption.txt -
  https://archive.ics.uci.edu/ml/machine-learning-databases/00235/household_power_consumption.zip
  (extract the .txt file)
  
• kc_house_data.csv -
  https://www.kaggle.com/harlfoxem/housesalesprediction
  

---

Funding

The authors want to thank The Alan Turing Institute and the University of Oxford
for the financial support given. FC is supported by The Alan Turing Institute, TU/C/000021,
under the EPSRC Grant No. EP/N510129/1. HO is supported by the EPSRC grant Datasig
[EP/S026347/1], The Alan Turing Institute, and the Oxford-Man Institute.