Note 5 Exercises
Question 1
Assume $x = \begin{pmatrix} x_1 \\ x_2 \\ x_3 \end{pmatrix} \sim N_3(\mu, \Sigma)$, where
$$ \Sigma = \begin{pmatrix} 1.5 & 0.5 & 1 \\ 0.5 & 1.5 & 1 \\ 1 & 1 & 2 \end{pmatrix} $$(1) Find $Var(x_1, x_2 | x_3)$
Solution: We partition the covariance matrix $\Sigma$ into parts corresponding to $A = \{1, 2\}$ and $B = \{3\}$.
$$ \Sigma = \begin{pmatrix} \Sigma_{A} & \Sigma_{AB} \\ \Sigma_{BA} & \Sigma_{B} \end{pmatrix} = \begin{pmatrix} \begin{matrix} 1.5 & 0.5 \\ 0.5 & 1.5 \end{matrix} & \begin{matrix} 1 \\ 1 \end{matrix} \\ \begin{matrix} 1 & 1 \end{matrix} & 2 \end{pmatrix} $$The conditional variance formula is:
$$ Var(X_A | X_B) = \Sigma_{A} - \Sigma_{AB}\Sigma_{B}^{-1}\Sigma_{BA} $$Substituting the values:
$$ Var\left(\begin{pmatrix} x_1 \\ x_2 \end{pmatrix} \middle| x_3\right) = \begin{pmatrix} 1.5 & 0.5 \\ 0.5 & 1.5 \end{pmatrix} - \begin{pmatrix} 1 \\ 1 \end{pmatrix} (2)^{-1} \begin{pmatrix} 1 & 1 \end{pmatrix} $$$$ = \begin{pmatrix} 1.5 & 0.5 \\ 0.5 & 1.5 \end{pmatrix} - \frac{1}{2} \begin{pmatrix} 1 & 1 \\ 1 & 1 \end{pmatrix} $$$$ = \begin{pmatrix} 1.5 & 0.5 \\ 0.5 & 1.5 \end{pmatrix} - \begin{pmatrix} 0.5 & 0.5 \\ 0.5 & 0.5 \end{pmatrix} = \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix} $$(2) What is $(\Sigma^{-1})_{21}$? (Hint: you don’t need to compute $\Sigma^{-1}$ to answer this question)
Solution: From part (1), we found that the conditional covariance matrix is the identity matrix $\begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}$. The off-diagonal element (between $x_1$ and $x_2$) is 0. This implies that $x_1 \perp x_2 | x_3$ (conditionally independent). For a multivariate normal distribution, if $x_i$ and $x_j$ are conditionally independent given all other variables, the corresponding entry in the precision matrix (inverse covariance matrix) is zero. Therefore:
$$ (\Sigma^{-1})_{21} = 0 $$Question 2
Assume observations $x_1, \dots, x_n$ came from $N_p(0, \sigma^2 I)$.
(1) Compute log-likelihood for $x_1, \dots, x_n$
Solution: The likelihood function $L$ is given by the product of the individual densities:
$$ L(\sigma^2) = \prod_{i=1}^n \frac{1}{(2\pi)^{p/2} |\sigma^2 I|^{1/2}} \exp\left( -\frac{1}{2} x_i^T (\sigma^2 I)^{-1} x_i \right) $$The determinant $|\sigma^2 I| = (\sigma^2)^p$. The inverse $(\sigma^2 I)^{-1} = \frac{1}{\sigma^2}I$. Taking the log:
$$ \ell(\sigma^2) = \sum_{i=1}^n \left[ -\frac{p}{2} \log(2\pi) - \frac{1}{2} \log((\sigma^2)^p) - \frac{1}{2\sigma^2} x_i^T x_i \right] $$Ignoring the constant term regarding $\pi$:
$$ \ell(\sigma^2) = -\frac{np}{2} \log(\sigma^2) - \frac{1}{2\sigma^2} \sum_{i=1}^n \|x_i\|^2 $$(2) Find MLE for $\sigma^2$
Solution: To find the Maximum Likelihood Estimator, we take the derivative with respect to $\sigma^2$ and set it to 0. Let $v = \sigma^2$.
$$ \frac{\partial \ell}{\partial v} = -\frac{np}{2v} + \frac{1}{2v^2} \sum_{i=1}^n \|x_i\|^2 = 0 $$Multiply by $2v^2$:
$$ -np v + \sum_{i=1}^n \|x_i\|^2 = 0 $$$$ v = \hat{\sigma}^2 = \frac{\sum_{i=1}^n \|x_i\|^2}{np} $$Question 3
If $M \sim W_p(\Sigma, n)$ (Wishart distribution), show that:
(1) $AMA^T \sim W_q(A\Sigma A^T, n)$ for $A \in \mathbb{R}^{q \times p}$
Solution: By definition, if $M \sim W_p(\Sigma, n)$, then $M = X^T X$ where $X = \begin{pmatrix} x_1^T \\ \vdots \\ x_n^T \end{pmatrix}$ and each $x_i \sim N_p(0, \Sigma)$. Consider $AMA^T$:
$$ AMA^T = A X^T X A^T = (X A^T)^T (X A^T) $$Let $Y = X A^T$. The rows of $Y$, denoted $y_i$, are $y_i = A x_i$. Since $x_i \sim N_p(0, \Sigma)$, by the property of linear transformations of Normal vectors:
$$ y_i \sim N_q(0, A \Sigma A^T) $$Thus, $Y^T Y = AMA^T$ follows a Wishart distribution with scale matrix $A \Sigma A^T$ and degrees of freedom $n$.
$$ AMA^T \sim W_q(A \Sigma A^T, n) $$(2) $a^T M a \sim a^T \Sigma a \cdot \chi^2(n)$
Solution: This is a specific case of part (1) where $A = a^T$ (a row vector, $1 \times p$). Using the result from (1):
$$ a^T M a \sim W_1(a^T \Sigma a, n) $$A 1-dimensional Wishart distribution $W_1(\sigma^2, n)$ is equivalent to $\sigma^2 \chi^2(n)$. Here, the scalar variance is $a^T \Sigma a$. Therefore:
$$ a^T M a \sim a^T \Sigma a \cdot \chi^2(n) $$Question 4
If $M_1 \sim W_p(\Sigma, n_1)$ and $M_2 \sim W_p(\Sigma, n_2)$ and are independent, show that $M_1 + M_2 \sim W_p(\Sigma, n_1 + n_2)$.
Solution: By definition of the Wishart distribution:
$$ M_1 = {X^{(1)}}^T X^{(1)} \quad \text{where } X^{(1)} \text{ is } n_1 \times p \text{ with rows } \sim N_p(0, \Sigma) $$$$ M_2 = {X^{(2)}}^T X^{(2)} \quad \text{where } X^{(2)} \text{ is } n_2 \times p \text{ with rows } \sim N_p(0, \Sigma) $$The sum is:
$$ M_1 + M_2 = {X^{(1)}}^T X^{(1)} + {X^{(2)}}^T X^{(2)} $$We can stack the data matrices:
$$ M_1 + M_2 = \begin{pmatrix} X^{(1)} \\ X^{(2)} \end{pmatrix}^T \begin{pmatrix} X^{(1)} \\ X^{(2)} \end{pmatrix} $$Let $X_{new} = \begin{pmatrix} X^{(1)} \\ X^{(2)} \end{pmatrix}$. This matrix has $n_1 + n_2$ rows. Since $M_1$ and $M_2$ are independent, the rows of $X^{(1)}$ are independent of the rows of $X^{(2)}$. Thus, all $n_1 + n_2$ rows of $X_{new}$ are i.i.d. $N_p(0, \Sigma)$. By definition, $X_{new}^T X_{new} \sim W_p(\Sigma, n_1 + n_2)$.
Question 5
Suppose $x_1 \dots x_n \sim N_2(\mu, \Sigma)$ where $\Sigma$ is known and has Eigen Decomposition (ED):
$$ \Sigma = \begin{pmatrix} 1/\sqrt{2} & -1/\sqrt{2} \\ 1/\sqrt{2} & 1/\sqrt{2} \end{pmatrix} \begin{pmatrix} 4 & 0 \\ 0 & 1 \end{pmatrix} \begin{pmatrix} 1/\sqrt{2} & 1/\sqrt{2} \\ -1/\sqrt{2} & 1/\sqrt{2} \end{pmatrix} $$We want to test $H_0: \mu = \begin{pmatrix} 0 \\ 0 \end{pmatrix}$ vs $H_1: \mu \neq \begin{pmatrix} 0 \\ 0 \end{pmatrix}$.
(1) Draw a 95% confidence ellipse for $\bar{x}$.
i.e., find an ellipse $E \subseteq \mathbb{R}^2$ such that $P(\bar{x} \in E) = 0.95$.
Solution: Under the null hypothesis $H_0$, $\bar{x} \sim N_2(0, \frac{\Sigma}{n})$. The confidence ellipse is defined by the quadratic form:
$$ \bar{x}^T \left( \frac{\Sigma}{n} \right)^{-1} \bar{x} \leq \chi^2_2(0.95) $$The critical value is $\chi^2_{0.95, df=2} \approx 5.99$. The covariance of the sample mean is $\frac{\Sigma}{n}$. Its eigenvalues are $\frac{4}{n}$ and $\frac{1}{n}$. Its eigenvectors are the same as $\Sigma$: $v_1 = \begin{pmatrix} 1/\sqrt{2} \\ 1/\sqrt{2} \end{pmatrix}$ and $v_2 = \begin{pmatrix} -1/\sqrt{2} \\ 1/\sqrt{2} \end{pmatrix}$. The axes of the ellipse are aligned with the eigenvectors. The half-lengths of the axes are:
$$ \text{Major axis length} = \sqrt{\chi^2_{crit} \cdot \lambda_1} = \sqrt{5.99 \cdot \frac{4}{n}} \approx \sqrt{\frac{24}{n}} $$$$ \text{Minor axis length} = \sqrt{\chi^2_{crit} \cdot \lambda_2} = \sqrt{5.99 \cdot \frac{1}{n}} \approx \sqrt{\frac{6}{n}} $$Visualization: An ellipse rotated 45 degrees counter-clockwise (due to $v_1$).
(2) How does the confidence ellipse change when $n$ increases?
Solution: As $n$ increases, the lengths of the axes ($\sqrt{\frac{24}{n}}$ and $\sqrt{\frac{6}{n}}$) decrease. The ellipse shrinks towards the origin (0,0), making the confidence region tighter.
(3) Suppose $\bar{x}_{obs} = \begin{pmatrix} 1 \\ 1 \end{pmatrix}$, find values $n$ for which $H_0$ is rejected.
Solution: Note that $\bar{x}_{obs} = \begin{pmatrix} 1 \\ 1 \end{pmatrix}$ lies exactly on the direction of the first eigenvector $v_1 = \begin{pmatrix} 1/\sqrt{2} \\ 1/\sqrt{2} \end{pmatrix} \propto \begin{pmatrix} 1 \\ 1 \end{pmatrix}$. The distance from origin to $\bar{x}_{obs}$ is $\sqrt{1^2 + 1^2} = \sqrt{2}$. Since it lies on the major axis, we simply compare the distance to the major axis half-length. We reject $H_0$ if the point is outside the ellipse:
$$ \text{Point Distance} > \text{Axis Length} $$$$ \sqrt{2} > \sqrt{\frac{24}{n}} $$Squaring both sides:
$$ 2 > \frac{24}{n} \implies 2n > 24 \implies n > 12 $$$H_0$ is rejected for $n > 12$ (e.g., $n = 13, 14, \dots$).
(4) For which $n$ we fail to reject $H_0$?
Solution: Based on the inequality above, we fail to reject $H_0$ when $n \leq 12$.
(5) Let $\bar{x}_{obs} = \begin{pmatrix} 0.5 \\ 2 \end{pmatrix}$ and $n=10$. Compute $\chi_{obs}^2$. Can we reject $H_0$?
Solution: (Note: The solution PDF calculates for $\bar{x}_{obs} = \binom{2}{0.5}$, but let’s follow the steps for the general formula). Let’s use the vector from the solution PDF example $\bar{x} = \binom{2}{0.5}$ to match the calculated $\chi^2 = 19$. Formula: $\chi^2_{obs} = n \bar{x}_{obs}^T \Sigma^{-1} \bar{x}_{obs}$. First, compute $\Sigma^{-1}$. Eigenvalues of $\Sigma^{-1}$ are $1/4$ and $1$.
$$ \Sigma^{-1} = V \Lambda^{-1} V^T = \begin{pmatrix} \frac{1}{\sqrt{2}} & -\frac{1}{\sqrt{2}} \\ \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} \end{pmatrix} \begin{pmatrix} 0.25 & 0 \\ 0 & 1 \end{pmatrix} \begin{pmatrix} \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} \\ -\frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} \end{pmatrix} $$$$ = \begin{pmatrix} 5/8 & -3/8 \\ -3/8 & 5/8 \end{pmatrix} $$If $\bar{x}_{obs} = \binom{2}{0.5}$:
$$ \chi^2_{obs} = 10 \cdot \begin{pmatrix} 2 & 0.5 \end{pmatrix} \begin{pmatrix} 5/8 & -3/8 \\ -3/8 & 5/8 \end{pmatrix} \begin{pmatrix} 2 \\ 0.5 \end{pmatrix} = 19 $$Since $\chi^2_{obs} = 19 > \chi^2_{crit} = 5.99$, we Reject $H_0$. P-value: $P(\chi^2_2 > 19) \approx 7 \times 10^{-5} < 0.05$.
(6) Conduct individual tests. Compare the results.
Solution: We test the margins separately.
$H_0: \mu_1 = 0$. $\bar{x}_1 = 2$. Marginal variance of $x_1$ is $\Sigma_{11} = 2.5$ (Calculated from ED reconstruction: $0.5(4) + 0.5(1) = 2.5$). $Z_{obs} = \frac{2 - 0}{\sqrt{2.5/10}} = \frac{2}{0.5} = 4$. P-value $\approx 0$. Reject $H_0$.
$H_0: \mu_2 = 0$. $\bar{x}_2 = 0.5$. Marginal variance of $x_2$ is $\Sigma_{22} = 2.5$. $Z_{obs} = \frac{0.5 - 0}{\sqrt{2.5/10}} = \frac{0.5}{0.5} = 1$. P-value $= 2P(Z > 1) \approx 0.32 > 0.05$. Fail to reject $H_0$.
Comparison: The joint test (part 5) rejected the null hypothesis strongly ($p \approx 10^{-5}$). However, the individual test for $\mu_2$ failed to reject. This illustrates that variables can be significant jointly due to correlation even if they are not significant individually (or vice versa).
Note 6 Exercises
Question 1
For $X = (f_1 \dots f_p) \in \mathbb{R}^{n \times p}$, show that total variance in the data, i.e., $S_{f_1}^2 + \dots + S_{f_p}^2$, is equal to $d_1 + \dots + d_p$ where $d_1, \dots, d_p$ are eigenvalues of $S$.
Solution: The sample covariance matrix is $S$. The total variance is defined as the sum of the diagonal elements of $S$, which is the trace of $S$.
$$ \text{Total Variance} = \sum_{i=1}^p S_{f_i}^2 = \text{tr}(S) $$Using the Eigen Decomposition $S = U \Lambda U^T$, where $\Lambda = \text{diag}(d_1, \dots, d_p)$:
$$ \text{tr}(S) = \text{tr}(U \Lambda U^T) $$By the cyclic property of the trace ($\text{tr}(ABC) = \text{tr}(BCA)$):
$$ \text{tr}(S) = \text{tr}(\Lambda U^T U) $$Since $U$ is orthogonal, $U^T U = I$:
$$ \text{tr}(S) = \text{tr}(\Lambda I) = \text{tr}(\Lambda) = \sum_{i=1}^p d_i $$Thus, the sum of variances equals the sum of eigenvalues.
Question 2
You are given data $X = \begin{pmatrix} -3 & 0 \\ 0 & 1 \\ 3 & 0 \\ 0 & -1 \end{pmatrix}$.
(1) What are the $PC_1$ and $PC_2$ directions for $X$? (Hint: draw a picture for $X$)
Solution: Drawing the points $(-3,0), (0,1), (3,0), (0,-1)$, we see the data forms a cross shape aligned with the axes. The variance is clearly maximized along the x-axis (range -3 to 3) compared to the y-axis (range -1 to 1). Thus, the Principal Components are the standard basis vectors. $PC_1$ direction: $v_1 = \begin{pmatrix} 1 \\ 0 \end{pmatrix}$ (axis of max variance). $PC_2$ direction: $v_2 = \begin{pmatrix} 0 \\ 1 \end{pmatrix}$.
(2) What are variances explained by $PC_1$ and $PC_2$?
Solution: First, compute the covariance matrix (or $X^T X$ since means are 0).
$$ S = \frac{X^T X}{n-1} \quad \text{(or usually } \frac{X^T X}{n} \text{ for PCA derivation)} $$Using $n=4$:
$$ X^T X = \begin{pmatrix} -3 & 0 & 3 & 0 \\ 0 & 1 & 0 & -1 \end{pmatrix} \begin{pmatrix} -3 & 0 \\ 0 & 1 \\ 3 & 0 \\ 0 & -1 \end{pmatrix} = \begin{pmatrix} 18 & 0 \\ 0 & 2 \end{pmatrix} $$Eigenvalues (Variances):
$$ \lambda_1 = \frac{18}{4} = 4.5 $$$$ \lambda_2 = \frac{2}{4} = 0.5 $$So, Variance Explained ($VE_1$) = 4.5, $VE_2$ = 0.5.
(3) What are the proportions of variances explained by $PC_1$ and $PC_2$?
Solution: Total Variance = $4.5 + 0.5 = 5.0$.
$$ PVE_1 = \frac{4.5}{5} = 0.9 \quad (90\%) $$$$ PVE_2 = \frac{0.5}{5} = 0.1 \quad (10\%) $$(4) Suppose the first column in X was measured in meters and the second is in centimeters. You transform both measurements in centimeters. What happens to the $PC_1$ and $PC_2$ directions?
Solution: Transforming column 1 to cm means multiplying by 100. New data $\tilde{X} = \begin{pmatrix} -300 & 0 \\ 0 & 1 \\ 300 & 0 \\ 0 & -1 \end{pmatrix}$. The spread along the x-axis is now massive (-300 to 300) compared to y-axis (-1 to 1). The directions remain the same because the axes were already aligned. $\tilde{v}_1 = \begin{pmatrix} 1 \\ 0 \end{pmatrix}$ and $\tilde{v}_2 = \begin{pmatrix} 0 \\ 1 \end{pmatrix}$.
(5) What happens to the VEs and PVEs?
Solution: New Eigenvalues:
$$ \tilde{\lambda}_1 = \frac{(-300)^2 + 300^2}{4} = \frac{180000}{4} = 45000 $$$$ \tilde{\lambda}_2 = 0.5 \quad \text{(unchanged)} $$New Proportions:
$$ \tilde{PVE}_1 = \frac{45000}{45000.5} \approx 1 \quad (100\%) $$$$ \tilde{PVE}_2 = \frac{0.5}{45000.5} \approx 0 \quad (0\%) $$This shows that PCA is sensitive to scaling; the variable with larger units dominates the variance.
Note 7 Exercises
Question 1
Assume $X \sim N_p(0, \Sigma)$. Let $V_1 \dots V_r$ be the directions of $PC_1 \dots PC_r$ and $Z_{(1)} = X^T V_1 \dots Z_{(r)} = X^T V_r$ be the corresponding scores.
(1) Find marginal distributions of $Z_{(1)} \dots Z_{(r)}$
Solution: The vector of scores is $Z = V^T X$. Since $X$ is Normal, a linear combination $Z$ is also Normal.
$$ E[Z] = V^T E[X] = 0 $$$$ Var(Z) = V^T \Sigma V $$In PCA, $V$ contains the eigenvectors of $\Sigma$, so $\Sigma = V \Lambda V^T$.
$$ Var(Z) = V^T (V \Lambda V^T) V = (V^T V) \Lambda (V^T V) = I \Lambda I = \Lambda $$Marginally, each score $Z_{(i)}$ follows a univariate normal distribution:
$$ Z_{(i)} \sim N(0, \lambda_i) $$(2) Find joint distribution of $Z_{(1)} \dots Z_{(r)}$
Solution: Collecting the results from above, the vector $Z = (Z_{(1)}, \dots, Z_{(r)})^T$ follows a multivariate normal distribution with diagonal covariance matrix (since $\Sigma_Z = \Lambda$):
$$ \begin{pmatrix} Z_{(1)} \\ \vdots \\ Z_{(r)} \end{pmatrix} \sim N_r \left( \mathbf{0}, \begin{pmatrix} \lambda_1 & & 0 \\ & \ddots & \\ 0 & & \lambda_r \end{pmatrix} \right) $$(3) Are $Z_{(1)} \dots Z_{(r)}$ independent?
Solution: Yes. Since $Z_{(1)} \dots Z_{(r)}$ follow a joint multivariate normal distribution and their covariance matrix is diagonal (uncorrelated), uncorrelatedness implies independence for Gaussian variables.
Question 2
Explain why finding $V_1 \dots V_r$ in PCA is equivalent to $\max_{V \in \mathbb{R}^{p \times r}} \text{tr}(V^T S V)$ subject to $V^T V = I_r$.
Solution: The objective of PCA is to maximize the variance of the projected data. For a single direction $v$, the variance is $v^T S v$. For $r$ directions represented by matrix $V$, we want to maximize the sum of variances of the uncorrelated projections:
$$ \sum_{i=1}^r Var(X v_i) = \sum_{i=1}^r v_i^T S v_i = \text{tr}(V^T S V) $$The constraint $V^T V = I_r$ enforces that the principal component directions are orthonormal (unit length and orthogonal to each other). The solution to maximizing this trace subject to orthogonality is given by the top $r$ eigenvectors of $S$.
Question 3
Suppose $X \in \mathbb{R}^{n \times p}$ for $n > p$, we aim to minimize $\|X - \hat{X}\|_F^2$ subject to $rank(\hat{X}) = r$.
(1) Show that if $rank(\hat{X}) = r$ then $\hat{X} = QA$ where $Q \in \mathbb{R}^{n \times r}$ is column-orthogonal and $A \in \mathbb{R}^{r \times p}$.
Solution: Any rank-$r$ matrix can be decomposed via SVD or rank factorization as $C F^T$. We can perform Gram-Schmidt (QR decomposition) on $C$ to get an orthogonal basis $Q$. Thus, we can write $\hat{X} = Q A$, where the columns of $Q$ form an orthonormal basis for the column space of $\hat{X}$, so $Q^T Q = I_r$.
(2) If $Q$ is fixed, show that $\|X - QA\|_F^2$ is minimized when $A = Q^T X$.
Solution: This is a regression problem. We want to approximate $X$ using basis $Q$ with coefficients $A$.
$$ \min_A \|X - QA\|_F^2 $$The solution to this least squares problem is:
$$ A = (Q^T Q)^{-1} Q^T X $$Since $Q$ is column-orthogonal, $Q^T Q = I$.
$$ A = Q^T X $$(3) Show that (*) is equivalent to $\max_{Q} \text{tr}(Q^T X X^T Q)$ subject to $Q^T Q = I_r$.
Solution: Substitute optimal $A = Q^T X$ into the objective:
$$ \|X - Q Q^T X\|_F^2 = \text{tr}\left( (X - Q Q^T X)^T (X - Q Q^T X) \right) $$Expanding this:
$$ = \text{tr}(X^T X - X^T Q Q^T X - X^T Q Q^T X + X^T Q Q^T Q Q^T X) $$Since $Q^T Q = I$:
$$ = \text{tr}(X^T X - 2 X^T Q Q^T X + X^T Q Q^T X) $$$$ = \text{tr}(X^T X) - \text{tr}(X^T Q Q^T X) $$Since $\text{tr}(X^T X)$ is constant w.r.t $Q$, minimizing the error is equivalent to maximizing the negative term:
$$ \max \text{tr}(X^T Q Q^T X) = \max \text{tr}(Q^T X X^T Q) \quad \text{(Cyclic property)} $$(4) Conclude from (3) that optimal $Q = U_{(r)} = (u_1 \dots u_r)$ where $u_i$ are top eigenvectors of $XX^T$.
Solution: The problem $\max \text{tr}(Q^T (XX^T) Q)$ s.t. $Q^T Q = I$ is the same form as Question 2, but applied to the matrix $XX^T$. The solution is the top $r$ eigenvectors of $XX^T$, which are the left singular vectors $U$ of $X$.
(5) Show that if $X = U D V^T$ is SVD of X then optimal $A = D_{(r)} V_{(r)}^T$.
Solution: We know optimal $A = Q^T X$. Using optimal $Q = U_{(r)}$:
$$ A = U_{(r)}^T (U D V^T) $$$$ A = \begin{pmatrix} I_r & 0 \end{pmatrix} D V^T = D_{(r)} V_{(r)}^T $$(6) Conclude that optimal $\hat{X} = U_{(r)} D_{(r)} V_{(r)}^T$.
Solution:
$$ \hat{X} = Q A = U_{(r)} (D_{(r)} V_{(r)}^T) $$This is exactly the Truncated SVD of $X$.
Note 8 Exercise
Question 1
Find feature mapping for cubic kernel $K(a,b) = (1 + \langle a, b \rangle)^3$. What is $q$ (dimension of feature space)?
Solution: Expand $(1 + \sum a_i b_i)^3$.
$$ = 1 + \sum a_i^3 b_i^3 + 3\sum a_i b_i + 3\sum a_i^2 b_i^2 + \dots $$The terms correspond to monomials of degree 0, 1, 2, and 3. The feature map $\phi(a)$ contains terms like: $1, \sqrt{3}a_i, \sqrt{3}a_i^2, \sqrt{6}a_i a_j, \dots$ The number of terms corresponds to the number of ways to choose terms with replacement up to degree 3.
$$ q = \binom{p+3}{3} $$Question 2
In Kernel PCA:
(1) Show that $v_i = \Phi^T \frac{u_i}{d_i}$
Solution: From SVD in feature space, $\Phi = U D V^T$. Right singular vectors $V$ (eigenvectors of covariance) satisfy:
$$ \Phi^T U = V D^T = V D $$Multiply by $D^{-1}$:
$$ V = \Phi^T U D^{-1} \implies v_i = \Phi^T \frac{u_i}{d_i} $$(2) Express PC scores $\phi(x)^T v_i$ in terms of kernel function.
Solution:
$$ \phi(x)^T v_i = \phi(x)^T \Phi^T \frac{u_i}{d_i} = (\Phi \phi(x))^T \frac{u_i}{d_i} $$The vector $\Phi \phi(x)$ contains dot products $\langle \phi(x_j), \phi(x) \rangle$, which is the kernel $K(x_j, x)$.
$$ \text{Score} = \begin{pmatrix} K(x_1, x) & \dots & K(x_n, x) \end{pmatrix} \frac{u_i}{d_i} $$(3) Explain why adding new observation to Kernel PCA biplot doesn’t require computing $\phi(x)$.
Solution: As shown in (2), the projection (score) depends only on the kernel values $K(x, x_i)$ between the new point and the training data. We never need to explicitly calculate the high-dimensional vector $\phi(x)$.
Question 3 (CCA vs Regression)
Assume $q=1$.
(1) What is dimensionality of $\tilde{S}_{xy}$?
Solution: $\tilde{S}_{xy} = S_x^{-1/2} S_{xy} S_y^{-1/2}$. Since $Y$ is 1-dimensional ($q=1$), $S_{xy}$ is $p \times 1$ and $S_y$ is scalar. Thus $\tilde{S}_{xy} \in \mathbb{R}^{p \times 1}$.
(2) Show that $\tilde{u}_1 = \frac{\tilde{S}_{xy}}{\|\tilde{S}_{xy}\|_2}$.
Solution: We perform SVD on $\tilde{S}_{xy}$. Since it is a vector, its left singular vector $\tilde{u}_1$ is simply the unit vector in the direction of the vector itself.
$$ \tilde{u}_1 = \frac{\tilde{S}_{xy}}{\|\tilde{S}_{xy}\|} $$(3) Show that $u_1 = c S_x^{-1} S_{xy}$.
Solution: The relation between CCA direction and transformed direction is $u_1 = S_x^{-1/2} \tilde{u}_1$.
$$ u_1 = S_x^{-1/2} \frac{\tilde{S}_{xy}}{\|\tilde{S}_{xy}\|} = \frac{1}{\|\tilde{S}_{xy}\|} S_x^{-1/2} (S_x^{-1/2} S_{xy} S_y^{-1/2}) $$Collapsing scalars into constant $c$:
$$ u_1 = c S_x^{-1} S_{xy} $$(4) Argue that $u_1 = c \cdot \hat{\beta}$.
Solution: For OLS regression of $y$ on $X$, $\hat{\beta} = (X^T X)^{-1} X^T y$. Noting that $S_x \propto X^T X$ and $S_{xy} \propto X^T y$:
$$ S_x^{-1} S_{xy} \propto (X^T X)^{-1} X^T y = \hat{\beta} $$Thus, the CCA direction is proportional to the OLS coefficient.
Question 4
Assume $\begin{pmatrix} X \\ Y \end{pmatrix} \sim N_{p+q} \left( 0, \begin{pmatrix} \Sigma_x & \Sigma_{xy} \\ \Sigma_{yx} & \Sigma_y \end{pmatrix} \right)$.
(1) Explain how to find solution $u_1, v_1$.
Solution: Compute $\tilde{\Sigma}_{xy} = \Sigma_x^{-1/2} \Sigma_{xy} \Sigma_y^{-1/2}$. Find $\tilde{u}_1$ and $\tilde{v}_1$ as the top left and right singular vectors of $\tilde{\Sigma}_{xy}$. Transform back: $u_1 = \Sigma_x^{-1/2} \tilde{u}_1$ and $v_1 = \Sigma_y^{-1/2} \tilde{v}_1$.
(2) What is the distribution of $a_1 = X^T u_1$ and $b_1 = Y^T v_1$?
Solution: Since $X$ and $Y$ are normal, linear combinations are normal. $a_1 \sim N(0, u_1^T \Sigma_x u_1)$. By CCA constraints, variance is 1. So $a_1 \sim N(0, 1)$. Similarly $b_1 \sim N(0, 1)$.
(3) What is the joint distribution of $\binom{a_1}{b_1}$?
Solution: They are jointly normal. We need the covariance. $Cov(a_1, b_1) = u_1^T \Sigma_{xy} v_1$. Substitute definitions: $u_1^T \Sigma_{xy} v_1 = \tilde{u}_1^T \tilde{\Sigma}_{xy} \tilde{v}_1 = \sigma_1$ (the first singular value / canonical correlation).
$$ \begin{pmatrix} a_1 \\ b_1 \end{pmatrix} \sim N_2 \left( \begin{pmatrix} 0 \\ 0 \end{pmatrix}, \begin{pmatrix} 1 & \sigma_1 \\ \sigma_1 & 1 \end{pmatrix} \right) $$(4) Extend to first $r$ components.
Solution: Let $a = (a_1 \dots a_r)^T$ and $b = (b_1 \dots b_r)^T$. $Cov(a_i, a_j) = 0$ for $i \neq j$ (uncorrelated by design). Same for $b$. $Cov(a_i, b_j) = 0$ if $i \neq j$. $Cov(a_i, b_i) = \sigma_i$. The joint distribution is $N_{2r}(0, \Sigma_{block})$ where the covariance matrix is block diagonal with $2 \times 2$ blocks $\begin{pmatrix} 1 & \sigma_i \\ \sigma_i & 1 \end{pmatrix}$ for each pair $(a_i, b_i)$.