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 solutions · Revision

Q1. Least squares and transformed responses (16)

Paired solutions Q1

Fit the affine model to the four observations. Use observation minus prediction as the residual.

$$\begin{gathered} \begin{array}{c|rrrr}x_i&-1&0&1&2\\y_i&1&2&2&5\end{array}\qquad \widehat y=a+bx,\quad r_i=y_i-\widehat y_i. \end{gathered}$$

(a) [6]

Construct the design matrix, derive the normal equations, find the unique OLS coefficients, and justify uniqueness.

Paired solutions Q1(a)

(b) [6]

Find the residual vector, RSS and R². Check both normal-equation orthogonality conditions and explain guaranteed nonnegative training R².

$$\begin{gathered} R^2=1-\mathrm{RSS}/\mathrm{TSS},\qquad\mathrm{TSS}=\sum_i(y_i-\bar y)^2. \end{gathered}$$

Paired solutions Q1(b)

(c) [4]

For each displayed model give a transformed response, design matrix, actual squared-error objective, domain restrictions and parameter recovery. No numerical fit is required. Does either transformation guarantee minimum RSS in the original response scale?

$$\begin{gathered} \text{(i) }y=AB^x,\qquad \text{(ii) } y=\frac1{\alpha+\beta e^{-x}}. \end{gathered}$$

Paired solutions Q1(c)

Q2. Standardization, ridge and LASSO (18)

Paired solutions Q2

Standardize each feature using its population standard deviation. Do not standardize the response.

$$\begin{gathered} \begin{array}{c|rrr}i&u_i&v_i&y_i\\1&2&10&1\\2&2&14&3\\3&6&10&5\\4&6&14&11\end{array} \qquad z_1=\frac{u-\mu_u}{s_u},\quad z_2=\frac{v-\mu_v}{s_v},\quad\widehat y=\beta_0+\beta_1z_1+\beta_2z_2. \end{gathered}$$

(a) [4]

Find means and standard deviations, construct M=[1 z₁ z₂], and compute MᵀM and Mᵀy.

Paired solutions Q2(a)

(b) [6]

Derive the ridge equation, find all coefficients, and restore the model to u,v. The intercept is not penalized.

$$\begin{gathered} \min_\beta\|M\beta-y\|_2^2+4(\beta_1^2+\beta_2^2). \end{gathered}$$

Paired solutions Q2(b)

(c) [5]

Instead minimize the displayed LASSO objective. Derive the one-coordinate soft-threshold rule and find all coefficients. If the factor 1/2 is removed, what coefficient replaces 10 to preserve the fitted model?

$$\begin{gathered} \min_\beta\frac12\|M\beta-y\|_2^2+10(|\beta_1|+|\beta_2|). \end{gathered}$$

Paired solutions Q2(c)

(d) [3]

Explain the flaw in computing feature means/standard deviations on the entire dataset before k-fold selection of the ridge penalty. State the correct order within a fold.

Paired solutions Q2(d)

Q3. Rectangular SVD and minimum norm (18)

Paired solutions Q3

Use the given matrix and right-hand side.

$$\begin{gathered} A=\begin{pmatrix}2&1&1\\2&-1&-1\end{pmatrix},\qquad b=\binom62. \end{gathered}$$

(a) [6]

Find a full SVD with U of size2×2, Σ of size2×3, V of size3×3. Order singular values decreasingly and show left/right vector pairing.

Paired solutions Q3(a)

(b) [4]

Compute A⁺ and x*=A⁺b; directly verify Ax*=b.

Paired solutions Q3(b)

(c) [5]

Describe all solutions. Use an orthogonal decomposition and norm identity to prove x* is the unique minimum-norm solution.

Paired solutions Q3(c)

(d) [3]

Find the truncated rank-one approximation and both Frobenius and spectral error norms.

Paired solutions Q3(d)

Q4. Centered PCA and reconstruction (15)

Paired solutions Q4

Observations are rows. Use sample covariance with denominator n−1, n=4.

$$\begin{gathered} X=\begin{pmatrix}5&3\\1&-1\\4&0\\2&2\end{pmatrix},\qquad S=\frac{X_c^TX_c}{n-1}. \end{gathered}$$

(a) [4]

Find the mean, centered matrix and covariance.

Paired solutions Q4(a)

(b) [6]

Find the principal direction with positive first coordinate, scores, and reconstructions in original coordinates.

Paired solutions Q4(b)

(c) [5]

Compute the fraction of total variance retained and the total squared reconstruction error. For arbitrary unit q prove the displayed identity and use it to justify the principal direction.

$$\begin{gathered} \|X_c-X_cqq^T\|_F^2=\|X_c\|_F^2-(n-1)q^TSq. \end{gathered}$$

Paired solutions Q4(c)

Q5. Gonzalez farthest-first guarantee (12)

Paired solutions Q5

Run farthest-first with k=2, first center0, and smaller-coordinate tie breaking. The comparison optimum may place centers anywhere on the real line, not only at observations.

$$\begin{gathered} P=\{0,2,3,7,10,12\},\quad d(x,y)=|x-y|,\quad R(C)=\max_{x\in P}\min_{c\in C}|x-c|. \end{gathered}$$

(a) [4]

Find the second center, show each nearest-center distance, and calculate the final radius.

Paired solutions Q5(a)

(b) [3]

Find optimal unrestricted centers and radius. Prove optimality by a lower bound and compute the approximation ratio.

Paired solutions Q5(b)

(c) [5]

Prove the general metric-space bound R_G≤2R*. Identify the k+1 points used in the pigeonhole argument and prove their pairwise separation.

Paired solutions Q5(c)

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

Paired solutions Q6

Use one-dimensional k-means with squared Euclidean loss. Start at centers0,1. Assign all observations first, then update nonempty clusters to their means. Ties go to cluster1. Stop when assignment is unchanged; no empty cluster occurs here.

$$\begin{gathered} P=\{0,1,4,6,7,12\},\qquad k=2,\quad c_1^{(0)}=0,\quad c_2^{(0)}=1. \end{gathered}$$

(a) [6]

Show every assignment and center update through termination.

Paired solutions Q6(a)

(b) [3]

Find final SSE and compare with the partition {0,1,4},{6,7,12}, each using its optimal center. Is the terminal solution globally optimal?

Paired solutions Q6(b)

(c) [3]

Prove that replacing the center of any fixed nonempty cluster by its mean cannot increase SSE. Why does this not ensure a globally optimal final clustering?

Paired solutions Q6(c)

Q7. Voronoi cells and center location (9)

Paired solutions Q7

Use ordinary Euclidean distance. Closed cells contain points no farther from their site than from others; boundaries may belong to several cells.

$$\begin{gathered} s_1=(0,0),\qquad s_2=(4,0),\qquad s_3=(0,6). \end{gathered}$$

(a) [3]

Express all three cells as linear inequalities and find the point shared by all three.

Paired solutions Q7(a)

(b) [3]

For arbitrary sites in Rᵖ derive the halfspace inequality for the distance comparison and prove every closed Euclidean Voronoi cell is convex.

Paired solutions Q7(b)

(c) [3]

Prove the k-means center of a fixed nonempty cluster lies in its convex hull. Must it be observed? Contrast k-medoids.

Paired solutions Q7(c)