Over-Constrained System

Definition

${\mathbf{A}}_{m\times n}\mathbf{x}=\mathbf{b}$ where $m>n$

The number of unknowns (n) < the number of equations (m) no solution for equality

Solutions

Non-Homogeneous Over-Constrained System

solve the non-homogeneous over-constrained linear system $\mathbf{Ax}=\mathbf{b}$

The error term $(\mathbf{Ax}-\mathbf{b})$ of projection is orthogonal to the column space of $\mathbf{A}$, $\mathbf{C}(\mathbf{A})$. $(\mathbf{Ax}-\mathbf{b})\perp \mathbf{C}(\mathbf{A})$ Therefore, ${\mathbf{A}}^{⊺}(\mathbf{Ax}-\mathbf{b})=0\Rightarrow {\mathbf{A}}^{⊺}\mathbf{Ax}={\mathbf{A}}^{⊺}\mathbf{b}\Rightarrow \hat{\mathbf{x}}=({\mathbf{A}}^{⊺}\mathbf{A}{)}^{-1}{\mathbf{A}}^{⊺}\mathbf{b}$. Now, $\mathbf{A}\hat{\mathbf{x}}=\mathbf{A}({\mathbf{A}}^{⊺}\mathbf{A}{)}^{-1}{\mathbf{A}}^{⊺}\mathbf{b}$ is the least square solution and $\mathbf{A}({\mathbf{A}}^{⊺}\mathbf{A}{)}^{-1}{\mathbf{A}}^{⊺}$ become a projection matrix onto the column space of $\mathbf{A}$, $\mathbf{C}(\mathbf{A})$.

Homogeneous Over-Constrained System

solve the homogeneous over-constrained linear system $\mathbf{Ax}=0$

Let the Eigendecomposition of ${\mathbf{A}}^{⊺}\mathbf{A}$ be $({\mathbf{A}}^{⊺}\mathbf{A})\mathbf{v}=\lambda \mathbf{A}$ where $\lambda$ is the eigenvalue and $\mathbf{v}$ is the corresponding eigenvector. Then, we can change the expression into ${\mathbf{v}}^{⊺}{\mathbf{A}}^{⊺}\mathbf{Av}={\mathbf{v}}^{⊺}\lambda \mathbf{v}=\lambda {\mathbf{v}}^{⊺}\mathbf{v}=\lambda ||\mathbf{v}||$ by multiplying ${\mathbf{v}}^{⊺}$ to the both left side So, $||\mathbf{Av}|{|}^2=\lambda ||\mathbf{v}||\Rightarrow \lambda =\frac{||\mathbf{Av}|{|}^2}{||\mathbf{v}|{|}^2}\in \mathbb{R}\ge 0$ holds by the property of the real-valued gram matrix Since over-constrained system doesn’t have the solution for equality, $\mathbf{v}\ne 0\Rightarrow \lambda ||\mathbf{v}||=||\mathbf{Av}|{|}^2\ne 0$. Therefore, the eigenvalue of over-constrained system is positive and real $\lambda =\frac{||\mathbf{Av}|{|}^2}{||\mathbf{v}|{|}^2}\in \mathbb{R}>0$.

Since there is not exist the exact solution $\mathbf{x}$ for the $\mathbf{Ax}=0$, the $\underset{\mathbf{x}}{\mathrm{argmin}}||\mathbf{Av}|{|}^2$ is the best solution for the over-constrained system. By the above expansion $||\mathbf{Av}|{|}^2=\lambda ||\mathbf{v}|{|}^2$. So we can change the expression into $\underset{\mathbf{x}}{\min }||\mathbf{Av}|{|}^2=\underset{\mathbf{v}}{\min }\lambda ||\mathbf{v}|{|}^2$ Therefore, $\underset{\mathbf{x}}{\mathrm{argmin}}\lambda ||\mathbf{x}|{|}^2$ subject $||\mathbf{x}||=1$ is the eigenvector with the minimum eigenvalue of ${\mathbf{A}}^{⊺}\mathbf{A}$.

Facts

$\mathbf{Ax}$ is the linear combination of column vectors in $\mathbf{A}$. So $\mathbf{Ax}\in \mathbf{C}(\mathbf{A})$. Also, since$\mathbf{Ax}\ne \mathbf{b}$, $\mathbf{b}\notin \mathbf{C}(\mathbf{A})$. Thus, $\underset{\mathbf{x}}{\min }||\mathbf{Ax}-\mathbf{b}|{|}^2$ is the best solution. This is the projection of $\mathbf{b}$ onto the subspace of $\mathbf{A}$.

If $\mathbf{b}$ is in $\mathbf{C}(\mathbf{A})$, then $\mathbf{Ax}=\mathbf{b}$ There exists a solution satisfying all equality

If $\mathbf{b}$ is perpendicular to the every column vectors in $\mathbf{A}$, $\mathbf{C}(\mathbf{A})$, then ${\mathbf{A}}^{⊺}\mathbf{b}=0$. In other words, $\mathbf{b}$ become the Left Null Space of $\mathbf{A}$.

If $\mathbf{A}$ is square($n\times n$) and invertible, then $\mathbf{C}(\mathbf{A})$ = ${\mathbb{R}}^n$, $\mathbf{b}\in \mathbf{C}(\mathbf{A})$, and $\mathbf{Pb}=\mathbf{b}$

If $({\mathbf{A}}^{⊺}\mathbf{A})$ is non-invertable^[singular], then solve the Under-Constrained System ${\mathbf{A}}^{⊺}\mathbf{Ax}={\mathbf{A}}^{⊺}\mathbf{b}\Rightarrow \mathbf{Bx}=\mathbf{c}$