Difference between revisions of "optimal Solutions forSparse Principal Component Analysis"
(→Conclusion) 
m (Conversion script moved page Optimal Solutions forSparse Principal Component Analysis to optimal Solutions forSparse Principal Component Analysis: Converting page titles to lowercase) 
(No difference)

Latest revision as of 09:45, 30 August 2017
Contents
Introduction
Principal component analysis (PCA) is a method for finding linear combinations of features, called principal components, that correspond to the directions of maximum variance in the data, which are orthogonal to one another. In practice, performing PCA on a data set involves applying the singular value decomposition to the data matrix.
PCA facilitates the interpretation of the data if the components are linear combinations of only a few latent variables, and not many or all of the original ones. This is particularly true in many applications in which the coordinate axes that correspond to the factors have a direct physical interpretation; for instance, in financial or biological applications, each axis might correspond to a specific asset or to a specific gene. Constraining the number of nonzero factor coefficients (loadings) in sparse principal components to a very low number relative to the total number of coefficients whilst having these sparse vectors explain a maximum amount of variance in the data is known as sparse PCA. In other words, sparse PCA is an extension of PCA method that attempts to maintain a tradeoff between statistical fidelity and interpretability by computing principal components that can be represented using the least number of coefficients (in linear combination) while preserving as much data variation as possible. Sparse PCA has many applications in biology, finance and many machine learning problems. Sparse principal components, like principal components, are vectors that span a lowerdimensional space that explain most of variance in the original data. However, in order to find the sparse principal components using sparse PCA, it is necessary to make some sacrifices:
 There is a reduction in the explained variance in the original data captured by the sparse principal components as compared to PCA.
 There is a reduction in the orthogonality (independence or correlation) between the resulting variables (sparse principal components) as compared to PCA.
In this paper we are going to focus on the problem of sparse PCA which can be written as:
[math]\textrm{subject} \; \textrm{to} \; \x\_2 \le 1[/math]
where:
 [math]x\in \mathbb{R}^n[/math]
 [math]\Sigma \in S_n[/math] is the symmetric positive semidefinite sample covariance matrix
 [math]\,\rho[/math] is the parameter which controls the sparsity
 [math]\textbf{Card}(x)[/math] expresses the cardinality ([math]\,l_0[/math] norm) of [math]\,x[/math].
Note that while solving the standard PCA problem is not complicated (since, for each factor, one simply needs to find a leading eigenvector, and this can be done in [math]\,O(n^2)[/math] time), solving sparse PCA is NP hard (since sparse PCA is a particular case of the sparse generalized eigenvalue problem).
The paper begins by formulating the sparse PCA (SPCA) problem, whose algorithm is based on the representation of PCA as a regressiontype optimization problem (Zou et al., 2006) that allows the application of the LASSO (Tibshirani, 1996) (which is a penalization technique based on the [math]\,l_1[/math] norm). The [math]l_0[/math] goal of the cardinality and the [math]l_1[/math] solution using LASSO are actually fundamentally related. The conditions for guaranteeing sparse variable selection or recovery using the [math]l_1[/math] norm for solving [math]l_0[/math] problems are based on the restricted isometry property. This connection was established recently by Candes and Tao<ref name="candes2005">E. J. Candes and T. Tao. Decoding by linear programming. IEEE Transactions on Information Theory. 51(12):42034215, 2005.</ref> and Donoho and Tanner<ref name="donoho2005">D. L. Donoho and J. Tanner. Sparse nonnegative solutions of underdetermined linear equations by linear programming. Proceedings of the National Academy of Sciences, 102(27):94469451, 2005.</ref>, among others. Interestingly, it also serves as the basis for compressed sensing, another topic we have seen in this course (see here and here).
The main part of this paper then derives an approximate greedy algorithm for computing an approximate full set of good solutions with total complexity [math]\,O(n^3)[/math]. It also formulates a convex relaxation for sparse PCA and uses it to derive tractable sufficient conditions for a vector [math]\,x[/math] to be a global optimum of the above optimization problem. In the general approach to SPCA described in this paper, for a given vector [math]\,x[/math] having support [math]\,I[/math], [math]\,x[/math] can be tested to see if it is a globally optimal solution to the above optimization problem simply by performing a few steps of binary search to solve a onedimensional convex minimization problem.
Notation
 For a vector [math]\,x \in\mathbb{R}^n[/math], [math]\x\_1=\sum_{i=1}^n x_i[/math] and [math] \textbf{Card}(x)[/math] is the cardinality of [math]\,x[/math] (the number of nonzero coefficients of [math]\,x[/math]).
 The support [math]\,I[/math] of [math]\,x[/math] is the set [math]\{i: x_i \neq 0\}[/math] and [math]\,I^c[/math] denotes its complement.
 [math]\,\beta_{+} = \max\{\beta , 0\}[/math].
 For a symmetric [math]n \times n [/math] matrix [math]\,X[/math] with eigenvalues [math]\,\lambda_i[/math], [math]\operatorname{Tr}(X)_{+}=\sum_{i=1}^{n}\max\{\lambda_i,0\}[/math].
 The vector of all ones is written [math]\textbf{1}[/math], and the identity matrix is written [math]\,\textbf{I}[/math]. The diagonal matrix with the vector [math]\,u[/math] on the diagonal is written [math]\textbf{diag}(u)[/math].
 For [math]\Sigma \, [/math], a symmetric [math]n \times n [/math] matrix, we can define [math]\phi(\rho) = \max_{\x\ \leq 1} x^T \Sigma x  \rho \textbf{Card}(x)[/math].
Sparse PCA
The sparse PCA problem can be written as:
[math]\textrm{subject} \; \textrm{to} \; \x\_2=1.[/math]
Since [math]\,\Sigma \in S_{n}[/math], [math]\,\Sigma[/math] has a square root. Let [math]\,A \in R^{n \times n}[/math] denote the square root of [math]\,\Sigma[/math] where [math]\,\Sigma = A^TA[/math].
The above problem is directly related to the following problem which involves finding a cardinalityconstrained maximum eigenvalue:
[math]\textrm{subject} \; \textrm{to} \; \x\_2=1,\,\,\,\,\,\,\,\,\,\,\,\,\,(1)[/math]
[math]\textbf{Card}(x)\leq k,[/math]in the variable [math]\,x \in R^n[/math]. Suppose the features of [math]\,\Sigma[/math] are ordered in decreasing size of variance, i.e. [math]\Sigma_{11} \geq \dots \geq \Sigma_{nn}[/math].
Using duality, we can bound the solution of [math]\,(1)[/math] by:
where [math]\,P[/math] is the set of penalty values for which [math]\,\phi(\rho)[/math] has been computed. This tells us that if we prove [math]\,x[/math] is optimal for [math]\,\phi(\rho)[/math] then [math]\,x[/math] is the global optimum for [math]\,(1)[/math], with the cardinality of [math]\,x[/math] being exactly [math]\,k[/math].
For the remainder of the paper, the authors assume [math]\rho \leq \Sigma_{11}[/math]. To see why this is the case, we will assume for the moment that [math]\rho \geq \Sigma_{11}[/math]. Then, since [math]x^T \Sigma x\leq \Sigma_{11}(\sum_{i=1}^nx_i)^2[/math] and [math](\sum_{i=1}^nx_i)^2 \leq \x\^2\textbf{Card}(x) \; \forall x \in R^n[/math] we get the following:
[math]\leq (\Sigma_{11}\rho)\textbf{Card}(x)[/math]
This implies that the optimal solution to the SPCA problem is simply [math]\,x = 0[/math]. Thus, we assume [math]\,\rho \leq \Sigma_{11}[/math] and in this case the inequality [math]\,\x\ \le 1[/math] is tight.
Using the fact that the sparsity pattern of a vector [math]\,x[/math] can be represented by a vector [math]\,u \in \{0, 1\}^n[/math], the fact that [math]\,\textbf{diag}(u)^2 = \textbf{diag}(u)[/math] for all variables [math]\,u \in \{0, 1\}^n[/math], and the fact that for any matrix [math]\,B[/math], [math]\,\lambda_{max}(B^TB) = \lambda_{max}(BB^T)[/math], the SPCA problem can be reexpressed as:
[math]\,\phi(\rho) \; = \max_{u \in \{0,1\}^n} \; \lambda_{max}(\textbf{diag}(u) \; \Sigma \; \textbf{diag}(u))  \rho\textbf{1}^Tu[/math]
 [math]= \max_{u \in \{0,1\}^n} \; \lambda_{max}(\textbf{diag}(u) \; A^TA \; \textbf{diag}(u))  \rho\textbf{1}^Tu[/math]
 [math]= \max_{u \in \{0,1\}^n} \; \lambda_{max}(A \; \textbf{diag}(u) \; A^T)  \rho\textbf{1}^Tu[/math]
 [math]= \max_{ \x\ = 1} \; \max_{u \in \{0,1\}^n} x^T A \; \textbf{diag}(u) \; A^T x  \rho\textbf{1}^Tu[/math]
 [math]= \max_{ \x\ = 1} \; \max_{u \in \{0,1\}^n} \sum_{i=1}^n u_i((a_i^T x)^2  \rho) [/math].
Then, if we maximize in [math]\,u[/math] and use the fact that [math]\,max_{v \in \{0,1\}} \beta v = \beta_+[/math], the SPCA problem, in the case where [math]\,\rho \le \Sigma_{11}[/math], becomes:
Here, the [math]\,a_i[/math]'s are the columns of the matrix [math]\,A[/math] where [math]\,A^T A = \Sigma[/math] (i.e. [math]\,A[/math] is the square root of [math]\,\Sigma[/math]).
For more details refer to <ref name= "afl" > Alexandre d'Aspremont, Francis Bach, and Laurent El Ghaoui. Optimal Solutions for Sparse Principal Component Analysis. J. Mach. Learn. Res. 9 (June 2008), 12691294. </ref>.
Greedy Solution
Before presenting their approximate greedy search algorithm for solving the SPCA problem, the authors first presented the full greedy search algorithm which follows directly from Moghaddam et al. <ref name="M2006a">B. Moghaddam, Y. Weiss, and S. Avidan. Spectral bounds for sparse PCA: Exact and greedy algorithms. Advances in Neural Information Processing Systems, 18, 2006.</ref>. This algorithm starts from an initial solution (having cardinality one) at [math]\,\rho = \Sigma_{11}[/math], and then it updates an increasing sequence of index sets [math]\,I_k \subseteq [1, n][/math] by scanning all the remaining variables to find the index that gives the maximum contribution in terms of variance.
The following pseudocode (taken from <ref name = "afl"/>) summarizes this full greedy search algorithm:
At every step, [math]\,I_k[/math] represents the set of nonzero elements, or the sparsity pattern, of the current point. Given [math]\,I_k[/math], the solution to the SPCA problem can be defined as [math]\,x_k = \underset{\{x_{I_k^c} = 0, \x\ = 1\}}{\operatorname{argmax}} x^T \Sigma x  \rho k[/math], i.e. [math]\,x_k[/math] is formed simply by padding zeros to the leading eigenvector of the submatrix [math]\,\Sigma_{I_k,I_k}[/math].
Since estimating [math]\,nk[/math] eigenvalues at each iteration is costly, we can use the fact that [math]\,uu^T[/math] is a subgradient of [math]\,\lambda_{max}[/math] at [math]\,X[/math] if [math]\,u[/math] is a leading eigenvector of [math]\,X[/math] to get [math]\lambda_{max}(\sum_{j\in I_k\cup \{i\}}a_ja_j^T)\geq \lambda_{max}(\sum_{j\in I_k}a_ja_j^T)+(x_k^Ta_i)^2[/math] Proof.
With this, the authors have a lower bound on the objective which does not require finding [math]\,n  k[/math] eigenvalues at each iteration.
The authors then derive the following algorithm for solving the SPCA problem:
Approximate Greedy Search Algorithm
Input: [math]\Sigma \in \textbf{R}^{n\times n}[/math]
Algorithm:
1.Preprocessing: sort variables decreasingly diagonal elements and permute elements of [math]\Sigma[/math] accordingly. Compute Cholesky decomposition [math]\,\Sigma =A^TA[/math].
2.Initialization:[math]I_1=\{\}, x_1=a_1/\a_1\[/math]
3.Compute [math]i_k= {\arg\max}_{i\notin I_k}(x_k^Ta_i)^2[/math]
4.Set [math]I_{k+1}=I_k\cup\{i_k\}[/math] and compute [math]\,x_{k+1}[/math] as the leading eigenvector of [math]\sum_{j\in I_{k+1}}a_j a_j^T[/math]
5.Set [math]\,k=k+1[/math] if [math]\,k\lt n[/math] go back to step 3.
Output: sparsity patterns [math]\,I_k[/math]
As in the full greedy search algorithm, at every step, [math]\,I_k[/math] represents the set of nonzero elements, or the sparsity pattern, of the current point and, given [math]\,I_k[/math], the solution to the SPCA problem can be defined as [math]\,x_k =
\underset{\{x_{I_k^c} = 0, \x\ = 1\}}{\operatorname{argmax}} x^T \Sigma x  \rho k[/math], i.e. we form [math]\,x_k[/math] simply by padding zeros to the leading eigenvector of the submatrix [math]\,\Sigma_{I_k,I_k}[/math].
Computational Complexity
The full greedy search algorithm for solving the SPCA problem has a complexity of [math]\,O(n^4)[/math] because, at each step [math]\,k[/math], it computes [math]\,nk[/math] maximum eigenvalues of matrices having size [math]\,k[/math]. On the other hand, the authors' approximate greedy search algorithm for solving the SPCA problem has a complexity of [math]\,O(n^3)[/math]. This is because the first Cholesky decomposition has a complexity of [math]\,O(n^3)[/math] and, in the [math]\,k[/math]th iteration, there is a complexity of [math]\,O(k^2)[/math] for the maximum eigenvalue problem and a complexity of [math]\,O(n^2)[/math] for finding all products [math]\,x^T a_j[/math].
Convex Relaxation
As mentioned above, the sparse PCA problem can be written as:
Because the variable [math]\,x[/math] only appears through [math]\,X = xx^T[/math], the above form of the SPCA problem can be reformulated in terms of only [math]\,X[/math] by using the fact that, when [math]\,\x\ = 1[/math], [math]\,X = xx^T[/math] is equivalent to [math]\,\textbf{Tr}(X) = 1[/math], [math]\,X \ge 0[/math] and [math]\,\textbf{Rank}(X) = 1[/math].
Thus, the authors obtained the following form of the SPCA problem:
As the goal of the above form of the SPCA problem is to maximize a convex function over the convex set (http://en.wikipedia.org/wiki/Spectrahedron spectahedron]) [math]\,\Delta_n=\{X\in S_n : \textbf{Tr}(X)=1, X\geq 0\}[/math], the solution must be an extreme point of [math]\,\Delta_n[/math] and is therefore a rankone matrix. Unfortunately, this form of the SPCA problem is convex in [math]\,X[/math] and not concave, so the problem is still hard to solve. However, it is shown in <ref name="afl"/> that, on rankone elements of [math]\,\Delta_n[/math], this form of the SPCA problem is equal to a concave function of [math]X[/math]. Using this fact, the authors produced a convex relaxation of this form of the SPCA problem.
The proposition is given below and the proof is provided in the authors' paper listed in Reference.
Proposition 1 Let [math]A\in{R}^{n\times n}, \rho \geq0[/math] and denotes by [math]a_1,...,a_n\in R^n[/math] the columns of [math]A[/math], an upper bound on:
can be computed by solving
in the variable [math]X\in S_n[/math], where [math]B_i=a_ia_i^T\rho I[/math] or also:
, which is a semidefinite program in the variables [math]X\in S_n, P_i\in S_n[/math].
It is always true that [math]\,\psi(\rho) \ge \phi(\rho)[/math], and, when the solution to the above semidefinite program has rank one, we have that [math]\,\psi(\rho) = \phi(\rho)[/math] and the convex relaxation ( which is [math]\psi(\rho)=\max\sum_{i=1}^n(\textbf{Tr}(P_iB_i)_{+} \;\; s.t. \; \textbf{Tr}(X)=1, X\geq 0, X\geq P_i \geq 0[/math] ) is tight.
Optimality Conditions
In this section, the optimality conditions considered by the authors are briefly discussed.
Dual problem and optimality conditions
The authors first derived the dual problem to the convex relaxation of SPCA ( which is [math]\psi(\rho)=\max\sum_{i=1}^n(\textbf{Tr}(P_iB_i)_{+} \;\; s.t. \; \textbf{Tr}(X)=1, X\geq 0, X\geq P_i \geq 0[/math] ) as well as the associated KarushKuhnTucker (KKT) optimality conditions. They began by presenting the following lemma (taken from the authors' paper listed in References and whose proof is also given in that paper):
Optimality conditions for rank one solutions
The authors then derived the KKT conditions for the convex relaxation of SPCA for the particular case in which we have a rank one candidate solution [math]\,X = xx^T[/math] and we need to test our candidate solution's optimality. The following lemma (taken from the authors' paper listed in References and whose proof is also given in that paper) then provides an important connection between the convex relaxation of SPCA and the original nonconvex form of the SPCA problem (which is [math] \;\phi(\rho) \;\; \textrm{subject} \; \textrm{to} \; \x\_2=1[/math]):
Based on the necessary and sufficient optimality conditions for the convex relaxation of SPCA as given in lemma 2, lemma 3 gives that, for any candidate vector [math]\,x[/math], we can test the optimality of [math]\,X = xx^T[/math] for the convex relaxation of SPCA by solving a semidefinite feasibility problem in the variables [math]\,Y_i \in S_n[/math], and that, if the rank one candidate solution [math]X = xx^T[/math] is optimal for the convex relaxation of SPCA, then [math]\,x[/math] is globally optimal for the original nonconvex combinatorial form of SPCA ( which is [math] \;\phi(\rho) \;\; \textrm{subject} \; \textrm{to} \; \x\_2=1[/math] ).
Solution improvements and randomization
If the conditions are not met, then the rank of the convex relaxation of SPCA's optimal solution would be strictly greater than one, and hence the convex relaxation of SPCA would not be tight. If this is the case, then a different relaxation such as DSPCA by d’Aspremont et al. (2007b) (more details regarding it is available in d’Aspremont et al.'s paper) may be used to try to get a better solution for SPCA. Furthermore, following BenTal and Nemirovski (2002), randomization techniques may also be applied to improve the quality of the convex relaxation of SPCA's solution.
Application
In this section we mention the application of sparse PCA to subset selection. One of the other application is compressed sensing which you can see more detail about it on the main paper:
Subset selection
we consider [math]\,p[/math] datapoints in [math]\,R^n[/math] in a data matrix [math]X \in R^{p\times n}[/math]. We are given real numbers [math] y \in R^p[/math] to predict from [math]\,X[/math] using linear regression, estimated by least squares. In subset selection problem we are looking for sparse coefficients [math]\,w[/math], i.e a vector [math]\,w[/math] with many zeros in its entries. We thus consider the problem:
Using sparsity pattern [math]u\in \{0,1\}[/math] and optimizing with respect to [math]\,w[/math] and rewriting the formula using generalized eigenvalue we thus have:
The simple bound on the optimal value of the subset selection problem has the following form:
where [math]B\geq0[/math], and thus we have:
[math]\y\^2s_0\geq(k)\geq\y\^2s_0B(\min_{v\in\{0,1\}^n,1^Tv=k}\lambda_{min}(X(v)^TX(v)))^{1} \geq\y\^2s_0B(\lambda_{min}(X^TX))^{1}[/math]
This bound gives a sufficient condition for optimality in subset selection, for any problem instances and any given subset.
Conclusion
This paper presented a novel formulation of sparse PCA (SPCA) problem based on a semidefinite relaxation scheme. Using this formulation, a greedy algorithm was developed to compute a full set of good solutions to the SPCA problem. The algorithm was shown to be efficient. i.e. have complexity of [math] O(n^3)[/math], and provide candidate solutions, many of which turn out to be optimal in practice. Furthermore, the sufficient conditions for global optimality of candidate solutions were derived <ref name="afl"/>. Finally, the resulting upper bound was shown to have direct application to problems such as sparse recovery and subset selection.
References
<references />