M2-001M2: Classical Machine LearningLinear RegressionEasy
⚡Flashcard Drill➔Mastery:

Formulate the Closed-Form Normal Equation for Linear Regression and Its Necessary Preconditions

🎯 Active Recall Self-Check (Draft First, Verify After)
Login-free practice tracker: recall core answer, audit pitfalls, and log review status.
Step 1 · Draft your concise answer & assumptions
Step 2 · Check Pitfalls & Follow-up Inquiries
Next: M2-002 →
📐 Mathematical Definition
w^=(X⊤X)−1X⊤y\hat w=(X^\top X)^{-1}X^\top y
⚡ One-Sentence Core Answer
The OLS closed-form solution is β^=(XTX)−1XTy\hat{\beta} = (X^T X)^{-1} X^T y, which strictly requires XTXX^T X to be invertible (full column rank with no perfect multicollinearity).

📌 Key Takeaways

  • •
    Normal equation: β^=(XTX)−1XTy\hat{\beta} = (X^T X)^{-1} X^T y, derived by setting the gradient of squared error ∇β∥y−Xβ∥2=0\nabla_\beta \|y - X\beta\|^2 = 0.
  • •
    Invertibility precondition: X∈RN×dX \in \mathbb{R}^{N \times d} must have full column rank Rank(X)=d\text{Rank}(X) = d, which requires sample size N≥dN \ge d.
  • •
    Rank deficiency: If features are collinear or N<dN < d, XTXX^T X is singular and has no unique inverse, requiring pseudoinverse X+X^+ or Ridge regularization.

📐 Mathematical Derivations

The Ordinary Least Squares objective is L(β)=12∥y−Xβ∥22=12(y−Xβ)T(y−Xβ)=12(yTy−2βTXTy+βTXTXβ)L(\beta) = \frac{1}{2} \|y - X\beta\|_2^2 = \frac{1}{2}(y - X\beta)^T (y - X\beta) = \frac{1}{2}(y^T y - 2\beta^T X^T y + \beta^T X^T X \beta). Taking the gradient with respect to β\beta: ∇βL(β)=−XTy+XTXβ\nabla_\beta L(\beta) = -X^T y + X^T X \beta. Setting ∇βL(β)=0\nabla_\beta L(\beta) = 0 yields the Normal Equations: XTXβ=XTyX^T X \beta = X^T y. If the Gram matrix XTXX^T X is non-singular (positive definite), multiplying by (XTX)−1(X^T X)^{-1} gives the unique closed-form estimator: β^=(XTX)−1XTy\hat{\beta} = (X^T X)^{-1} X^T y. The Hessian is ∇2L(β)=XTX⪰0\nabla^2 L(\beta) = X^T X \succeq 0, confirming a global convex minimum.

🏭 Production Trade-offs

Computational complexity: Computing (XTX)−1(X^T X)^{-1} via Cholesky decomposition costs O(Nd2+d3)O(N d^2 + d^3) time and O(d2)O(d^2) memory. In modern big data regimes where feature dimension d>100,000d > 100,000 or sample size N>108N > 10^8, closed-form matrix inversion is completely intractable. Instead, iterative first-order optimization (Stochastic Gradient Descent / Mini-batch SGD) with complexity O(Nd)O(Nd) per epoch is used exclusively in production.
⚠️ Common Interview Pitfalls
  • ✕
    Inverting XTXX^T X directly using np.linalg.inv rather than solving the linear system via Cholesky scipy.linalg.solve(X.T @ X, X.T @ y, assume_a='pos').
  • ✕
    Attempting closed-form inversion when N<dN < d without regularization.
🎯 Interviewer Follow-up Inquiries
  • ?
    Why is QR decomposition X=QRX = QR numerically superior to forming XTXX^T X directly in OLS?
  • ?
    How does the Gauss-Markov Theorem prove that OLS is the Best Linear Unbiased Estimator (BLUE)?
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔
📚

Associated Knowledge Base Guides & Mindmaps

← PreviousM1-089: Explain the Synthetic Control Method and Its Application in Geo-Testing and Policy Evaluation📋 Back to BankNext →M2-002: Enumerate the Four Classical Assumptions of Linear Regression and the Consequences of Their Violation