I am reading in the soft-imputing paper for low-rank-based matrix completion. They suggested another solution for $$\hat{Z} = \text{argmin}_Z\lVert X - Z \rVert_F^2 + \lambda \lVert Z \rVert_*$$

instead of solving it by the soft thresholding operator $\hat{Z} = S_\lambda(X) = UD'V, D' = diag([(d_1 - \lambda)_+ \dots (d_n - \lambda)_+])$ where $d_i$ is the singular values for $X$ and $(p)_+$ operator will return $p$ if $p \ge 0$, $0$ otherwise.

Their solution is an iterative one where in each iteration they solve for a surrogate function, $Q_\lambda(Z | Z^\sim) = .5 \lVert P_\Omega(X) + P^\bot_\Omega(Z^\sim) - Z\rVert_F^2 + \lambda \lVert Z\rVert_*$, where:

$$ P_\Omega (Y) (i, j) = \begin{cases} Y_{ij}, & \text{ if } (i, j) \in \Omega \\ 0 ,& \text{ if } (i, j) \notin \Omega \\ \end{cases} $$

and $Z = P^\bot_\Omega(Z) + P_\Omega(Z) $, $ P^\bot$ is the complementary projection. The solution is an iterative solution for $\text{argmin}_{Z^{k+1}} Q_\lambda(Z^{k+1} | Z^{k})$. My question what is the computational advantage we may get by iteratively solving with respect to the surrogate function $Q$ instead of a one-shot solution $S_\lambda$? In other words, what is the computational advantage of solving for $S_\lambda( P_\Omega(X)+P^\bot_\Omega(Z^k))$ over $S_\lambda(X)$?


Your Answer

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

Browse other questions tagged or ask your own question.