Online Robust PCA via Stochastic Optimization
Robust PCA methods are typically based on batch optimization and have to load all the samples into memory during optimization. This prevents them from efficiently processing big data. In this paper, we develop an Online Robust PCA (OR-PCA) that processes one sample per time instance and hence its memory cost is independent of the number of samples, significantly enhancing the computation and storage efficiency. The proposed OR-PCA is based on stochastic optimization of an equivalent reformulation of the batch RPCA. Indeed, we show that OR-PCA provides a sequence of subspace estimations converging to the optimum of its batch counterpart and hence is provably robust to sparse corruption. Moreover, OR-PCA can naturally be applied for tracking dynamic subspace. Comprehensive simulations on subspace recovering and tracking demonstrate the robustness and efficiency advantages of the OR-PCA over online PCA and batch RPCA methods.
The paper presents a iterative algorithm to a robust 
      principal component matrix factorization. The data is modeled as a sum of 
      a low rank matrix approximation and a sparse noise matrix. Constraining 
      the norms of the row and column factors of the former part of the sum 
      allows to implement the nuclear norm minimization of the batch robust pca 
      algorithm in an online stochastic gradient descent fashion. The 
      approach taken by the authors resembles very much the approach taken by 
      Marial et al 2009 (ICML) and 2010 (JMLR), only that the objective is 
      slightly different (Robust PCA was not dealt with in the JMLR version). 
      One difference between the JMLR and the ICML version is that a standard 
      stochastic gradient version of the objective function did not perform as 
      well as the proposed online dictionary learning approach (in which the 
      statistics of the data are accumulated in the matrices A and B) in the 
      ICML version, but in the JMLR version, a standard stochastic gradient 
      implementation with appropriately chosen learning rate seemed to perform 
      ok. As storing and updating the matrices A and B can be costly, it would 
      be interesting to see whether a standard first order or quasi-newton 
      stochastic gradient approach for optimizing eq. (2) performs as well as 
      the solution proposed in algorithms 1 and 2. Quality The 
      manuscript is very well written. Clarity All parts of the 
      manuscript appear to be very accessible. Problem formulation and 
      motivation for the method are clear, objective function and the algorithm 
      are comprehensible. Simulations are sensible and well done. 
      Originality The approach proposed by the authors seems very 
      similar to the one proposed by Marial et al in their 2009 and 2010 paper. 
      The proofs appear to be based on the same techniques, in large parts. 
      Convergence to a global optimum instead of a local optimum is new. 
      Using a low-norm factorization instead of a batch version of nuclear 
      norm minimization is fairly well established, see e.g. Rennie and Srebro, 
      'Fast Maximum Margin Matrix Factorization for Collaborative Prediction', 
      ICML, 2005. Significance Iterative methods are becoming more 
      relevant with growing data set sizes. It is important to have scalable 
      versions of simple methods such as PCA and robust versions thereof for 
      large scale data sets. Although the ingredients are well known, to the 
      best of my knowledge, the proposed method is novel and potentially 
      relevant to a large part of the research community.