JSM 2015 Preliminary Program

Online Program Home
My Program

Abstract Details

Activity Number: 465
Type: Invited
Date/Time: Wednesday, August 12, 2015 : 8:30 AM to 10:20 AM
Sponsor: IMS
Abstract #314668
Title: Phase Transitions for High-Dimensional Clustering and Related Problems
Author(s): Zheng Tracy Ke* and Jiashun Jin and Wanjie Wang
Companies: The University of Chicago and Carnegie Mellon University and University of Pennsylvania
Keywords: Principal Component Analysis ; clustering ; feature selection ; phase transition ; hypothesis testing ; low-rank matrix recovery
Abstract:

We consider the two-class clustering problem, where we have measurements of a large number of features but only a small fraction of them contribute to the power of clustering. In the two-dimensional phase space calibrating the rarity of the useful features and their strengths, we find the precise demarcation for the Region of Impossibility and Region of Possibility. In the former, the useful features are too rare/weak to allow successful clustering. In the latter, the useful features are strong enough and successful clustering is possible. We propose both classical PCA and Important Features PCA (IF-PCA) for clustering. For a threshold t > 0, IF-PCA first removes all columns of X whose L2-norm falls below t, and then performs clustering using the classical PCA. We also propose two aggregation methods for clustering. We show that, for any parameter in the Region of Possibility, one or more of these four methods yield successful clustering. We also extend the study to two closely related problems: the signal recovery problem and the hypothesis testing problem. We compare the fundamental limits for all three problems and expose some interesting insight.


Authors who are presenting talks have a * after their name.

Back to the full JSM 2015 program





For program information, contact the JSM Registration Department or phone (888) 231-3473.

For Professional Development information, contact the Education Department.

The views expressed here are those of the individual authors and not necessarily those of the JSM sponsors, their officers, or their staff.

2015 JSM Online Program Home