SUBSPACE CLUSTERING

Find k low-dimensional linear subspaces to ap-proximate a set of unlabeled data points. • k-means objective: minC cost(C;X), where cost(C;X) = ∑ni=1 minkj=1 d2(xi,Sj)/n. DIFFERENTIAL PRIVACY Definition. A randomized algorithm A is (ε, δ)-differentially private if for all X,Y satisfying d(X,Y) = 1 and all measurable sets S, we have Pr[A(X) ∈ S] ≤ eε Pr[A(Y) ∈ S] + δ. Objective. Develop differentially private sub-space clustering algorithms and characterize the tradeoff between statistical efficiency and guaran-teed privacy. • Important as subspace clustering is an in-creasingly popular tool for anlyzing sensi-tive medical and social network data. DP tools. Sample-and-aggregate [1], exponential mechanism [2], SuLQ [3], etc. METHODS 1. Sample-and-aggregate based private subspace clustering • f(·) can be any approximation algorithm for subspace clustering. • Requires stability of f (i.e., f(XS) ≈ f(X)) to work. 2. Exponential mechanism based private subspace clustering p({S`}k`=1, {zi}ni=1;X) ∝ exp −