Linear regression — normal equation, gradient descent derivation

Linear regression finds the best-fit line (or hyperplane) through data by minimizing the sum of squared errors. In aerospace, this powers trajectory prediction, sensor calibration, and control system parameter identification.

Why Linear Regression?

Problem Setup

Vectorized form: Stack data into matrix $\mathbf{X} \in \mathbb{R}^{n \times d}$ (each row is $\mathbf{x}_i^T$), targets $\mathbf{y} \in \mathbb{R}^{n}$. Absorb bias into $\mathbf{w}$ by adding a column of 1s to $\mathbf{X}$. Then:

Method 1: Normal Equation (Closed-Form Solution)

Derivation from First Principles

Goal: Find $\mathbf{w}$ that minimizes $J(\mathbf{w})$ using calculus.

Step 1: Expand the cost function.

Why this step? Converting the norm into a dot product so we can apply matrix derivative rules.

Expand:

Since $\mathbf{y}^T\mathbf{X}\mathbf{w}$ is a scalar, it equals its transpose: $\mathbf{y}^T\mathbf{X}\mathbf{w} = \mathbf{w}^T\mathbf{X}^T\mathbf{y}$.

Step 2: Take the derivative with respect to $\mathbf{w}$ and set to zero.

Why this step? At the minimum, the gradient is zero (no slope in any direction). We use:

• $\frac{\partial}{\partial \mathbf{w}} (\mathbf{a}^T\mathbf{w}) = \mathbf{a}$
• $\frac{\partial}{\partial \mathbf{w}} (\mathbf{w}^T\mathbf{A}\mathbf{w}) = 2\mathbf{A}\mathbf{w}$ (for symmetric $\mathbf{A}$)

Set gradient to zero:

Step 3: Solve for $\mathbf{w}$.

Geometric intuition: $\mathbf{X}\mathbf{w}^*$ is the orthogonal projection of $\mathbf{y}$ onto the column space of $\mathbf{X}$. The error vector $\mathbf{y} - \mathbf{X}\mathbf{w}^*$ is perpendicular to all columns of $\mathbf{X}$, hence $\mathbf{X}^T(\mathbf{y} - \mathbf{X}\mathbf{w}^*) = 0$.

When to Use Normal Equation

Pros:

• One-shot solution (no iteration)
• Exact (up to numerical precision)

Cons:

• Computing $(\mathbf{X}^T\mathbf{X})^{-1}$ is $O(d^3)$ where $d$ is feature count
• Fails if $\mathbf{X}^T\mathbf{X}$ is singular (multicollinearity)
• Impractical for $d > 10{,}000$ (common in aerospace sensor fusion)

Method 2: Gradient Descent (Iterative Optimization)

Derivation from First Principles

Core idea: Start with a random $\mathbf{w}$, repeatedly step in the direction that decreases $J$ the fastest (negative gradient).

Step 1: Compute the gradient of $J$ with respect to $\mathbf{w}$.

From earlier:

Why this form? $\mathbf{X}\mathbf{w} - \mathbf{y}$ is the error vector (predictions minus actuals). Multiplying by $\mathbf{X}^T$ weights each feature by how much it contributed to the error.

Step 2: Update rule.

Why this step? We move against the gradient (downhill). $\alpha$ controls how big the step is—too large and we overshoot, too small and convergence is slow.

Step 3: Repeat until convergence.

Convergence criteria:

• $\|\nabla_{\mathbf{w}} J\| < \epsilon$ (gradient nearly zero)
• $|J_{t+1} - J_t| < \epsilon$ (cost stops decreasing)
• Maximum iterations reached

Variants

Worked Examples

Add bias column: $\mathbf{X} = \begin{bmatrix} 1 & 1 \\ 1 & 2 \\ 1 & 3 \end{bmatrix}$, $\mathbf{y} = \begin{bmatrix} 2 \\ 4 \\ 5 \end{bmatrix}$

$\mathbf{X}^T\mathbf{X} = \begin{bmatrix} 3 & 6 \\ 6 & 14 \end{bmatrix}$, $\mathbf{X}^T\mathbf{y} = \begin{bmatrix} 11 \\ 25 \end{bmatrix}$

Why this step? Matrix multiplication: $(3 \times 2)^T (3 \times 2) = (2 \times 2)$. The first entry of $\mathbf{X}^T\mathbf{y}$ is $1\cdot2 + 1\cdot4 + 1\cdot5 = 11$; the second is $1\cdot2 + 2\cdot4 + 3\cdot5 = 2 + 8 + 15 = 25$.

Solve $\begin{bmatrix} 3 & 6 \\ 6 & 14 \end{bmatrix} \begin{bmatrix} b \\ w \end{bmatrix} = \begin{bmatrix} 11 \\ 25 \end{bmatrix}$:

Inverse: $(\mathbf{X}^T\mathbf{X})^{-1} = \frac{1}{3 \cdot 14 - 36} \begin{bmatrix} 14 & -6 \\ -6 & 3 \end{bmatrix} = \frac{1}{6} \begin{bmatrix} 14 & -6 \\ -6 & 3 \end{bmatrix}$

$\mathbf{w}^* = \frac{1}{6} \begin{bmatrix} 14 & -6 \\ -6 & 3 \end{bmatrix} \begin{bmatrix} 11 \\ 25 \end{bmatrix} = \frac{1}{6} \begin{bmatrix} 154 - 150 \\ -66 + 75 \end{bmatrix} = \frac{1}{6}\begin{bmatrix} 4 \\ 9 \end{bmatrix} = \begin{bmatrix} 0.667 \\ 1.5 \end{bmatrix}$

Result: $b = 0.667$, $w = 1.5$. So $\hat{y} = 1.5x + 0.667$.

Why this matters: Aerospace sensor calibration often involves fitting lines to reference measurements.

Iteration 0:

• Predictions: $\hat{\mathbf{y}} = \mathbf{X} \begin{bmatrix} 0 \\ 0 \end{bmatrix} = \begin{bmatrix} 0 \\ 0 \\ 0 \end{bmatrix}$
• Error: $\mathbf{X}\mathbf{w} - \mathbf{y} = \begin{bmatrix} -2 \\ -4 \\ -5 \end{bmatrix}$
• Gradient: $\nabla J = \frac{1}{3} \begin{bmatrix} 1 & 1 & 1 \\ 1 & 2 & 3 \end{bmatrix} \begin{bmatrix} -2 \\ -4 \\ -5 \end{bmatrix} = \frac{1}{3} \begin{bmatrix} -11 \\ -25 \end{bmatrix} = \begin{bmatrix} -3.667 \\ -8.333 \end{bmatrix}$
• Why this step? $\mathbf{X}^T$ has shape $(2 \times 3)$, error is $(3 \times 1)$, result is $(2 \times 1)$. Second component: $1\cdot(-2) + 2\cdot(-4) + 3\cdot(-5) = -2 - 8 - 15 = -25$.
• Update: $\mathbf{w}_1 = \begin{bmatrix} 0 \\ 0 \end{bmatrix} - 0.1 \begin{bmatrix} -3.667 \\ -8.333 \end{bmatrix} = \begin{bmatrix} 0.367 \\ 0.833 \end{bmatrix}$

Iteration 1:

• $\hat{\mathbf{y}} = \mathbf{X}\mathbf{w}_1 = \begin{bmatrix} 0.367 + 0.833 \\ 0.367 + 1.667 \\ 0.367 + 2.500 \end{bmatrix} = \begin{bmatrix} 1.200 \\ 2.033 \\ 2.867 \end{bmatrix}$
• Error: $\begin{bmatrix} -0.800 \\ -1.967 \\ -2.133 \end{bmatrix}$
• Gradient: $\frac{1}{3}\begin{bmatrix} -4.900 \\ -11.133 \end{bmatrix} = \begin{bmatrix} -1.633 \\ -3.711 \end{bmatrix}$
• Update: $\mathbf{w}_2 = \begin{bmatrix} 0.530 \\ 1.204 \end{bmatrix}$

Continue until convergence → approaches $[0.667, 1.5]^T$.

Why gradient descent? When $d = 10{,}000$ (e.g., image features for spacecraft pose estimation), computing the inverse is infeasible, but each gradient step is fast.

Common Mistakes

Active Recall

The normal equation is like using a ruler and protractor to calculate the exact perfect angle and position in one go. You do some matrix math and boom—done.

Gradient descent is like starting with a random line, then slowly tilting and sliding it. You look at where the dots are, figure out which way makes things worse, and move the opposite way. You repeat this over and over, each time making a small adjustment, until the line can't get any better. It takes longer but works even if the "ruler method" is too complicated (like if you have a million dots).

Aerospace engineers use this to predict things like how much fuel a plane will burn at different speeds—plot speed vs. fuel, find the best line, then use it to plan flights.

Gradient Descent = "ITERATIVE steps ALPHA tuned"

• Iterative process
• Tiny steps (learning rate $\alpha$)
• Efficient for high dimensions

Connections

• Least Squares Estimation — same MSE criterion, generalized to weighted/nonlinear cases
• Matrix Pseudoinverse — handles singular $\mathbf{X}^T\mathbf{X}$
• Convex Optimization — why gradient descent converges (MSE is convex)
• Feature Scaling — essential for GD convergence
• Regularization (Ridge, Lasso) — adds penalty term to prevent overfitting
• Kalman Filtering — recursive least squares for dynamic systems (spacecraft tracking)
• Neural Networks — gradient descent generalizes to backpropagation

Summary

• Normal equation: $\mathbf{w}^* = (\mathbf{X}^T\mathbf{X})^{-1}\mathbf{X}^T\mathbf{y}$ (one-shot, $O(d^3)$, requires invertibility)
• Gradient descent: $\mathbf{w}_{t+1} = \mathbf{w}_t - \alpha \nabla J$ (iterative, $O(nd)$ per step, scales to large $d$)
• Derived from minimizing $\frac{1}{2n}\|\mathbf{y} - \mathbf{X}\mathbf{w}\|^2$ by setting $\nabla J = 0$ or stepping against $\nabla J$
• Key tradeoffs: exact vs. iterative, memory vs. computation, batch vs. stochastic

#flashcards/coding

What is the normal equation for linear regression? :: $\mathbf{w}^* = (\mathbf{X}^T\mathbf{X})^{-1}\mathbf{X}^T\mathbf{y}$

Derive the normal equation from $J(\mathbf{w}) = \frac{1}{2n}\|\mathbf{y} - \mathbf{X}\mathbf{w}\|^2$ :: Expand to $\frac{1}{2n}(\mathbf{y}^T\mathbf{y} - 2\mathbf{w}^T\mathbf{X}^T\mathbf{y} + \mathbf{w}^T\mathbf{X}^T\mathbf{X}\mathbf{w})$, take derivative $\frac{\partial J}{\partial \mathbf{w}} = \frac{1}{n}(\mathbf{X}^T\mathbf{X}\mathbf{w} - \mathbf{X}^T\mathbf{y})$, set to zero: $\mathbf{X}^T\mathbf{X}\mathbf{w} = \mathbf{X}^T\mathbf{y}$, solve: $\mathbf{w}^* = (\mathbf{X}^T\mathbf{X})^{-1}\mathbf{X}^T\mathbf{y}$

Concept Map

Hinglish (regional understanding)

Hinglish (regional understanding)