7.3 Principal Components, Discriminant, Cluster and Canonical Correlation Analysis
Four ways to reduce and organise multivariate data: principal components (the eigenvectors of the covariance matrix), Fisher's linear discriminant and optimal classification rules, hierarchical and $k$-means clustering with their linkages and dendrograms, and canonical correlations between two sets of variables — each with its theory, its computation and its traps.
A modern data set rarely has one or two variables. A hospital records twenty blood markers per patient, a satellite measures reflectance in a dozen wavelength bands, a psychologist scores fifty questionnaire items, and a geneticist measures thousands of genes on a few hundred samples. The multivariate normal theory of §7.1–§7.2 tells us how to make inferences about mean vectors and covariance matrices; this section is about the complementary task of understanding such data: finding the few directions in which the data really vary, separating groups, discovering groups nobody labelled, and relating one block of variables to another. The four classical tools — principal component analysis, discriminant analysis, cluster analysis and canonical correlation analysis — are all, at heart, applications of one piece of linear algebra: the maximisation of a ratio of quadratic forms, solved by an eigenvalue or singular value decomposition.
Principal components maximise $a^{\mathsf T}\Sigma a$ over unit vectors $a$ (an eigenvalue problem for $\Sigma$). Fisher's discriminant maximises the ratio $(a^{\mathsf T}d)^2/(a^{\mathsf T}Sa)$ of between-group to within-group variation (answer: $a\propto S^{-1}d$). Canonical correlations maximise a correlation $a^{\mathsf T}\Sigma_{12}b/\sqrt{a^{\mathsf T}\Sigma_{11}a\;b^{\mathsf T}\Sigma_{22}b}$ (a singular value problem). Cluster analysis is different in flavour — it is combinatorial — but its most popular method, $k$-means, minimises the same within-group sum of squares that appears in the analysis of variance (§6.2). CSIR Part B questions ask for the proportion of variance explained by the first components, a discriminant function or its error rate, a merge height in a dendrogram, or a canonical correlation from a small correlation matrix. Part C questions test the theory: which properties are invariant under rescaling, when an extra variable can help discrimination, which linkages produce a monotone dendrogram, what $k$-means is and is not guaranteed to do, and how canonical correlations compare with ordinary and multiple correlations.
Notation. Vectors are columns and $^{\mathsf T}$ is the transpose. $X=(X_1,\dots,X_p)^{\mathsf T}$ is a random vector with mean $\mu$ and covariance matrix $\Sigma=(\sigma_{ik})$, which is symmetric and positive semidefinite (§7.1). For data $x_1,\dots,x_n\in\mathbb{R}^p$ we write $\bar x=\frac1n\sum x_i$ and $S=\frac1{n-1}\sum_{i=1}^n(x_i-\bar x)(x_i-\bar x)^{\mathsf T}$ for the sample covariance matrix. We use the spectral theorem of linear algebra (Unit 1): a real symmetric $p\times p$ matrix $A$ can be written $A=\sum_{j=1}^p\lambda_je_je_j^{\mathsf T}=E\Lambda E^{\mathsf T}$ with real eigenvalues $\lambda_1\ge\dots\ge\lambda_p$ and an orthonormal basis of eigenvectors $e_1,\dots,e_p$ (the columns of the orthogonal matrix $E$). If $A$ is positive definite, $A^{1/2}=E\Lambda^{1/2}E^{\mathsf T}$ and $A^{-1/2}=E\Lambda^{-1/2}E^{\mathsf T}$. The Mahalanobis distance of §7.1 is $\Delta^2=(\mu_1-\mu_2)^{\mathsf T}\Sigma^{-1}(\mu_1-\mu_2)$.
Principal Component Analysis
Suppose we must summarise $p$ correlated measurements by a single number. A natural choice is the linear combination $a^{\mathsf T}X$ that varies the most — it separates the individuals best. Since $\operatorname{Var}(a^{\mathsf T}X)=a^{\mathsf T}\Sigma a$ can be made as large as we like by scaling $a$, we normalise $\|a\|=1$. Having found the best direction, we look for the best direction among those that carry new information, i.e. that are uncorrelated with what we already have.
Let $X$ have covariance matrix $\Sigma$. The first principal component of $X$ is a linear combination $Y_1=a_1^{\mathsf T}X$ with $\|a_1\|=1$ that maximises $\operatorname{Var}(a^{\mathsf T}X)$ over all unit vectors $a$. For $k=2,\dots,p$, the $k$-th principal component is $Y_k=a_k^{\mathsf T}X$ with $\|a_k\|=1$ that maximises $\operatorname{Var}(a^{\mathsf T}X)$ over unit vectors $a$ subject to $\operatorname{Cov}(a^{\mathsf T}X,Y_j)=0$ for $j=1,\dots,k-1$ (in the degenerate case that some earlier $Y_j$ has variance $0$ we also require $a\perp a_j$). The vectors $a_k$ are the loadings (coefficient vectors). Often the components are centred, $Y_k=a_k^{\mathsf T}(X-\mu)$; this changes no variance or covariance.
Let $\Sigma=\sum_{j=1}^p\lambda_je_je_j^{\mathsf T}$ with $\lambda_1\ge\lambda_2\ge\dots\ge\lambda_p\ge0$ and $e_1,\dots,e_p$ orthonormal. Then for every unit vector $a$,
$$\lambda_p\le a^{\mathsf T}\Sigma a\le\lambda_1,$$with the maximum attained at $a=e_1$ and the minimum at $a=e_p$. More generally, the maximum of $a^{\mathsf T}\Sigma a$ over unit vectors $a\perp e_1,\dots,e_{k-1}$ is $\lambda_k$, attained at $a=e_k$. Consequently the principal components are
$$Y_k=e_k^{\mathsf T}X,\qquad\operatorname{Var}(Y_k)=\lambda_k,$$ $$\operatorname{Cov}(Y_j,Y_k)=0\quad(j\ne k).$$The loadings are unique up to sign exactly when $\lambda_k$ is a simple eigenvalue; if $\lambda_k$ is repeated, any unit vector of its eigenspace (orthogonal to the earlier loadings) will do.
Proof. Expand $a=\sum_jc_je_j$ with $c_j=e_j^{\mathsf T}a$; orthonormality gives $\|a\|^2=\sum_jc_j^2$ and $\Sigma a=\sum_j\lambda_jc_je_j$, so
$$a^{\mathsf T}\Sigma a=\sum_{j=1}^p\lambda_jc_j^2 .$$If $\|a\|=1$, this is a weighted average of the $\lambda_j$ with weights $c_j^2\ge0$ summing to $1$, so it lies between $\lambda_p$ and $\lambda_1$; it equals $\lambda_1$ when $c=(1,0,\dots,0)$, i.e. $a=e_1$, and $\lambda_p$ when $a=e_p$. If in addition $a\perp e_1,\dots,e_{k-1}$, then $c_1=\dots=c_{k-1}=0$, and $a^{\mathsf T}\Sigma a=\sum_{j\ge k}\lambda_jc_j^2\le\lambda_k\sum_{j\ge k}c_j^2=\lambda_k$, with equality at $a=e_k$.
It remains to match the constraint "uncorrelated with $Y_1,\dots,Y_{k-1}$" with "$a\perp e_1,\dots,e_{k-1}$", arguing by induction on $k$. Suppose $Y_j=e_j^{\mathsf T}X$ for $j\lt k$. Then $\operatorname{Cov}(a^{\mathsf T}X,Y_j)=a^{\mathsf T}\Sigma e_j=\lambda_j\,a^{\mathsf T}e_j$. If $\lambda_j\gt0$, this vanishes iff $a\perp e_j$; if $\lambda_j=0$, orthogonality is required by the definition. So the admissible $a$ are exactly the unit vectors orthogonal to $e_1,\dots,e_{k-1}$, the maximum is $\lambda_k$, and $a_k=e_k$ is a maximiser; hence $Y_k=e_k^{\mathsf T}X$ and $\operatorname{Var}(Y_k)=\lambda_k$. Finally $\operatorname{Cov}(Y_j,Y_k)=e_j^{\mathsf T}\Sigma e_k=\lambda_k e_j^{\mathsf T}e_k=0$ for $j\ne k$. If $\lambda_k\gt\lambda_{k+1}$ and $\lambda_k\lt\lambda_{k-1}$, equality $\sum_{j\ge k}\lambda_jc_j^2=\lambda_k$ forces $c_j=0$ for $j\gt k$, so $a=\pm e_k$; if $\lambda_k$ is repeated, every unit vector of the eigenspace gives equality. ∎
The ratio $a^{\mathsf T}\Sigma a/a^{\mathsf T}a$ is the Rayleigh quotient of $\Sigma$; the theorem is the Rayleigh–Ritz characterisation of eigenvalues, read statistically. In matrix form, $Y=E^{\mathsf T}(X-\mu)$ is an orthogonal change of coordinates — a rotation (possibly with reflections) of the axes to the principal axes of the ellipsoids $\{x:(x-\mu)^{\mathsf T}\Sigma^{-1}(x-\mu)=c^2\}$, which are the contours of the $N_p(\mu,\Sigma)$ density (§7.1). The $k$-th semi-axis of such an ellipsoid has length $c\sqrt{\lambda_k}$ along $e_k$.
With the notation of Theorem 7.26 and $Y=E^{\mathsf T}(X-\mu)$:
- Total and generalised variance are preserved: $\sum_{k=1}^p\operatorname{Var}(Y_k)=\sum_k\lambda_k=\operatorname{tr}\Sigma=\sum_i\sigma_{ii}$, and $\prod_k\lambda_k=\det\Sigma$.
- Reconstruction: $X=\mu+\sum_{k=1}^pY_ke_k$.
- Loadings as correlations: $\operatorname{Cov}(Y_k,X_i)=\lambda_ke_{ik}$, where $e_{ik}$ is the $i$-th entry of $e_k$; hence, if $\sigma_{ii}\gt0$ and $\lambda_k\gt0$,
- Bounds by the diagonal: $\lambda_1\ge\max_i\sigma_{ii}$ and $\lambda_p\le\min_i\sigma_{ii}$.
- Normal case: if $X\sim N_p(\mu,\Sigma)$, then $Y_1,\dots,Y_p$ are independent, $Y_k\sim N(0,\lambda_k)$.
Proof. (1) $\operatorname{Cov}(Y)=E^{\mathsf T}\Sigma E=\Lambda$, so $\sum\operatorname{Var}(Y_k)=\operatorname{tr}\Lambda$ $=\operatorname{tr}(E^{\mathsf T}\Sigma E)$ $=\operatorname{tr}(\Sigma EE^{\mathsf T})=\operatorname{tr}\Sigma$, and $\det\Lambda=\det(E^{\mathsf T})\det\Sigma\det E=\det\Sigma$ because $\det E=\pm1$. (2) $EE^{\mathsf T}=I$, so $X-\mu=EY=\sum_kY_ke_k$. (3) With $u_i$ the $i$-th standard basis vector, $\operatorname{Cov}(Y_k,X_i)=e_k^{\mathsf T}\Sigma u_i=\lambda_ke_k^{\mathsf T}u_i=\lambda_ke_{ik}$; divide by $\sqrt{\lambda_k\sigma_{ii}}$. (4) Take $a=u_i$ in Theorem 7.26: $\lambda_p\le u_i^{\mathsf T}\Sigma u_i=\sigma_{ii}\le\lambda_1$. (5) $Y$ is a linear transformation of a normal vector, hence normal (§7.1), with diagonal covariance $\Lambda$; uncorrelated components of a jointly normal vector are independent. ∎
Why keep only the first few components? Because they give the best low-dimensional picture of $X$ in a precise sense: no other $k$-dimensional projection loses less of the total variance.
Let $1\le k\le p$ and let $A$ be any $p\times k$ matrix with orthonormal columns, so that $P=AA^{\mathsf T}$ is the orthogonal projection onto a $k$-dimensional subspace. Then
$$E\big\|(X-\mu)-P(X-\mu)\big\|^2=\operatorname{tr}\Sigma-\operatorname{tr}(A^{\mathsf T}\Sigma A)$$ $$\ge\sum_{j=k+1}^p\lambda_j,$$with equality when the columns of $A$ are $e_1,\dots,e_k$. For data, with $\Sigma$ replaced by $S$: among all $k$-dimensional affine subspaces through $\bar x$, the one spanned by the first $k$ sample principal directions minimises the sum of squared perpendicular distances $\sum_i\|(x_i-\bar x)-P(x_i-\bar x)\|^2$, and the minimum is $(n-1)\sum_{j\gt k}\hat\lambda_j$.
Proof. Write $W=X-\mu$. Since $P$ is symmetric and idempotent, $\|W-PW\|^2=W^{\mathsf T}W-W^{\mathsf T}PW$, and $E[W^{\mathsf T}MW]=\operatorname{tr}(M\Sigma)$ for any fixed matrix $M$. So the left side equals $\operatorname{tr}\Sigma-\operatorname{tr}(AA^{\mathsf T}\Sigma)=\operatorname{tr}\Sigma-\operatorname{tr}(A^{\mathsf T}\Sigma A)$. Now
$$\operatorname{tr}(A^{\mathsf T}\Sigma A)=\sum_{j=1}^p\lambda_j\|A^{\mathsf T}e_j\|^2=\sum_{j=1}^p\lambda_jw_j,$$where $w_j=\|A^{\mathsf T}e_j\|^2$ is the squared length of the projection of the unit vector $e_j$ onto the column space of $A$, so $0\le w_j\le1$, and $\sum_jw_j=\operatorname{tr}(A^{\mathsf T}EE^{\mathsf T}A)=\operatorname{tr}(A^{\mathsf T}A)=k$. A sum $\sum\lambda_jw_j$ with $\lambda_1\ge\dots\ge\lambda_p$, weights in $[0,1]$ and total weight $k$ is largest when the weight is put on the $k$ largest $\lambda$'s: indeed $$\sum_{j\le k}\lambda_j-\sum_j\lambda_jw_j=\sum_{j\le k}\lambda_j(1-w_j)-\sum_{j\gt k}\lambda_jw_j$$ $$\ge\lambda_k\Big(\sum_{j\le k}(1-w_j)-\sum_{j\gt k}w_j\Big)=\lambda_k(k-k)=0.$$ Hence $\operatorname{tr}(A^{\mathsf T}\Sigma A)\le\lambda_1+\dots+\lambda_k$, which is the inequality; for $A=(e_1,\dots,e_k)$, $w_j=1$ for $j\le k$ and $0$ otherwise, giving equality. The data version is the same computation with the empirical distribution of the $x_i$ in place of the law of $X$ (expectation becomes $\frac1{n-1}\sum_i$, $\mu$ becomes $\bar x$, $\Sigma$ becomes $S$). ∎
So the first principal component line is the orthogonal regression line: it minimises perpendicular distances, treating all variables symmetrically. The least-squares line of $x_2$ on $x_1$ (§6.3) minimises vertical distances instead, and the two lines differ unless the points are collinear (Exercise I.8).
Let $S=\sum_j\hat\lambda_j\hat e_j\hat e_j^{\mathsf T}$ with $\hat\lambda_1\ge\dots\ge\hat\lambda_p\ge0$. The sample principal components are $\hat y_k=\hat e_k^{\mathsf T}(x-\bar x)$; the numbers $\hat y_{ik}=\hat e_k^{\mathsf T}(x_i-\bar x)$ are the scores of observation $i$. The proportion of variance explained by the first $k$ components is
$$\frac{\hat\lambda_1+\dots+\hat\lambda_k}{\hat\lambda_1+\dots+\hat\lambda_p}=\frac{\hat\lambda_1+\dots+\hat\lambda_k}{\operatorname{tr}S}.$$A scree plot is the graph of $\hat\lambda_k$ against $k$. PCA on the correlation matrix means PCA of the standardised variables $z_{ij}=(x_{ij}-\bar x_j)/\sqrt{s_{jj}}$, whose covariance matrix is the sample correlation matrix $R$; then $\operatorname{tr}R=p$ and the proportion explained by component $k$ is $\hat\lambda_k/p$.
The sample scores have exactly the properties of Theorem 7.27 with respect to the empirical distribution: the $k$-th column of scores has mean $0$ and sample variance $\hat\lambda_k$, and different columns have sample correlation $0$. How many components to keep is a judgement; common rules are: keep enough to explain a stated proportion (often $80$–$90\%$); look for the "elbow" of the scree plot; or, for a correlation matrix, keep components with $\hat\lambda_k\gt1$ (Kaiser's rule — "better than one original variable"), a rule that tends to keep too many when $p/n$ is not small (see the Research–Teaching Nexus). For inference, if $x_1,\dots,x_n$ are iid $N_p(\mu,\Sigma)$ and $\lambda_k$ is a simple eigenvalue of $\Sigma$, then $\sqrt n(\hat\lambda_k-\lambda_k)\to N(0,2\lambda_k^2)$ in distribution (a classical result of T. W. Anderson, stated without proof), which gives the approximate $100(1-\alpha)\%$ interval
$$\frac{\hat\lambda_k}{1+z_{\alpha/2}\sqrt{2/n}}\le\lambda_k\le\frac{\hat\lambda_k}{1-z_{\alpha/2}\sqrt{2/n}}.$$| specimen | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| $x_1$ | 6 | 8 | 10 | 12 | 14 |
| $x_2$ | 3 | 5 | 5 | 7 | 5 |
- Decide between $\Sigma$ (or $S$) and the correlation matrix: use the correlation matrix when the variables are in different units or have very different variances for reasons of scale only.
- Look for structure before computing: a block-diagonal matrix splits into separate smaller problems; for $\begin{pmatrix}a&b\\b&a\end{pmatrix}$ the eigenvectors are $(1,\pm1)/\sqrt2$ with eigenvalues $a\pm b$; for the equicorrelation matrix $(1-\rho)I+\rho\mathbf 1\mathbf 1^{\mathsf T}$ they are $1+(p-1)\rho$ (eigenvector $\mathbf 1/\sqrt p$) and $1-\rho$ (repeated).
- For a $2\times2$ matrix use $\lambda^2-(\operatorname{tr})\lambda+\det=0$; check every answer with $\sum\lambda_j=\operatorname{tr}$ and $\prod\lambda_j=\det$.
- Proportions of variance use $\operatorname{tr}$ ($=p$ for a correlation matrix), never the largest diagonal entries.
- For interpretation, convert loadings to correlations $e_{ik}\sqrt{\lambda_k}/\sqrt{\sigma_{ii}}$; for each variable their squares sum to $1$ over $k$.
Discriminant Analysis and Classification
A bank must decide from an applicant's financial ratios whether to treat the applicant as a likely defaulter; a botanist assigns a specimen to one of two species from its measurements; a screening test labels a patient as healthy or diseased from several blood markers. In each case there are known populations, training data from each, and a new observation $x$ to be allocated. We first find the best possible rule when the populations are known, and then Fisher's sample rule.
Two populations $\mathcal P_1,\mathcal P_2$ have densities $f_1,f_2$ on $\mathbb{R}^p$ and prior probabilities $\pi_1,\pi_2$ ($\pi_1+\pi_2=1$). A classification rule is a partition $\mathbb{R}^p=R_1\cup R_2$: an observation in $R_k$ is allocated to $\mathcal P_k$. The misclassification probabilities are
$$P(2\mid1)=\int_{R_2}f_1(x)\,dx,$$ $$P(1\mid2)=\int_{R_1}f_2(x)\,dx .$$If allocating a member of $\mathcal P_1$ to $\mathcal P_2$ costs $c(2\mid1)\gt0$ and the reverse error costs $c(1\mid2)\gt0$, the expected cost of misclassification is $\mathrm{ECM}=c(2\mid1)\pi_1P(2\mid1)+c(1\mid2)\pi_2P(1\mid2)$. With equal costs it is proportional to the total probability of misclassification $\mathrm{TPM}=\pi_1P(2\mid1)+\pi_2P(1\mid2)$.
The rule
$$R_1=\Big\{x:\ \frac{f_1(x)}{f_2(x)}\ge k\Big\},\qquad k=\frac{c(1\mid2)\,\pi_2}{c(2\mid1)\,\pi_1},$$and $R_2$ its complement (with $f_1/f_2=+\infty$ where $f_2=0\lt f_1$), minimises the ECM among all classification rules. Points with $f_1(x)=kf_2(x)$ may be allocated either way without changing the ECM. With equal costs and equal priors, the rule allocates $x$ to the population with the larger density: it is the likelihood ratio rule.
Proof. For any rule, $P(2\mid1)=1-\int_{R_1}f_1$, so
$$\mathrm{ECM}=c(2\mid1)\pi_1$$ $$+\int_{R_1}\big[c(1\mid2)\pi_2f_2(x)-c(2\mid1)\pi_1f_1(x)\big]dx .$$The first term does not depend on the rule. The integral is smallest when $R_1$ contains every point where the integrand is negative and no point where it is positive, i.e. $R_1=\{x:c(2\mid1)\pi_1f_1(x)\ge c(1\mid2)\pi_2f_2(x)\}$ up to the set where the integrand is $0$, which contributes nothing. Dividing by $c(2\mid1)\pi_1f_2(x)$ gives the stated form. ∎
The same argument with $g$ populations shows that, with equal costs, the rule "allocate $x$ to the $k$ that maximises $\pi_kf_k(x)$" — equivalently, to the population with the largest posterior probability $P(\mathcal P_k\mid x)$ — minimises the total probability of misclassification. This is the Bayes classifier; it is the Neyman–Pearson lemma (§5.1) in another guise, with the threshold $k$ fixed by priors and costs instead of by a size.
Let $f_k$ be the $N_p(\mu_k,\Sigma)$ density, $k=1,2$, with $\Sigma$ positive definite and $\mu_1\ne\mu_2$. Put
$$a=\Sigma^{-1}(\mu_1-\mu_2),$$ $$W(x)=a^{\mathsf T}\Big(x-\frac{\mu_1+\mu_2}{2}\Big).$$Then $\log\{f_1(x)/f_2(x)\}=W(x)$, so the minimum-ECM rule allocates $x$ to $\mathcal P_1$ iff $W(x)\ge\log k$: the boundary is a hyperplane. Under $\mathcal P_1$, $W(X)\sim N(\tfrac12\Delta^2,\Delta^2)$ and under $\mathcal P_2$, $W(X)\sim N(-\tfrac12\Delta^2,\Delta^2)$, where $\Delta^2=(\mu_1-\mu_2)^{\mathsf T}\Sigma^{-1}(\mu_1-\mu_2)$ is the Mahalanobis distance (§7.1). Hence
$$P(2\mid1)=\Phi\Big(\frac{\log k-\Delta^2/2}{\Delta}\Big),$$ $$P(1\mid2)=\Phi\Big(\frac{-\log k-\Delta^2/2}{\Delta}\Big),$$and with $k=1$ (equal priors and costs) both equal $\Phi(-\Delta/2)$, which decreases to $0$ as $\Delta\to\infty$.
Proof. The normalising constants of $f_1$ and $f_2$ are equal, so
$$\log\frac{f_1(x)}{f_2(x)}=-\tfrac12(x-\mu_1)^{\mathsf T}\Sigma^{-1}(x-\mu_1)$$ $$+\tfrac12(x-\mu_2)^{\mathsf T}\Sigma^{-1}(x-\mu_2).$$Expanding, the quadratic terms $x^{\mathsf T}\Sigma^{-1}x$ cancel, leaving $(\mu_1-\mu_2)^{\mathsf T}\Sigma^{-1}x-\frac12(\mu_1^{\mathsf T}\Sigma^{-1}\mu_1-\mu_2^{\mathsf T}\Sigma^{-1}\mu_2)$. Since $\Sigma^{-1}$ is symmetric, $\mu_1^{\mathsf T}\Sigma^{-1}\mu_1-\mu_2^{\mathsf T}\Sigma^{-1}\mu_2=(\mu_1-\mu_2)^{\mathsf T}\Sigma^{-1}(\mu_1+\mu_2)$, so the log ratio is $a^{\mathsf T}x-\frac12a^{\mathsf T}(\mu_1+\mu_2)=W(x)$. The rule follows from Theorem 7.29. $W(X)$ is a linear function of a normal vector, hence normal; under $\mathcal P_1$ its mean is $a^{\mathsf T}(\mu_1-\frac{\mu_1+\mu_2}2)=\frac12a^{\mathsf T}(\mu_1-\mu_2)=\frac12\Delta^2$, under $\mathcal P_2$ it is $-\frac12\Delta^2$, and in both cases its variance is $a^{\mathsf T}\Sigma a=(\mu_1-\mu_2)^{\mathsf T}\Sigma^{-1}\Sigma\Sigma^{-1}(\mu_1-\mu_2)=\Delta^2$. Then $P(2\mid1)=P(W\lt\log k\mid\mathcal P_1)$ $=\Phi\big((\log k-\frac12\Delta^2)/\Delta\big)$ and $P(1\mid2)=P(W\ge\log k\mid\mathcal P_2)$ $=1-\Phi\big((\log k+\frac12\Delta^2)/\Delta\big)$, which is the stated value by $1-\Phi(t)=\Phi(-t)$. ∎
If the covariance matrices differ, $\Sigma_1\ne\Sigma_2$, the quadratic terms no longer cancel and the optimal boundary is the quadric $$-\tfrac12x^{\mathsf T}(\Sigma_1^{-1}-\Sigma_2^{-1})x$$ $$+(\mu_1^{\mathsf T}\Sigma_1^{-1}-\mu_2^{\mathsf T}\Sigma_2^{-1})x-\kappa=\log k,$$ where $\kappa=\frac12\log\frac{\det\Sigma_1}{\det\Sigma_2}$ $+\frac12(\mu_1^{\mathsf T}\Sigma_1^{-1}\mu_1-\mu_2^{\mathsf T}\Sigma_2^{-1}\mu_2)$: this is quadratic discriminant analysis (Exercise II.3).
In practice $\mu_1,\mu_2,\Sigma$ are unknown. R. A. Fisher (1936) found the same linear rule from a distribution-free argument: look for the linear combination $y=a^{\mathsf T}x$ whose two group means are as far apart as possible relative to the spread within the groups.
Let $x_{11},\dots,x_{1n_1}$ and $x_{21},\dots,x_{2n_2}$ be training samples from $\mathcal P_1$ and $\mathcal P_2$, with means $\bar x_1,\bar x_2$, covariance matrices $S_1,S_2$, and pooled covariance matrix
$$S_{\text{pl}}=\frac{(n_1-1)S_1+(n_2-1)S_2}{n_1+n_2-2},$$assumed positive definite. Write $d=\bar x_1-\bar x_2$. For $a\ne0$ the separation ratio of $y=a^{\mathsf T}x$ is $J(a)=(a^{\mathsf T}d)^2/(a^{\mathsf T}S_{\text{pl}}a)$: the squared difference of the group means of $y$ divided by the pooled sample variance of $y$. Fisher's linear discriminant function is $\hat y=\hat a^{\mathsf T}x$ with $\hat a=S_{\text{pl}}^{-1}d$, and Fisher's rule allocates $x_0$ to $\mathcal P_1$ iff
$$\hat a^{\mathsf T}x_0\ge\hat m,\qquad\hat m=\tfrac12\hat a^{\mathsf T}(\bar x_1+\bar x_2).$$For every $a\ne0$,
$$J(a)=\frac{(a^{\mathsf T}d)^2}{a^{\mathsf T}S_{\text{pl}}a}\le d^{\mathsf T}S_{\text{pl}}^{-1}d=D^2,$$with equality iff $a=cS_{\text{pl}}^{-1}d$ for some $c\ne0$. The maximum $D^2$ is the sample Mahalanobis distance between the group means. Fisher's rule is the minimum-ECM rule of Theorem 7.30 with equal priors and costs, after replacing $\mu_1,\mu_2,\Sigma$ by $\bar x_1,\bar x_2,S_{\text{pl}}$; with priors and costs one compares $\hat a^{\mathsf T}x_0-\hat m$ with $\log k$. The two-sample Hotelling statistic of §7.2 is $T^2=\frac{n_1n_2}{n_1+n_2}D^2$, so the test of $H_0:\mu_1=\mu_2$ is also a test of whether the discriminant separates the populations at all.
Proof. $S_{\text{pl}}$ is positive definite, so $S_{\text{pl}}^{1/2}$ and $S_{\text{pl}}^{-1/2}$ exist. Put $u=S_{\text{pl}}^{1/2}a$ and $v=S_{\text{pl}}^{-1/2}d$. Then $a^{\mathsf T}d=u^{\mathsf T}v$ and $a^{\mathsf T}S_{\text{pl}}a=u^{\mathsf T}u$, so by the Cauchy–Schwarz inequality
$$(a^{\mathsf T}d)^2=(u^{\mathsf T}v)^2\le(u^{\mathsf T}u)(v^{\mathsf T}v)$$ $$=(a^{\mathsf T}S_{\text{pl}}a)\,(d^{\mathsf T}S_{\text{pl}}^{-1}d),$$with equality iff $u=cv$, i.e. $a=cS_{\text{pl}}^{-1/2}S_{\text{pl}}^{-1/2}d=cS_{\text{pl}}^{-1}d$. With $\hat a=S_{\text{pl}}^{-1}d$, the plug-in version of $W(x)$ in Theorem 7.30 is $d^{\mathsf T}S_{\text{pl}}^{-1}(x-\frac{\bar x_1+\bar x_2}2)=\hat a^{\mathsf T}x-\hat m$, so the two rules coincide. The last statement is the definition of $T^2$ in §7.2 with $D^2$ substituted. ∎
Notice what the proof does not use: normality. Fisher's discriminant is the best linear separator in the sense of $J$ for any distributions with a common covariance matrix; normality is what makes it the optimal classifier and gives the error rates $\Phi(-\Delta/2)$. The rule is also invariant under nonsingular linear changes of the variables (Example 4(c)), unlike principal components.
- If $\mathcal P_k=N_p(\mu_k,\Sigma)$, $k=1,\dots,g$, with priors $\pi_k$ and equal costs, the Bayes rule allocates $x$ to the population with the largest linear discriminant score $d_k(x)=\mu_k^{\mathsf T}\Sigma^{-1}x-\frac12\mu_k^{\mathsf T}\Sigma^{-1}\mu_k+\log\pi_k$. With equal priors this is the population whose mean is nearest to $x$ in Mahalanobis distance.
- For training samples of sizes $n_1,\dots,n_g$ ($n=\sum n_k$), let $B=\sum_kn_k(\bar x_k-\bar x)(\bar x_k-\bar x)^{\mathsf T}$ and $W=\sum_k\sum_j(x_{kj}-\bar x_k)(x_{kj}-\bar x_k)^{\mathsf T}$ be the between- and within-group matrices, $W$ positive definite. The ratio $a^{\mathsf T}Ba/a^{\mathsf T}Wa$ is maximised by an eigenvector of $W^{-1}B$ for its largest eigenvalue; the successive Fisher discriminants are the eigenvectors of $W^{-1}B$, and at most $\min(g-1,p)$ eigenvalues are nonzero. For $g=2$, $B=\frac{n_1n_2}{n}dd^{\mathsf T}$ and the single discriminant is $W^{-1}d\propto S_{\text{pl}}^{-1}d$.
Proof. (1) $\log(\pi_kf_k(x))=d_k(x)-\frac12x^{\mathsf T}\Sigma^{-1}x+\text{const}$, and the last two terms are the same for every $k$; maximise $\pi_kf_k$ as in the remark after Theorem 7.29. With equal priors, $-2d_k(x)+x^{\mathsf T}\Sigma^{-1}x=(x-\mu_k)^{\mathsf T}\Sigma^{-1}(x-\mu_k)$. (2) Put $b=W^{1/2}a$: the ratio becomes $b^{\mathsf T}Mb/b^{\mathsf T}b$ with $M=W^{-1/2}BW^{-1/2}$ symmetric, a Rayleigh quotient maximised by the top eigenvector of $M$ (Theorem 7.26). If $Mb=\lambda b$ then $W^{-1}B(W^{-1/2}b)=W^{-1/2}Mb=\lambda W^{-1/2}b$, so $a=W^{-1/2}b$ is an eigenvector of $W^{-1}B$ with the same eigenvalue. The vectors $\bar x_k-\bar x$ satisfy $\sum_kn_k(\bar x_k-\bar x)=0$, so they span a space of dimension at most $g-1$; hence $\operatorname{rank}B\le\min(g-1,p)$, and $M$ has at most that many nonzero eigenvalues. For $g=2$, $\bar x_1-\bar x=\frac{n_2}{n}d$ and $\bar x_2-\bar x=-\frac{n_1}{n}d$, which gives $B=\frac{n_1n_2}{n}dd^{\mathsf T}$; then $W^{-1}Ba\propto W^{-1}d$ for every $a$, and $W=(n-2)S_{\text{pl}}$. ∎
Estimating the error rate. The apparent error rate — the proportion of training observations misclassified by a rule built from those same observations — is optimistic, because the rule was tuned to them. Honest estimates use a separate test sample or leave-one-out (Lachenbruch's method): classify each $x_i$ by the rule computed without $x_i$ and count the errors (Exercise II.8). Under normality, $\Phi(-D/2)$ also estimates the error rate, but it is biased downwards for small samples because $D^2$ overestimates $\Delta^2$.
(b) For $p=2$ and $\rho_{12}\gt0$, the first principal component of the correlation matrix is always $(Z_1+Z_2)/\sqrt2$.
(c) Fisher's rule is unchanged if every observation $x$ is replaced by $Cx+c$ with $C$ nonsingular.
(d) If two populations have equal mean vectors, no linear rule $\{a^{\mathsf T}x\ge t\}$ has $P(2\mid1)+P(1\mid2)\lt1$.
Cluster Analysis
Discriminant analysis starts from labelled groups. Cluster analysis looks for groups that nobody has labelled: market segments among customers, subtypes of a disease among patients, communities among species sampled at different sites. The starting point is a measure of how unlike two objects are.
A dissimilarity on objects $1,\dots,n$ is a function $d$ with $d(i,j)=d(j,i)\ge0$ and $d(i,i)=0$; it is a metric if also $d(i,k)\le d(i,j)+d(j,k)$, and an ultrametric if $d(i,k)\le\max\{d(i,j),d(j,k)\}$. Common choices for $x_i,x_j\in\mathbb{R}^p$ are the Euclidean distance $\|x_i-x_j\|$, the city-block distance $\sum_l|x_{il}-x_{jl}|$, Euclidean distance after standardising each variable, and the Mahalanobis distance $\sqrt{(x_i-x_j)^{\mathsf T}S^{-1}(x_i-x_j)}$. For binary attributes, with $a$ = number of attributes present in both objects, $b$ and $c$ = present in only one, and $e$ = absent from both, the simple matching similarity is $(a+e)/(a+b+c+e)$ and the Jaccard similarity is $a/(a+b+c)$; a dissimilarity is $1-$similarity.
Start with the $n$ singleton clusters. At each step, merge the two clusters $A,B$ with the smallest inter-cluster distance $D(A,B)$, record the merge height $h=D(A,B)$, and repeat until one cluster remains ($n-1$ merges). The linkage defines $D$ from $d$:
- single linkage (nearest neighbour): $D(A,B)=\min\{d(i,j):i\in A,j\in B\}$;
- complete linkage (furthest neighbour): $D(A,B)=\max\{d(i,j):i\in A,j\in B\}$;
- average linkage (UPGMA): $D(A,B)=\frac1{|A||B|}\sum_{i\in A}\sum_{j\in B}d(i,j)$;
- centroid linkage: $D(A,B)=\|\bar x_A-\bar x_B\|$; Ward's method: $D(A,B)$ is the increase in the within-cluster sum of squares caused by merging $A$ and $B$.
The dendrogram is the tree that draws each merge as a horizontal bar at its height joining the two merged clusters. Cutting it at a level $h$ gives a partition into clusters. The cophenetic distance $c(i,j)$ is the height at which $i$ and $j$ first belong to the same cluster.
For single, complete and average linkage:
- after $A$ and $B$ merge, $\min\{D(A,C),D(B,C)\}$ $\le D(A\cup B,C)$ $\le\max\{D(A,C),D(B,C)\}$ for every other cluster $C$;
- the successive merge heights are non-decreasing: $h_1\le h_2\le\dots\le h_{n-1}$;
- the cophenetic distance is an ultrametric: $c(i,k)\le\max\{c(i,j),c(j,k)\}$ for all $i,j,k$.
For centroid linkage (2) can fail: a later merge can occur at a smaller height (an inversion).
Proof. (1) For single and complete linkage, $D(A\cup B,C)$ is the minimum or the maximum over the pairs in $(A\times C)\cup(B\times C)$, i.e. $\min$ or $\max$ of $D(A,C)$ and $D(B,C)$. For average linkage, splitting the double sum,
$$D(A\cup B,C)=\frac{|A|\,D(A,C)+|B|\,D(B,C)}{|A|+|B|},$$a weighted mean, which lies between the two values. (2) Let $A,B$ merge at height $h=D(A,B)$, the minimum of $D$ over all pairs of current clusters. After the merge, the distances between clusters not involving $A\cup B$ are unchanged and hence $\ge h$, and by (1) $D(A\cup B,C)\ge\min\{D(A,C),D(B,C)\}\ge h$. So every distance between the new clusters is $\ge h$, and the next merge height is $\ge h$. (3) Let $h=\max\{c(i,j),c(j,k)\}$ and let $t$ be the later of the two merge steps at which $i,j$ and $j,k$ first share a cluster. After step $t$ (clusters only grow), $i$ and $j$ are in one cluster and $j$ and $k$ are in one cluster, which must be the same cluster; so $i$ and $k$ were joined at step $t$ or earlier, at a height $\le h_t=h$ by (2). ∎
The centroid counterexample: three points at the vertices of an equilateral triangle of side $1$. The first merge joins two of them at height $1$; their centroid is the midpoint of a side, at distance $\sqrt3/2=0.866$ from the third vertex, so the second merge happens at $0.866\lt1$ and the dendrogram crosses itself (Exercise III.3). Ward's method is monotone (its update formula, of Lance–Williams type, gives $D(A\cup B,C)\ge D(A,B)$ by the same argument).
For $h\ge0$ let $G_h$ be the graph on the objects with an edge $\{i,j\}$ whenever $d(i,j)\le h$. The clusters obtained by performing all single-linkage merges of height at most $h$ are exactly the connected components of $G_h$. Consequently, the $n-1$ single-linkage merge heights are the edge lengths of a minimum spanning tree of the complete graph with edge weights $d(i,j)$.
Proof. Each single-linkage merge of $A$ and $B$ at height $D(A,B)\le h$ is caused by a pair $i\in A,j\in B$ with $d(i,j)=D(A,B)\le h$, i.e. an edge of $G_h$ between them; by induction every cluster formed by merges of height $\le h$ is connected in $G_h$. Conversely, by Theorem 7.33(2) the merges of height $\le h$ are exactly the first ones, and when they are finished every remaining pair of clusters has $D\gt h$ — otherwise a further merge of height $\le h$ would occur. So no edge of $G_h$ joins two different clusters, and each cluster is a union of components of $G_h$. Being connected, each cluster is exactly one component. For the last statement: single linkage examines the pairs in increasing order of $d$ and joins two clusters whenever the pair links different clusters; this is Kruskal's algorithm for the minimum spanning tree, whose accepted edges have lengths equal to the merge heights. ∎
This explains the chaining behaviour of single linkage: two dense groups joined by a thin chain of intermediate points are merged at the small height of the chain's links. Complete linkage favours compact clusters of similar diameter; average linkage is a compromise.
Hierarchical methods give a whole family of partitions. If the number $K$ of clusters is fixed in advance, one can instead optimise a criterion directly.
For data $x_1,\dots,x_n\in\mathbb{R}^p$ and a partition $\mathcal C=\{C_1,\dots,C_K\}$ into nonempty clusters with means $\bar x_k$, the within-cluster, between-cluster and total sums of squares are
$$W(\mathcal C)=\sum_{k=1}^K\sum_{i\in C_k}\|x_i-\bar x_k\|^2,$$ $$B(\mathcal C)=\sum_{k=1}^K|C_k|\,\|\bar x_k-\bar x\|^2,$$ $$T=\sum_{i=1}^n\|x_i-\bar x\|^2 .$$$k$-means clustering seeks a partition minimising $W(\mathcal C)$. Lloyd's algorithm starts from $K$ centres $c_1,\dots,c_K$ and repeats two steps until nothing changes: assignment — put each $x_i$ in the cluster of its nearest centre (keeping its current cluster in case of a tie); update — replace each centre by the mean of its cluster.
- For any finite set $C$ and any $c\in\mathbb{R}^p$: $\sum_{i\in C}\|x_i-c\|^2$ $=\sum_{i\in C}\|x_i-\bar x_C\|^2+|C|\,\|\bar x_C-c\|^2$. So the mean is the unique best centre.
- For every partition, $T=W(\mathcal C)+B(\mathcal C)$; minimising $W$ is the same as maximising $B$.
- Each step of Lloyd's algorithm does not increase $\Phi(\mathcal C,c)=\sum_k\sum_{i\in C_k}\|x_i-c_k\|^2$. As long as no cluster becomes empty, the algorithm stops after finitely many steps at a partition in which every point is at least as close to its own cluster mean as to any other mean.
- The limit depends on the starting centres and need not minimise $W$ (Example 6).
Proof. (1) Write $x_i-c=(x_i-\bar x_C)+(\bar x_C-c)$ and expand: the cross term is $2(\bar x_C-c)^{\mathsf T}\sum_{i\in C}(x_i-\bar x_C)=0$. (2) Apply (1) to each cluster with $c=\bar x$ and add: $\sum_k\sum_{i\in C_k}\|x_i-\bar x\|^2$ $=\sum_k\big(\sum_{i\in C_k}\|x_i-\bar x_k\|^2+|C_k|\|\bar x_k-\bar x\|^2\big)$, i.e. $T=W+B$; $T$ does not depend on the partition. (3) The assignment step minimises $\Phi(\cdot,c)$ for fixed centres, since each term $\|x_i-c_{k(i)}\|^2$ is minimised separately; the update step minimises $\Phi(\mathcal C,\cdot)$ for a fixed partition by (1). Hence $\Phi$ never increases. After an update, $\Phi(\mathcal C,c)=W(\mathcal C)$. If the next assignment changes the partition to $\mathcal C'$, some point has moved to a strictly nearer centre (ties keep the old cluster), so $\Phi(\mathcal C',c)\lt\Phi(\mathcal C,c)$, and after the following update $W(\mathcal C')\le\Phi(\mathcal C',c)\lt W(\mathcal C)$. Thus $W$ strictly decreases each time the partition changes, no partition can occur twice, and since there are finitely many partitions the algorithm stops; at that point no point is strictly closer to another mean. (4) is shown by Example 6. ∎
In practice $k$-means is run from many random starts and the best result kept. Because $W$ always decreases as $K$ grows (Exercise III.6), $K$ is chosen by other criteria: an "elbow" in the plot of the minimum $W$ against $K$, the ratio $B/T$, the silhouette width, or the gap statistic. $k$-means implicitly assumes compact, roughly spherical clusters of similar spread, and it depends on the scale of the variables, like PCA.
Canonical Correlation Analysis
Sometimes the variables come in two natural blocks: physical measurements and performance scores of athletes, climate variables and crop yields, a set of blood tests and a set of symptoms. Canonical correlation analysis (H. Hotelling, 1936) asks for the linear combination of the first block that is most correlated with a linear combination of the second, and then for further pairs carrying new information. In this subsection $X$ is a $p$-vector and $Y$ a $q$-vector, and $Y$ no longer denotes principal components. Write
$$\operatorname{Cov}\begin{pmatrix}X\\Y\end{pmatrix}=\begin{pmatrix}\Sigma_{11}&\Sigma_{12}\\\Sigma_{21}&\Sigma_{22}\end{pmatrix},\qquad\Sigma_{21}=\Sigma_{12}^{\mathsf T},$$with $\Sigma_{11}$ and $\Sigma_{22}$ positive definite, and $m=\min(p,q)$.
The first pair of canonical variates is a pair $U_1=a_1^{\mathsf T}X$, $V_1=b_1^{\mathsf T}Y$ with $\operatorname{Var}(U_1)=\operatorname{Var}(V_1)=1$ that maximises $\operatorname{corr}(a^{\mathsf T}X,b^{\mathsf T}Y)$; the maximum $\rho_1^*$ is the first canonical correlation. For $k=2,\dots,m$, the $k$-th pair $(U_k,V_k)$ maximises the same correlation subject to unit variances and to $U_k$ being uncorrelated with $U_1,\dots,U_{k-1}$ and $V_k$ with $V_1,\dots,V_{k-1}$; the maximum is $\rho_k^*$.
Let $K=\Sigma_{11}^{-1/2}\Sigma_{12}\Sigma_{22}^{-1/2}$ (a $p\times q$ matrix) have singular value decomposition $K=\sum_{j=1}^m\rho_ju_jv_j^{\mathsf T}$ with $\rho_1\ge\dots\ge\rho_m\ge0$, orthonormal $u_1,\dots,u_m\in\mathbb{R}^p$ and orthonormal $v_1,\dots,v_m\in\mathbb{R}^q$. Then $\rho_k^*=\rho_k$, and the canonical variates are
$$U_k=u_k^{\mathsf T}\Sigma_{11}^{-1/2}X,\qquad V_k=v_k^{\mathsf T}\Sigma_{22}^{-1/2}Y .$$Equivalently, $\rho_1^{*2}\ge\dots\ge\rho_m^{*2}$ are the $m$ largest eigenvalues of
$$\Sigma_{11}^{-1}\Sigma_{12}\Sigma_{22}^{-1}\Sigma_{21}\quad(p\times p),$$and $a_k$ is a corresponding eigenvector, normalised by $a_k^{\mathsf T}\Sigma_{11}a_k=1$; then $b_k\propto\Sigma_{22}^{-1}\Sigma_{21}a_k$. The canonical variates satisfy $\operatorname{corr}(U_k,V_l)=0$ for $k\ne l$ as well.
Proof. Put $c=\Sigma_{11}^{1/2}a$ and $d=\Sigma_{22}^{1/2}b$. Then $\operatorname{Var}(a^{\mathsf T}X)=c^{\mathsf T}c$, $\operatorname{Var}(b^{\mathsf T}Y)=d^{\mathsf T}d$ and $\operatorname{Cov}(a^{\mathsf T}X,b^{\mathsf T}Y)=a^{\mathsf T}\Sigma_{12}b=c^{\mathsf T}Kd$, so the problem is to maximise $c^{\mathsf T}Kd$ over unit vectors $c,d$. Using the SVD and then Cauchy–Schwarz,
$$c^{\mathsf T}Kd=\sum_{j=1}^m\rho_j(c^{\mathsf T}u_j)(v_j^{\mathsf T}d)$$ $$\le\rho_1\Big(\sum_j(c^{\mathsf T}u_j)^2\Big)^{1/2}\Big(\sum_j(v_j^{\mathsf T}d)^2\Big)^{1/2}\le\rho_1,$$because $\sum_j(c^{\mathsf T}u_j)^2\le\|c\|^2=1$ (Bessel's inequality) and likewise for $d$. Equality holds at $c=u_1$, $d=v_1$, so $\rho_1^*=\rho_1$ with $a_1=\Sigma_{11}^{-1/2}u_1$, $b_1=\Sigma_{22}^{-1/2}v_1$. For the $k$-th pair, $\operatorname{Cov}(a^{\mathsf T}X,U_j)=a^{\mathsf T}\Sigma_{11}\Sigma_{11}^{-1/2}u_j=c^{\mathsf T}u_j$, so the constraints say $c\perp u_1,\dots,u_{k-1}$ and similarly $d\perp v_1,\dots,v_{k-1}$. The terms $j\lt k$ of the sum then vanish and the same estimate gives $c^{\mathsf T}Kd\le\rho_k$, with equality at $(u_k,v_k)$. Moreover $\operatorname{Cov}(U_k,V_l)=u_k^{\mathsf T}Kv_l=\rho_l\,u_k^{\mathsf T}u_l=0$ for $k\ne l$. Finally, $KK^{\mathsf T}u_k=\rho_k^2u_k$ reads $\Sigma_{11}^{-1/2}\Sigma_{12}\Sigma_{22}^{-1}\Sigma_{21}\Sigma_{11}^{-1/2}u_k=\rho_k^2u_k$; multiplying on the left by $\Sigma_{11}^{-1/2}$ gives $\Sigma_{11}^{-1}\Sigma_{12}\Sigma_{22}^{-1}\Sigma_{21}a_k=\rho_k^2a_k$, and $K^{\mathsf T}u_k=\rho_kv_k$ gives $b_k=\Sigma_{22}^{-1/2}v_k\propto\Sigma_{22}^{-1}\Sigma_{21}a_k$ when $\rho_k\gt0$. ∎
- Invariance: the canonical correlations of $(AX+\alpha,\ BY+\beta)$ equal those of $(X,Y)$ for all nonsingular $A$ ($p\times p$), $B$ ($q\times q$) and vectors $\alpha,\beta$. In particular they can be computed from correlation matrices.
- Bounds: $0\le\rho_k^*\le1$; $\rho_1^*\ge|\operatorname{corr}(X_i,Y_j)|$ for all $i,j$; and $\rho_1^*\ge R_{Y_j\cdot X}$, the multiple correlation coefficient of $Y_j$ on $X$ (§7.2). If $q=1$, $\rho_1^*=R_{Y\cdot X}$.
- Rank: the number of nonzero canonical correlations is $\operatorname{rank}\Sigma_{12}$; all are $0$ iff $\Sigma_{12}=0$, which for jointly normal $(X,Y)$ means that $X$ and $Y$ are independent.
- $\rho_1^*=1$ iff $a^{\mathsf T}X-b^{\mathsf T}Y$ is almost surely constant for some $a\ne0$, $b\ne0$; this cannot happen when the joint covariance matrix is positive definite.
Proof. (1) As $a$ ranges over $\mathbb{R}^p\setminus\{0\}$, so does $A^{\mathsf T}a$, and $a^{\mathsf T}(AX+\alpha)=(A^{\mathsf T}a)^{\mathsf T}X+\text{const}$. So the families of linear combinations, their correlations and the uncorrelatedness constraints are the same for both pairs of vectors, and the successive maxima coincide. Taking $A,B$ diagonal with entries $1/\sqrt{\sigma_{ii}}$ standardises the variables. (2) $\rho_k^*=\rho_k$ is a correlation, and a maximum over a set containing $a=e_i$ (a standard basis vector), $b=e_j$, so $\rho_1^*\ge\operatorname{corr}(X_i,Y_j)$; replacing $b$ by $-b$ handles the absolute value. If $q=1$, the matrix of Theorem 7.36 has the single nonzero eigenvalue $\sigma_{YX}\Sigma_{11}^{-1}\sigma_{XY}/\sigma_{YY}$ (its trace, since it has rank one), where $\sigma_{XY}=\operatorname{Cov}(X,Y)$; this is the squared multiple correlation $R^2_{Y\cdot X}$ of §7.2, so $\rho_1^*=R_{Y\cdot X}$, the largest correlation between $Y$ and a linear combination of $X$. For general $q$, fixing $b=e_j$ restricts the maximisation to the pair $(X,Y_j)$, whose canonical correlation is $R_{Y_j\cdot X}$; hence $\rho_1^*\ge R_{Y_j\cdot X}$. (3) $\Sigma_{11}^{-1/2}$ and $\Sigma_{22}^{-1/2}$ are nonsingular, so $\operatorname{rank}K=\operatorname{rank}\Sigma_{12}$, which is the number of nonzero singular values. For jointly normal vectors, zero cross-covariance is equivalent to independence (§7.1). (4) A correlation equals $1$ iff the two variables are almost surely linearly related with positive slope; then $(a^{\mathsf T},-b^{\mathsf T})$ times the joint vector has variance $0$, so the joint covariance matrix is singular. ∎
Sample canonical correlations and a test. Replacing $\Sigma$ by the sample covariance (or correlation) matrix gives sample canonical correlations $r_1\ge\dots\ge r_m$ and sample canonical variates. The following result, quoted without the distributional part of the proof, is the standard test.
Let the $n$ observations of $(X,Y)$ be iid $N_{p+q}$ with positive definite covariance matrix and sample correlation matrix $R=\begin{pmatrix}R_{11}&R_{12}\\R_{21}&R_{22}\end{pmatrix}$. The likelihood ratio test of $H_0:\Sigma_{12}=0$ (independence of $X$ and $Y$) rejects for small values of
$$\Lambda=\frac{\det R}{\det R_{11}\,\det R_{22}}=\prod_{k=1}^m(1-r_k^2),$$and under $H_0$, for large $n$, Bartlett's statistic $-\big(n-1-\tfrac12(p+q+1)\big)\log\Lambda$ is approximately $\chi^2_{pq}$. To test that only the first $s$ canonical correlations are nonzero, use
$$-\big(n-1-\tfrac12(p+q+1)\big)\sum_{k=s+1}^m\log(1-r_k^2)$$ $$\approx\ \chi^2_{(p-s)(q-s)} .$$Proof of the identity. By the Schur complement formula, $\det R=\det R_{11}\det(R_{22}-R_{21}R_{11}^{-1}R_{12})$, and $R_{22}-R_{21}R_{11}^{-1}R_{12}=R_{22}^{1/2}(I-\hat K^{\mathsf T}\hat K)R_{22}^{1/2}$ with $\hat K=R_{11}^{-1/2}R_{12}R_{22}^{-1/2}$. The eigenvalues of $\hat K^{\mathsf T}\hat K$ are $r_1^2,\dots,r_m^2$ together with $q-m$ zeros, so $\det(I-\hat K^{\mathsf T}\hat K)=\prod_k(1-r_k^2)$ and $\det R=\det R_{11}\det R_{22}\prod_k(1-r_k^2)$. The ratio is unchanged if $R$ is replaced by $S$, because the diagonal scalings cancel. That this ratio is the likelihood ratio statistic to the power $2/n$ is a standard computation with the normal likelihood: the unrestricted maximum involves $\det\hat\Sigma$, the maximum under $\Sigma_{12}=0$ involves $\det\hat\Sigma_{11}\det\hat\Sigma_{22}$, and the exponential terms are equal. The $\chi^2$ approximation is Wilks' theorem (§5.1) — $H_0$ removes the $pq$ free parameters of $\Sigma_{12}$ — with Bartlett's correction factor improving the approximation. ∎
- PCA depends on the units. With $\Sigma=\begin{pmatrix}1&0.6\\0.6&1\end{pmatrix}$ (both variables in metres) the first component is $(X_1+X_2)/\sqrt2$ with $80\%$ of the variance; record $X_2$ in centimetres and the first component is essentially $X_2$ alone, with $99.99\%$ (Exercise I.7). Covariance-based and correlation-based PCA are different analyses (Example 1).
- Correlation-matrix PCA with $p=2$ always gives $45^\circ$. The directions $(1,\pm1)/\sqrt2$ do not depend on $\rho$; only the eigenvalues $1\pm\rho$ do (Example 4(b), Interactive 1).
- Repeated eigenvalues make components arbitrary. If $\Sigma=\sigma^2I$, every orthonormal basis gives principal components; software output is then an accident of rounding.
- Uncorrelated is not independent. Principal components are always uncorrelated, but independent only under (for example) multivariate normality.
- Large variance is not importance. In regression on principal components, the component that predicts the response can be the one with the smallest variance: if $X_1,X_2$ have equal variances, $\operatorname{corr}(X_1,X_2)=0.99$ and $Y=X_1-X_2$, the response is a function of the second component only.
- The first principal axis is not the regression line. It minimises perpendicular, not vertical, distances; its slope lies strictly between the slopes of the two regression lines when $0\lt|r|\lt1$ (Example 2, Exercise I.8).
- Fisher's direction is not the mean difference. $S_{\text{pl}}^{-1}d$ differs from $d$ unless $d$ is an eigenvector of $S_{\text{pl}}$; in Exercise II.2 the means differ in both variables but the optimal rule uses only $x_1$.
- A variable with no mean difference can still help. Adding $X_2$ with equal means but correlation $0.8$ with $X_1$ raises $\Delta^2$ from $1$ to $2.78$ and lowers the error rate from $0.309$ to $0.202$ (Exam corner E5).
- Equal means do not prevent discrimination when the covariance matrices differ (Example 4(d)); the optimal rule is then quadratic.
- The apparent error rate is optimistic. In Exercise II.8 it is $0$ while leave-one-out gives $25\%$.
- Single linkage chains; centroid linkage inverts. Points $1,2,4,7,11,16$ merge one at a time under single linkage (Exercise III.1); the equilateral triangle gives a centroid-linkage dendrogram whose second merge is lower than its first (Theorem 7.33).
- $k$-means finds local minima (Example 6), always finds clusters even in uniform noise (Interactive 2), splits elongated clusters wrongly, is pulled by outliers, and its $W$ decreases with $K$, so minimising $W$ cannot choose $K$.
- The first canonical correlation can be far larger than every pairwise correlation. With $\operatorname{corr}(X_1,X_2)=0.8$ and $\operatorname{corr}(Y,X_1)=-\operatorname{corr}(Y,X_2)=0.3$, $\rho_1^*=0.949$ (Exercise IV.5). Conversely, canonical weights are not measures of importance: they change with the correlations inside each block.
Exercises
- 1 Find the principal components of $\Sigma=\begin{pmatrix}3&1\\1&3\end{pmatrix}$, the proportion of variance explained by the first, and $\operatorname{corr}(Y_1,X_1)$.
- 2 Find the principal components of $\Sigma=\begin{pmatrix}4&2&0\\2&4&0\\0&0&3\end{pmatrix}$ and the proportions of variance explained by the first one and by the first two.
- 3 Find the eigenvalues and eigenvectors of the equicorrelation matrix $R=(1-\rho)I_p+\rho\mathbf 1\mathbf 1^{\mathsf T}$. For which $\rho$ is $R$ positive definite? For $p=5$, $\rho=0.6$, what proportion of the variance does the first component explain?
- 4 Prove that $\sum_{k=1}^p\operatorname{corr}(Y_k,X_i)^2=1$ for each $i$ when $\Sigma$ is positive definite.
- 5 Show that $\Sigma$ and $\Sigma+cI$ ($c\gt0$) have the same principal directions, and that the proportion of variance explained by the first component is a non-increasing function of $c$. Interpret $\Sigma+cI$.
- 6 A sample of $n=200$ gives $\bar x=(10,20)^{\mathsf T}$ and $S=\begin{pmatrix}4.88&3.84\\3.84&7.12\end{pmatrix}$. Find the sample principal components, the scores of $x_0=(13,24)^{\mathsf T}$, and an approximate $95\%$ confidence interval for $\lambda_1$ under normality.
- 7 Two lengths in metres have $\Sigma=\begin{pmatrix}1&0.6\\0.6&1\end{pmatrix}$. Find the first principal component and its share of the variance. Now record $X_2$ in centimetres. Find the new covariance matrix, the angle between the new first principal direction and the $X_2$-axis, and its share.
- 8 Show that $\sum_i\|(x_i-\bar x)-(a^{\mathsf T}(x_i-\bar x))a\|^2$ $=(n-1)(\operatorname{tr}S-a^{\mathsf T}Sa)$ for every unit vector $a$. For $p=2$ and $s_{12}\gt0$, prove that the slope of the first principal axis lies between the slopes $s_{12}/s_{11}$ (regression of $x_2$ on $x_1$) and $s_{22}/s_{12}$ (regression of $x_1$ on $x_2$, drawn in the same plane). Check with $S=\begin{pmatrix}5&2\\2&2\end{pmatrix}$.
- 9 (Applied) A PCA of six standardised water-quality measurements gives eigenvalues $2.9,\ 1.4,\ 0.8,\ 0.5,\ 0.3,\ 0.1$. Give the cumulative proportions, and the number of components kept by Kaiser's rule and by an $80\%$ rule. Which would you report, and why?
Type a symmetric matrix of size up to $5\times5$, rows separated by semicolons. The lab computes its eigenvalues (Jacobi rotations), unit eigenvectors, the proportions of variance and their cumulative sums, optionally after converting a covariance matrix to a correlation matrix. Use it for Examples 1 and 2 and Exercises I.1–I.3, I.6, I.7.
- 1 $\mathcal P_1=N(0,1)$ and $\mathcal P_2=N(2,1)$, equal costs. Find the optimal rule and its total probability of misclassification (a) with equal priors, (b) with $\pi_1=0.8$, $\pi_2=0.2$. In case (b), what is the TPM of the equal-prior rule?
- 2 $\mathcal P_1=N_2(\mu_1,\Sigma)$, $\mathcal P_2=N_2(\mu_2,\Sigma)$ with $\mu_1=(2,1)^{\mathsf T}$, $\mu_2=(0,0)^{\mathsf T}$, $\Sigma=\begin{pmatrix}1&0.5\\0.5&1\end{pmatrix}$, equal priors and costs. Find the optimal rule and its error rate. Explain why the rule ignores $x_2$ although the means differ in $x_2$.
- 3 $\mathcal P_1=N(0,1)$, $\mathcal P_2=N(0,4)$, equal priors and costs. Find the optimal rule, $P(2\mid1)$, $P(1\mid2)$ and the TPM.
- 4 Training samples of $n_1=n_2=10$ give $\bar x_1=(6,4)^{\mathsf T}$, $\bar x_2=(4,3)^{\mathsf T}$, $S_{\text{pl}}=\begin{pmatrix}4&1\\1&1\end{pmatrix}$. Find Fisher's rule, allocate $x_0=(5,\ 3.8)^{\mathsf T}$, estimate the error rate, and test equality of the mean vectors at the $5\%$ level. Comment.
- 5 Derive the formulas for $P(2\mid1)$ and $P(1\mid2)$ in Theorem 7.30 for a general threshold $k$, and check them against part 1(b).
- 6 (Regression and discrimination) Code the group membership as $z_i=1$ for the $n_1$ cases of $\mathcal P_1$ and $z_i=0$ for the $n_2$ cases of $\mathcal P_2$, and regress $z$ on $x$ by least squares with an intercept. Prove that the vector of slopes is proportional to $S_{\text{pl}}^{-1}(\bar x_1-\bar x_2)$.
- 7 Three populations $N_2(\mu_k,I)$ with $\mu_1=(0,0)$, $\mu_2=(4,0)$, $\mu_3=(0,4)$ and equal priors. Describe the optimal regions and allocate $x_0=(2.5,\ 2)$.
- 8 One-dimensional training data: group 1: $1,\ 2,\ 3,\ 4.3$; group 2: $4.6,\ 6,\ 7,\ 8$. The rule allocates to group 1 iff $x$ is below the midpoint of the two group means. Find the apparent error rate and the leave-one-out error rate.
- 1 Cluster the six numbers $1,2,4,7,11,16$ with Euclidean distance by single, complete and average linkage. Give the merge heights and the two-cluster partitions.
- 2 Prove that for points on a line the single-linkage merge heights are exactly the $n-1$ gaps between consecutive ordered points, in increasing order.
- 3 Three points form an equilateral triangle of side $1$. Find the merge heights under single, complete, average and centroid linkage, and under Ward's method (heights = increase in $W$). Which are monotone?
- 4 Run Lloyd's algorithm with $K=2$ on $(0,0),(1,0),(0,1),(5,5),(6,5),(5,6)$ starting from the centres $(0,0)$ and $(1,0)$. Give each step, the final $W$, $T$ and $B/T$.
- 5 Prove $T=W(\mathcal C)+B(\mathcal C)$ directly for a partition into two clusters, and express $B$ in terms of the two cluster means only.
- 6 Let $W^*(K)$ be the minimum of $W$ over partitions into $K$ nonempty clusters ($1\le K\le n$, distinct points). Prove that $W^*(K+1)\lt W^*(K)$ for $K\lt n$ and $W^*(n)=0$. What does this imply for choosing $K$?
- 7 Two plant specimens are scored for presence (1) or absence (0) of eight rare traits: $(1,0,0,1,1,0,0,0)$ and $(1,0,0,0,1,0,0,1)$. Compute the simple matching and Jaccard similarities. Which is more sensible here?
- 8 (Ward) Prove that merging clusters $A$ and $B$ increases $W$ by $\frac{|A||B|}{|A|+|B|}\|\bar x_A-\bar x_B\|^2$. Evaluate it for $A=\{(0,0),(2,0)\}$, $B=\{(5,4)\}$ and check directly.
- 1 Show that for $p=q=1$ the canonical correlation is $|\rho_{XY}|$, and that for $p=1$ (one $X$, several $Y$'s) $\rho_1^{*2}=\sigma_{12}\Sigma_{22}^{-1}\sigma_{21}/\sigma_{11}$, the squared multiple correlation of $X$ on $Y$.
- 2 $\operatorname{corr}(X,Y_1)=\operatorname{corr}(X,Y_2)=0.6$ and $\operatorname{corr}(Y_1,Y_2)=0.5$. Find the canonical correlation between $X$ and $(Y_1,Y_2)$ and the canonical variate $V_1$.
- 3 Prove Theorem 7.37(1) directly from the eigenvalue form of Theorem 7.36: show that $\Sigma_{11}^{-1}\Sigma_{12}\Sigma_{22}^{-1}\Sigma_{21}$ changes to a similar matrix under $X\mapsto AX$, $Y\mapsto BY$.
- 4 Standardised $X=(X_1,X_2)$ and $Y=(Y_1,Y_2)$ have $R_{11}=R_{22}=I$ and $R_{12}=\begin{pmatrix}0.4&0.2\\0.2&0.4\end{pmatrix}$. Find the canonical correlations and variates, and check that the joint correlation matrix is positive definite.
- 5 $\operatorname{corr}(X_1,X_2)=0.8$, $\operatorname{corr}(Y,X_1)=0.3$, $\operatorname{corr}(Y,X_2)=-0.3$. Find the canonical correlation between $(X_1,X_2)$ and $Y$ and the canonical variate $U_1$. Comment.
- 6 With $n=60$ observations on $p=3$ and $q=2$ variables, the sample canonical correlations are $0.55$ and $0.20$. Test $H_0:\Sigma_{12}=0$ and then the significance of the second canonical correlation at the $5\%$ level.
- 7 Prove Theorem 7.37(2) and (4) in detail, and give an example of a singular joint covariance matrix with $\rho_1^*=1$ although no $|\operatorname{corr}(X_i,Y_j)|$ equals $1$.
E1. CSIR Part B GATE ST A random vector $X=(X_1,X_2,X_3)^{\mathsf T}$ has covariance matrix $\Sigma=\begin{pmatrix}6&2&0\\2&3&0\\0&0&4\end{pmatrix}$. The proportion of the total variance explained by the first two principal components is (A) $53.8\%$; (B) $76.9\%$; (C) $84.6\%$; (D) $69.2\%$.
E2. CSIR Part B Two populations are $N_2(\mu_1,\Sigma)$ and $N_2(\mu_2,\Sigma)$ with $\mu_1-\mu_2=(2,2)^{\mathsf T}$ and $\Sigma=\begin{pmatrix}2&1\\1&1\end{pmatrix}$. With equal priors and equal costs, the probability that the optimal rule misclassifies an observation from the first population is (A) $\Phi(-1)$; (B) $\Phi(-\sqrt2)$; (C) $\Phi(-2)$; (D) $\Phi(-4)$.
E3. CSIR Part B The five numbers $0,1,4,6,12$ are clustered by agglomerative hierarchical clustering with complete linkage and Euclidean distance. The height of the final merge in the dendrogram is (A) $6$; (B) $8$; (C) $9.25$; (D) $12$.
E4. CSIR Part C Let $\Sigma$ be a $p\times p$ positive definite covariance matrix with diagonal entries $\sigma_{11},\dots,\sigma_{pp}$ and eigenvalues $\lambda_1\ge\dots\ge\lambda_p$. Which of the following are true? (One or more options may be correct.) (A) $\lambda_1\ge\max_i\sigma_{ii}$. (B) If $D=\operatorname{diag}(\sigma_{11},\dots,\sigma_{pp})$ and $e$ is an eigenvector of $\Sigma$, then $D^{1/2}e$ is an eigenvector of the correlation matrix $D^{-1/2}\Sigma D^{-1/2}$. (C) $\lambda_1\lambda_2\cdots\lambda_p=\det\Sigma$. (D) $\lambda_p\ge\min_i\sigma_{ii}$.
E5. CSIR Part C GATE ST Observations come from $N_p(\mu_1,\Sigma)$ or $N_p(\mu_2,\Sigma)$ with $\mu_1\ne\mu_2$, $\Sigma$ positive definite, equal priors and equal costs. Let $\Delta^2=(\mu_1-\mu_2)^{\mathsf T}\Sigma^{-1}(\mu_1-\mu_2)$. Which of the following are true? (One or more options may be correct.) (A) The rule minimising the total probability of misclassification has a linear boundary. (B) Its total probability of misclassification is $\Phi(-\Delta/2)$. (C) The optimal rule depends on $x$ only through $(\mu_1-\mu_2)^{\mathsf T}x$. (D) Adding a further variable whose mean is the same in both populations can never reduce the minimal total probability of misclassification.
E6. CSIR Part C Let $X=(X_1,X_2)^{\mathsf T}$ and $Y=(Y_1,Y_2)^{\mathsf T}$ have a positive definite joint covariance matrix, with canonical correlations $\rho_1^*\ge\rho_2^*$. Which of the following are true? (One or more options may be correct.) (A) $\rho_1^*\ge|\operatorname{corr}(X_i,Y_j)|$ for all $i,j$. (B) The canonical correlations are unchanged if $(X_1,X_2)$ is replaced by $(X_1+X_2,\ X_1-X_2)$. (C) If $|\operatorname{corr}(X_i,Y_j)|\le0.3$ for all $i,j$, then $\rho_1^*\le0.6$. (D) $\rho_1^{*2}+\rho_2^{*2}\le1$.
Suggested plan — 3 lectures × 60 min.
- Principal components. Motivate with a two-variable scatter; Definition 7.10 and Theorem 7.26 with the full proof (the expansion $a=\sum c_je_j$ is the key idea of the whole section). Theorem 7.27 quickly; Example 1 on the board, including the correlation-matrix version. Project Interactive 1: rotate the trial direction, then switch to $R$ and ask the class why the axes jump to $45^\circ$. Finish with Theorem 7.28 (the $w_j$ argument fits in five minutes) and Example 2.
- Discrimination. Definition 7.12 and Theorem 7.29 (the proof is two lines — let students find it). Theorem 7.30 with the error rates; Example 4(d) as a surprise. Fisher's criterion via Cauchy–Schwarz (Theorem 7.31), Example 3, and a short discussion of apparent versus leave-one-out error (Exercise II.8). Mention Theorem 7.32 for several groups.
- Clustering and canonical correlation. Definition 7.15, Example 5 with the dendrograms drawn live; Theorem 7.33 and the equilateral-triangle inversion; single linkage as a minimum spanning tree. $k$-means: Theorem 7.35 and Example 6, then Interactive 2 (round clusters, then long thin ones, then uniform noise). Last 20 minutes: canonical correlations — Theorem 7.36 via the SVD, Example 7, Bartlett's test.
Discussion questions. (1) A PCA of ten exam marks has a first component with all loadings positive. Is that a discovery about the students or a consequence of something else? (Think of the equicorrelation matrix.) (2) A screening rule built on 40 patients misclassifies none of them. What would you report to the clinic, and what extra computation would you do? (3) Why can clustering never be "wrong" in the way a hypothesis test can be wrong, and what does that mean for how clusters should be reported?
Misconceptions to watch for. Computing proportions of variance from diagonal entries rather than eigenvalues; forgetting that PCA depends on scale; believing that components with large variance are the important ones; taking $\mu_1-\mu_2$ as the discriminant direction; believing that a variable with equal means is useless for discrimination; trusting the apparent error rate; reading a single-linkage dendrogram as compact groups; expecting $k$-means to find the global optimum or the "true" $K$; thinking that canonical correlations cannot exceed the largest pairwise correlation.
Suggested homework. I(1, 2, 3, 6, 7, 8), II(1, 2, 4, 6, 8), III(1, 3, 4, 6, 8), IV(2, 4, 5, 6); Exam corner E2, E4, E5.
Research question. How many principal components does a data set really have? When the variables are pure noise, how many components does Kaiser's "eigenvalue greater than one" rule keep, and does Horn's parallel analysis — comparing each eigenvalue with the same eigenvalue of simulated noise — do better?
Why it matters. The number of components or factors decides how questionnaires in psychology and education are scored, how many "modes" of climate variability are reported from sea-surface temperature fields, and how many population-structure axes are used to correct genetic association studies. Over-extraction produces spurious structure; under-extraction hides real effects.
What to do.
- Simulate $n=100$ observations of $p=10$ independent $N(0,1)$ variables, compute the eigenvalues of the sample correlation matrix, and repeat $1000$ times. Record the average of the largest eigenvalue and the distribution of the number of eigenvalues above $1$.
- Compare the largest eigenvalue with the Marchenko–Pastur edge $(1+\sqrt{p/n})^2$, the limit of the largest eigenvalue of a pure-noise correlation matrix as $n,p\to\infty$ with $p/n$ fixed.
- Now simulate a two-factor model: variables $1$–$5$ load $0.7$ on one factor, variables $6$–$10$ load $0.5$ on another, with unique variances making each variable's variance $1$. Find the population eigenvalues, then apply Kaiser's rule and parallel analysis (keep component $k$ while $\hat\lambda_k$ exceeds the $95$th percentile of the $k$-th noise eigenvalue from step 1) to $1000$ samples.
- Vary $n$ (50, 100, 500) and the loadings, and summarise when each rule recovers the true number of factors.
Tools: Python (numpy) or R; the check lab under Exercise card I for single matrices.
Hand in: A two-page note with a table of the number of components chosen by each rule in each scenario and a recommendation for practitioners.
Going further. Read about the "spiked covariance" model and the phase transition (Baik–Ben Arous–Péché): a population eigenvalue $1+\ell$ produces a sample eigenvalue that separates from the noise bulk only when $\ell\gt\sqrt{p/n}$.
🧪 Self-check quiz
Q1. A PCA of the correlation matrix of four variables gives eigenvalues $2.4,\ 0.9,\ 0.5,\ 0.2$. The first component explains
Q2. With group means $\bar x_1,\bar x_2$ and pooled covariance $S_{\text{pl}}$, Fisher's linear discriminant direction is
Q3. Which linkage can produce a dendrogram in which a later merge occurs at a smaller height than an earlier one?
Q4. Lloyd's algorithm for $k$-means is guaranteed to
Q5. When the second set consists of a single variable $Y$ ($q=1$), the first canonical correlation between $X$ and $Y$ equals