8674

Alternating Maximization: Unifying Framework for 8 Sparse PCA Formulations and Efficient Parallel Codes

Peter Richtarik, Martin Takac, Selin Damla Ahipasaoglu
School of Mathematics, University of Edinburgh, Edinburgh, EH93JZ, United Kingdom
arXiv:1212.4137 [stat.ML] (17 Dec 2012)

@article{2012arXiv1212.4137R,

   author={Richt{‘a}rik}, P. and {Tak{‘a}{v c}}, M. and {Damla Ahipa{c s}ao{u g}lu}, S.},

   title={"{Alternating Maximization: Unifying Framework for 8 Sparse PCA Formulations and Efficient Parallel Codes}"},

   journal={ArXiv e-prints},

   archivePrefix={"arXiv"},

   eprint={1212.4137},

   primaryClass={"stat.ML"},

   keywords={Statistics – Machine Learning, Computer Science – Learning, Mathematics – Optimization and Control},

   year={2012},

   month={dec},

   adsurl={http://adsabs.harvard.edu/abs/2012arXiv1212.4137R},

   adsnote={Provided by the SAO/NASA Astrophysics Data System}

}

Download Download (PDF)   View View   Source Source   Source codes Source codes

Package:

1912

views

Given a multivariate data set, sparse principal component analysis (SPCA) aims to extract several linear combinations of the variables that together explain the variance in the data as much as possible, while controlling the number of nonzero loadings in these combinations. In this paper we consider 8 different optimization formulations for computing a single sparse loading vector; these are obtained by combining the following factors: we employ two norms for measuring variance (L2, L1) and two sparsity-inducing norms (L0, L1), which are used in two different ways (constraint, penalty). Three of our formulations, notably the one with L0 constraint and L1 variance, have not been considered in the literature. We give a unifying reformulation which we propose to solve via a natural alternating maximization (AM) method. We show the the AM method is nontrivially equivalent to GPower (Journ'{e}e et al; JMLR 11:517–553, 2010) for all our formulations. Besides this, we provide 24 efficient parallel SPCA implementations: 3 codes (multi-core, GPU and cluster) for each of the 8 problems. Parallelism in the methods is aimed at i) speeding up computations (our GPU code can be 100 times faster than an efficient serial code written in C++), ii) obtaining solutions explaining more variance and iii) dealing with big data problems (our cluster code is able to solve a 357 GB problem in about a minute).
Rating: 2.5/5. From 3 votes.
Please wait...

* * *

* * *

HGPU group © 2010-2024 hgpu.org

All rights belong to the respective authors

Contact us: