# Difference between revisions of "large-Scale Supervised Sparse Principal Component Analysis"

(Created page with "== 1. Introduction == The drawbacks of most existing technique: '''1 Drawbacks of Existing techniques''' Existing techniques include ad-hoc methods(e.g. factor rotation techn...") |
(→1. Introduction) |
||

Line 11: | Line 11: | ||

'''2 Contribution of this paper''' | '''2 Contribution of this paper''' | ||

− | This paper solves DSPCA in a computationally easier way, and hence it is a good solution for large scale data sets. This paper applies a block coordinate ascent algorithm with computational complexity | + | This paper solves DSPCA in a computationally easier way, and hence it is a good solution for large scale data sets. This paper applies a block coordinate ascent algorithm with computational complexity <math>O(\hat{n^3})</math>, where <math>\hat{n}</math> is the intrinsic dimension of the data. Since <math>\hat{n}</math> could be very small compared to the dimension <math>n</math> of the data, this algorithm is computationally easy. |

+ | |||

+ | == 2. Primal problem == | ||

+ | |||

+ | The sparse PCA problem can be formulated as <math>max_x \ x^T \Sigma x - \lambda \| x \|_0 : \| x \|_2=1</math>. | ||

+ | |||

+ | This is equivalent to <math>max_z</math> '''Tr'''<math>\Sigma Z - \lambda \sqrt{\| Z \|_0} : Z \succeq 0</math>, Tr <math>Z=1</math>, Rank<math>(Z)=1</math>. | ||

+ | |||

+ | Replacing the <math>\sqrt{\| Z \|_0}</math> with <math>\| Z \|_1</math> and dropping the rank constraint gives a relaxation of the original non-convex problem: | ||

+ | |||

+ | <math>max_z</math> '''Tr'''<math>\Sigma Z - \lambda \| Z \|_1 : Z \succeq 0</math>, Tr <math>Z=1</math>. | ||

+ | |||

+ | Fortunately, this relaxation approximates the original non-convex problem to a convex problem. |

## Revision as of 21:53, 4 August 2013

## 1. Introduction

The drawbacks of most existing technique:

**1 Drawbacks of Existing techniques**

Existing techniques include ad-hoc methods(e.g. factor rotation techniques, simple thresholding), greedy algorithms, SCoTLASS, the regularized SVD method, SPCA, the generalized power method. These methods are based on non-convex optimization and they don't guarantee global optimum.

A semi-definite relaxation method called DSPCA can guarantee global convergence and has better performance than above algorithms, however, it is computationally expensive.

**2 Contribution of this paper**

This paper solves DSPCA in a computationally easier way, and hence it is a good solution for large scale data sets. This paper applies a block coordinate ascent algorithm with computational complexity [math]O(\hat{n^3})[/math], where [math]\hat{n}[/math] is the intrinsic dimension of the data. Since [math]\hat{n}[/math] could be very small compared to the dimension [math]n[/math] of the data, this algorithm is computationally easy.

## 2. Primal problem

The sparse PCA problem can be formulated as [math]max_x \ x^T \Sigma x - \lambda \| x \|_0 : \| x \|_2=1[/math].

This is equivalent to [math]max_z[/math] **Tr**[math]\Sigma Z - \lambda \sqrt{\| Z \|_0} : Z \succeq 0[/math], Tr [math]Z=1[/math], Rank[math](Z)=1[/math].

Replacing the [math]\sqrt{\| Z \|_0}[/math] with [math]\| Z \|_1[/math] and dropping the rank constraint gives a relaxation of the original non-convex problem:

[math]max_z[/math] **Tr**[math]\Sigma Z - \lambda \| Z \|_1 : Z \succeq 0[/math], Tr [math]Z=1[/math].

Fortunately, this relaxation approximates the original non-convex problem to a convex problem.