Recovery of Coherent Data via Low-Rank Dictionary Pursuit
The recently established RPCA [4] method provides a convenient way to restore low-rank matrices from grossly corrupted observations. While elegant in theory and powerful in reality, RPCA is not an ultimate solution to the low-rank matrix recovery problem. Indeed, its performance may not be perfect even when data are strictly low-rank. This is because RPCA ignores clustering structures of the data which are ubiquitous in applications. As the number of cluster grows, the coherence of data keeps increasing, and accordingly, the recovery performance of RPCA degrades. We show that the challenges raised by coherent data (i.e., data with high coherence) could be alleviated by Low-Rank Representation (LRR) [13], provided that the dictionary in LRR is configured appropriately. More precisely, we mathematically prove that if the dictionary itself is low-rank then LRR is immune to the coherence parameter which increases with the underlying cluster number. This provides an elementary principle for dealing with coherent data and naturally leads to a practical algorithm for obtaining proper dictionaries in unsupervised environments. Experiments on randomly generated matrices and real motion sequences verify our claims. See the full paper at arXiv:1404.4032.
The paper proposes to use Low Rank Representation (LRR) with some learned dictionary A to improve the effectiveness of RPCA. In particular, the authors show that the incoherence parameter \mu which often thought of as a bottleneck in the recovery guarantee in RPCA can in fact correspond to some additional clustering structure in the data. Under some condition on the dictionary A, the authors show that one can exploit such structure using LRR and partially remove the dependence on \mu and get a theoretically stronger guarantee in both exact low-rank and sparse decomposition and its noisy extension.The method is novel and significant to the field. It is closely related to the union-of-subspace structure assumed in previous subspace clustering papers such as “Wang and Xu: Noisy Sparse Subspace Clustering & Provable subspace clustering: When LRR meets SSC”, and “Soltanolkotabi and Candes: A geometric analysis of subspace clustering with outliers” “Soltanolkotabi et al: Robust subspace clustering” but are less explicit about the assumption on “clustering”, which is reasonable and more probably more general. The simulation and real data experiments verify the theoretical analysis and I think the new structure can be found in many other real applications too (such as text data as remarked in the paper).In summary, the paper contains a substantial contribution to the field of compressed sensing and I think it should be accepted by NIPS.That said, I do have a number of discussions and stylistic suggestions which are summarized in the detailed comments below. 1.	Line 80-82: Need some re-writing to make the description clearer. What do you mean by “our data”? Also even if the problem captures all the structures in the problem, there is still yet another condition to qualify to have “perfect recovery”.2.	Line 88: … is no longer a method of perfect (WHAT?).3.	Please proof-read the papers more carefully for problems like the above two. Be specific and precise about what to claim and what you are referring to in the text. In general, please work on clarity of the language in the paper.4.	Wang and Xu also have written in their paper “Noisy Sparse Subspace Clustering” how higher coherence parameter is actually good for subspace clustering (unlike in RPCA and matrix completion). The key difference from here is that the data need not be low-rank in overall, only every cluster has to be low-rank. The structure exploited here in this paper can be thought of as a combination of low-rank structure and union-of-subspace cluster structure.5.	It will be interesting to compare the proposed algorithm against first solving noisy subspace clustering with \ell_1 penalty then do PCA for each subspace. No provable guarantee exists to date for the later version though.6.	Section 4.2 essentially proposes a new method for solving subspace clustering problem with sparse corruption in the data. The method leads to significant improvements over the standard RPCA+SSC on Hopkins155 dataset which I think is a hidden contribution here in this paper and the authors should point it out.