Home Page

Papers

Submissions

News

Editorial Board

Announcements

Proceedings

Open Source Software

Search

Login



RSS Feed

A Deterministic Analysis of Noisy Sparse Subspace Clustering for Dimensionality-reduced Data

Yining Wang, Yu-Xiang Wang, Aarti Singh
Proceedings of The 32nd International Conference on Machine Learning, pp. 1422–1431, 2015

Abstract

Subspace clustering groups data into several lowrank subspaces. In this paper, we propose a theoretical framework to analyze a popular optimization-based algorithm, Sparse Subspace Clustering (SSC), when the data dimension is compressed via some random projection algorithms. We show SSC provably succeeds if the random projection is a subspace embedding, which includes random Gaussian projection, uniform row sampling, FJLT, sketching, etc. Our analysis applies to the most general deterministic setting and is able to handle both adversarial and stochastic noise. It also results in the first algorithm for privacy-preserved subspace clustering.

Related Material