On Application of Block Kaczmarz Methods in Matrix Factorization
This incremental improvement addresses speed and memory bottlenecks in recommender systems and collaborative filtering applications.
The paper tackles the computational inefficiency of exact least-squares solvers in matrix factorization by proposing a block Kaczmarz solver, which reduces runtime and memory usage while slightly increasing factorization error.
Matrix factorization techniques compute low-rank product approximations of high dimensional data matrices and as a result, are often employed in recommender systems and collaborative filtering applications. However, many algorithms for this task utilize an exact least-squares solver whose computation is time consuming and memory-expensive. In this paper we discuss and test a block Kaczmarz solver that replaces the least-squares subroutine in the common alternating scheme for matrix factorization. This variant trades a small increase in factorization error for significantly faster algorithmic performance. In doing so we find block sizes that produce a solution comparable to that of the least-squares solver for only a fraction of the runtime and working memory requirement.