3
$\begingroup$

In class, in the context of matrix completion (recommender Systems, collaborative filtering), we have seen that the Eckart-Young theorem says the best rank-$k$ approximation to a matrix $A$ is given by taking the dominant first $k < \mbox{rank}(A)$ singular values.

Thus, if we have a rating matrix, like in the Netflix data, it was mentioned that the rating matrix has many unobserved values that are not defined. The task is to infer these entries. One solution approach we have seen is via Matrix Factorization using Alternating Least Squares.

Why can't we use SVD to solve this problem?

Since with the Eckart-Young theorem it is guaranteed that we get the best rank-$k$ approximation of the rating matrix, it seems that unobserved values incur a problem, we cannot just set the unobserved values to $0$ or the mean of the data, but why is that?

Does it have to do with the rank-k constraint in the minimization problem

$$ A_k = \arg \min_{\mbox{rank}(B)=k} \left\Vert A - B \right\Vert_F^2 $$

because with the rank constrained it is a non-convex problem and Eckart-Young theorem does not guarantee the best rank-$k$ approximation anymore if there are unobserved values in $A$?

$\endgroup$
  • $\begingroup$ What is a rating matrix? Where is it defined? $\endgroup$ – Rodrigo de Azevedo Jul 6 '19 at 6:32
  • $\begingroup$ We cannot do SVD on a matrix if we don't know some of it's values. What to do when you are supposed to multiply or add this unknown value with anything? $\endgroup$ – mathreadler Jul 7 '19 at 11:08
  • $\begingroup$ Rating matrix is defined as follows: the rows represent the users, columns represent 'items'. $\endgroup$ – gammaALpha Jul 8 '19 at 13:12
1
$\begingroup$

If you have started getting good at vectorization and Kronecker products, one approach you can do is

$$\min_{U,V,\Sigma} \{C_1\|A-U\Sigma V^T\|+ \|UU^T-I\|+ \|VV^T-I\| + \|C_2\Sigma\| \}$$

  1. Weight matrix $C_1$ should reflect which values of $A$ are unknown.

  2. Weight matrix $C_2$ should reflect the rank you seek. $k$ small $\epsilon$s and the rest large values along diagonal and outside. Should work neatly.

As it probably needs some maturity and skills, it might be suitable work for a PhD student main project.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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