Alternating maximization: unifying framework for 8 sparse PCA formulations and efficient parallel codes
Peter Richtárik Majid Jahani Selin Damla Ahipaşaoğlu Martin Takáč
Abstract
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: we employ two norms for measuring variance (L2, L1) and two sparsity-inducing norms (L0, L1), which are used in two 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 the alternating maximization (AM) method. We show that AM is equivalent to GPower for all 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
中文速览
多变量数据中，稀疏主成分分析（Sparse PCA）希望在解释尽量多数据方差的同时，让载荷向量只有少数几个非零元素，从而提升可解释性——但现有研究对各类优化模型的统一处理和高效实现都还不够完善。这篇论文系统地整理了8种稀疏主成分分析的优化形式（组合了L2/L1方差度量、L0/L1稀疏约束或惩罚两两搭配），其中3种（尤其是L0约束加L1方差的形式）此前从未被研究过，并提出了一种统一的交替最大化（Alternating Maximization, AM）算法来求解所有这8种问题，同时从理论上证明该算法与已有的GPower方法等价。在工程实现层面，作者为8种模型分别在多核CPU、GPU和计算机集群三种硬件架构上提供了共24套并行开源代码，GPU实现比高效的单核C++代码快约100倍，集群版本可以在一分钟内处理357 GB的超大规模数据集。这项工作既在理论上统一了一类重要的稀疏PCA方法，又提供了可直接用于大规模实际场景的高性能计算工具，对机器学习、基因组学、金融等需要处理海量高维数据的领域具有重要价值。
原文 arXiv:1212.4137;中英对照 + 大白话阅读 https://aha.fim.ai/paper/1212.4137v2