Solving Linear Equations using QR Decomposition

QR decomposition is another powerful technique to solve linear equations. In QR decomposition, the co-efficient matrix $A \in \mathcal{R}^{M\times K}$ need not to be a symmetric matrix. In special cases where the input signal is compressible or sparse, QR decomposition can directly operate on matrix $A$ if $K$ less than $M$ . This way an underdetermined linear system is solved. Matrix $A$ is factored using QR factorization as

(1)

where matrix $Q$ is an orthonormal matrix of size $M\times M$ and $R$ is an upper-triangular matrix with non-zero diagonal entries of size $K\times K$ . The pseudoinverse is computed as

(2)

If matrix $A$ is square then there is no need to append zero to the $R^{-1}$ matrix. The signal estimation is computed as follows

(3)

where $Y = \langle{Q}^{T},y\rangle$ is the inner product between $Q^T$ and y. The signal estimation $\hat{x}$ can be computed in two ways. One possible way is to compute the pseudoinverse and then multiply it with $y$ . On the other hand, $Y$ can be evaluated first and then the result is multiplied by the inverse of $R$ . The later method saves the timing complexity of pseudoinverse computation and storage requirement to store the pseudoinverse matrix.

The inverse of the $R$ matrix is computed by the following two equations

(4)

QR decomposition can be evaluated in three possible ways and they are Gram-Schimdt (GS) algorithm, Householder algorithm, and Givens rotation (GR) algorithm. Out of these three algorithms, the modified Gram-Schimdt algorithm (MGS) and GR algorithm are mostly used. These two algorithms are discussed here.

Solving linear equations using MGS algorithm

MGS algorithm is the most popular technique to factorize a matrix into $Q$ and $R$ . This algorithm has many use in the field of linear algebra. MGS algorithm is more efficient than the GS algorithm in terms of accuracy over the iterations. MGS algorithm is shown in Algorithm 1. This algorithm involves several vector-vector products and scalar-vector products. The major hurdle of this algorithm is to compute ${||u||}_2$ which indicates norm-2 of the column vector $u$ . Norm-2 is nothing but a computation of Euclidean distance. This operation involves multiplication, addition, and square root operation. Division operation is also required in this algorithm. Thus computation complexity of this algorithm is high compared to previous techniques discussed to solve linear equations.

Solving linear equations using an efficient MGS algorithm

This is another popular version of MGS algorithm which is very helpful in solving linear equations very efficiently. This algorithm eliminates the need for square root operation but division operation is unavoidable. Thus sometimes this algorithm, shown in Algorithm 2, is known as the square root free MGS algorithm. This algorithm factors the matrix $A$ into $Q^*$ and $R^*$ . Here, $R^*$ is an upper triangular matrix but $Q^*$ is an orthogonal matrix. This algorithm does not have the requirement to compute the Euclidean distance or norm. Thus the requirement of the square root is not there. Division operation can be approximated by the reciprocal operation.

Solving Linear equations using Givens rotation Algorithm

GR algorithm is a very powerful algorithm to perform QR decomposition on any matrix. MGS algorithm is an iterative way to perform QR factorization but GR algorithm provides a parallel method to obtain Q and R matrix. GR algorithm for QR decomposition is shown in Algorithm 3. This algorithm is also can be applied to a rectangular or square version of the coefficient matrix. But the algorithm considers that the co-efficient matrix is square. GR algorithm is based on multiplying the input matrix multiple times by the Givens rotation matrices until all the elements below the diagonal become zero.

GR algorithm paved the way to perform the QR decomposition in parallel. Many research papers published to improve the performance of QR decomposition using GR algorithm which is mostly implemented by Co-Ordinate Rotation DIigital Computer (CORDIC). CORDIC computes the angle between two elements and then rotates the entire rows by that angle to nullify one element. Previously in our post, we discussed how to implement QR decomposition using CORDIC algorithm.

Matlab Code for QR decomposition to solve linear equation (1527 downloads )

Solving linear equations using MGS algorithm

Solving linear equations using an efficient MGS algorithm

Solving Linear equations using Givens rotation Algorithm

Related Posts