Minimum Norm Problem

The Problem

Consider the problem

where $A \in \mathbb C^{m \times n}$ is full rank and $m < n$.

This is an under-determined system with an infinite number of solutions.

Suppose $\pmb x_0$ is a solution to the problem such that $A \pmb x_0 = \pmb b$.

Since $A$ has more columns than rows, the $\mathcal N(A)$ is non-trivial

Therefore we now have an infinite set of solutions. For every $\pmb v \in \mathcal N(A)$ we have another solution $A(\pmb x_0 + \pmb v) = \pmb b$.

These solutions form an affine set of solutions.

To pin down a specific $\pmb x$ we put a norm on $\pmb x$ that we want to minimize subject to satisfying this system of equations.

This new formulation is written as

Solving

We know that all solutions to the problem must satisfy the constraint so let’s investigate $A$ and its null space a bit further.

Let the rows of $A$ be written as:

Then using knowledge that $\pmb v \in \mathcal N(A)$ we have

Since $\pmb y_i^H \pmb v = 0$, each vector in the null space is orthogonal to $\pmb y_i^H$.

Therefore $\mathcal N(A) = M^\perp$ where $M = \text{span}(\pmb y_1 \dots, \pmb y_m)$.

Thus we now now know that the candidate solutions come from $\pmb x_0 + M^\perp$.

We don’t have enough tools to prove this next part beyond proof by picture but the “shortest” solution is orthogonal to $M^\perp$. In other words $\pmb x \in (M^{\perp\perp}=M=\text{span}(\pmb y_1 \dots, \pmb y_m))$. Therefore the best $\pmb x$ can be expressed as

Now returning to the constraint $A \pmb x = \pmb b$ and using our new found knowledge of $\pmb x$ we write

Bringing it all home