# Why we even try to minimize a loss function, which is non-convex, in matrix factorization?

In matrix factorization (especially under the scenario of recommendation system), we often try to factorize a matrix Y into two low rank matrices: $Y=U\cdot V^T$

If we assume there $m$ instances in $Y$ and error satisfies Gaussian distribution, then this leads us to a squared loss function:

$L(U,V)=1/2 \sum_{i=1}^m\Big( y^{(i)} - u^{(i)}v^{(i)} \Big)^2$

Many textbooks just say we could solve this minimization by gradient descent.

However, I think this loss function is non-convex (as its Hessian matrix is not positive semidefinite), why could we solve it with gradient descent? Gradient descent only leads us to local optimum, and there might be multiple local optimum over there, what is the point for getting one of them?

• Because a local optimum is better than no optimum. Sometimes it may be good enough for the applications. – Marc Claesen Nov 4 '14 at 14:06
• @MarcClaesen Is that means we have to run the gradient descent many times and choose the best result one? Because each time we might get different local optimums. – ice_lin Nov 5 '14 at 5:18