Correlated-PCA: Principal Components' Analysis when Data and Noise are Correlated
Given a matrix of observed data, Principal Components Analysis (PCA) computes a small number of orthogonal directions that contain most of its variability. Provably accurate solutions for PCA have been in use for a long time. However, to the best of our knowledge, all existing theoretical guarantees for it assume that the data and the corrupting noise are mutually independent, or at least uncorrelated. This is valid in practice often, but not always. In this paper, we study the PCA problem in the setting where the data and noise can be correlated. Such noise is often also referred to as "data-dependent noise". We obtain a correctness result for the standard eigenvalue decomposition (EVD) based solution to PCA under simple assumptions on the data-noise correlation. We also develop and analyze a generalization of EVD, cluster-EVD, that improves upon EVD in certain regimes.
The paper analyzes the PCA (eigen value decomposition -EVD) for the cases where underlying data and noise are correlated. The authors prove the correctness of this approach, providing an upper bound on the subspace recovery error, and then provide a generalization of PCA - cluster EVD, which overcomes limitations on the sample complexity of PCA, which is bound by the condition number of the covariance matrix.   The paper provides various models of correlation between data and noise, and provides background literature on the recovery error and sample complexity for existing approaches that solve this problem.   The main contribution is the derivation of cluster-EVD, and proving the upperbound on the sample complexity when assumptions on the nature of clustering of eigen values across scales holds.  
The paper analyzes the PCA (eigen value decomposition -EVD) for the cases where underlying data and noise are correlated. The authors prove the correctness of this approach, providing an upper bound on the subspace recovery error, and then provide a generalization of PCA - cluster EVD, which overcomes limitations on the sample complexity of PCA, which is bound by the condition number of the covariance matrix.   The adaptation of clustering of eigen vlaues and the strategy used are novel.   The proofs are reasonably well structured and clear. The authors could possibly position theoram 3.3 earlier in the text, and add the proof outline later.   The authors study some cases of videos where the assumption of clustered eigen values is observed. Some more practical scenarios will be useful to understand the scope of applicability of the algorithm.  The experiment section is validates the method in their chosen metrics, in comparison to other methods that solve similar problems in PCA. The authors clarify that there are certain generalized cases (where the clustered eigenvalues assumption doesn't hold, assumption on missing/corrupted values doesn't hold), where cluster-EVD is not optimal. A possible experiment would be a comparison with other methods when these assumptions are not satisfied. A satisfactory performance would be show that cluster-EVD can be used in less restrictive cases as well.   Overall, the paper provides a key observation that solves a specific problem. The paper is well written.