a Direct Formulation For Sparse PCA Using Semidefinite Programming: Difference between revisions
No edit summary |
No edit summary |
||
| Line 3: | Line 3: | ||
==Introduction== | ==Introduction== | ||
Principle Component | [http://en.wikipedia.org/wiki/Principal_component_analysis Principle Component Analysis] is a popular technique which finds a transformation from correlated variables to uncorrelated ones. In sparse [http://en.wikipedia.org/wiki/Principal_component_analysis PCA], the embedded variables are called principle components that are linear combination of the input variables subject to the constraint that the number of non-zero elements in this combination is limited. Sparse PCA decomposition interpretation will be facilitated if the coordinate axes have a physical meaning. It is also helpful in expressing a space of a set of low-dimensional vectors with minimum loss of information. | ||
Semidefinite programs are convex optimization. It optimize a linear function by constraining it to an affine combination of symmetric matrices is positive semidefinite. Semidefinite programs can be solved in polynomial time by interior-point solvers like SEDUMI or SDPT3. Unfortunately it is not viable and practical for high dimensional data sets. | [http://en.wikipedia.org/wiki/Semidefinite_programming Semidefinite programs] are convex optimization. It optimize a linear function by constraining it to an affine combination of symmetric matrices is positive semidefinite. Semidefinite programs can be solved in polynomial time by interior-point solvers like SEDUMI or SDPT3. Unfortunately it is not viable and practical for high dimensional data sets. | ||
The related paper suggests a direct approach for formulation of sparse PCA via semidefinite programming which is convex. Since interior-point solvers cannot handle large data sets, Nesterov’s smoothing technique is used efficiently to help solving large dimensional problems. | The related paper suggests a direct approach for formulation of sparse PCA via semidefinite programming which is convex. Since interior-point solvers cannot handle large data sets, Nesterov’s smoothing technique is used efficiently to help solving large dimensional problems. | ||
| Line 35: | Line 35: | ||
==Algorithm== | ==Algorithm== | ||
=== | ===Smoothing technique=== | ||
===Application o sparse PCA=== | ===Application o sparse PCA=== | ||
| Line 43: | Line 43: | ||
Rewriting the above formulas in semidefinite programming, the following formulas are achived in square and non-square cases: | Rewriting the above formulas in semidefinite programming, the following formulas are achived in square and non-square cases: | ||
maximize <math>x^{T}\textbf{A}x</math> | |||
subject to <math>\|x\|_2=1</math> | |||
<math>textbf</math> | |||
==References== | |||
<references /> | |||
Revision as of 20:15, 9 November 2010
Still under construction
Introduction
Principle Component Analysis is a popular technique which finds a transformation from correlated variables to uncorrelated ones. In sparse PCA, the embedded variables are called principle components that are linear combination of the input variables subject to the constraint that the number of non-zero elements in this combination is limited. Sparse PCA decomposition interpretation will be facilitated if the coordinate axes have a physical meaning. It is also helpful in expressing a space of a set of low-dimensional vectors with minimum loss of information.
Semidefinite programs are convex optimization. It optimize a linear function by constraining it to an affine combination of symmetric matrices is positive semidefinite. Semidefinite programs can be solved in polynomial time by interior-point solvers like SEDUMI or SDPT3. Unfortunately it is not viable and practical for high dimensional data sets.
The related paper suggests a direct approach for formulation of sparse PCA via semidefinite programming which is convex. Since interior-point solvers cannot handle large data sets, Nesterov’s smoothing technique is used efficiently to help solving large dimensional problems.
First order methods require less memory which is an important issue in interior-point solvers. On the other hand their convergence is slower but it is not a major concern in the certain case.
The content of the paper could be summarized as below:
1-Semidefinite relaxation
2-A robustness interpretation
3-Sparse decomposition
4-Algorithm
4-1-A smoothing technique
4-2-Application o sparse PCA
5-Numerical result and application
Semidefinite relaxation
Robustness interpretation
Sparse decomposition
Algorithm
Smoothing technique
Application o sparse PCA
A is assumed to be a symmetric matrix and WLOG, A is a covariance matrix and we are going to maximize the variance of vector x ∈ Rn while it is sparse.
Rewriting the above formulas in semidefinite programming, the following formulas are achived in square and non-square cases:
maximize [math]\displaystyle{ x^{T}\textbf{A}x }[/math]
subject to [math]\displaystyle{ \|x\|_2=1 }[/math] [math]\displaystyle{ textbf }[/math]
References
<references />