Alternating Direction Method of Multipliers for Sparse Principal Component Analysis

作     者：Shiqian Ma 

作者机构：Department of Systems Engineering and Engineering ManagementThe Chinese University of Hong KongShatinNTHong Kong 

出 版 物：《Journal of the Operations Research Society of China》 (中国运筹学会会刊（英文）)

年 卷 期：2013年第1卷第2期

页      面：253-274页

核心收录：

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 07[理学] 070105[理学-运筹学与控制论] 0701[理学-数学] 

主　　题：Sparse PCA Semidefinite programming Alternating direction method Augmented L agrangian method Deflation Projection onto the simplex 

摘      要：We consider a convex relaxation of sparse principal component analysisproposed by d Aspremont et al. (SIAM Rev. 49:434 448, 2007). This convex relax-ation is a nonsmooth semidefinite programming problem in which the ξ1 norm of thedesired matrix is imposed in either the objective function or the constraint to improvethe sparsity of the resulting matrix. The sparse principal component is obtained by arank- one decomposition of the resulting sparse matrix. We propose an alternating di-rection method based on a variable-splitting technique and an augmented I agrangianframework for solving this nonsmooth semidefinite programming problem. In con-trast to the first-order method proposed in d Aspremont et al. (SIAM Rev. 49:434448, 2007), which solves approximately the dual problem of the original semidefiniteprogramming problem, our method deals with the primal problem directly and solvesit exactly, which guarantees that the resulting matrix is a sparse matrix. A globalconvergence result is established for the proposed method. Numerical results on bothsynthetic problems and the real applications from classification of text data and senatevoting data are reported to demonstrate the efficacy of our method.