Matrix factorization in recommender systems: adding a new user

Question

I estimate ratings in a user-item matrix by decomposing the matrix into two matrices P and Q and then using gradient descent to minimize the error. Now, if I want to add a new user, the most obvious solution is to retrain the model. This, however, takes a lot of time even with a small number of steps.

Singular Value Decomposition allows to easily add a new user by computing: user_k = Sigma^(-1) * Ut * user

Is there anything like that for matrix factorization? Can a new user be added without recomputing everything?

Answer 1

Since your training matrix decomposition with gradient descent, I assume you have some loss function $L(X - PQ)$ where $L$ is squared Frobenius norm or something similar.

When you add a new user (let's say rows of $X$ correspond to users, and $x$ is new user's row, so that $X$' is $X$ with concatenated $x$) your objective becomes $$L(X' - P'Q)$$ and if your loss is something that can be calculated by summing over rows, $$L(X' - P'Q) = L(X - PQ) + L(x - x_pQ)$$.

If you already have trained $P, Q$ so that they minimize $L(X - PQ)$ then you have a guess for $P, Q$.

If you want to incorporate new user, but not recompute everything, you could either optimize $L(x - x_pQ)$ with $Q$ fixed or changed.