Skip to content
Glacius
Linear algebraConcept reference

Normal equations

For a real least-squares problem Ax=b, the normal equations are AᵀAx=Aᵀb.

2 min read1 figureSources & further reading
On this page 8 sections
  1. Overview
  2. The normal equations characterize a least-squares fit by its leftover error
  3. Let A have columns u=(1,1,0) and v=(0,1,1)
  4. For u=(1,1,0), v=(0,1,1), b=(2,3,1), each row below dots one column with u, v and b
  5. These equations explain regression geometry and lead to regularized variants later
  6. Key takeaway
  7. Sources & further reading
  8. Concept connections

01The normal equations characterize a least-squares fit by its leftover error#

The normal equations characterize a least-squares fit by its leftover error. At the best fit, moving along any model column cannot remove more error to first order. The residual is perpendicular, or normal, to those columns; that is where the name comes from.

At the closest attainable output Ax, the residual b−Ax is perpendicular to every column of A. For A=(1,1)ᵀ and b=(2,4), the closest output is (3,3). Its residual is (−1,1), whose dot product with (1,1) is zero.

Multiplying the residual by Aᵀ collects those zero dot products. Expand Aᵀ(b−Ax)=0 and rearrange. The result is called the normal equations:

ATAx=ATbA^TAx=A^Tb

For a matrix with mm rows and nn columns, ATAA^TA is n×nn\times n and ATbA^Tb has nn entries. Each left-side entry compares two feature columns by a dot product. Each right-side entry compares a feature column with the target. Build both products before trying to solve for the nn coefficients.

Check your reasoning

Form [ATA∣ATb][A^TA\mid A^Tb]. [A∣b]=[1224][A\mid b]=\left[\begin{array}{r|r}1&2\\2&4\end{array}\right].

  1. A[510]\left[\begin{array}{r|r}5&10\end{array}\right]
  2. B[36]\left[\begin{array}{r|r}3&6\end{array}\right]
  3. C[56]\left[\begin{array}{r|r}5&6\end{array}\right]
Show answer and explanation
[510]\left[\begin{array}{r|r}5&10\end{array}\right]

12+22=51^2+2^2=5; 2+8=102+8=10.

02Let A have columns u=(1,1,0) and v=(0,1,1)#

Let A have columns u=(1,1,0) and v=(0,1,1). The entries of AᵀA are column dot products: u·u=2, u·v=1 and v·v=2. The reverse cross-product v·u also equals 1.

ATA=[2112]A^TA=\begin{bmatrix}2&1\\1&2\end{bmatrix}

For columns u=(1,1,0), v=(0,1,1) and target b=(2,3,1), dot each column with b to form the right side:

u⋅b=2+3=5v⋅b=3+1=4\begin{gathered}u\cdot b=2+3=5\\v\cdot b=3+1=4\end{gathered}

Thus Aᵀb=(5,4).

Check your reasoning

A model predicts wtwt. Data (t,b)(t,b): (1,3)(1,3), (2,1)(2,1). Form the normal equation for ww as [coefficient∣right side][\text{coefficient}\mid\text{right side}].

  1. A[34]\left[\begin{array}{r|r}3&4\end{array}\right]
  2. B[105]\left[\begin{array}{r|r}10&5\end{array}\right]
  3. C[55]\left[\begin{array}{r|r}5&5\end{array}\right]
Show answer and explanation
[55]\left[\begin{array}{r|r}5&5\end{array}\right]

∑t2=5\sum t^2=5; ∑tb=5\sum tb=5.

03For u=(1,1,0), v=(0,1,1), b=(2,3,1), each row below dots one column with u, v and b#

For u=(1,1,0), v=(0,1,1), b=(2,3,1), each row below dots one column with u, v and b. It forms 2x₁+x₂=5 and x₁+2x₂=4.

Rows labeled u and v are dotted with columns labeled u, v, b. With u=(1,1,0), v=(0,1,1), b=(2,3,1), the entries are (2,1|5) and (1,2|4). The first two columns are AᵀA; the last is Aᵀb.Rows labeled u and v are dotted with columns labeled u, v, b. With u=(1,1,0), v=(0,1,1), b=(2,3,1), the entries are (2,1|5) and (1,2|4). The first two columns are AᵀA; the last is Aᵀb.
Figure 1Rows labeled u and v are dotted with columns labeled u, v, b. With u=(1,1,0), v=(0,1,1), b=(2,3,1), the entries are (2,1|5) and (1,2|4). The first two columns are AᵀA; the last is Aᵀb.
Link to this figure ↗Download SVGDownload PNG

The normal equations can be formed even when A has dependent columns. They then need not select a unique input. Writing an inverse of AᵀA would require independent columns; forming the two products does not require an inverse.

Check your reasoning

A learner uses ∑b\sum b on the right. Repair [ATA∣ATb][A^TA\mid A^Tb]. [A∣b]=[23−11][A\mid b]=\left[\begin{array}{r|r}2&3\\-1&1\end{array}\right].

  1. A[15]\left[\begin{array}{r|r}1&5\end{array}\right]
  2. B[55]\left[\begin{array}{r|r}5&5\end{array}\right]
  3. C[54]\left[\begin{array}{r|r}5&4\end{array}\right]
Show answer and explanation
[55]\left[\begin{array}{r|r}5&5\end{array}\right]

ATb=6−1=5A^Tb=6-1=5.

04These equations explain regression geometry and lead to regularized variants later#

These equations explain regression geometry and lead to regularized variants later. Forming them and solving them are different tasks. In numerical work, QR or SVD may be preferable to explicitly forming and inverting ATAA^TA, especially when columns are nearly dependent.

Key takeaway

Form AᵀAx=Aᵀb using column dot products. These equations characterize least-squares inputs; a unique input additionally requires independent columns.

  • Form both sides of the normal equations.

Sources & further reading

  1. [1]

Reference this concept

Link to this page, a section, or an individual figure.

Glacius. “Normal equations.” Math behind ML. /learn/la-normal-equations