Relations among Some Low Rank Subspace Recovery Models

Abstract

Recovering intrinsic low dimensional subspaces from data distributed on them is a key preprocessing step to many applications. In recent years, there has been a lot of work that models subspace recovery as low rank minimization problems. We find that some representative models, such as Robust Principal Component Analysis (R-PCA), Robust Low Rank Representation (R-LRR), and Robust Latent Low Rank Representation (R-LatLRR), are actually deeply connected. More specifically, we discover that once a solution to one of the models is obtained, we can obtain the solutions to other models in closed-form formulations. Since R-PCA is the simplest, our discovery makes it the center of low rank subspace recovery models. Our work has two important implications. First, R-PCA has a solid theoretical foundation. Under certain conditions, we could find better solutions to these low rank models at overwhelming probabilities, although these models are non-convex. Second, we can obtain significantly faster algorithms for these models by solving R-PCA first. The computation cost can be further cut by applying low complexity randomized algorithms, e.g., our novel ${\ell }_{2,1}$ filtering algorithm, to R-PCA. Experiments verify the advantages of our algorithms over other state-of-the-art ones that are based on the alternating direction method.

arXiv commentSubmitted to Neural Computation

References in corpus (6)

• Robust Recovery of Subspace Structures by Low-Rank Representation
• Randomized algorithms for matrices and data
• Fixed-Rank Representation for Unsupervised Visual Learning
• Analysis and Improvement of Low Rank Representation for Subspace segmentation
• A Counterexample for the Validity of Using Nuclear Norm as a Convex Surrogate of Rank
• Structural Similarity and Distance in Learning