Supplementary material: - swissroll.gif: GIF animation over iterations of the result of our algorithm on a 3000-point 100D swissroll data set with over 93% missing values at random. To display the result, we project the data set back into 3D. Our initial data set imputation (iteration 0) is provided by fitting a Gaussian with EM to the present values provided, and imputing the missing ones as the conditional mean under the model. Thereafter we run alternating steps of MBMS (with parameters as shown in the animation) and refilling the present values. - mocap.gif: GIF animation of the reconstruction of the 148 frames of a walking motion (intrinsically 1 dimensional) with 85% missing values at random, from nlPCA, SVP, Gaussian model and our algorithms (based on GBMS and MBMS) initialized from the other three, with parameters as in the paper. Each frame has 50 3D sensor readings (thus each frame is a 150D data point). Our algorithm improves each of the three initializations. All these animations may be seen with a web browser or with specialized GIF image viewers.