Timezone: »

 
Poster
Sparse PCA via Bipartite Matchings
Megasthenis Asteris · Dimitris Papailiopoulos · Anastasios Kyrillidis · Alex Dimakis

Wed Dec 09 04:00 PM -- 08:59 PM (PST) @ 210 C #57
in Poster Session »
We consider the following multi-component sparse PCA problem:given a set of data points, we seek to extract a small number of sparse components with \emph{disjoint} supports that jointly capture the maximum possible variance.Such components can be computed one by one, repeatedly solving the single-component problem and deflating the input data matrix, but this greedy procedure is suboptimal.We present a novel algorithm for sparse PCA that jointly optimizes multiple disjoint components. The extracted features capture variance that lies within a multiplicative factor arbitrarily close to $1$ from the optimal.Our algorithm is combinatorial and computes the desired components by solving multiple instances of the bipartite maximum weight matching problem.Its complexity grows as a low order polynomial in the ambient dimension of the input data, but exponentially in its rank.However, it can be effectively applied on a low-dimensional sketch of the input data.We evaluate our algorithm on real datasets and empirically demonstrate that in many cases it outperforms existing, deflation-based approaches.
[ PDF] 

Author Information

Megasthenis Asteris (University of Texas at Austin)
Dimitris Papailiopoulos (UC Berkeley)
Anastasios Kyrillidis (University of Texas at Austin)
Alex Dimakis (University of Texas, Austin)

More from the Same Authors