Foundations — Linear regression — normal equation, gradient descent derivation

Before you can read the parent note Linear Regression fluently, you must own every symbol it throws at you. This page builds each one from nothing, in an order where each block rests on the one before it. Read top to bottom.

1. A data point $(x_i,y_i)$

Picture a scatter of dots. Each dot sits at a horizontal position $x_i$ and a height $y_i$.

• $x_i$ → how far right the dot is (the thing you know, e.g. altitude).
• $y_i$ → how far up the dot is (the thing you want to predict, e.g. fuel burn).
• $n$ → the count of dots. If $i$ runs $1,2,3$ then $n=3$.

Why the topic needs it. Regression's whole job is to summarise all these dots with one rule. Without a symbol for "dot number $i$" we couldn't talk about "all the dots at once."

2. The prediction $\hat{y}$ and the line $y=wx+b$

A straight line has two knobs:

Why two knobs and not one? With only $w$ the line would be forced through the origin $(0,0)$; real data rarely passes through zero, so $b$ lets the line slide up or down freely.

3. The error and why we square it

Look at the vertical dashed sticks in the figure — each is one error. We want the total length of all sticks to be small. But there is a trap:

So the quantity we minimise is the sum of squared errors: ${\sum }_{i=1}^n(y_i-{\hat{y}}_i{)}^2$

The symbol ${\sum }_{i=1}^n$ (capital Greek sigma) simply means "add up the thing on the right for $i=1,2,\dots ,n$." It is a compact "add them all."

4. The cost function $J$

Why the $\frac{1}{2n}$?

• The $\frac{1}{n}$ makes it a mean (average), so the score doesn't blow up just because you have more data.
• The extra $\frac{1}{2}$ is a convenience: when we differentiate, the square brings down a factor of $2$, and the $\frac{1}{2}$ cancels it so formulas stay clean. It never changes where the minimum is.

5. Vectors and matrices — the bulk notation

When there are many inputs and many points, writing sums by hand is unbearable. We pack numbers into grids.

• ${\mathbf{x}}_i$ → all the inputs of point $i$ stacked in a column.
• $\mathbf{X}\in {\mathbb{R}}^{n\times d}$ → the design matrix: $n$ rows (one per point), $d$ columns (one per input feature). The symbol ${\mathbb{R}}^{n\times d}$ just says "a grid of real numbers with $n$ rows and $d$ columns."
• $\mathbf{y}\in {\mathbb{R}}^n$ → the column of true answers.
• $\mathbf{w}$ → the column of weights, one per feature.

Transpose ${\mathbf{X}}^T$

Matrix-times-vector $\mathbf{Xw}$

This packs all predictions into one object. Row $i$ of $\mathbf{Xw}$ is exactly $w{x}_i+b$. So $\mathbf{Xw}$ = the whole column of guesses $\hat{\mathbf{y}}$ in one symbol.

The dot product and ${\mathbf{w}}^T\mathbf{x}$

The norm $\Vert \cdot \Vert$

This is the language of Least Squares Estimation and rests on the Matrix Pseudoinverse.

6. Slope, derivative, gradient — the downhill compass

Why the minus sign in gradient descent? The gradient points uphill (toward more cost). We want less cost, so we step the opposite way: $-\nabla J$. That is the entire logic of ${\mathbf{w}}_{t+1}={\mathbf{w}}_t-\alpha \nabla J$.

• $\alpha$ = learning rate: how big a step to take. Too big → overshoot the valley and bounce; too small → crawl. See Feature Scaling for why unequal input sizes force $\alpha$ to be tiny.
• The subscript $t$ = iteration number (${\mathbf{w}}_0,{\mathbf{w}}_1,\dots$), a time step, not a power.
• $ϵ$ (epsilon) = a tiny threshold; "stop when the change is smaller than $ϵ$."

7. How they fit together

The bowl-shaped $J$ has exactly one bottom because it is convex — see Convex Optimization. That guarantee is why both methods reach the same best line.

Downstream this same machinery grows into Regularization (Ridge, Lasso), Kalman Filtering, and Neural Networks.

Equipment checklist

Cover the right side and answer aloud. If any stalls you, reread that section.