Dimensionality Reduction with Subspace Structure Preservation
Modeling data as being sampled from a union of independent subspaces has been widely applied to a number of real world applications. However, dimensionality reduction approaches that theoretically preserve this independence assumption have not been well studied. Our key contribution is to show that 2K projection vectors are sufficient for the independence preservation of any K class data sampled from a union of independent subspaces. It is this non-trivial observation that we use for designing our dimensionality reduction technique. In this paper, we propose a novel dimensionality reduction algorithm that theoretically preserves this structure for a given dataset. We support our theoretical analysis with empirical results on both synthetic and real world data achieving state-of-the-art results compared to popular dimensionality reduction techniques.
The paper presents a dimensionality reduction method based for data that lives in a union of independent subspaces. The method is based on the observation that two independent subspaces collapse into two lines if a projection consisting of one vector from each subspace is applied on the data. The authors then present an algorithm to find vectors from different subspaces to be used for projection. Experimental results show that the proposed method performs better than state-of-the-art.In general, I believe that the paper presents a new approach, it explores a new idea, and it provides very good experimental results, and therefore eventually it's worth publishing. However, in my opinion, the paper is not written very well. The authors stress in multiple places that the idea  that 2K projection vectors are sufficient for K class data is "non-trivial". This might be the case, but it's a very intuitive result. I'm very surprised that the paper first presents a formal proof before the geometrical explanation, and this geometrical explanation is not very clear, and Figure 1 is very poorly designed. The proof is also very convoluted, for instance the same subscript j is used to both denote the components of vectors & matrices, as well as different subspaces. Section 3 can be re-organized into a theory and algorithm section, the current structure is not making this distinction clear.The authors can give simple directions how to go about proving Lemma 4 (why is this not Lemma 1?) In the same lemma, there's no guarantee that gamma_hat != 0. Is this a problem? Please comment. In line 179, I wouldn't use \Sigma for subspaces. Or if you do, it'll be good to briefly explain what addition of subspaces mean.It is clear that two major potential problem for the proposed method is noise, and cases where the independent subspaces assumption is not valid. I think the paper doesn't provide enough empirical evidence to investigate these cases. The study in Section 4.1 just verifies the theorems presented in the previous sections, which are already proven. What happens when the independence subspace assumption is not valid? It is not clear what value Section 4.1.2 and Figure 4 have. These can potentially be removed and a more-in-depth analysis can be added instead.The algorithms compared with in Section 4.2 are not state-of-the-art, not even close. There has been a large progress in this area (low rank and sparse subspace clustering), and I think it's unacceptable to ignore all of these recent methods and just compare with older methods like PCA and LDA..