sketched-pseudoinverse

Code of the paper "Asymptotics of the Sketched Pseudoinverse"

Setup

Create an empty conda environment, activate it, and then install the dependencies:

$ conda create -n sketched-pseudoinverse
$ conda activate sketched-pseudoinverse
$ conda install -c conda-forge --file requirements.txt

The FJLT and SRHT implementation in the practical sketching experiments uses dnbaker's fork of FALCONN-LIB/FFHT, which fixes Python C bindings extends the implementation to multi-dimensional fast Hadamard transform, until their fork gets merged. Install it via

$ git clone https://github.com/dnbaker/FFHT.git --recurse-submodules
$ cd FFHT
$ git checkout 2e08bbb8e3badf1efa80ebb5a6f4ad647fb035a0
$ CFLAGS="-fopenmp" pip install .

Note the CFLAGS="-fopenmp". For some reason, the Python build chain doesn't always pass this compiler flag, so you may need to pass it manually like I have done here.

Generating plots

Plots are generated by running the Jupyter notebooks in the experiments directory.

$ jupyter-lab

Unit tests

You can run the unit tests with

$ python -m unittest

in this directory. While the unit tests do not test all functionality, they do test the basic asymptotic equivalence which is the core implementation behind most things.