Matrix Sketching

Dependencies

Most of this code can be run using standard anaconda libraries. The necessary packages are stored in the virtual environment thesis-python which can be activated by source thesis-python/bin/activate. Just do workon sketching.

The experiments will run using the Discrete Cosine Transform, the following is optional. We also use a fastwht' library for efficient computation of the Fast Walsh Hadamard Transform. This can be found at https://bitbucket.org/vegarant/fastwht/src/master/' Then do git clone https://bitbucket.org/vegarant/fastwht.git' and navigate to the directory. Then run python setup.py installfollowed bypython test.pyto execute the tests. Finally, obtain the path by runningpwdwhich will printYOUR PATHand, as a hack (this bit should be improved somehow??) copy that to line 7ofsrht_sketch.pyin thesys.path.append(YOUR PATH)so that thefastwht.pyfunction can be read from thehadamard.pyfile ofhttps://bitbucket.org/vegarant/fastwht/src/master/`. This can be avoided by adding the directory to the venv by add2virtualenv . if you have used mkvirtualenv myenv workon myenv see https://stackoverflow.com/questions/4757178/how-do-you-set-your-pythonpath-in-an-already-created-virtualenv/47184788#47184788

Note that https://bitbucket.org/vegarant/fastwht/src/master/ requires the swig software. If you are running anaconda python then this can easily be obtained from https://anaconda.org/anaconda/swig. Alternatively, this can be obtained via homebrew.

Experiments

We provide the following experimentst that are all located in the lib/experiment-scripts/ directory.

IHS & CountSketch:Synthetic Data

1. experiment0-ihs-ols.py examines the performance of random projections in the ihs vs classical setting.
2. experiment1-error-opt-model.py examines how the ihs model fares under varying the sketches and sketch sizes
3. experiment2-ihs-timings.py runs the same experiment as in 2 but also obtains wall-clock times and test error performance.