---
abstract: '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 *disjoint* supports that jointly capture the maximum possible variance. These components can be computed one by one, repeatedly solving the single-component problem and deflating the input data matrix, but as we show 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 matrix, but exponentially in its rank. However, it can be effectively applied on a low-dimensional sketch of the data; this allows us to obtain polynomial-time approximation guarantees via spectral bounds. We evaluate our algorithm on real data-sets and empirically demonstrate that in many cases it outperforms existing, deflation-based approaches.'
author:
- |
    Megasthenis Asteris$^{\alpha}$, Dimitris Papailiopoulos$^{\beta}$, Anastasios Kyrillidis$^{\alpha}$ Alexandros G. Dimakis$^{\alpha}$\
    $^{\alpha}$UT Austin, $^{\beta}$UC Berkeley
bibliography:
- 'spcamulti.bib'
date: August 2015
title: Sparse PCA via Bipartite Matchings
---

Acknowledgments {#acknowledgments .unnumbered}
===============

DP is generously supported by NSF awards CCF-1217058 and CCF-1116404 and MURI AFOSR grant 556016. This research has been supported by NSF Grants CCF 1344179, 1344364, 1407278, 1422549 and ARO YIP W911NF-14-1-0258.
