RandomizedSVD

Implementation of Fast Randomized SVD [1] for low-rank approximation of matrices using C++/Eigen.

Also:

• Demo of background removal in webcam feed using randomized SVD
• Implementation of robust PCA [4]

Requirements

• Eigen (currently assumed to be in eigen folder in root)
• OpenCV (for background removal demo)

Building

cd [eigen from somewhere else] .
mkdir build
cd build
cmake ..
make

Using

Implementation of randomized SVD is in randomized_svd.h, robust PCA in robust_pca.h. For the randomized SVD, the interface is the same as Eigen's SVD.

• TryRandomizedSvd: Apply randomized SVD to large matrix to demonstrate speed advantages, reconstruction error (spectral norm).
• BackgroundRemoval: Use rSVD to separate (dynamic) foreground from (static) background in webcam feed.
• TryRobustPca: Apply robust PCA (separating matrix into low-rank and sparse components) on small matrix

References

1. Nathan Halko, Per-Gunnar Martinsson, and Joel Tropp, Finding structure with randomness: probabilistic algorithms for constructing approximate matrix decompositions, 2009 (available on arXiv)
2. Facebook implementation of Fast Randomized SVD (python/numpy)
3. fast.ai Numerical Linear Algebra course
4. Candès, Emmanuel J., et al. "Robust principal component analysis." Journal of the ACM (JACM) 58.3 (2011): 11. APA