A randomized generalized low rank approximations of matrices algorithm for high dimensionality reduction and image compression

High-dimensionality reduction techniques are very important tools in machine learning and data mining. The method of generalized low rank approximations of matrices (GLRAM) is a popular technique for dimensionality reduction and image compression. However, it suffers from heavily computational overhead in practice, especially for data with high dimension. In order to reduce the cost of this algorithm, we propose a randomized GLRAM algorithm based on randomized singular value decomposition (RSVD). The theoretical contribution of our work is threefold. First, we discuss the decaying property of singular values of the matrices during iterations of the GLRAM algorithm, and provide a target rank required in the RSVD process from a theoretical point of view. Second, we establish the relationship between the reconstruction errors generated by the standard GLRAM algorithm and the randomized GLRAM algorithm. It is shown that the reconstruction errors generated by the former and the latter are comparable, even if the solutions are computed inaccurately during iterations. Third, the convergence of the randomized GLRAM algorithm is investigated. Numerical experiments on some real-world data sets illustrate the superiority of our proposed algorithm over its original counterpart and some state-of-the-art GLRAM-type algorithms.

Automated summary

High-dimensionality reduction techniques are crucial in machine learning and data mining, and the randomized GLRAM algorithm based on randomized singular value decomposition (RSVD) offers a more cost-effective solution with superior performance in real-world data sets. The theoretical contributions of the algorithm include discussing the decaying property of singular values, establishing the relationship between reconstruction errors, and investigating the convergence of the algorithm.