Matrix Factorization for Collaborative Filtering

Problem Description

Matrix factorization is a way to generate latent features when multiplying two different kinds of entities. Collaborative filtering is the application of matrix factorization to identify the relationship between items’ and users’ entities. With the input of users’ ratings on the shop items, we would like to predict how the users would rate the items so the users can get the recommendation based on the prediction.

Collaborative Filtering: Collaborative filtering is to discover the similarities on the user’s past behavior and make predictions to the user based on a similar preferecne with other users. This model is then used to predict items (or ratings for items) that the user may have an interest in.

Bounds Chart

Step Chart

Improvement Table

Complexity Classes	Algorithm Paper Links	Lower Bounds Paper Links
Exp/Factorial
Polynomial > 3
Cubic	[ LU Matrix Decomposition (1945)]
Quadratic	[ QR Matrix Decomposition (1955)] [ Cholesky Decomposition (1983)]
nlogn
Linear
logn