Implementation of Frequent-Directions algorithm for efficient matrix sketching [E. Liberty, SIGKDD2013]
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
.gitignore
LICENSE
README.rst
fd_sketch.py
fd_sketch_test.py
sample_usps_pca_rep.py

README.rst

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