The Data Science Lab
Matrix Inverse from Scratch Using QR Decomposition with C#
The Helper Functions
The purpose of most of the 10 helper functions should be clear from their names or by examining the source code.
Helper function MatInverseUpperTri() is used to compute the inverse of the R matrix that results from QR decomposition. The technique used to compute the inverse of an upper triangular or lower triangular matrix is called back-substitution.
The VecNorm(v) function computes the norm() of a vector, which is the square root of the sum of the squared elements of vector v. The VecDot(v1, v2) function computes the dot product of vectors v1 and v2, which is the sum of the products of corresponding elements of v1 and v2.
Wrapping Up
Inverting a matrix using QR decomposition is a good, general-purpose approach. For special types of matrices, there are more efficient algorithms. If the source matrix is 3-by-3 or smaller, then it's possible to compute the inverse using brute force. If you need the determinant of the source matrix, then using LUP decomposition (Crout or Doolittle algorithm) is useful. If the source matrix is a covariance matrix, then using Cholesky decomposition is efficient.
The implementation of QR-Householder matrix inverse presented in this article emphasizes simplicity and ease-of-modification over robustness and performance. Two other versions of the QR algorithm are Gram-Schmidt and Givens. Computing the inverse of a matrix, regardless of the algorithm used, can fail in many ways, and so in a production system you must add lots of error checking.
It's not feasible to list all the machine learning algorithms that use matrix inverses -- there are just too many. That said however, examples of ML algorithms that use a matrix inverse are linear regression, logistic regression, Gaussian mixture model clustering, Gaussian process regression and kernel ridge regression.
About the Author
Dr. James McCaffrey works for Microsoft Research in Redmond, Wash. He has worked on several Microsoft products including Azure and Bing. James can be reached at [email protected].