Chapter 39 — Exercises: Capstone Project Milestones

These are not ordinary problem-set exercises; they are project milestones for the capstone. Work the ⭐ and ⭐⭐ tiers for every track (they build the shared understanding), then go deep on the tier-⭐⭐⭐ and tier-⭐⭐⭐⭐ milestones for the one track you chose. Mark which require a proof (📐) versus code (💻). All numeric targets match the numpy in index.md.

Tier ⭐ — Conceptual (do all of these)

39.1 ⭐ Name, in dependency order, the toolkit modules that svd_from_scratch ultimately rests on. Stop at vectors.py. (One sentence per module.)

39.2 ⭐ For each of the five tracks, state in one sentence what the rows and columns of its matrix mean. (This is step 1 of the §39.8 recipe.)

39.3 ⭐ Which single matrix decomposition is shared by Track A (image compression), Track D (PCA), and the comparison route of Track B (recommender)? In one sentence, why does the same decomposition do three different jobs?

39.4 ⭐ True or false, with a reason: "A capstone demo should re-implement matmul from scratch so it stays pure-Python."

39.5 ⭐ Match each track to the linear algebra object you read meaning out of: singular values, the dominant eigenvector, covariance eigenvectors, transformed homogeneous coordinates, latent dot products.

Tier ⭐⭐ — Computation by hand / small numpy (do all of these)

39.6 ⭐⭐ 💻 Run the full toolkit smoke test (§39.1.2): import every module you built and confirm each __main__ self-check passes. Report any module that fails and why.

39.7 ⭐⭐ For a 512×512 image kept at rank k = 20, compute by hand: (a) the storage k(m+n+1); (b) the compression ratio mn / (k(m+n+1)). Confirm your ratio lies between the k=10 (25.58×) and k=50 (5.12×) values in the chapter's table.

39.8 ⭐⭐ 💻 Reproduce the PageRank result for the 4-node graph {0→[1,2], 1→[2], 2→[0], 3→[0,2]} by power iteration (d = 0.85). Confirm you get [0.3797, 0.1989, 0.3839, 0.0375] and the ranking page 2 > page 0 > page 1 > page 3.

39.9 ⭐⭐ Given covariance eigenvalues [239.32, 1.06, 0.23], compute the explained-variance ratio of the first principal component and the cumulative ratio of the first two. Confirm 0.9946 and 0.9990.

39.10 ⭐⭐ 💻 For the rotation-about-y block R3 at 45° in Track E, verify numerically that R3 @ R3.T is the identity and det(R3) = 1. Explain in one sentence why these two facts mean the cube is not distorted.

Tier ⭐⭐⭐ — Build / prove (do these for your chosen track)

Track A — SVD image compression

39.11 ⭐⭐⭐ 💻 Run toolkit/capstone/image_compression.py and reproduce the four-row table. Then add k = 1 and k = 100 rows and confirm error still decreases monotonically.

39.12 ⭐⭐⭐ 📐 Prove that the relative reconstruction error equals the Eckart–Young tail sqrt(Σ_{i>k} σᵢ²)/‖A‖_F. (Use the orthonormality of U and V and the fact that ‖A‖_F² = Σ σᵢ².) State the condition under which this holds.

39.13 ⭐⭐⭐ 💻 Swap numpy's np.linalg.svd for your svd_from_scratch (eig of Aᵀ A). Confirm the singular values and the reconstruction A_k match numpy to tolerance, even if U differs by column signs. Explain the sign cancellation.

Track B — Recommender

39.14 ⭐⭐⭐ 💻 Run toolkit/capstone/recommender.py and reproduce mu = 3.111, train RMSE 0.21, and the two predicted blanks (1.5, 2.98). Confirm RMSE falls 0.437 → 0.210 → 0.063 as k goes 1 → 2 → 3.

39.15 ⭐⭐⭐ 💻 Hold out one known rating as a test entry (zero it in the mask). Refit and report the predicted value versus the held-out truth. Why is this a more honest measure of the model than train RMSE?

39.16 ⭐⭐⭐ 📐 Show that fitting R ≈ μ + UVᵀ with the masked error is not the same optimization as taking the truncated SVD of the blank-filled matrix. (One paragraph: where does the fill bias the answer?)

Track C — PageRank

39.17 ⭐⭐⭐ 💻 Cross-validate your power-iteration result against np.linalg.eig(G): confirm the dominant eigenvalue is 1.0000 and the dominant eigenvector (normalized to sum 1) matches your iterate.

39.18 ⭐⭐⭐ 💻 Add a dangling node (a page with no outgoing links) to the graph and watch what breaks. Fix it the standard way (treat a dangling column as linking uniformly to all pages) and confirm the ranking is sensible again.

39.19 ⭐⭐⭐ 📐 State the Perron–Frobenius conditions that guarantee a unique dominant eigenvector for the Google matrix G, and explain in one sentence what the damping term (1−d)/n · 𝟙𝟙ᵀ does to ensure them.

Track D — PCA

39.20 ⭐⭐⭐ 💻 Run PCA two ways on the 5×3 dataset — covariance eigendecomposition and SVD of the centered data — and assert s²/(N−1) equals the covariance eigenvalues [239.32, 1.06, 0.23].

39.21 ⭐⭐⭐ 💻 Multiply one feature by 1000 (change its units) and rerun PCA without standardizing. Show the first component now points almost entirely along that feature, and explain why. Then z-score and rerun.

39.22 ⭐⭐⭐ 📐 Prove that the principal components (eigenvectors of the symmetric covariance matrix) are orthogonal. Name the theorem and its condition.

Track E — 3D rendering

39.23 ⭐⭐⭐ 💻 Push the cube vertex (1,1,1,1) through P · T · Ry and reproduce the model-space, clip, and NDC coordinates (1.4142, 1, −5, 1) → (1.4142, 1, 3.8889, 5) → (0.2828, 0.2, 0.7778).

39.24 ⭐⭐⭐ 💻 Demonstrate non-commutativity: compute T @ Ry and Ry @ T for the cube and show the resulting vertex positions differ. Describe the two different motions in words.

39.25 ⭐⭐⭐ 📐 Explain why translation requires the 4th homogeneous coordinate. (Show no 3×3 matrix can map 𝟎 to a nonzero vector, hence translation is not linear on ℝ³.)

Tier ⭐⭐⭐⭐ — Application / extension (pick one for your track)

39.26 ⭐⭐⭐⭐ 💻 (A) Extend image compression to color: run the SVD on each RGB channel (or a luminance/chrominance split) and compare the per-channel k you need against a single grayscale channel. Present a side-by-side at matched storage.

39.27 ⭐⭐⭐⭐ 💻 (B) Build a proper train/test split, sweep k ∈ {1,…,5} and a few reg values, and plot test RMSE versus k. Identify the k that generalizes best and explain why it is not the largest k.

39.28 ⭐⭐⭐⭐ 💻 (C) Scrape or hand-build a real small network (a Wikipedia category, a citation list, a friend graph of ~20 nodes). Compute PageRank, then plot how the convergence speed of power iteration changes as d varies from 0.5 to 0.95.

39.29 ⭐⭐⭐⭐ 💻 (D) Run PCA on a labeled dataset (the iris measurements, or 8×8 digit images). Project onto the first two components, scatter-plot by label, and report whether the classes separate. State the cumulative variance you kept.

39.30 ⭐⭐⭐⭐ 💻 (E) Add flat lighting to your renderer: shade each face by the dot product of its surface normal with a fixed light direction (clamped to [0,1]). Note that this is Chapter 18's dot product doing the work, and present the lit cube at two light angles.

Capstone deliverable (all tracks)

39.31 ⭐⭐⭐⭐ Produce the five-section write-up of §39.9.2 (problem & encoding, method with conditions, results with one figure, validation, limitations & next steps) for your chosen track. Complete every box of the §39.10 validation checklist. This is the final artifact of the entire book.