Subspace clustering is the problem of partitioning unlabeled data points into a number of clusters so that data points within one cluster lie approximately on a low-dimensional linear subspace. In many practical scenarios, the dimensionality of data points to be clustered are compressed due to constraints of measurement, computation or privacy. In this paper, we study the theoretical properties of a popular subspace clustering algorithm named sparse subspace clustering (SSC) and establish formal success conditions of SSC on dimensionality-reduced data. Our analysis applies to the most general fully deterministic model where both underlying subspaces and data points within each subspace are deterministically positioned, and also a wide range of dimensionality reduction techniques (e.g., Gaussian random projection, uniform subsampling, sketching) that fall into a subspace embedding framework (Meng & Mahoney, 2013; , 2014). Finally, we apply our analysis to a differentially private SSC algorithm and established both privacy and utility guarantees of the proposed method.
proposed a novel dimensionality reduction algorithm to preserve independent subspace structures @cite_8 . They showed that by using @math , where @math is the number of subspaces, one can preserve the independence structure among subspaces. However, their analysis only applies to noiseless and independent subspaces, while our analysis applies even when the least principal angle between two subspaces diminishes and can tolerate a fair amount of noise. Furthermore, in our analysis the target dimension @math required depends on the maximum intrinsic subspace dimension @math instead of @math . Usually @math is quite small in practice .
@cite_8
2132788060
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 @math projection vectors are sufficient for the independence preservation of any @math 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 results compared to popular dimensionality reduction techniques.