1
$\begingroup$

I am trying to implement the algorithm for matrix completion proposed by Keshavan, Montanari and Oh (2009). It consists of three steps:

  1. Trimming which nulls some rows and columns to make the high singular values stand out

  2. Projecting which basically does a SVD of a 'sparse' matrix

  3. Cleaning which minimizes the residual errors

I have some problems understanding the cleaning step: Projecting gives you $U$, $\Sigma$ and $V$ (eq 3). Cleaning requires a $S$ matrix in $R(r,r)$ minimizing the cost function (eq 4). Optimizing the cost function with the Gradient Descent algorithm (below Remark 6.2) requires $S$. However, I cannot find any information how to calculate $S$. Can anybody please bring some light into how to understand these equations?

$\endgroup$
2
  • 1
    $\begingroup$ isn't $S$ just the $r\times r$ real matrix that minimizes the function defined in equation 5 from that paper? $\endgroup$ Dec 27, 2015 at 19:25
  • $\begingroup$ Thanks Carlo! Just to clarify: Do you mean I have to find a new optimal S after each iteration in the Gradient Descent algorithm? $\endgroup$
    – J. Doe
    Dec 27, 2015 at 19:29

0

Your Answer

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

Browse other questions tagged or ask your own question.