In this talk, we present a new algorithm for low rank LU decomposition that uses random projections type techniques that can be used to efficiently compute a low rank approximation of large matrices. The randomized LU algorithm can be parallelized and efficiently run on GPUs making it suitable for image processing tasks. Moreover, it can utilize sparsity to accelerate the computations even more. Several error bounds for the algorithm’s approximations are proved using random Gaussian and random sparse matrices.
As a machine learning application, the algorithm can be used for fast dictionary learning that can be utilized for classification, file content detection and anomaly detection and more. It is based on the paper titled Randomized LU Decomposition.
Joint work with Gil Shabat and Yaniv Shmueli – part of their PhD theses.