Least squares approximation | Linear Algebra | Khan Academy

1. Audio
   Observation

   The speaker says, "Let's say I have some matrix A."

2. Formula
   Observation

   Yellow handwritten $A$ is written at the upper left.

A

An $n \times k$ matrix whose columns are used to form linear combinations.

$A \in \mathbb{R}^{n \times k}$

1. Audio
   Observation

   The speaker says, "I have the equation Ax is equal to b" and later "x would have to be a member of Rk."

2. Formula
   Observation

   Yellow handwritten $\vec{x}$ appears in $A\vec{x}=\vec{b}$, with $\vec{x}\in\mathbb{R}^k$ written nearby.

$\vec{x}$

Unknown vector in the matrix equation $A\vec{x}=\vec{b}$.

$\vec{x}\in\mathbb{R}^k$

1. Audio
   Observation

   The speaker says, "Ax is equal to b" and "b is a member of Rn."

2. Formula
   Observation

   Yellow handwritten $\vec{b}$ appears in $A\vec{x}=\vec{b}$, with $\vec{b}\in\mathbb{R}^n$ written nearby.

$\vec{b}$

Right-hand-side vector in the equation $A\vec{x}=\vec{b}$.

$\vec{b}\in\mathbb{R}^n$

1. Audio
   Observation

   The speaker says, "it's an n by k matrix" and explains that $x$ has $k$ entries because there are $k$ columns.

2. Formula
   Observation

   Yellow handwritten $n \times k$ is placed under $A$.

n, k

Dimensions of $A$: $n$ rows and $k$ columns.

Positive integers

1. Audio
   Observation

   The speaker says, "If I write A like this, A1, A2 ... all the way through Ak" and refers to them as column vectors.

2. Formula
   Observation

   Pink handwritten bracketed expression $[\vec{a}_1\ \vec{a}_2\ \cdots\ \vec{a}_k]$ is written below the initial equation.

$\vec{a}_1$,$\vec{a}_2$,$\ldots$,$\vec{a}_k$

Column vectors of $A$, indexed from $1$ to $k$.

Each $\vec{a}_j$ is a column of $A$; hence $\vec{a}_j\in\mathbb{R}^n$

1. Audio
   Observation

   The speaker says, "multiply it times x1, x2 all the way through xk."

2. Formula
   Observation

   Pink handwritten column vector $\begin{bmatrix}x_1\\x_2\\\vdots\\x_k\end{bmatrix}$ is written next to the column expansion of $A$.

$x_1$,$x_2$,$\ldots$,$x_k$

Scalar components of the unknown vector $\vec{x}$, used as weights on the columns of $A$.

$x_j\in\mathbb{R}$ for $j=1,\ldots,k$

1. Audio
   Observation

   The speaker says, "b is not in the column space of A."

2. Formula
   Observation

   Yellow handwritten text states "$\vec{b}$ is not in the $C(A)$".

$C(A)$

Column space of $A$, i.e. the set of all linear combinations of the columns of $A$.

Subspace of $\mathbb{R}^n$

1. Audio
   Observation

   The speaker says, "I want to find some x star for now where A times x star is..."

2. Formula
   Observation

   Yellow handwritten $\vec{x}^*$ appears at the lower left, followed by "where $A\vec{x}^*$".

1. The sentence and displayed condition after $A\vec{x}^*$ are cut off before completion.

$\vec{x}^*$

A candidate vector introduced for a better approximate solution when $A\vec{x}=\vec{b}$ has no exact solution.

Intended to lie in $\mathbb{R}^k$ by analogy with $\vec{x}$, but the clip does not explicitly restate the domain

1. Formula
   Observation

   Matrix A appears in $A x = b$ and is described as $n\times k$.

2. Audio
   Observation

   The speaker refers to multiplying a vector by the matrix A and getting a member of its column space.

A

An $n\times k$ matrix whose columns span $C(A)$.

$n\times k$ matrix

1. Formula
   Observation

   $x \in R^k$ is written beside $A x = b$.

2. Audio
   Observation

   The speaker says any vector in $R^k$ times the matrix A gives a member of the column space.

x

Unknown vector in $R^k$.

$R^k$

1. Formula
   Observation

   $b \in R^n$ is written beside $A x = b$.

2. Audio
   Observation

   The speaker repeatedly refers to making Ax* as close as possible to b.

b

Target vector in $R^n$ that generally lies outside $C(A)$ in this setup.

$R^n$

1. Formula
   Observation

   x* is introduced in the line 'x* where Ax* is as close to b as possible'.

2. Audio
   Observation

   The speaker defines x* through minimizing ||b - Ax*||.

x^*

Vector chosen so that Ax* is the closest point in $C(A)$ to b.

$R^k$

1. Audio
   Observation

   The speaker introduces a matrix $A$ that is $n$ by $k$ and the equation $Ax=b$, then states the dimensions of $x$ and $b$.

2. Formula
   Observation

   Yellow handwritten $A$, $n\times k$, $A\vec{x}=\vec{b}$, $\vec{x}\in\mathbb{R}^k$, and $\vec{b}\in\mathbb{R}^n$ appear across the top of the board.

The clip begins with a general linear system written as $A\vec{x}=\vec{b}$, where $A$ is an $n\times k$ matrix. Dimension compatibility forces $\vec{x}$ to have $k$ entries and $\vec{b}$ to have $n$ entries, so $\vec{x}\in\mathbb{R}^k$ and $\vec{b}\in\mathbb{R}^n$.

1. $A$ has $n$ rows and $k$ columns

2. The product $A\vec{x}$ is defined only when $\vec{x}$ has $k$ entries

3. The resulting vector has $n$ entries, matching $\vec{b}$

1. A
2. $\vec{x}$
3. $\vec{b}$
4. n, k

1. Audio
   Observation

   The speaker expands $A$ into its column vectors and multiplies by the components of $x$, saying this is the same equation rewritten.

2. Formula
   Observation

   Pink handwritten $[\vec{a}_1\ \vec{a}_2\ \cdots\ \vec{a}_k]\begin{bmatrix}x_1\\x_2\\\vdots\\x_k\end{bmatrix}=\vec{b}$ is written, followed by $x_1\vec{a}_1+x_2\vec{a}_2+\cdots+x_k\vec{a}_k=\vec{b}$.

The equation $A\vec{x}=\vec{b}$ is rewritten by expressing $A$ in terms of its columns. Multiplying the column-expanded matrix by the component vector gives the weighted sum of the columns of $A$, showing that solving $A\vec{x}=\vec{b}$ is equivalent to finding weights that express $\vec{b}$ as a linear combination of the columns of $A$.

1. $\vec{a}_j$ denotes the $j$th column of $A$

2. $x_j$ denotes the $j$th component of $\vec{x}$

3. The equivalence uses the standard column interpretation of matrix-vector multiplication

1. Matrix equation setup and dimension matching
2. $\vec{a}_1$,$\vec{a}_2$,$\ldots$,$\vec{a}_k$
3. $x_1$,$x_2$,$\ldots$,$x_k$

1. Audio
   Observation

   The speaker says there is no solution, then explains that this means no set of weights on the column vectors of $A$ can get to $b$, equivalently no linear combination equals $b$, and finally says $b$ is not in the column space of $A$.

2. Formula
   Observation

   Cyan handwritten text reads "No solution to $A\vec{x}=\vec{b}$"; yellow handwritten text reads "$\vec{b}$ is not in the $C(A)$".

When $A\vec{x}=\vec{b}$ has no solution, the vector $\vec{b}$ cannot be obtained as any linear combination of the columns of $A$. The clip names this geometrically by saying $\vec{b}$ is not in the column space $C(A)$.

1. $C(A)$ is the set of all linear combinations of the columns of $A$

2. The equivalence is stated for the specific system under discussion

1. Matrix-vector product as a linear combination of columns
2. $C(A)$

1. Formula
   Observation

   The board states 'No solution to Ax = b' and shows the equivalent column-combination equation.

2. Diagram
   Observation

   A cyan arrow labeled b points outside the purple plane labeled $C(A)$, with text 'b is not in the $C(A)$'.

This segment begins from the case where the exact linear system Ax=b has no solution because b does not belong to the column space of A. The video expresses Ax both as a matrix product and as a linear combination of the columns of A, making clear that solvability requires b to lie in $C(A)$.

1. A is $n\times k$

2. $x \in R^k$

3. $b \in R^n$

4. b ∉ $C(A)$ in the motivating picture

1. Formula
   Observation

   The speaker writes 'minimize ||b - Ax*||'.

2. Audio
   Observation

   He says, 'when I say close, I'm talking about length' and 'I want to minimize the length of b minus Ax*'.

3. Diagram
   Observation

   The vector Ax* is identified with v inside $C(A)$, while b remains outside the plane.

The least-squares idea is introduced geometrically: choose x* so that Ax*, viewed as a point v in the column space, is as close as possible to b. Closeness is measured by vector length, so the problem becomes minimizing the norm of the residual b - Ax*.

1. Ax* must lie in $C(A)$

2. Distance is measured by Euclidean length

1. Inconsistent system Ax=b when b is outside $C(A)$

1. Audio
   Observation

   The speaker says, 'Ax is going to be a member of my column space' and repeats that any Ax is in the column space.

2. Formula
   Observation

   He writes v = Ax* on the diagram.

3. Diagram
   Observation

   The vector v is placed inside the purple plane labeled $C(A)$.

The video uses the identity v = Ax* to translate the optimization into a geometric search inside $C(A)$. Because Ax is always a linear combination of the columns of A, the candidate output vector must remain in the column space, and the task is to pick the best such vector relative to b.

1. $x* \in R^k$

2. A is $n\times k$

1. Inconsistent system Ax=b when b is outside $C(A)$
2. Least-squares objective as distance minimization

1. Formula
   Observation

   The board expands the norm into the vector [$b_1 - v_1$, $b_2 - v_2$, ..., $b_n - v_n$]^T.

2. Audio
   Observation

   The speaker says to take the difference between each of the elements.

Once v = Ax* is introduced, the residual b - Ax* is rewritten as b - v and then displayed as the vector of componentwise differences. This makes explicit that the distance being minimized depends on all coordinate mismatches between b and the chosen column-space vector v.

1. b,$v \in R^n$

1. Every Ax lies in the column space $C(A)$
2. Least-squares objective as distance minimization

1. Formula
   Observation

   The board shows ||[$b_1-v_1$, ..., $b_n-v_n$]^T||^$2 = (b_1-v_1)^2 + (b_2-v_2)^2$ + ... + ($b_n-v_n$)^2.

2. Audio
   Observation

   The speaker says, 'the length squared of this is just going to be ...' and lists the squared terms.

The lecture converts the geometric minimization of length into an algebraic minimization of a sum of squares. By squaring the residual norm, the objective becomes the explicit quadratic expression in the componentwise errors, which motivates the terminology 'least squares'.

1. Using the standard Euclidean norm on $R^n$

1. Residual vector written componentwise

1. Audio
   Observation

   The speaker says, 'I want to get the least squares estimate here' and explains that this is why it is called the least squares estimate.

2. Formula
   Observation

   The board adds the label 'least squares' pointing to x*.

After deriving the sum-of-squared-residuals form, the video names the object x* as the least squares estimate, also calling it the least squares solution or least squares approximation for Ax=b. The terminology is tied directly to minimizing the sum of squared component errors.

1. The minimization is over Ax* ∈ $C(A)$ approximating b

1. Squared Euclidean length equals sum of squared residuals
2. Least-squares objective as distance minimization

1. Formula
   Observation

   The board states 'No solution to Ax=b' and introduces x^* with A x^* as close to b as possible.

2. Audio
   Observation

   The speaker says there is no solution to this, but maybe we can find some x^* where A times x^* is as close to b as possible.

When the exact linear system Ax=b is inconsistent, the video defines a least-squares approach: choose x^* so that A x^* lies in the column space of A and is as close as possible to b.

1. Ax=b has no exact solution

2. A x^* must lie in $C(A)$

1. Formula
   Observation

   The board writes 'minimize ||b - A x^*||'.

2. Audio
   Observation

   The speaker says they want to get this vector to be as close to b as possible.

The least-squares problem is posed as minimizing the norm of the difference between b and A x^*.

1. b is fixed

2. x^* is the variable being chosen

1. Least-squares setup when Ax=b has no solution

1. Audio
   Observation

   The speaker says the closest vector in any subspace to a vector not in that subspace is the projection.

2. Formula
   Observation

   The board later writes A x^* = proj_{$C(A)$} b.

For a vector outside a subspace, the nearest point inside that subspace is its orthogonal projection onto the subspace. In this lesson the subspace is $C(A)$.

1. $C(A)$ is treated as a subspace

2. b is not in $C(A)$

1. Least-squares setup when Ax=b has no solution

1. Audio
   Observation

   The speaker states three equivalent ways of describing the same situation: no weights on the columns reach $b$, no linear combination equals $b$, and $b$ is not in the column space of $A$.

2. Formula
   Observation

   The board shows the expanded linear-combination equation and the statement "$\vec{b}$ is not in the $C(A)$".

For the system $A\vec{x}=\vec{b}$, having no solution is equivalent to saying that $\vec{b}$ is not a linear combination of the columns of $A$, equivalently $\vec{b}\notin C(A)$.

1. $A$ is an $n\times k$ matrix

2. $\vec{x}\in\mathbb{R}^k$ and $\vec{b}\in\mathbb{R}^n$

3. $C(A)$ denotes the column space of $A$

For the given matrix $A$ and vector $\vec{b}$, the absence of any $\vec{x}$ satisfying $A\vec{x}=\vec{b}$ is equivalent to $\vec{b}\notin C(A)$.

1. Formula
   Observation

   The board explicitly states 'b is not in the $C(A)$'.

2. Diagram
   Observation

   The cyan vector b is drawn outside the purple plane $C(A)$.

3. Audio
   Observation

   The spoken explanation continues from the premise that there is no solution to Ax=b.

In the setup shown, because b is not in the column space $C(A)$, the equation Ax=b has no solution.

1. A is $n\times k$

2. $x \in R^k$

3. $b \in R^n$

4. b ∉ $C(A)$

For the displayed A, x, and b in this example setup.

1. Audio
   Observation

   The speaker says, 'any Ax is going to be in your column space' and repeats the statement.

2. Formula
   Observation

   He writes v = Ax* and places v inside $C(A)$.

For any $x \in R^k$, the vector Ax is a member of the column space $C(A)$.

1. A is $n\times k$

2. $x \in R^k$

For all x in $R^k$.

1. Formula
   Observation

   The objective is written as minimize ||b - Ax*||.

2. Audio
   Observation

   The speaker says he wants Ax* to be as close as possible to b and identifies Ax* with v in $C(A)$.

Choosing x* to minimize ||b - Ax*|| is equivalent to choosing the vector v = Ax* in $C(A)$ that is closest to b.

1. $b \in R^n$

2. A is $n\times k$

3. $x* \in R^k$

4. Distance measured by Euclidean norm

For the given A and b in the inconsistent-system setup.

1. Formula
   Observation

   The board displays the equality between the squared norm and the sum of squared component differences.

2. Audio
   Observation

   The speaker verbally derives the same expression as the length squared.

For b,$v \in R^n$, ||b-v||^$2 = (b_1-v_1)^2 + (b_2-v_2)^2$ + ... + ($b_n-v_n$)^2.

1. b,$v \in R^n$

2. Standard Euclidean norm

For all component indices $i = 1$,...,n.

1. Audio
   Observation

   The speaker states that the closest vector to b that is in the subspace is the projection of b onto the column space.

2. Diagram
   Observation

   The diagram shows b outside the plane $C(A)$ and identifies the nearest point in the plane as the projection.

If b is not in a subspace, then the closest vector to b inside that subspace is the orthogonal projection of b onto the subspace.

1. There is a subspace, here $C(A)$

2. b is a vector not in that subspace

For the given vector b and the given subspace $C(A)$.

1. Formula
   Observation

   The board writes and boxes A x^* = proj_{$C(A)$} b.

2. Audio
   Observation

   The speaker says Ax needs to be equal to the projection of b on my column space.