Alternating Least Squares Regression

Matrix decomposition

Consider a movie recommendation system with $n$ users and $m$ movies. Suppose the matrix $A \in \R^{n \times m}$ represents the rating matrix where its $(i,j)^{th}$ entry $A_{ij}$ represents the rating given by the $i^{th}$ user to the $j^{th}$ movie. We would like to represent/decompose the matrix $A$ as a product of the two matrices $X \in \R^{n \times r}, Y \in \R^{m \times r}$ as follows:

Here, $X \in \R^{n \times r}, Y \in \R^{m \times r}$ are often referred to as the user and item matrices, respectively. The user matrix $X$ can represent the behavior of all $n$ users in an $r$-dimensional latent space. Similarly, the item matrix $Y$ can represent all $m$ movies in the same $r$-dimensional latent space.

Furthermore, the computational complexity to multiply the matrices $X$ and $Y$ is of the order $O(nmr)$ ...