5
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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.

$\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.