17 Projections, Least Squares, Linear Regression

Lecture from 13.11.2024 | Video: Videos ETHZ

Projections

Videos ETHZ (Previous Year)

Definition: Projection onto a Subspace

The projection of a vector $\mathbf{b}\in {\mathbb{R}}^m$ onto a subspace $S\subseteq {\mathbb{R}}^m$ is the closest point $\mathbf{p}$ in $S$ to $\mathbf{b}$. Formally:

${\text{proj}}_S(\mathbf{b})=\underset{\mathbf{p}\in S}{\mathrm{argmin}}\Vert \mathbf{b}-\mathbf{p}\Vert$

Projection onto a Subspace (General Case)

Given a subspace $S=\mathcal{C}(A)$ (where $A$ is an $m\times n$ matrix whose columns form a basis for $S$), the projection of $\mathbf{b}$ onto $S$ is:

${\text{proj}}_S(\mathbf{b})=A\hat{\mathbf{x}}$

where $\hat{\mathbf{x}}$ satisfies the normal equations:

$A^{T}A\hat{\mathbf{x}}=A^T\mathbf{b}$

Derivation: The error vector $\mathbf{e}=\mathbf{b}-A\hat{\mathbf{x}}$ is orthogonal to $S$, meaning it’s orthogonal to each column of $A$. This leads to the normal equations.

$A^{T}A$ Invertible

Lemma 5.2.4

The matrix $A^{T}A$ is invertible if and only if the matrix $A$ has linearly independent columns.

Proof

We will prove the equivalence by chaining together several “if and only if” statements:

1. $A^{T}A$ is invertible $⟺$ $A^{T}A$ has linearly independent columns: This is a fundamental property of matrices. A square matrix is invertible if and only if its columns (or rows) are linearly independent.

2. $A^{T}A$ has linearly independent columns $⟺$ $\mathcal{N}(A^{T}A)=\{0\}$: The nullspace of a matrix contains only the zero vector if and only if its columns are linearly independent. If there were a non-zero vector in the nullspace, it would represent a non-trivial linear combination of the columns that equals zero, contradicting linear independence.

3. $\mathcal{N}(A^{T}A)=\{0\}⟺\mathcal{N}(A)=\{0\}$: We’ve proven this previously (see the lemma about the link between nullspaces of $A$ and $A^{T}A$).

4. $\mathcal{N}(A)=\{0\}⟺$ Columns of $A$ are linearly independent: Again, this is a fundamental property. The nullspace of a matrix contains only the zero vector if and only if its columns are linearly independent.

Therefore, by connecting these equivalences, we have shown that $A^{T}A$ is invertible if and only if $A$ has linearly independent columns. This result is essential for least squares problems, as it guarantees a unique solution when the columns of $A$ are linearly independent.

Explicit Formula for Projection (Theorem 5.2.6)

When the columns of matrix $A$ are linearly independent, we can derive a direct formula for the projection of $\mathbf{b}$ onto the subspace $S$ spanned by those columns ($S=\mathcal{C}(A)$).

1. Normal Equations: We know the projection ${\text{proj}}_S(\mathbf{b})$ can be expressed as $A\hat{\mathbf{x}}$, where $\hat{\mathbf{x}}$ satisfies the normal equations: $A^{T}A\hat{\mathbf{x}}=A^T\mathbf{b}$.

2. Invertibility of $A^{T}A$: A crucial fact (proven in Lemma 5.2.4) is that if $A$ has linearly independent columns, then the matrix $A^{T}A$ is invertible. This invertibility is key to finding a direct solution for $\hat{\mathbf{x}}$.

3. Solving for $\hat{\mathbf{x}}$: Since $A^{T}A$ is invertible, we can solve for $\hat{\mathbf{x}}$ by multiplying both sides of the normal equations by $(A^{T}A{)}^{-1}$: $\hat{\mathbf{x}}=(A^{T}A{)}^{-1}{A}^T\mathbf{b}$

4. The Projection Formula: Substitute this expression for $\hat{\mathbf{x}}$ back into ${\text{proj}}_S(\mathbf{b})=A\hat{\mathbf{x}}$: ${\text{proj}}_S(\mathbf{b})=A(A^{T}A{)}^{-1}{A}^T\mathbf{b}$

5. The Projection Matrix: This formula reveals that the projection operation is a linear transformation represented by the matrix $P=A(A^{T}A{)}^{-1}{A}^T$. We call $P$ the projection matrix. So, the projection is simply:

   ${\text{proj}}_S(\mathbf{b})=P\mathbf{b}$

Properties of P:

• Idempotence ($P^2=P$): Projecting a vector that’s already in the subspace $S$ shouldn’t change it. Mathematically, projecting the projection gives the same projection: $P(P\mathbf{b})=P^2\mathbf{b}=P\mathbf{b}$.

  Proof: $P^2=(A(A^{T}A{)}^{-1}{A}^T)(A(A^{T}A{)}^{-1}{A}^T)=AI(A^{T}A{)}^{-1}{A}^T=P$

• Projection onto the Orthogonal Complement: The matrix $I-P$ projects onto $S^{\perp }$, the orthogonal complement of $S$. This is because $\mathbf{b}$ can be uniquely decomposed as the sum of its projection onto $S$ and its projection onto $S^{\perp }$: $\mathbf{b}=P\mathbf{b}+(I-P)\mathbf{b}$.

  

  Proof: Let $\mathbf{p}$ be the projection of $\mathbf{b}$ onto $S$. Then $\mathbf{p}=P\mathbf{b}$. The error vector $\mathbf{e}$ is the difference between $\mathbf{b}$ and its projection $\mathbf{p}$: $\mathbf{e}=\mathbf{b}-\mathbf{p}=\mathbf{b}-P\mathbf{b}=(I-P)\mathbf{b}$

• Idempotence of $(I-P)$: Similar to $P$, projecting onto $S^{\perp }$ twice has the same effect as projecting once: $(I-P{)}^2=I-2P+P^2=I-2P+P=I-P$.

• Invertibility: It’s important to note that while $A$ and $A^T$ might not be square and therefore might not have inverses, the matrix $A^{T}A$ is always square. And when the columns of $A$ are linearly independent, $A^{T}A$ is guaranteed to be invertible.

Least Squares

Videos ETHZ (Previous Year)

Definition

Given $A\in {\mathbb{R}}^{m\times n}$ and $\mathbf{b}\in {\mathbb{R}}^m$, a least squares solution minimizes the squared error:

${\min }_{\mathbf{x}\in {\mathbb{R}}^n}\Vert A\mathbf{x}-\mathbf{b}{\Vert }^2$

Connection to Projections

The least squares solution is equivalent to finding the projection of $\mathbf{b}$ onto the column space of $A$:

${\min }_{\mathbf{x}\in {\mathbb{R}}^n}\Vert A\mathbf{x}-\mathbf{b}{\Vert }^2={\min }_{\mathbf{p}\in \mathcal{C}(A)}\Vert \mathbf{b}-\mathbf{p}{\Vert }^2=\Vert \mathbf{b}-{\text{proj}}_{\mathcal{C}(A)}(\mathbf{b}){\Vert }^2$

The least squares solution $\hat{\mathbf{x}}$ is given by the normal equations: $A^{T}A\hat{\mathbf{x}}=A^T\mathbf{b}$. If $A$ has linearly independent columns, the explicit solution is $\hat{\mathbf{x}}=(A^{T}A{)}^{-1}{A}^T\mathbf{b}$.

Application: Linear Regression

Linear regression aims to find the “best-fitting” straight line through a set of data points $(t_k,b_k)$, where $k=1,\dots ,m$. We represent this line by the equation $y={\alpha }_0+{\alpha }_{1}t$, where ${\alpha }_0$ is the y-intercept and ${\alpha }_1$ is the slope. “Best-fitting” means minimizing the sum of the squared vertical distances between the data points and the line.

The vertical distance between a data point $(t_k,b_k)$ and the line $y={\alpha }_0+{\alpha }_{1}t$ at $t=t_k$ is given by $|b_k-({\alpha }_0+{\alpha }_1{t}_k)|$. We square these distances to eliminate the absolute value and to penalize larger deviations more heavily. The sum of squared errors is:

${\sum }_{k=1}^m(b_k-({\alpha }_0+{\alpha }_1{t}_k){)}^2$

We are effectively summing up the error $error=(b_{real}-b_{approx}{)}^2$ for each $k$. Our goal is to find the values of ${\alpha }_0$ and ${\alpha }_1$ that minimize this sum.

Given an ${\alpha }_0,{\alpha }_1$ we can use them to create a line.

Matrix-Vector Formulation:

We can express this problem concisely using matrices and vectors. Let’s define:

• $A=\left[\begin{array}{cc}1& t_1\\ ⋮& ⋮\\ 1& t_m\end{array}\right]$: This $m\times 2$ matrix holds the $t$ values (and a column of 1s so that we can multiply by ${\alpha }_0$ to get the constant term).
• $\mathbf{x}=\left[\begin{array}{c}{\alpha }_0\\ {\alpha }_1\end{array}\right]$: This vector holds the unknowns we want to determine.
• $\mathbf{b}=\left[\begin{array}{c}{b}_1\\ ⋮\\ b_m\end{array}\right]$: This vector holds the $b$ values (the vertical coordinates of the data points).

Now, the product $A\mathbf{x}$ gives us the predicted $y$ values for each $t_k$:

$A\mathbf{x}=\left[\begin{array}{cc}1& t_1\\ ⋮& ⋮\\ 1& t_m\end{array}\right]\left[\begin{array}{c}{\alpha }_0\\ {\alpha }_1\end{array}\right]=\left[\begin{array}{c}{\alpha }_0+{\alpha }_1{t}_1\\ ⋮\\ {\alpha }_0+{\alpha }_1{t}_m\end{array}\right]$

The difference between the actual $\mathbf{b}$ values and the predicted $A\mathbf{x}$ values represents the errors: $A\mathbf{x}-\mathbf{b}$. The sum of squared errors is then $\Vert A\mathbf{x}-\mathbf{b}{\Vert }^2$. Thus, the linear regression problem becomes:

${\min }_{\mathbf{x}}\Vert A\mathbf{x}-\mathbf{b}{\Vert }^2$

This is a least squares problem.

Explicit Solution for Linear Regression Coefficients

We can solve this least squares problem using the normal equations:

$A^{T}A\mathbf{x}=A^T\mathbf{b}$

Solving this system of equations for $\mathbf{x}$ gives us the optimal values for ${\alpha }_0$ and ${\alpha }_1$.

The explicit solution for the linear regression coefficients ${\alpha }_0$ and ${\alpha }_1$, when the matrix A has linearly independent columns, is given by:

$\left[\begin{array}{c}{\alpha }_0\\ {\alpha }_1\end{array}\right]=(A^{T}A{)}^{-1}{A}^T\mathbf{b}$

Expanding $A^{T}A$ and $A^T\mathbf{b}$ gives:

$\left[\begin{array}{c}{\alpha }_0\\ {\alpha }_1\end{array}\right]={\left[\begin{array}{cc}m& {\sum }_{k=1}^m{t}_k\\ {\sum }_{k=1}^m{t}_k& {\sum }_{k=1}^m{t}_k^2\end{array}\right]}^{-1}\left[\begin{array}{c}{\sum }_{k=1}^m{b}_k\\ {\sum }_{k=1}^m{b}_k{t}_k\end{array}\right]$

This formula provides a direct way to calculate ${\alpha }_0$ and ${\alpha }_1$ from the data points $(t_k,b_k)$. It’s important to remember that this explicit form relies on the invertibility of $A^{T}A$, which holds when the columns of $A$ (and thus the $t_k$ values) are not all identical. If the $t_k$ values are all the same, the matrix $A^{T}A$ is singular, and we must resort to other methods to find a “best-fit” solution (which, in the case of $t_k$ all being equal, would represent a vertical line).

Another good video…

Practice problem…

Linear Independence

The columns of $A$ are linearly independent unless all the $t_k$ values are identical. If all $t_k$ are the same, the columns of $A$ are linearly dependent, and $A^{T}A$ is not invertible, meaning there isn’t a unique least squares solution. Geometrically, this corresponds to all data points lying on a vertical line, in which case any vertical line through the data points would minimize the (vertical) least squares error. However, if there is even a slight variation in the $t_k$ values, the columns of $A$ become linearly independent, and a unique least squares solution exists. This unique solution corresponds to the familiar “line of best fit.”

Simplification with Orthogonal Columns (Observation 5.3.3)

The columns of $A$ are orthogonal if their dot product is zero. For the given design matrix, this means:

$\left[\begin{array}{c}1\\ 1\\ ⋮\\ 1\end{array}\right]\cdot \left[\begin{array}{c}{t}_1\\ t_2\\ ⋮\\ t_m\end{array}\right]={\sum }_{k=1}^m(1)(t_k)={\sum }_{k=1}^m{t}_k=0$

So, the condition for orthogonality of the columns of A is that the sum of the independent variable values ($t_k$) is zero.

Simplified Normal Equations

The normal equations are given by $A^{T}A\mathbf{x}=A^T\mathbf{b}$. If the columns of $A$ are orthogonal (i.e., ${\sum }_{k=1}^m{t}_k=0$), then $A^{T}A$ becomes:

$A^{T}A=\left[\begin{array}{cccc}1& 1& \dots & 1\\ t_1& t_2& \dots & t_m\end{array}\right]\left[\begin{array}{cc}1& t_1\\ 1& t_2\\ ⋮& ⋮\\ 1& t_m\end{array}\right]=\left[\begin{array}{cc}m& {\sum }_{k=1}^m{t}_k\\ {\sum }_{k=1}^m{t}_k& {\sum }_{k=1}^m{t}_k^2\end{array}\right]=\left[\begin{array}{cc}m& 0\\ 0& {\sum }_{k=1}^m{t}_k^2\end{array}\right]$

Simplified Solution: Since $A^{T}A$ is diagonal, its inverse is easy to compute:

$(A^{T}A{)}^{-1}=\left[\begin{array}{cc}\frac{1}{m}& 0\\ 0& \frac{1}{{\sum }_{k=1}^m{t}_k^2}\end{array}\right]$

And the least squares solution $\mathbf{x}=\left[\begin{array}{c}{\alpha }_0\\ {\alpha }_1\end{array}\right]$ becomes:

$\left[\begin{array}{c}{\alpha }_0\\ {\alpha }_1\end{array}\right]=(A^{T}A{)}^{-1}{A}^T\mathbf{b}=\left[\begin{array}{cc}\frac{1}{m}& 0\\ 0& \frac{1}{{\sum }_{k=1}^m{t}_k^2}\end{array}\right]\left[\begin{array}{c}{\sum }_{k=1}^m{b}_k\\ {\sum }_{k=1}^m{b}_k{t}_k\end{array}\right]=\left[\begin{array}{c}\frac{1}{m}{\sum }_{k=1}^m{b}_k\\ \frac{{\sum }_{k=1}^m{b}_k{t}_k}{{\sum }_{k=1}^m{t}_k^2}\end{array}\right]$

Fitting a Parabola (Quadratic Regression)

Just as we fit a line to data points using linear regression, we can fit a parabola (or any higher-degree polynomial) using a similar least squares approach. For a parabola, the model is:

$b_k\approx {\alpha }_0+{\alpha }_1{t}_k+{\alpha }_2{t}_k^2$

where $(t_k,b_k)$ are the data points, and ${\alpha }_0$, ${\alpha }_1$, and ${\alpha }_2$ are the coefficients we want to determine.

Matrix-Vector Formulation:

To formulate this as a least squares problem, we define the following matrices and vectors:

• $A=\left[\begin{array}{ccc}1& t_1& t_1^2\\ 1& t_2& t_2^2\\ ⋮& ⋮& ⋮\\ 1& t_m& t_m^2\end{array}\right]$. Each row corresponds to a data point, and the columns represent the constant, linear, and quadratic terms.

• $\mathbf{x}=\left[\begin{array}{c}{\alpha }_0\\ {\alpha }_1\\ {\alpha }_2\end{array}\right]$: This vector contains the unknown parabola coefficients.

• $\mathbf{b}=\left[\begin{array}{c}{b}_1\\ b_2\\ ⋮\\ b_m\end{array}\right]$: This vector holds the $b_k$ values of the data points.

The least squares problem is then: ${\min }_{{\alpha }_0,{\alpha }_1,{\alpha }_2}\Vert A\mathbf{x}-\mathbf{b}{\Vert }^2$ Note that we can extend this to cubic, quadratic, etc… powers.

Continue here: 18 Orthonormal Bases, Properties of Orthogonal Matrices