# Computational advantage for soft-impute method over other methods

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)$$?