3
$\begingroup$

I'm trying to prove the convergence of Matrix factorization. The problem is described below. $|X-WH|^2 + |H|_2^2 +|W|_2^2$.

My optimization steps are using Alternating least squares which update H with fixing W and update W with fixing H.

Although I can prove the convergence of subproblems(e.x. update H with fixing W), I have no idea to prove the convergence of this problem but not subproblems.

Does someone give some clues about how to prove the convergence of matrix factorization globally?

Thanks.

$\endgroup$
3
  • 1
    $\begingroup$ which Norm are you using (trace norm, spectral norm, or some other norm?). $\endgroup$
    – user35593
    Aug 21, 2014 at 10:03
  • $\begingroup$ Your algorithm generates a monoton decreasing sequence. Furthermore the functional is bounded from below by 0. Hence the values of the functional will converge. Given a constant $c>0$ we know that the domain where the functional is smaller than c is finite. Hence the sequence (H_i,W_i) has a subsequence converging to some(\bar{H},\bar{W}). Now one can prove that (\bar{H},\bar{W}) is a critical point. If you can prove that your functional is convex u are basically done as then ur functional has a unique minimum which is also the unique critical point. However I dont know how to prove convexity. $\endgroup$
    – user35593
    Aug 21, 2014 at 10:10
  • $\begingroup$ I use the Frobenius norm. $\endgroup$
    – Chao
    Aug 22, 2014 at 6:08

1 Answer 1

3
$\begingroup$

Your problem is a special case of Alternating Minimization, on which many papers have been written.

One of the clearest (for your nonconvex problem) is this classic paper, which pays particular attention to the two block case: L. Grippo, M. Sciandrone, On the convergence of the block nonlinear Gauss–Seidel method under convex constraints. Operation Research Letters 26(2000), 127--136.

$\endgroup$
1
  • $\begingroup$ Super thank you to your answer. I will read this paper. $\endgroup$
    – Chao
    Sep 3, 2014 at 12:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.