2
$\begingroup$

I'm learning PCA and I found the following optimization problem in pages 9 and 13 of Afonso Bandeira's lecture notes.

$$\begin{array}{ll} \underset{V \in \mathbb{R}^{n \times d}}{\text{maximize}} & \mbox{tr} \left(V^T \Sigma V \right)\\ \text{subject to} & V^T V = I_{d}\end{array}$$

where $\Sigma$ is the covariance matrix.

The solution is the first $d$ eigenvectors of $\Sigma$, but I don't know how to get this solution. I tried using Lagrange multipliers but failed to get the solution here.

$\endgroup$
3
  • $\begingroup$ researchweb.iiit.ac.in/~anurag.ghosh/notes/… $\endgroup$ Jun 27, 2020 at 3:36
  • $\begingroup$ I think the typical way to do this is via induction and a version of the max-min theorem that characterizes the $d$th largest eigenvalue as the max over all $d$ dimensional subspaces of the minimum Rayleigh quotient over that subspace (which is attained on the span of the top $d$ eigenvectors). $\endgroup$
    – J.G
    Jun 27, 2020 at 3:37
  • 2
    $\begingroup$ I believe this a duplicate of math.stackexchange.com/q/3637453/27978 $\endgroup$
    – copper.hat
    Jun 27, 2020 at 4:01

1 Answer 1

1
$\begingroup$

Write $\Sigma=XDX^t$ where $X$ is orthonormal and $D$ is diagonal with non-negative entries.

We want to maximize $tr(V^tXDX^tV)$. Consider the transformation $W=X^tV$ and ovserve that $W^tW=V^tXX^tV=V^tV=I$. Since $X^t$ is an invertible matrix, this defines an invertible transofmration on the space of allowable $V$s, so the original optimization problem is equivalent to

$max Tr(W^tDW), W^tW=I_d$

On the other hand, $Tr(W^tDW)=Tr(DWW^T)=\sum_i d_i (WW^T)_{ii}$.

Lemma

$0\leq (WW^T)_{ii}\leq 1$.

Proof of lemma

The first inequality is clear, because $(WW^T)_{ii}$ is the squared norm of the $i$th row of $W$. To establish the second, observe that for any matrix $M$, the norm of any column of $M$ is bounded by the largest singular value of $M$. This follows immediately from the characterization $\sigma_1(M)=\sup_{|v|=1} |Mv|$, and noting that the $i$th column is given by $Me_i$, where $e_i$ is a standard basis vector. Furthermore, it is a general fact that the singular values of $M$ are the square roots of the eigenvalues of $MM^T$. In particular, since $W^tW=I$, we conclude that all singular values of $W^t$ are equal to 1, and consequently the norm of each column of $W^t$ is bounded by 1.

(end proof of lemma)

Given the constraints on $(WW^T)_{ii}$ it is clear that $\sum_i d_i (WW^T)_{ii}$ is maximized when $(WW^T)_{ii}=1$ if if $i\leq k$ and $0$ if not (we assume WLOG that the entires of $D$ are ordered from largest to smallest). This can be attained by setting the $i$th column of $W$ to be $e_i$ if $i\leq k$ and $0$ if $i>k$. Finally, remembering that $W=X^tV$ where $X$ is the matrix of eigenvalues of $\Sigma$, we see that $V$ consists precisely of the top $k$ eigenvectors of $\Sigma$.

$\endgroup$
0

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.