How can one implement PCA using gradient descent? 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.
 A: 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. 
