A Theoretical Analysis of Noisy Sparse Subspace Clustering on Dimensionality-Reduced Data
From MaRDI portal
Publication:4615334
DOI10.1109/TIT.2018.2879912zbMATH Open1432.62192arXiv1610.07650WikidataQ128995002 ScholiaQ128995002MaRDI QIDQ4615334FDOQ4615334
Authors:
Publication date: 28 January 2019
Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)
Abstract: 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; Avron et al., 2014). Finally, we apply our analysis to a differentially private SSC algorithm and established both privacy and utility guarantees of the proposed method.
Full work available at URL: https://arxiv.org/abs/1610.07650
Cited In (3)
This page was built for publication: A Theoretical Analysis of Noisy Sparse Subspace Clustering on Dimensionality-Reduced Data
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4615334)
