“To be considered for an 2015 IEEE Jack Keil Wolf ISIT Student Paper Award.” This work studies two interrelated problems - online robust PCA (RPCA) and online matrix completion (MC). Both problems assume that an accurate estimate of the low-dimensional subspace from which the first true data vector is generated is available. We develop a practical modification of a recently proposed algorithm to solve both problems; and we obtain correctness results for the proposed algorithms under mild assumptions.