Finding sparse approximations to extreme eigenvectors: generalized power method for sparse PCA and extensions
Finding sparse approximations to extreme eigenvectors: generalized power method for sparse PCA and extensions
复制标题
寻找极端特征向量的稀疏近似：稀疏 PCA 和扩展的广义幂方法
DOI：
--
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
Peter Richtárik
中科院分区：
文献类型：
--
作者：
Peter Richtárik
在本文的第一部分，我们在文献[2]的基础上，提出了一种新的稀疏主成分分析方法(稀疏主成分分析)。我们提出了该问题的四个优化公式，旨在提取一个或多个稀疏优势成分。当初始公式涉及非凸函数时，我们将其重写为涉及紧集上凸函数最大化的优化程序的形式，并提出并分析了求解它的一种简单的梯度法(广义幂方法)。我们在一组随机和基因表达测试问题上的数值演示表明，我们的方法在获得解的质量和速度上都优于现有算法。上述思想的自然推广允许我们构造一种方法，用于同时寻找与对称PSD矩阵的最大和最小特征值相关联的特征向量的联合稀疏逼近。该问题等价于压缩感知问题，即寻找非对称受限等距常数的边界，并增加对稀疏特征向量在同一集合上的支持的新要求。我们证明了该方法迭代过程中出现联合稀疏性的一个结果，并且证明了在非惩罚情况下，迭代过程与用于最小化凸二次函数的柯西最陡下降法的迭代过程的归一化梯度相同[1]。一、设A=[A1，.。。，An]∈Rp×n，其中p n.设λ(Rp.λ)是最大的(分别S的最小)本征值=AA。修复γ>；0。II.稀疏主成分分析的广义幂方法为简单起见，我们集中于寻找稀疏近似z∗到S的特征向量的问题，该特征向量对应于λ。也就是说，我们寻找一个稀疏单位范数向量z∗∈R，使得‖Az∗‖2是大的。考虑以下优化问题：max{‖Az‖2−γ‖z‖1：‖z‖2≤1}。(1)(1)的最优解z∗由z∗=z/‖z‖2，z=Sign(Ai X)[|ai x|−γ]+，i=1，.。。，n，其中x是求解光滑凸极大化问题
In the first part of this work, based on [2], we develop a new approach to sparse principal component analysis (sparse PCA). We propose four optimization formulations of the problem, aimed at extracting one or several sparse dominant components. While the initial formulations involve nonconvex functions, we rewrite them into the form of an optimization program involving maximization of a convex function on a compact set and propose and analyze a simple gradient method for solving it (generalized power method). We demonstrate numerically on a set of random and gene expression test problems that our approach outperforms existing algorithms both in quality of the obtained solution and in speed. A natural extension of the ideas above allows us to construct a method for finding, simultaneously, jointly sparse approximations to the eigenvectors associated with the largest and smallest eigenvalues of a symmetric psd matrix. This problem is equivalent to the Compressed Sensing problem of finding bounds on the asymmetric Restricted Isometry constants with the additional new requirement for the respective sparse eigenvectors to be supported on the same set. We prove a result on the emergence of joint sparsity in the iterates of the method and show that in the non-penalized case, the iterates are identical to the normalized gradients of the iterates of the Cauchy steepest descent method applied to minimizing a convex quadratic function [1]. I. PRELIMINARIES Let A = [a1, . . . , an] ∈ Rp×n, with p n. Let λ (resp. λ) be the largest (resp. smallest) eigenvalue of S = AA. Fix γ > 0. II. GENERALIZED POWER METHOD FOR SPARSE PCA For simplicity, we focus here on the problem of finding a sparse approximation z∗ to the eigenvector of S “corresponding” to λ. That is, we seek a sparse unit-norm vector z∗ ∈ R such that ‖Az∗‖2 is large. Consider the following optimization problem: max{‖Az‖2 − γ‖z‖1 : ‖z‖2 ≤ 1}. (1) It turns out that the optimal solution z∗ of (1) is given by z∗ = z/‖z‖2, z = sign(ai x)[|ai x| − γ]+, i = 1, . . . , n, where x is solves the smooth convex maximization problem