frequent-direction

Implementation of Frequent-directions algorithm for efficient matrix sketching [Liberty2013] .

Usage

Locate fd_sketch.py on your current directory. Run the following commands on pyton console:

>>> import fd_sketch
>>> import numpy as np
>>> a = np.random.randn(1000, 100)
>>> b = fd_sketch.sketch(a, 150)
>>> b
>>> fd_sketch.calculateError(a, b)

Run unit test

fd_sketch_test.py contains unit tests for fd_sketch.

$ python fd_sketch_test.py

Run USPS PCA sample

Download the USPS hand-written image dataset from the following URL and extract the archived zip.train file into ./data/elem/usps/. http://ttic.uchicago.edu/~ryotat/teaching/enshu13/zip.train.gz

Then run the sample script and get the plot figures in result directory.

$ mkdir result
$ python sample_usps_pca_rep.py

More details

We refer the interested users to the original conference paper for detailed algorithm, theoretial analysis, and performance evaluations.

Liberty2013

Edo. Liberty, "Simple and Deterministic Matrix Sketching", ACM SIGKDD, 2013. http://www.cs.yale.edu/homes/el327/papers/simpleMatrixSketching.pdf