Computational Complexity Reduction for Factorization-Based Collaborative Filtering Algorithms

Alternating least squares (ALS) is a powerful matrix factorization (MF) algorithm for both implicit and explicit feedback based recommender systems. We show that by using the Shernian-Morrison formula (SMF), we can reduce the computational complexity of several ALS based algorithms. It also reduces the complexity of greedy forward and backward feature selection algorithms by an order of magnitude. We propose linear kernel ridge regression (KRR) for users with few ratings. We show that both SAW and KRR can efficiently handle new ratings.