Compressed Singular Value Decomposition for Image and Video Processing

N. Benjamin Erichson, Steven L. Brunton, J. Nathan Kutz; Proceedings of the IEEE International Conference on Computer Vision (ICCV), 2017, pp. 1880-1888

We demonstrate a heuristic algorithm to compute the approximate low-rank singular value decomposition. The algorithm is inspired by ideas from compressed sensing and, in particular, is suitable for image and video processing applications. Specifically, our compressed singular value decomposition (cSVD) algorithm employs aggressive random test matrices to efficiently sketch the row space of the input matrix. The resulting compressed representation of the data enables the computation of an accurate approximation of the dominant high-dimensional left and right singular vectors. We benchmark cSVD against the current state-of-the-art randomized SVD and show a performance boost while attaining near similar relative errors. The cSVD is simple to implement as well as embarrassingly parallel, i.e, ideally suited for GPU computations and mobile platforms.