7
$\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$
7
  • 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$ Sep 15, 2019 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, 2019 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$ Sep 15, 2019 at 16:38
  • 2
    $\begingroup$ This is an unusual way to look at PCA. Please give more context to the question. $\endgroup$
    – Dave
    Sep 15, 2019 at 17:52
  • 3
    $\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, 2019 at 20:54

1 Answer 1

9
$\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$
4
  • $\begingroup$ What about convexity? $\endgroup$ Sep 16, 2019 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$ Sep 16, 2019 at 10:04
  • 1
    $\begingroup$ @RodrigodeAzevedo The function is concave (updated the calculations). Therefore, our approach will converge to maxima. $\endgroup$ Sep 16, 2019 at 11:29
  • $\begingroup$ @honeybadger 's answer is wrong. Because a positive determinant doesn't guarantee semi positive definite. $\endgroup$
    – Xiangpeng
    Aug 27, 2021 at 4:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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