Finding Structure with Randomness Probabilistic Algorithms for Approximate Matrix Decompositions Research Project Report "Sparsity and Compressed Sensing" course
Matrix factorization is a powerful tool to achieve tasks efficiently in numerical linear algebra. A problem arises when we compute low rank approximations for massive matrices: we have to reduce the algorithms' complexity in time to hope to be efficient. A way to adapt these techniques for such computational environments is randomization. This report presents a framework for these new techniques, mainly based on the recent work by N. Halko, P. G. Martinsson and J. Tropp presented in "Finding Structure with Randomness: Probabilistic Algorithms for Constructing approximate Matrix Decompositions" [HMT11, Tro14] The main intuition behind the various algorithms presented herein is using random sampling to apprehend the action of the matrix in a "compressed" subspace. We can apply then the classical methods on the resulting matrix the one acting on the "compressed" subspace to obtain a low rank approximation. Another application that rises from this explanation is the fact that this method is thus more robust addressing incomplete data sets that one can get in information sciences, while other. The benefits of such methods will depend on the matrix. We will decline the results for two main classes: dense matrices where the new complexity is about log( compared to for classical methods being the numerical rank; sparse matrices, and in general, structured matrices. [HMT11] also studied massive matrices that do not fit in fast memory (RAM) for which the access time which surpasses computation time can be reduced to one pass, comparing to passes, but due to space constraint we will not present it here. A clean Octave implementation was developed, and we will present 2 experiments, done on both dense and sparse matrices, in order to confirm the theoretical analysis. *If needed, see on line at http:/lbo.k.vu/pcs2016 for an e version of this report, as well as additional resources (slides, code, figures, complete bibliography etc) open sourced under the MIT License.