A direct formulation for sparse PCA using semidefinite programming
A direct formulation for sparse PCA using semidefinite programming
复制标题
DOI：
10.1137/050645506
复制
发表时间：
2007-09-01
期刊：
影响因子：
10.2
通讯作者：
Lanckriet, Gert R. G.
中科院分区：
文献类型：
--
作者：
d'Aspremont, Alexandre;El Ghaoui, Laurent;Lanckriet, Gert R. G.
给定一个协方差矩阵，我们考虑最大化由输入变量的特定线性组合所解释的方差的问题，同时约束该组合中非零系数的数量。这个问题出现在协方差矩阵分解成稀疏因子或稀疏主成分分析（PCA）中，并且具有从生物学到金融的广泛应用。我们使用修改的对称矩阵的最大特征值的经典变分表示，其中基数是受约束的，并推导出一个半定规划为基础的放松我们的问题。我们还讨论了Nesterov的光滑最小化技术应用于半定程序中产生的稀疏PCA问题的半定松弛。该方法的复杂度为O（n（4）root log（n）/n），其中n是基础协方差矩阵的大小，e是问题最优值的期望绝对精度。
Given a covariance matrix, we consider the problem of maximizing the variance explained by a particular linear combination of the input variables while constraining the number of nonzero coefficients in this combination. This problem arises in the decomposition of a covariance matrix into sparse factors or sparse principal component analysis (PCA), and has wide applications ranging from biology to finance. We use a modification of the classical variational representation of the largest eigenvalue of a symmetric matrix, where cardinality is constrained, and derive a semidefinite programming-based relaxation for our problem. We also discuss Nesterov's smooth minimization technique applied to the semidefinite program arising in the semidefinite relaxation of the sparse PCA problem. The method has complexity O(n(4) root log(n)/epsilon), where n is the size of the underlying covariance matrix and e is the desired absolute accuracy on the optimal value of the problem.