ChapterZero

Full-rank underdetermined systems

Filed under: Mathematics — Alex @ 6:07 pm 11/2/2006

Usually when we think of non-square systems of linear equations, we think of skinny full rank matrices: i.e., of systems of the form

$\displaystyle Ax = b, \quad A \in \C^{m \times n}, m > n, \text{rank}(A)=n.$

One way of solving these systems is to use the (reduced) QR factorization, which decomposes into a matrix $Q \in \C^{m \times n}$ which has orthonormal columns, and an upper-triangular invertible matrix $R \in \C^{n \times n}$ . Intuitively, the Q matrix is the result of applying the Gram-Schmidt orthonormalization process to the columns of , and combines the columns of to get back . There is also a full factorization, A= Q_f R_f where $Q_f \in \C^{m \times m}$ is unitary, and $R_f \in \C^{m \times n}$ is upper triangular. A full factorization can be obtained from a reduced one by completing the basis in , and adding m-n zeros to the bottom of .

Something really cool, that I learnt today while doing my linear algebra homework, is that the QR factorization is useful for solving full-rank underdetermined systems as well. That is, suppose your problem is now
$\displaystyle Ax = b, \quad A \in \C^{m \times n}, m < n, \text{rank}(A)=m.$

Then this has at least one solution, but there may be multiple ones. What if you'd like to select the solution with minimum Euclidean norm? The idea is that $A^\star$ is a full-ranked skinny matrix, so has a QR decomposition: $A^\star = QR$ .

Then minimizing $\|x\|$ given Ax = b is the same as minimizing it given $x^\star Q R = b^\star$ , which is the same as minimizing it given $Q(R^\star)^{-1} b = QQ^\star x$ (since $Q^\star Q = I$ , remember has orthonormal columns). But then $QQ^\star$ is a projection, so the with minimum length that satisfies this equation is just $QQ^\star (Q(R^\star)^{-1}b) = Q(R^\star)^{-1}b$ . So the minimum length vectors that satisfies Ax = b is simply $Q(R^\star)^{-1}b$ . Pretty neat.