90 minutes · 100 marks · 7 questions. Original self-study practice, not an official examination specification or weighting forecast. Answer every part; show essential calculations and proofs. Exact values are preferred; if a decimal answer is requested, state the rounding used. Consistent paired eigenvector/singular-vector sign changes are acceptable. Follow each question’s normalization, domain and tie rules; never assume an inverse exists. Use a Casio fx-50FH II for this practice; one double-sided A4 reference sheet may be used. These are practice conditions, not a new claim about official examination rules.

Paired paper · Revision

Mark allocations are self-assessment guidance. Give equivalent correct methods equal credit. Retain method marks after an isolated arithmetic error when subsequent reasoning remains valid. Read the question paper first; the answers below explain conditions and checks, not just final numbers.

Q1. Least squares and transformed responses (16)

Paired paper Q1

(a) [6]

The unknown vector has an intercept and a slope. Differentiate the squared residual norm. Summing the data gives the displayed matrix; subtracting equations solves the two unknowns. The positive determinant establishes full column rank, not merely that there are more observations than parameters.

There are two unknown real coefficients, so c belongs to R²; four observations give four rows, not four unknown coefficients. The leading column of ones multiplies the intercept. The aim is to minimize the sum of squared residuals: the four observation equations need not all hold exactly. In the last product, multiply each x by its own response before adding: −1+0+2+10=11. Divide the first normal equation by two, solve it for b, and substitute into the second. Finally the fitted function returns a response for any new x; the coefficients alone are not the requested prediction function.

$$\begin{gathered} M=\begin{pmatrix}1&-1\\1&0\\1&1\\1&2\end{pmatrix},\quad y=\begin{pmatrix}1\\2\\2\\5\end{pmatrix},\quad c=\binom ab. \\ \nabla_c\|y-Mc\|^2=2M^T(Mc-y)=0. \\ \sum x_i=2,\quad\sum x_i^2=6,\quad\sum y_i=10,\quad\sum x_iy_i=11. \\ \begin{pmatrix}4&2\\2&6\end{pmatrix}\binom ab=\binom{10}{11},\quad 2a+b=5,\quad 10b=12. \\ \widehat a=\frac{19}{10},\quad\widehat b=\frac65,\quad\det(M^TM)=20>0. \\ c\in\mathbb R^2,\quad M\in\mathbb R^{4\times2},\quad \widehat y(x)=\frac{19}{10}+\frac65x. \end{gathered}$$

Marking： Design and objective 2; normal equations/products 2; coefficients 1; uniqueness 1.

Paired paper Q1(a)

(b) [6]

Substitute each input before subtracting from the observation. The two zero inner products do not mean every residual is zero. A free intercept makes the constant training mean feasible; OLS minimizes the same training RSS, so it cannot be worse than this baseline. Equivalently the residual and centered prediction are orthogonal. This reasoning does not automatically apply to test data, models without an intercept, or transformed-response objectives.

TSS is calculated around the observed mean, not around the fitted values. Subtract 5/2 from each of 1,2,2,5 before squaring; the four contributions are displayed below. For the geometric check, insert and subtract the fitted vector in the centered response. The residual is perpendicular both to the constant column and to every fitted vector Mc, hence also to the centered fitted vector. Pythagoras therefore applies to these two vectors. The positivity of TSS matters: if all responses were identical, this definition of R² would divide by zero. Nonnegative training R² here follows from the available mean baseline and the exact objective being minimized, not from the name “regression”.

$$\begin{gathered} \widehat y=\frac1{10}(7,19,31,43)^T,\quad r=\frac1{10}(3,1,-11,7)^T. \\ \mathbf1^Tr=\frac{3+1-11+7}{10}=0,\quad x^Tr=\frac{-3-11+14}{10}=0. \\ \mathrm{RSS}=\frac{9+1+121+49}{100}=\frac95,\quad\bar y=\frac52,\quad\mathrm{TSS}=9,\quad R^2=1-\frac{9/5}{9}=\frac45. \\ 0\le\mathrm{RSS}_{\mathrm{OLS}}\le\mathrm{RSS}(\bar y,0)=\mathrm{TSS},\qquad \mathrm{TSS}=\mathrm{RSS}+\|\widehat y-\bar y\mathbf1\|^2=\frac95+\frac{36}5. \\ \mathrm{TSS}=(-3/2)^2+(-1/2)^2+(-1/2)^2+(5/2)^2=\frac{9+1+1+25}{4}=9.\\y-\bar y\mathbf1=r+(\widehat y-\bar y\mathbf1),\quad r^T(\widehat y-\bar y\mathbf1)=r^TM\widehat c-\bar y r^T\mathbf1=0. \end{gathered}$$

Marking： Residual 1; RSS 1; TSS/R² 2; orthogonality 1; baseline or decomposition proof 1.

Paired paper Q1(b)

(c) [4]

For the exponential model use real logarithms, requiring positive observations and positive A,B; exponentiate the fitted intercept and slope. For the reciprocal model observations must be nonzero, and its prediction denominator must also be nonzero. Its two coefficients need no inverse parameter transform. Neither nonlinear response transformation generally minimizes original-scale RSS. Exact interpolation can coincide on both scales but is not a general guarantee.

For the exponential model the inputs x and the design columns stay unchanged; it is the response vector that becomes (0,log2,log2,log5). Exponentiation restores A and B, not the observations used in the least-squares objective. For the reciprocal model, α and β already are the original parameters: only prediction must be inverted. Least squares itself imposes no extra condition keeping a future denominator away from zero. In a special exact-interpolation case both error scales may have the same minimizer, but one such coincidence does not establish general equivalence.

$$\begin{gathered} z_i=\log y_i,\quad\theta_0=\log A,\quad\theta_1=\log B,\quad \min_\theta\sum_i(\log y_i-\theta_0-\theta_1x_i)^2,\quad A=e^{\theta_0},\ B=e^{\theta_1}. \\ z=(0,\log2,\log2,\log5)^T,\quad M=\begin{pmatrix}1&-1\\1&0\\1&1\\1&2\end{pmatrix}. \\ t_i=1/y_i,\quad N=\begin{pmatrix}1&e\\1&1\\1&e^{-1}\\1&e^{-2}\end{pmatrix},\quad t=(1,1/2,1/2,1/5)^T, \\ \min_{\alpha,\beta}\sum_i(1/y_i-\alpha-\beta e^{-x_i})^2,\qquad \widehat y(x)=\frac1{\alpha+\beta e^{-x}}. \end{gathered}$$

Marking： Each model 2, including transformation/design, actual objective, domain and recovery.

Paired paper Q1(c)

Q2. Standardization, ridge and LASSO (18)

Paired paper Q2

(a) [4]

Average the four values and divide the squared deviations by four before taking square roots. The three columns are pairwise orthogonal, each with squared norm four. Unit population variance does not mean unit column norm.

Compute a mean by summing its four observations and dividing by four. The deviations of either feature are two −2 values and two +2 values, so its population variance is 16/4=4 and its standard deviation is 2. Divide each centered observation by 2 to obtain the displayed ±1 columns. A variance-one column has squared norm n, not one. Dot products of distinct design columns vanish because the positive and negative contributions cancel. For the second component of Mᵀy, the signed sum is −1−3+5+11=12; this checks both the row order and the multiplication.

$$\begin{gathered} \mu_u=4,\quad\mu_v=12,\quad s_u=s_v=\sqrt{(4+4+4+4)/4}=2. \\ M=\begin{pmatrix}1&-1&-1\\1&-1&1\\1&1&-1\\1&1&1\end{pmatrix},\quad M^TM=4I_3,\quad M^Ty=(20,12,8)^T. \\ \mu_u=\frac{2+2+6+6}{4}=4,\quad\mu_v=\frac{10+14+10+14}{4}=12,\quad s_u=\sqrt{\frac{(-2)^2+(-2)^2+2^2+2^2}{4}}=2=s_v. \end{gathered}$$

Marking： Statistics 1; design 1; each matrix product 1.

Paired paper Q2(a)

(b) [6]

Use a zero in the intercept position of the penalty matrix. Differentiation gives two factors of two. The resulting diagonal system has positive diagonal entries, hence a unique solution. Substitute the standardization definitions to recover the intercept rather than keeping the standardized intercept. Check at (6,14): both forms give 15/2. The common one-half shrinkage here depends on equal orthogonal column norms.

D has a zero in the intercept position and ones only in the two slope positions. Differentiating the loss contributes a factor 2; differentiating 4βᵀDβ contributes 8Dβ. Divide the entire equation by 2, not just the loss term. The resulting diagonal coefficients 4,8,8 are positive, giving strict convexity and a unique solution. To restore units, substitute both standardization definitions into the complete affine expression and collect constants. The intercept changes because both centered features contribute a constant. Check a single observation in both coordinate systems. The slopes shrink by one half here only because the feature columns are orthogonal with identical squared norm 4; correlated features do not obey this coordinate-by-coordinate shortcut.

$$\begin{gathered} D=\operatorname{diag}(0,1,1),\quad2M^T(M\beta-y)+8D\beta=0, \\(M^TM+4D)\widehat\beta=M^Ty,\quad\operatorname{diag}(4,8,8)\widehat\beta=(20,12,8)^T, \\\widehat\beta=(5,3/2,1)^T,\qquad\widehat y=5+\frac32\frac{u-4}{2}+\frac{v-12}{2}=-4+\frac34u+\frac12v. \\ \widehat y=5+\frac32\frac{u-4}{2}+\frac{v-12}{2}=5-3-6+\frac34u+\frac12v=-4+\frac34u+\frac12v.\\(u,v)=(6,14):\quad 5+\frac32+1=\frac{15}{2}=-4+\frac92+7.\\\frac{4}{4+4}=\frac12. \end{gathered}$$

Marking： D and derivative 2; equation and coefficients 2; full restoration 2.

Paired paper Q2(b)

(c) [5]

The centered feature columns make the unpenalized intercept the response mean. Orthogonality removes slope cross-terms. A positive coordinate candidate requires h>τ; a negative one requires h<−τ. At zero the left derivative must be nonpositive and the right derivative nonnegative, giving the inclusive threshold. The second slope vanishes exactly. Multiplying the whole objective by two preserves its minimizer. Check residual correlations: the positive coordinate reaches the threshold and the zero coordinate stays below it.

Centering the feature columns makes the unpenalized intercept equation independent of the slopes, so the intercept equals the response mean. Orthogonality then removes the slope cross-term; without it, solving each slope separately would not be justified. The zero branch cannot be found by differentiating |t| at zero. Instead the left derivative must be nonpositive and the right derivative nonnegative. For a positive fitted coefficient the feature-residual correlation equals the positive threshold; for a zero coefficient it may lie anywhere inside the threshold interval. Thus the residual check verifies the kink condition as well as the ordinary derivative conditions. Multiplying the whole objective by a positive number preserves the minimizer; changing only the squared-loss factor changes the relative penalty.

$$\begin{gathered} d=m^Tm>0,\quad h=m^Tr,\quad\tfrac12\|r-mt\|^2+\tau|t|=\tfrac d2t^2-ht+\tau|t|+\text{constant}. \\t>0:\quad dt-h+\tau=0\Longrightarrow t=(h-\tau)/d\quad(h>\tau). \\t<0:\quad dt-h-\tau=0\Longrightarrow t=(h+\tau)/d\quad(h<-\tau). \\ t^*=\frac{S(h,\tau)}d,\qquad S(h,\tau)=\begin{cases}h-\tau&h>\tau,\\0&|h|\le\tau,\\h+\tau&h<-\tau.\end{cases} \\ -h-\tau\le0\le-h+\tau\ \Longleftrightarrow\ |h|\le\tau. \\ \widehat\beta_0=5,\quad\widehat\beta_1=\frac{S(12,10)}4=\frac12,\quad\widehat\beta_2=\frac{S(8,10)}4=0. \\ \tfrac12\mathrm{RSS}+10(|\beta_1|+|\beta_2|)\ \longleftrightarrow\ \mathrm{RSS}+20(|\beta_1|+|\beta_2|). \\r=(-7/2,-3/2,-1/2,11/2)^T,\quad\mathbf1^Tr=0,\ z_1^Tr=10,\ z_2^Tr=8. \end{gathered}$$

Marking： Intercept/orthogonality 1; threshold including zero 2; coefficients 1; penalty20 and reason 1.

Paired paper Q2(c)

(d) [3]

Full-data preprocessing lets held-out feature distributions influence fitting. Split the fold first; estimate scaling using only its training subset; apply those fixed statistics to both subsets; fit candidate models only on training observations; then score validation observations. Aggregate folds to choose the penalty, refit preprocessing and coefficients on all development data, and keep any final test set outside selection. OLS scaling invariance in a special case does not justify leakage in ridge, whose penalty depends on scale.

The validation fold must imitate unseen observations. Its feature distribution must therefore not influence fitted means and standard deviations, even without using its responses. Split first; estimate preprocessing on that fold’s training subset; freeze it while transforming both subsets; fit each candidate penalty on transformed training data; evaluate on the held-out fold. After choosing the penalty from the aggregated validation errors, re-estimate preprocessing and coefficients on the entire development training set. A final test set is excluded from all those choices. Some unpenalized OLS predictions happen to be invariant to invertible rescaling, but ridge changes when scales alter the coefficient penalty; an invariant special case does not excuse a leaking general procedure.

Marking： Leakage source 1; training-only statistics 1; correct transform-fit-score order 1.

Paired paper Q2(d)

Q3. Rectangular SVD and minimum norm (18)

Paired paper Q3

(a) [6]

Use the smaller Gram matrix AAᵀ. Its eigenvalues8,4 give nonnegative singular values, not the singular values themselves. Obtain each right vector from Aᵀu/σ. Complete V with a unit null-space vector. Verify orthogonality and the two outer-product contributions; changing a left vector sign requires the paired right sign change.

A has two rows and three columns. Computing AAᵀ gives a smaller two-by-two eigenproblem than AᵀA. Solve (6−λ)²−4=0 to obtain 8 and 4, then take their nonnegative square roots for the singular values. Normalize each left eigenvector before using Aᵀu/σ to construct its paired right vector. A full decomposition requires a third right vector even though there are only two positive singular values: it spans the nullspace. Check the sizes U:2×2, Σ:2×3, V:3×3. Orthogonal columns alone are insufficient: reconstruct the two outer-product terms and verify their sum equals A. A sign flip in one left vector must be accompanied by the same sign flip in its right partner, so their outer product stays unchanged.

$$\begin{gathered} AA^T=\begin{pmatrix}6&2\\2&6\end{pmatrix},\quad(6-\lambda)^2-4=0,\quad \lambda=8,4. \\u_1=\frac1{\sqrt2}\binom11,\ u_2=\frac1{\sqrt2}\binom1{-1},\quad\sigma_1=2\sqrt2,\ \sigma_2=2. \\v_1=\frac{A^Tu_1}{\sigma_1}=(1,0,0)^T,\quad v_2=\frac{A^Tu_2}{\sigma_2}=\frac1{\sqrt2}(0,1,1)^T,\quad v_3=\frac1{\sqrt2}(0,1,-1)^T. \\U=\frac1{\sqrt2}\begin{pmatrix}1&1\\1&-1\end{pmatrix},\quad\Sigma=\begin{pmatrix}2\sqrt2&0&0\\0&2&0\end{pmatrix},\quad V=\begin{pmatrix}1&0&0\\0&1/\sqrt2&1/\sqrt2\\0&1/\sqrt2&-1/\sqrt2\end{pmatrix}. \\U^TU=I_2,\quad V^TV=I_3,\quad A=\begin{pmatrix}2&0&0\\2&0&0\end{pmatrix}+\begin{pmatrix}0&1&1\\0&-1&-1\end{pmatrix}. \\ \det(AA^T-\lambda I)=(6-\lambda)^2-4=0.\\\sigma_1u_1v_1^T=\begin{pmatrix}2&0&0\\2&0&0\end{pmatrix},\quad\sigma_2u_2v_2^T=\begin{pmatrix}0&1&1\\0&-1&-1\end{pmatrix},\quad A=\sigma_1u_1v_1^T+\sigma_2u_2v_2^T. \end{gathered}$$

Marking： Gram/eigenpairs2; singular values and pairing2; null basis and full dimensions2.

Paired paper Q3(a)

(b) [4]

The pseudoinverse swaps dimensions and reciprocates only nonzero singular values. Here full row rank makes every right-hand side consistent, so the least-squares solution is exact; this is not true for every pseudoinverse problem.

The pseudoinverse reverses the matrix dimensions. Thus Σ⁺ has three rows and two columns; invert only the two positive singular values, never the zero entry. Multiply VΣ⁺Uᵀ in that order. Multiplying A⁺ by b produces three coordinates; substituting these into the original two equations is a separate consistency check. Here A has full row rank, so AA⁺ is the two-by-two identity and every two-dimensional right-hand side is attainable. For a general matrix, A⁺b is only guaranteed to minimize residual norm. Calling it an exact solution requires consistency, which has actually been verified here.

$$\begin{gathered} \Sigma^+=\begin{pmatrix}1/(2\sqrt2)&0\\0&1/2\\0&0\end{pmatrix},\quad A^+=V\Sigma^+U^T=\frac14\begin{pmatrix}1&1\\1&-1\\1&-1\end{pmatrix}. \\x_*=\frac14(6+2,6-2,6-2)^T=(2,1,1)^T,\quad Ax_*=(4+1+1,4-1-1)^T=b,\quad AA^+=I_2. \\ Ax_*=(4+1+1,\ 4-1-1)^T=(6,2)^T=b,\quad AA^+=I_2. \end{gathered}$$

Marking： Pseudoinverse2; solution1; substitution1.

Paired paper Q3(b)

(c) [5]

Adding and subtracting the original equations fixes x₁ and the sum of the other two coordinates. Every remaining displacement lies in the null space and is orthogonal to x*. Expanding the norm gives a nonnegative extra term that vanishes only at zero displacement, proving both minimality and uniqueness. This illustrates row-space/null-space orthogonality despite nonunique exact solutions.

Adding the two original equations gives 4x₁=8; subtracting gives 2x₂+2x₃=4. Hence x₁=2 and the remaining two coordinates sum to 2, so introduce one free real number t. This parameterization covers every exact solution, not merely a few examples. The difference h from x∗ lies in the nullspace, and its inner product with x∗ is 2·0+t−t=0. Expand the squared norm before eliminating the cross-term. The nonnegative remainder proves minimality; its equality condition t=0 proves uniqueness. Geometrically the pseudoinverse solution lies in the row space and every permitted displacement lies in its orthogonal complement, the nullspace. Having infinitely many exact solutions does not prevent one unique shortest solution.

$$\begin{gathered} 2x_1+x_2+x_3=6,\quad2x_1-x_2-x_3=2\quad\Longrightarrow\quad x_1=2,\ x_2+x_3=2. \\x=(2,1+t,1-t)^T=x_*+h,\quad h=(0,t,-t)^T\in\ker A,\quad x_*^Th=0. \\\|x\|^2=\|x_*\|^2+2x_*^Th+\|h\|^2=6+2t^2\ge6,\qquad \text{equality iff }t=0. \\ 2x_1+x_2+x_3=6,\quad2x_1-x_2-x_3=2,\quad x_1=2,\quad x_2+x_3=2.\\\|x_*+h\|^2=\|x_*\|^2+2x_*^Th+\|h\|^2,\quad x_*^Th=2\cdot0+t-t=0. \end{gathered}$$

Marking： All solutions2; orthogonality1; norm identity1; equality/uniqueness1.

Paired paper Q3(c)

(d) [3]

Retain the largest singular component. The residual has only one nonzero singular value, so these two norms happen to agree. Its four nonzero entries have squared sum4, but the requested norm is2, not4. In general Frobenius norm aggregates all discarded squared singular values while spectral norm uses the largest.

Truncating to rank one means keeping the entire largest singular outer product, not just one entry or one row of A. Inspect the discarded matrix directly: its four nonzero entries are ±1, so the sum of their squares is 4 and the Frobenius norm is its square root, 2. The spectral norm is the largest singular value of that residual, also 2. These numbers coincide because only one singular direction remains. With more discarded directions, Frobenius combines their squared singular values, whereas the spectral norm selects only the largest; the two generally differ.

$$\begin{gathered} A_1=\sigma_1u_1v_1^T=\begin{pmatrix}2&0&0\\2&0&0\end{pmatrix},\quad\|A-A_1\|_F=\sqrt{\sigma_2^2}=2,\quad\|A-A_1\|_2=\sigma_2=2. \end{gathered}$$

Marking： Approximation1; each norm1.

Paired paper Q3(d)

Q4. Centered PCA and reconstruction (15)

Paired paper Q4

(a) [4]

Subtract the same mean row from every observation; each centered column must sum to zero. Use denominator3, not the population denominator4 from the earlier standardization question.

Compute each coordinate mean separately: the first coordinate sums to 12 and the second to 4. The observations are rows, so subtract the row vector μᵀ from every row. Both resulting column sums must be zero; check this before forming the covariance. Each diagonal entry of XcᵀXc is a column’s sum of squares, while each off-diagonal entry is a sum of paired products. This question specifies the sample covariance denominator n−1=3. Question 2 specified a population standard deviation with denominator n=4; the word “variance” does not license replacing one convention with the other.

$$\begin{gathered} \mu=(3,1)^T,\quad X_c=X-\mathbf1\mu^T=\begin{pmatrix}2&2\\-2&-2\\1&-1\\-1&1\end{pmatrix},\quad X_c^TX_c=\begin{pmatrix}10&6\\6&10\end{pmatrix},\quad S=\frac13\begin{pmatrix}10&6\\6&10\end{pmatrix}. \\ \mu=\left(\frac{5+1+4+2}{4},\frac{3-1+0+2}{4}\right)^T=(3,1)^T.\\ 2^2+(-2)^2+1^2+(-1)^2=10,\quad2\cdot2+(-2)(-2)+1(-1)+(-1)1=6. \end{gathered}$$

Marking： Mean1; centering1; product1; covariance denominator1.

Paired paper Q4(a)

(b) [6]

The strictly larger eigenvalue selects the principal axis; the sign convention selects its representative. Scores are four scalar coordinates, not reconstructed two-dimensional points. Multiply scores by the direction row and add the mean. The first two observations lie on the principal axis; the others project to the mean.

The symmetry of S makes (1,1) and (1,−1) natural eigenvector candidates. Normalize them and compare their eigenvalues; the larger one determines the principal axis. Since the eigenvalues are distinct, the axis is unique but its orientation has two signs; the positive-first-coordinate convention fixes the sign. The score vector has size 4×1: each entry is one scalar coordinate along the axis, not a two-dimensional reconstructed point. Multiply this coordinate back by wᵀ to reconstruct a row, then add the mean row to recover original units. The first two centered points already lie on the axis and are retained exactly. The other two are perpendicular to it; their scores are zero, so they reconstruct to the original mean (3,1), not to the original origin.

$$\begin{gathered} \lambda_1=16/3,\quad v_1=\frac1{\sqrt2}(1,1)^T,\quad\lambda_2=4/3,\quad v_2=\frac1{\sqrt2}(1,-1)^T. \\w=v_1,\quad z=X_cw=(2\sqrt2,-2\sqrt2,0,0)^T,\quad\widehat X_c=zw^T=\begin{pmatrix}2&2\\-2&-2\\0&0\\0&0\end{pmatrix},\quad\widehat X=\begin{pmatrix}5&3\\1&-1\\3&1\\3&1\end{pmatrix}. \end{gathered}$$

Marking： Leading eigenpair2; scores2; reconstruction and mean restoration2.

Paired paper Q4(b)

(c) [5]

Split each centered observation into its projection onto q and an orthogonal residual. Pythagoras, summed over rows, gives the identity because q has unit norm. The fixed total energy leaves only the Rayleigh quotient to maximize. Expanding q in the orthonormal eigenbasis proves the maximum and equality condition. The requested error is a total squared norm, not its square root or per-observation average.

Total variance is the trace of S, so divide the retained eigenvalue by the sum of both eigenvalues. For reconstruction error, the first two residual rows are zero and the last two are (1,−1) and (−1,1). Their squared lengths add to 4. This is a total squared error, not its average 1 and not its square root 2. The discarded eigenvalue check multiplies by n−1 because S used that denominator. To prove the general identity, subtract the projection of each centered observation onto a unit vector q. Its residual is perpendicular to q because qᵀq=1. Pythagoras splits each squared length into projection energy and residual energy. The projection vector’s squared length equals its scalar score squared because q is unit length. Sum over observations, replace XcᵀXc by (n−1)S, and rearrange. The total centered energy is fixed; minimizing residual energy is therefore maximizing qᵀSq. Express q in the orthonormal eigenbasis to prove that the maximum is λ₁, with equality only on ±v₁ when the eigenvalues are distinct. Both centering and the unit-length constraint are essential.

$$\begin{gathered} \frac{\lambda_1}{\lambda_1+\lambda_2}=\frac45,\quad\|X-\widehat X\|_F^2=0+0+2+2=4=(n-1)\lambda_2. \\x_{c,i}=q(q^Tx_{c,i})+[x_{c,i}-q(q^Tx_{c,i})],\quad q^T[x_{c,i}-q(q^Tx_{c,i})]=0. \\\|X_c\|_F^2=\|X_cqq^T\|_F^2+\|X_c-X_cqq^T\|_F^2,\quad \|X_cqq^T\|_F^2=\|X_cq\|^2=(n-1)q^TSq. \\ q=av_1+bv_2,\ a^2+b^2=1\quad\Longrightarrow\quad q^TSq=\lambda_1-(\lambda_1-\lambda_2)b^2\le\lambda_1, \quad\text{equality iff }q=\pm v_1. \\ x_{c,i}=q(q^Tx_{c,i})+[x_{c,i}-q(q^Tx_{c,i})],\quad q^T[x_{c,i}-q(q^Tx_{c,i})]=0.\\\|X_c\|_F^2=\|X_cqq^T\|_F^2+\|X_c-X_cqq^T\|_F^2,\quad\|X_cqq^T\|_F^2=\|X_cq\|^2.\\q=av_1+bv_2,\quad a^2+b^2=1,\quad q^TSq=\lambda_1a^2+\lambda_2b^2=\lambda_1-(\lambda_1-\lambda_2)b^2\le\lambda_1. \end{gathered}$$

Marking： Ratio1; total error1; orthogonal identity2; eigenvalue argument1.

Paired paper Q4(c)

Q5. Gonzalez farthest-first guarantee (12)

Paired paper Q5

(a) [4]

With only center0 the farthest point is12. For each observation take the smaller of its two distances before taking the maximum over observations; reversing these operations changes the objective. Point7 supplies the worst service distance.

With only center 0, all observations are nonnegative, so their distances equal their coordinates. That is why 12 is selected next; do not choose the point farthest from an arbitrary different reference. After adding 12, the nearest-center groups are {0,2,3} and {7,10,12}. At 7, the distances to the two centers are 7 and 5, and the smaller is 5. The largest of all six smaller distances is therefore 5. This maximum service distance is a k-center radius, not a sum of distances or squared errors.

$$\begin{gathered} c_2=12,\qquad\begin{array}{c|rrrrrr}x&0&2&3&7&10&12\\|x|&0&2&3&7&10&12\\|x-12|&12&10&9&5&2&0\\d(x,C)&0&2&3&5&2&0\end{array},\quad R_G=5. \end{gathered}$$

Marking： Center1; distance table2; radius1.

Paired paper Q5(a)

(b) [3]

The proposed centers cover the two indicated intervals. For a lower bound inspect0,7,12: every pair is at least5 apart. Two covering balls must put two of these three points in one ball; triangle inequality forces radius at least5/2. This matches the construction. Restricting comparison centers to data points would be a different optimization problem.

A feasible construction supplies an upper bound on the unknown optimum, not by itself a proof of optimality. The first interval [0,3] needs only radius 3/2 around 3/2, whereas [7,12] needs radius 5/2 around 19/2. The common radius can be 5/2 even though the first group does not attain it. For the lower bound, the three pairwise distances among 0,7,12 are 7,12,5. Any two balls covering these three points must put a pair in one ball. If the radius were less than 5/2, that pair would be less than 5 apart by triangle inequality, a contradiction. Matching this lower bound to the construction proves the optimum; the ratio 5/(5/2)=2 shows the guarantee can be attained exactly.

$$\begin{gathered} c_1^*=3/2,\quad c_2^*=19/2,\quad [0,3]\subseteq B(3/2,5/2),\quad[7,12]\subseteq B(19/2,5/2). \\R^*\le5/2,\qquad5\le d(u,v)\le d(u,c)+d(c,v)\le2r\ \Longrightarrow\ R^*\ge5/2. \\R^*=5/2,\qquad R_G/R^*=2. \end{gathered}$$

Marking： Feasible centers1; three-point/two-ball lower bound1; optimum and ratio1.

Paired paper Q5(b)

(c) [5]

If the final radius is zero the result is immediate. Otherwise append a farthest observation p to the k selected centers only for the proof. At each selection, the candidate’s distance to every earlier center is at least that round’s covering radius, which cannot be below the final radius. The appended point also has that separation from every final center. Assign these k+1 points to k optimal covering balls: two share one ball. Triangle inequality gives the bound. If an optimum is only an infimum, apply the argument to an arbitrarily near-optimal cover and let its excess radius approach zero. The proof uses an ordinary metric, not squared Euclidean distance, and concerns maximum radius rather than k-means SSE.

The proof has two separate jobs. First it must build k+1 well-separated input points; merely invoking the pigeonhole principle without the separation bound is insufficient. Adding a center cannot increase any observation’s distance to its nearest center, so the covering radii are nonincreasing. At the moment cj is selected, its distance to the earlier set is a minimum over earlier centers; if that minimum is at least the final radius, each individual distance is also at least that radius. The same reasoning applies to the appended farthest point. Second, compare these input points with an optimal cover, assigning each to one ball that contains it even if several do. The shared-ball pair has both the established lower distance bound and a 2R∗ upper bound. The extra point is a proof device, not an instruction to output k+1 centers.

$$\begin{gathered} d(p,\{c_1,\ldots,c_k\})=R_G,\qquad i<j\Longrightarrow d(c_j,c_i)\ge R_{j-1}\ge R_G. \\d(p,c_i)\ge R_G\quad\Longrightarrow\quad\{c_1,\ldots,c_k,p\}\text{ pairwise separated by at least }R_G. \\ R_G\le d(u,v)\le d(u,c^*)+d(c^*,v)\le2R^*. \\R_G\le2(R^*+\varepsilon)\quad(\varepsilon>0)\Longrightarrow R_G\le2R^*. \\|0-2|^2=4> |0-1|^2+|1-2|^2=2. \end{gathered}$$

Marking： Extra farthest point1; separation2; pigeonhole1; triangle bound1.

Paired paper Q5(c)

Q6. Lloyd iterations and a suboptimal fixed point (12)

Paired paper Q6

(a) [6]

In one dimension the midpoint separates two ordered centers. The first update does not finish the algorithm: recompute assignments using the updated centers. The third assignment agrees with the second, so the stated stopping rule applies. No sample lies on any of these boundaries. The four costs below correspond, in order, to initial assignment, first mean update, second assignment, and second mean update. They confirm that both assignment and update do not increase loss.

In one dimension the midpoint of two ordered centers is their nearest-center boundary. Start from (0,1), giving boundary 1/2: only 0 joins the first cluster. The second cluster mean is (1+4+6+7+12)/5=6. Updating means is not a stopping test: with centers (0,6), recompute assignments using boundary 3, which moves point 1. The new means are (0+1)/2=1/2 and (4+6+7+12)/4=29/4. Their midpoint is 31/8=3.875, still between 1 and 4, so a further assignment leaves both clusters unchanged. Only now has the specified stopping rule been checked. No observation equals any of these boundaries, so the tie rule is never activated. When checking descent, label whether an objective value is after assignment or after updating centers; otherwise a correct number can be attached to the wrong state.

$$\begin{gathered} \begin{array}{c|c|c|c} \text{assignment}&\text{boundary}&C_1,C_2&\text{updated centers}\\1&1/2&\{0\},\{1,4,6,7,12\}&0,6\\2&3&\{0,1\},\{4,6,7,12\}&1/2,29/4\\3&31/8&\{0,1\},\{4,6,7,12\}&1/2,29/4\end{array} \\191\ \ge\ 66\ \ge\ 42\ \ge\ 141/4. \\\frac{c_1+c_2}{2}=\frac{1/2+29/4}{2}=\frac{31}8=3.875. \end{gathered}$$

Marking： First round2; second round2; final check/stopping2.

Paired paper Q6(a)

(b) [3]

Compute each cluster’s deviations from its own mean. A single better feasible partition disproves global optimality; it is unnecessary to prove the alternative itself globally optimal. The positive exact gap is not rounding error.

Compute the final cost cluster by cluster using the final means. The first cluster contributes two deviations of magnitude 1/2. In the second cluster subtract 29/4 from 4,6,7,12 to get −13/4,−5/4,−1/4,19/4; square before summing. For the proposed alternative, calculate its own means rather than reusing Lloyd’s centers. Its two squared-error sums are 26/3 and 62/3, giving 88/3. A single feasible alternative with a strictly smaller objective disproves global optimality of the Lloyd endpoint. There is no need to prove that this alternative itself is globally optimal. The exact gap 71/12 is positive, so this is not a rounding effect.

$$\begin{gathered} \mathrm{SSE}_{\mathrm{Lloyd}}=\frac12+\frac{169+25+1+361}{16}=\frac{141}4. \\\bar x_A=5/3,\quad\bar x_B=25/3,\quad\mathrm{SSE}_A=\frac{25+4+49}{9}=\frac{26}3,\quad\mathrm{SSE}_B=\frac{49+16+121}{9}=\frac{62}3. \\\mathrm{SSE}_{\mathrm{alternative}}=\frac{88}3<\frac{141}4,\qquad\frac{141}4-\frac{88}3=\frac{71}{12}>0. \\ \mathrm{SSE}_1=(0-1/2)^2+(1-1/2)^2=\frac12,\quad\mathrm{SSE}_2=\frac{169+25+1+361}{16}=\frac{139}{4}.\\\mathrm{SSE}_A=\frac{25+4+49}{9}=\frac{26}{3},\quad\mathrm{SSE}_B=\frac{49+16+121}{9}=\frac{62}{3},\quad\frac{141}{4}-\frac{88}{3}=\frac{71}{12}>0. \end{gathered}$$

Marking： Terminal SSE1; alternative centers/SSE1; not globally optimal1.

Paired paper Q6(b)

(c) [3]

Expand around the mean. The cross term vanishes because centered observations sum to zero. The remaining extra term is nonnegative and vanishes only at the mean. Lloyd solves each block problem optimally while holding the other block fixed; the joint problem is not convex, and improving the partition may require simultaneous changes. The preceding example is a concrete counterexample to a global guarantee.

Keep the cluster membership fixed while proving the mean formula. Add and subtract μ inside every x−c and expand the squared length, retaining the cross-term until summation. The sum of centered observations is zero by the definition of μ, so that cross-term vanishes. The remaining m‖μ−c‖² is nonnegative; since m>0, it is zero only at c=μ. This establishes the unique best center for that fixed cluster. Lloyd alternates two conditional optimizations: best assignments with centers fixed, and best centers with assignments fixed. The joint problem is not thereby convex, and descent does not mean every possible grouping has been considered. A better grouping may require simultaneous changes of several assignments and centers; part (b) is a concrete counterexample to global optimality.

$$\begin{gathered} m=|C|>0,\quad\mu=\frac1m\sum_{x\in C}x,\quad\sum_{x\in C}(x-\mu)=0. \\\sum_{x\in C}\|x-c\|^2=\sum_{x\in C}\|(x-\mu)+(\mu-c)\|^2 \\=\sum_{x\in C}\|x-\mu\|^2+2\left(\sum_{x\in C}(x-\mu)\right)^T(\mu-c)+m\|\mu-c\|^2 \\=\sum_{x\in C}\|x-\mu\|^2+m\|\mu-c\|^2\ge\sum_{x\in C}\|x-\mu\|^2. \end{gathered}$$

Marking： Decomposition/cross term2; block-versus-global distinction1.

Paired paper Q6(c)

Q7. Voronoi cells and center location (9)

Paired paper Q7

(a) [3]

Square nonnegative distances and cancel common quadratic terms. The first two comparisons give vertical and horizontal bisectors; the third gives an oblique bisector. At the common vertex all three distances equal √13. Shared boundaries are allowed by the closed-cell definition; unique assignment would need another tie rule.

Compare s₁ against each of the other sites to obtain its two inequalities. To obtain the boundary between s₂ and s₃, expand both squared distances, cancel x²+y², and move the remaining linear terms. The direction of the inequality is determined by which site’s cell is being described; reverse it for the other cell. A point common to all three cells must have x≤2 and x≥2, and y≤3 and y≥3, so it must be (2,3). Verify this point also satisfies the third boundary equation and compute its three equal distances. Closed Voronoi cells are allowed to overlap along their boundaries. Assigning one unique cluster label on such a boundary is a separate tie-breaking decision, not a correction to the cell definition.

$$\begin{gathered} x^2+y^2\le(x-4)^2+y^2\Longleftrightarrow x\le2, \qquad x^2+y^2\le x^2+(y-6)^2\Longleftrightarrow y\le3. \\(x-4)^2+y^2\le x^2+(y-6)^2\Longleftrightarrow3y-2x\le5. \\R_1=\{(x,y):x\le2,y\le3\},\quad R_2=\{(x,y):x\ge2,3y-2x\le5\}, \\R_3=\{(x,y):y\ge3,3y-2x\ge5\},\quad R_1\cap R_2\cap R_3=\{(2,3)\},\quad3(3)-2(2)=5. \\ -8x+16\le-12y+36\ \Longleftrightarrow\ 3y-2x\le5,\quad\|(2,3)-s_i\|=\sqrt{13}\quad(i=1,2,3). \end{gathered}$$

Marking： Each cell0.75; common vertex and check0.75.

Paired paper Q7(a)

(b) [3]

Both lengths are nonnegative, so squaring preserves their order. Expansion yields a linear inequality. A convex combination of two points in a halfspace remains in it by linearity. If both points lie in every defining halfspace, the segment lies in their intersection. Thus the argument works in every dimension, without relying on a picture.

Squaring is legitimate because both distances are nonnegative; it preserves their order. After expansion the common quadratic term cancels, leaving a linear inequality in x and a constant right-hand side. This is why the region is a halfspace even in dimensions that cannot be drawn. To prove convexity, take two points satisfying the inequality and use nonnegative weights 1−t and t whose sum is one. The same inequality then holds at every point of the segment. If both endpoints belong to every halfspace, every segment point belongs to every halfspace too, hence to their intersection. Merely drawing a convex-looking region is not a proof.

$$\begin{gathered} \|x-s_i\|\le\|x-s_j\|\Longleftrightarrow x^Tx-2x^Ts_i+\|s_i\|^2\le x^Tx-2x^Ts_j+\|s_j\|^2 \\\Longleftrightarrow x^T(s_j-s_i)\le\frac{\|s_j\|^2-\|s_i\|^2}{2},\quad R_i=\bigcap_{j\ne i}\left\{x:x^T(s_j-s_i)\le\frac{\|s_j\|^2-\|s_i\|^2}{2}\right\}. \\u,v\in H=\{x:a^Tx\le b\},\quad t\in[0,1]\Longrightarrow a^T[(1-t)u+tv]\le(1-t)b+tb=b. \end{gathered}$$

Marking： Halfspace derivation1; halfspace convexity1; intersection argument1.

Paired paper Q7(b)

(c) [3]

The mean is a convex combination: its equal weights are nonnegative and sum to one. It need not be observed: {0,2} has mean1. A medoid must be an observed representative, so0 and2 are tied medoids for that example but1 is not eligible. Nonemptiness is essential because an empty cluster has neither the displayed mean nor these weights.

Part 6 established that the mean is the best center when a nonempty cluster is fixed. Membership in the convex hull follows by checking the definition of a convex combination: every coefficient 1/m is nonnegative and their sum is one. Being inside the hull is weaker than being one of the observed points. For {0,2}, the hull is the whole interval [0,2], so 1 lies in the hull but is unobserved. A fixed-cluster medoid is selected from the observations to minimize the sum of distances, rather than by taking an unrestricted arithmetic mean. Both endpoints tie as medoids in this example. If m=0, division by m and the displayed convex-combination proof are undefined; empty clusters need separate handling.

$$\begin{gathered} C=\{x_1,\ldots,x_m\},\quad m>0,\quad\mu=\sum_{i=1}^m\frac1m x_i,\quad\frac1m\ge0,\quad\sum_{i=1}^m\frac1m=1, \qquad\mu\in\operatorname{conv}(C). \end{gathered}$$

Marking： Convex combination1; counterexample1; medoid restriction1.

Paired paper Q7(c)