The sampling strategy for the coordinate blocks has a dramatic impact on the convergence rate [1]}. [2]} demonstrate that by optimizing the sampling probabilities one can obtain very significant speedups, however this optimization is a semidefinite program which may be even more challenging than the original optimization problem itself. Even when using a basic sampling strategy (such as uniform), the convergence analysis of RNM is challenging because it hinges on deriving the expected pseudoinverse of \(_{\hat{S}}\) , henceforth denoted \([(_{\hat{S}})^+]\) . Prior to this work, no simple closed form expression was known for this quantity.
