Convergence analysis of the rank-restricted soft SVD algorithm

Figure 1.  For a full-rank $ X $ matrix (left) Algorithms 1 and 3 have similar performance, however when $ X $ is approximately low-rank (right) Algorithm 3 is significantly faster. In both examples $ X $ is $ 500\times 500 $ and we set $ r = 10 $ and $ \lambda = 0.5 $ and the minimum cost is computed using $ A_{\rm opt}, B_{\rm opt} $. In the left panel the entries of $ X $ are independent standard Gaussian random variables. In the right panel $ \tilde A,\tilde B $ are $ 500\times 10 $ matrices with independent standard Gaussian entries and $ X = \tilde A\tilde B^\top + 10\tilde X $ where $ \tilde X $ is $ 500\times 500 $ with standard Gaussian entries

Figure 2.  Comparison of Algorithm 2 from [9] with our new Algorithm 3 on the same full-rank (left) and approximately low-rank (right) examples from Figure 1

Figure 3.  Comparison of the convergence of the singular vectors on the same full-rank (left) and approximately low-rank (right) examples from Figure 1. Error is measured by $ ||U_k^\top U_{(r+1:n)}||_{\max} $, where $ U_{(r+1:n)} $ is the matrix containing the $ (r+1) $-st through $ n $-th columns of $ U $. The theoretical convergence rate $ \left(\frac{s_{r+1}}{s_r}\right)^2 $ shown is proven in Theorem 2.3. Notice that the singular vectors converge for both Algorithm 2 from [9] and our new Algorithm 3