matrix factorization

Matrix factorization

A matrix factorization/decomposition is an exact multiplicative representation of a matrix as a product of matrices, in contrast to (matrix) composition, where we multiply matrices to get a single matrix. Both forms express the same transformation:

$$A=F_1{F}_2\cdots F_k$$

where $F_i$ are matrices which usually have special structure (e.g. triangular matrix, orthogonal matrix, diagonal matrix, etc.) that make them easier/more efficient to work with/simplify computation, or reveal properties of the original matrix $A$.

Examples:

• singular value decomposition (most general, works for any matrix)
• eigendecomposition (for square matrixs with enough linearly independent eigenvectors)
• Cholesky decomposition (for symmetric matrixs that are also positive definite)
• LU decomposition (for square matrixs)
• …

A low-rank approximation of a matrix via learned matrix factorization.

Given $X\in {\mathbb{R}}^{m\times n}$, choose rank $k\ll \min (m,n)$ and learn

$$X\approx U{V}^{\top },U\in {\mathbb{R}}^{m\times k},V\in {\mathbb{R}}^{n\times k}.$$

Typically fit by minimizing a regularized loss over observed entries $\Omega$:

$$\underset{U,V}{\min }\sum _{(i,j)\in \Omega }(X_{ij}-U_i^{\top }{V}_j{)}^2+\lambda (\Vert U{\Vert }_F^2+\Vert V{\Vert }_F^2).$$

Unlike plain SVD, MF handles sparsity/missing data and adds regularization.

This can be used nicely for recommender systems.