Solving Systems of Linear Equations (2)

The Minimum-Norm Solution of a Linear System

The previous post covered one case of linear systems—where the number of unknowns is smaller than the number of equations—and introduced the least-squares method. This post covers the other case, where the number of equations is smaller than the number of unknowns. Here the system has infinitely many solutions, but the one closest to the origin—the solution with the smallest norm—is unique. This is the minimum-norm solution of a linear system.

Consider the linear system $Ax=b$, where $A\in R^{m*n},m\le n$ . Finding its minimum-norm solution is equivalent to solving the following optimization problem:

\begin{align*} minimize\ ||x|| \\ subject\ to\ Ax=b \end{align*}

This is an equality-constrained optimization problem, which can be solved using the method of Lagrange multipliers; here we present a different approach.

We first state the result: the minimum-norm solution of this system is $x^{*}=A^{T}(AA^{T})^{-1}b$ . The proof follows:

||x||^{2}=||(x-x^{*})+x^{*}||^{2}\\ =||x-x^{*}||^{2}+||x^{*}||^{2}+2x^{*T}(x-x^{*})

Substituting $x^{*}=A^{T}(AA^{T})^{-1}b$ into the rightmost term above gives $2x^{*T}(x-x^{*})=0$ , so $||x||^{2}=||x-x^{*}||^{2}+||x^{*}||^{2}$ . Since $||x^{*}||^{2}$ is a fixed value, and $||x-x^{*}||^{2}>0$ holds whenever $x\neq x^{*}$ , we conclude that $x=x^{*}$ is the unique minimizer of this optimization problem, i.e., the minimum-norm solution.

The Kaczmarz Algorithm

The Kaczmarz algorithm is an iterative method for computing the minimum-norm solution. It avoids the step of computing $(AA^{T})^{-1}$ , making the computation more efficient. Assuming $A\in R^{m*n}$ , the iteration formula is given directly as follows. For the first $m$ iterations, i.e., when $k=0,1,...,m-1$ :

x^{(k+1)}=x^{(k)}+\mu(b_{k+1}-a_{k+1}^{T}x^{(k)})\frac{a_{k+1}}{a_{k+1}^{T}a_{k+1}}

For the $(m+1)$ -th iteration, we reuse the first row of $A$ and the first element of $b$ , i.e.,

x^{(m+1)}=x^{(m)}+\mu(b_{1}-a_{1}^{T}x^{(m)})\frac{a_{1}}{a_{1}^{T}a_{1}}

Every $m$ iterations the process cycles back to the beginning, and $\mu$ can be regarded as the step size of the iterative procedure. It can be proven that in the Kaczmarz algorithm, if $x^{(0)}=0$ , then as $k\to \infty$ , $x^{(k)}\to x^{*}=A^{T}(AA^{T})^{-1}b$ . The detailed proof is omitted here.

In a later post we will cover the general methods for solving linear systems, the pseudoinverse, and related topics. To be continued…

Technology

2018 · 07 · 21