1
$\begingroup$

Does anyone know how to justify the red and blue line in the attached proof of PCA?

Red line: $B \in \mathbb{R}^{ d \times n}$, arrange $B = [B_{j,1} | B_{j,2} | \cdots | B_{j,n}]$, then $B^\top B = \sum_{j = 1}^d \sum_{i = 1}^n B_{j,i}^2$. Since the columns are orthonormal, therefore $\sum_{i = 1}^n B_{j,i}^2 = 1$, hence $B^\top B = \sum_{j = 1}^d 1 = d$ not equal to $n$ as claimed.

Blue line: I do not see where the equality comes from. Why is it that for every orthogonal matrix $U \in \mathbb{R}^{ d\times n}$ you have an inequality on the trace, but as soon as you have that all columns of $U$ are the leading eigenvector of $A = X^\top X$, you obtain an equality?

See below for the relevant parts of the proof

enter image description here

$\endgroup$
2
  • $\begingroup$ For the red lines, this is an application of orthonormal. For the blue lines, you just combine the fact that the $U$ are orthonormal with the definition of the trace. $\endgroup$ – Sycorax Sep 25 '20 at 22:02
  • $\begingroup$ @Sycorax Hi, I'm still not sure about the red line as I did apply orthogonality, and the sum doesn't feel correct to me, and for the blue line, I can apply that $U^\top A U$ has the same eigenvalue as $A$, and trace is the sum of eigenvalues. However, $U$ does not necessarily have to be the n leading eigenvector of $A$, in fact any orthogonal matrix $U$ suffices for $U^\top AU$ to be a similarity transformation, so why is it not held with equality for any $U$ with orthonormal column? $\endgroup$ – Eldacar Hyarmendacil Sep 26 '20 at 0:05
2
$\begingroup$

The red line is correct. $B \in \mathbb{R}^{d \times n}$ is an orthogonal matrix, so each column has an $\ell_2$-norm of 1. Because each column vector of a matrix has length equal to the number of rows ($d$ in this case) of the matrix, the sum of the squared elements of a column vector should be a sum with $d$ summands, not $n$ as you wrote. So the correct expression is $\sum_{j=1}^d B_{j,i}^2 = 1$ for $i = 1, \dots, n$, and hence $\sum_{i=1}^n \sum_{j=1}^d B_{j,i}^2 = n$ (the source writes these sums in the more confusing order).

The blue line supposes that $U$ is the matrix whose columns are the $n$ leading eigenvectors of $A$. An eigenvector of $A$ by definition is a vector $x \ne 0$ where $Ax = \lambda x$. Thus, if the columns $u_j$ of $U$ are the leading eigenvectors, $Au_j = \lambda_j u_j$. So you can derive \begin{align} U^\text{T} A U & = U^\text{T} A \left[ \begin{matrix} | & & | \\ u_1 & \dots & u_n \\ | & & |\end{matrix} \right] \\ & = U^\text{T} \left[ \begin{matrix} | & & | \\ A u_1 & \dots & A u_n \\ | & & |\end{matrix} \right] \\ & = U^\text{T} \left[ \begin{matrix} | & & | \\ \lambda_1 u_1 & \dots & \lambda_n u_n \\ | & & |\end{matrix} \right] \\ & = \left[ \begin{matrix} - & u_1 & - \\ & \vdots & \\ - & u_n & -\end{matrix} \right] \left[ \begin{matrix} | & & | \\ \lambda_1 u_1 & \dots & \lambda_n u_n \\| & & |\end{matrix} \right] \\ & = \left[ \begin{matrix} \lambda_1 & 0 & \dots & 0 \\ 0 & \lambda_2 & & \vdots \\ \vdots & & \ddots \\ 0 & \dots & & \lambda_n \end{matrix} \right] \\ & = \text{diag} (\lambda_1, \dots, \lambda_n) \end{align} and now you can apply the definition of the trace to see that $\text{trace} (U^\text{T} A U) = \sum_{j=1}^n \lambda_j = \sum_{j=1}^n D_{j, j}$.

$\endgroup$

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.