High-Rank Matrix Completion and Clustering under Self-Expressive Models
We propose efficient algorithms for simultaneous clustering and completion of incomplete high-dimensional data that lie in a union of low-dimensional subspaces. We cast the problem as finding a completion of the data matrix so that each point can be reconstructed as a linear or affine combination of a few data points. Since the problem is NP-hard, we propose a lifting framework and reformulate the problem as a group-sparse recovery of each incomplete data point in a dictionary built using incomplete data, subject to rank-one constraints. To solve the problem efficiently, we propose a rank pursuit algorithm and a convex relaxation. The solution of our algorithms recover missing entries and provides a similarity matrix for clustering. Our algorithms can deal with both low-rank and high-rank matrices, does not suffer from initialization, does not need to know dimensions of subspaces and can work with a small number of data points. By extensive experiments on synthetic data and real problems of video motion segmentation and completion of motion capture data, we show that when the data matrix is low-rank, our algorithm performs on par with or better than low-rank matrix completion methods, while for high-rank data matrices, our method significantly outperforms existing algorithms.
The paper presents an extension to the sparse subspace clustering (SSC) algorithm that allows to complete missing values while also recovering the sparse representation of data. With the sparse representation at hand, the clustering is performed in exactly the same way as in the original SSC algorithm. The authors show that the joint matrix completion and sparse learning may yield better clustering results than performing the two steps independently.
Major comments: The paper describes an interesting extension of the SSC algorithm to allow joint matrix completion and sparse representation. The mathematical formulation is straightforward and the main contribution seems to be in the way the problem is made computationally tractable. I did not find any issues with the technical approach and I think the contribution in that respect is sound.  On the downside, I was not convinced of the practical importance of this framework. Yes, joint matrix completion and subspace clustering seems like an interesting theoretical problem to solve, but do we have a practical real-life example where the benefits of this framework would become evident, particularly compared to the approach where one performs matrix completion and clustering in sequence (especially since LRMC+SSC performed quite decently)?   - The paper shows that the proposed approach outperforms competition in the matrix completion task, but the specific scenario under which one would be interested in matrix completion accuracy feels contrived.  - Additionally, I think the "real" experiments presented in the paper are in fact simulated. The "real" experiments were performed on data that was generated by simulating particular distributions using realistic datasets as the basis. These are not experiments on realistic datasets that would justify the applicability of the approach in real life.   Minor comments:  1. I found the notations paragraph(lines 82-98) somewhat confusing, primarily because it felt unnecessarily generic. For example: - why not state simply that \bar{y_i} is the original datapoint with missing values replaced by zeros.  - why not describe U_{\Omega_j} in simple words. Also, matrices U and P are denoted as matrices of real values, while in reality they are matrices over {0,1}.  2. The font of the references section seems very small.