How to prove PCA using induction In Deep Learning (Goodfellow, et al), the optimization objective of PCA is formulated as 
$D^* = \arg\min_D ||X - XDD^T||_F^2, s.t. D^T D=I$
The book gives the proof of the 1-dimension case, i.e. 
$\arg\min_{d} || X - X dd^T||_F^2, s.t. d^T d = 1 $ 
equals the eigenvector of $X^TX$ with the largest eigenvalue. And the author says the general case (when $D$ is an $m \times l$ matrix, where $l>1$) can be easily proved by induction.
Could anyone please show me how I can prove that using induction?
I know that when $D^T D = I$:
$
D^* 
= \arg\min_D ||X - XDD^T||_F^2
= \arg\min_D tr D^T X^T X D 
$
and 
$ 
tr D^T X^T X D = \left(\sum_{i=1}^{l-1} \left(d^{(i)}\right)^T X^TX d^{(i)}\right) + \left(d^{(l)}\right)^T X^TX d^{(l)}
$
where the left-hand side of the addition reaches maximum when $d^{(i)}$ is the $ith$ largest eigenvector of $X^T X$ according to induction hypothesis. But how can I be sure that the result of the addition in a whole is also maximal?
 A: We will start from 
$$\begin{align}
D^* &= \underset{D}{arg\max}\;Tr\ (D^TX^TXD)\\
&= \underset{D}{arg\max}\left[Tr\ (D_{l-1}^TX^TXD_{l-1}) + d^{(l)T}X^TXd^{(l)}\right]
\end{align}
$$
Where we used the notation $D_{k}$ to denote the matrix with first $l-1$ columns of $D$.
The 2 summands in the expression share no common terms of $D$ and hence can be maximized independently.
Using the induction hypothesis, we conclude that $Tr\ (D_{l-1}^TX^TXD_{l-1})$ (with the constraint that the columns of $D_{l-1}$ are orthonormal) is maximized when $D_{l-1}$ comprises of the orthonormal eigenvectors corresponding the $l-1$ largest eigenvalues.
Notation:
Suppose $\lambda_1 \geqslant ... \geqslant\lambda_n$ are the eigenvalues and $v_1, ..., v_n$ are the corresponding orthonormal eigenvectors.
Denote $H_{l-1} = span\{v_1, ...,v_{l-1}\}$ and $H_{l-1}^{\bot}$ the orthogonal subspace of $H_{l-1}$ i.e. $H_{l-1}^{\bot} = span\{v_l,...,v_n\}$ 
Lemma:
$$\begin{align}\lambda_l &= \underset{d^{(l)}}{max}\ d^{(l)T}X^TXd^{(l)} \quad s.t. \Vert d^{(l)}\Vert = 1, d^{(l)} \in H_{l-1}^\bot \\
&=v_l^TX^TXv_l \end{align}$$
Proof:
Let $\Sigma = X^TX$. Because it's a symmetric positive semidefinite matrix, eigendecomposition exists and let it be $\Sigma = V\Lambda V^T$ where columns of $V$ are $v_1,...,v_n$ in that order and hence $\Lambda=diag(\lambda_1,...,\lambda_n)$.
$$
\begin{align}
d^{(l)T}\Sigma d^{(l)} &= d^{(l)T} V\Lambda V^T d^{(l)}\\
&= q^T \Lambda\ q \qquad [where\ q = V^Td^{(l)}]\\
&= \sum_{i=1}^n q_i^2 \lambda_i \qquad [where\ q_i = (V^Td^{(l)})_i = v_i^T d^{(l)}]\\
&= \sum_{i=l}^n q_i^2 \lambda_i \qquad [\because d^{(l)} \in H_{l-1}^\bot \implies q_i = v_i^T d^{(l)} = 0\ \forall i < l]\\
\end{align}
$$
Reminder:
$d^{(l)} \in H_{l-1}^\bot$ s.t. 
$\sum_{k=l}^n \alpha_k V_K; \sum_{k=l} \alpha_k^2 = 1$
Now
$$\begin{align}
\sum_{i=l}^n q_i^2
&= \sum_{i=1}^n (V_i^T \sum_{k=l}^n \alpha_k V_k)^2 \\
&= \sum_{i=l}^n (\alpha_i V_i^T V_i)^2 \qquad [\because V\ is\ orthogonal] \\
&= \sum_{i=l}^n \alpha^2 = 1
\end{align}
$$
Therefore $d^{(l)T} \Sigma d^{(l)}$ is a convex combination of $\lambda_l,...,\lambda_n$ and $$\underset{d^{(l)}}{max}\ d^{(l)T}\Sigma d^{(l)} = \underset{d^{(l)}}{max}\ d^{(l)T}X^TXd^{(l)} = v_l^TX^TXv_l = \lambda_l \ (qed)$$
We conclude that $D^*$ is obtained by augmenting $D_{l-1}$ with the column $v_l$ which completes the original proof.
