3
$\begingroup$

I have to implement PCA using gradient descent and stop at convergence. I am not able to find the objective function. I know that

  • the aim of PCA is to reduce the $n$-dimensional matrix to $k$ dimensions (where $k < n$).

  • I need to find $k$ such that the ratio of the average squared projection error to total variance is $\leq 0.01$ (as we need to minimise average squared projection error and maximise the spread of data).

I am confused. Do we need to find $k$ or do we need to find the dimensionally reduced matrix as an output to gradient descent algorithm? Also, I need help with the objective function.

I am stuck since yesterday and am not able to move.

$\endgroup$
  • 1
    $\begingroup$ PCA and „throwing away dimensions“ are only closely related but not the same, i.e. k=n for now. What PCA seeks is the „principal components“ or -just phrased differently- a linear transformation given in form of a matrix A such that $A^t C A$ becomes diagonal (where C is the covariance matrix), i.e. one obvious loss function would be to use the sum of square deviations of the off-diagonal terms of $A^t C A$ (because we want to make them zero!). $\endgroup$ – Fabian Werner Sep 15 '19 at 13:45
  • 6
    $\begingroup$ Why can’t you just calculate the covariance matrix and then find its eigenvalues and eigenvectors? Who asked you to do this with an objective function? $\endgroup$ – Dave Sep 15 '19 at 14:04
  • $\begingroup$ I have already implemented this with the standard method of finding Eigen values and Eigen vectors in my previous homework. This is a part of my new homework. $\endgroup$ – Shirley Sam Sep 15 '19 at 16:38
  • 1
    $\begingroup$ This is an unusual way to look at PCA. Please give more context to the question. $\endgroup$ – Dave Sep 15 '19 at 17:52
  • 1
    $\begingroup$ Yes, it is possible. If anything it is also widely used when doing some more specialised PCA variant. E.g. the standard Sparse PCA by Zou et al. reformulates SPCA as a ridge/elastic-net regression problem. In fairness most solution follow an alternating minimization approach because it is easy to ensure orthgonality that way but aside that, yeah, doable. Fun problem, +1! $\endgroup$ – usεr11852 Sep 15 '19 at 20:54
3
$\begingroup$

We can pose PCA as a variance maximization problem. These are some of the hints:

The objective is to find the directions in which the variance, $\Bbb E(\vec X \vec X^T)$, is maximum.

Let $\vec w$ denote the unit vector direction along which the variance is maximum. The variance along this direction is given by:

\begin{aligned} \sigma_{\vec{\omega}^{2}}^{2} &=\frac{1}{n} \sum_{i}(\overrightarrow{x_{i}} \cdot \vec{w})^{2} \\ &=\frac{1}{n}(\mathbf{x} \mathbf{w})^{T}(\mathbf{x} \mathbf{w}) \\ &=\frac{1}{n} \mathbf{w}^{T} \mathbf{x}^{T} \mathbf{x} \mathbf{w} \\ &=\mathbf{w}^{T} \frac{\mathbf{x}^{T} \mathbf{x}}{n} \mathbf{w} \\ &=\mathbf{w}^{T} \mathbf{v} \mathbf{w} \end{aligned}

We can take gradients wrt to $\vec w$ and set it zero to find the optimum values.

$$ \begin{aligned} \mathscr{L}(\mathbf{w}, \lambda) & \equiv \sigma_{\mathrm{w}}^{2}-\lambda\left(\mathbf{w}^{T} \mathbf{w}-1\right) \\ \frac{\partial L}{\partial \lambda} &=\mathbf{w}^{T} \mathbf{w}-1 \\ \frac{\partial L}{\partial \mathbf{w}} &=2 \mathbf{v} \mathbf{w}-2 \lambda \mathbf{w} \end{aligned} $$

Here $\mathscr{L}$ is the modified objective with Lagrange multipliers (they are required to ensure $\vec w$ is a unit vector)

Setting the derivatives to zero, gives you an eigenvalue problem!

If one wants to solve it using Gradient Descent, because we have obtained the gradients here, we can solve minimizing $\mathscr{L}$ using gradient descent as well.

Update: The above problem is concave: Hessian is $$ \begin{bmatrix} 0 & -2 \bf{w}^T \\ -2 \bf{w} & 2 \bf{v} - 2 \lambda \Bbb I \end{bmatrix} $$

The determinant of this Hessian can be computed as $$ {\rm det}\left|\begin{matrix} A & B \\ C & D \end{matrix}\right| = {\rm det}|D|\,{\rm det} \left|A - BD^{-1} C\right| $$

The determinant is -ve as the expression $$- {\rm det}(2 \bf{v} - 2 \lambda \Bbb I) {\rm det} (2 \bf{w}^T (2 \bf{v} - 2 \lambda \Bbb I)^{-1} 2 \bf{w} ) $$ is always negative. Therefore, it will converge to a maxima.

$\endgroup$
  • $\begingroup$ What about convexity? $\endgroup$ – Rodrigo de Azevedo Sep 16 '19 at 6:42
  • $\begingroup$ @RodrigodeAzevedo The $L_2$ norm is convex - therefore, $ \bf{w}^T \bf{w}$ is convex in $\bf{w}$. Using similar logic, it can be shown that $\bf{w}^T \bf{v} \bf{w}$ is convex. Let me know if I am missing something. $\endgroup$ – honeybadger Sep 16 '19 at 10:04
  • $\begingroup$ @RodrigodeAzevedo The function is concave (updated the calculations). Therefore, our approach will converge to maxima. $\endgroup$ – honeybadger Sep 16 '19 at 11:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.