Matrix factorization for expanding matrix In the paper Matrix Factorization Techniques for Recommender Systems Koren, Bell and Volinsky describe how the matrix $R_{n \times k}$ (users $\times$ movie ratings) can be decomposed to $P_{n \times m}$ and $Q_{m \times k}$ matrices using a matrix factorization that uses stochastic gradient descent. So we approximate $\hat{r}_{iu} = q_i^Tp_u$ and the prediction error is
$$
e_{iu} = r_{iu} - q_i^Tp_u
$$
what leads to the SGD update rule
$$
q_i \leftarrow q_i + \gamma (e_{ui} p_u-\lambda q_i) \\
p_u \leftarrow p_u + \gamma (e_{ui} q_i-\lambda p_u)
$$
where $\lambda$ is the regularization parameter and $\gamma$ is the learning rate. The algorithm iterates starting from the randomly initialized $P$ and $Q$.
What exactly can we do when new episode of Star Wars appears and our matrix expands to $R_{n \times k+1}$? The authors seem to say that the algorithm can handle that, but don't say how. I guess that we simply expand $Q_{m \times k}$ to $Q_{m \times k+1}$ with randomly initialized values, or is there a better approach?
 A: If you expand $Q_{m \times k}$ to $Q_{m \times k + 1}$ with a randomly initialized vector for the new movie it's equivalent to having had the new episode of Star Wars as a known movie all along, but with no observations in the rating matrix. 
All movies start with randomly initialized vectors in $Q$, and those vectors are updated based on the entries in the rating matrix. Since this new movie has no entries, it never gets updated, and remains at it's initial random initialization.
This allows the system to "work" in the sense that you can now make predictions for the new episode, but clearly the predictions will be meaningless.
In order to actually get meaningful recommendations you can follow the the last few paragraphs in the ADDITIONAL INPUT SOURCES section of the paper. For example, before the new episode of Star Wars is released you will have other non-rating information about the movie: genre, director, MPAA rating, actors, and so forth. Each of these attributes can be factorized, and the factorized representation added to the base movie vector.
You can adapt equation (6) in the paper like so:
$\hat{r}_{ui} = \mu + b_{i} + b_{u} + [q_{i} + \sum_{a \in A(i)} y_a ]^{T} p_{u} $
where movie $i$ corresponds to the set of attributes $A(i)$. Then you learn the factor representations for each attribute during the training process. As an example, the attribute "has JJ Abrams as director" will have a learned factor representation that is added in to all of item vectors for movies that JJ Abrams directed.
