Cholesky Decomposition
Cholesky Decomposition
The Cholesky decomposition factorizes a positive definite matrix A into a lower triangular matrix L and its transpose, L’ :
A = LL’
This decomposition is named after AndréLouis Cholesky (18751918), a French artillery officer who invented the method in the context of his work in the Geodesic Section of the Army Geographic Service.
The k × k real symmetric matrix A is positive definite if and only if x’Ax > 0 for any nonzero k vector. For such matrices, the corresponding Cholesky factor L (sometimes called the matrix square root ) always exists and is unique. Matrices of this sort arise in many econometric contexts, making the Cholesky decomposition a very useful computational tool. For example, it can be used to solve the normal equations of least squares to produce coefficient estimates in multiple regression analysis. In this case, the place of A is occupied by the matrix of squares and crossproducts of the regressors, X’X.
Given the Cholesky decomposition of A, the set of linear equations Ax = b in the unknown vector x may be written as LL’x = b. Writing y for L’x, we get Ly = b, which may be solved for y, then y = L’x is solved for x. It is trivial to solve equations on the pattern Mx = b for triangular M.
Algorithms for computing the decomposition are based on the following relationships between the elements a_{ij} of A and the elements l_{ij} of L :
Element l_{ij} can be computed if we know the elements to the left and above. The CholeskyCrout algorithm starts from the upper left corner of L and calculates the matrix column by column.
The beauty of the Cholesky method is that it is numerically stable and accurate (as noted by Turing 1948) while requiring fewer floatingpoint operations and less workspace (computer memory) than alternative methods. It does, however, have a problem if the matrix A is very illconditioned. (In the econometric context mentioned above, this occurs if there is a high degree of collinearity among the variables in the data matrix X.) Computing the decomposition requires that we calculate a sequence of square roots. The values under the square root sign in equation (2) are always positive in exact arithmetic, but for illconditioned A they may be very small. Given the rounding error inherent in finiteprecision computer arithmetic, these values may go negative—in which case the algorithm cannot continue—or they may simply fall below the magnitude at which rounding error is an acceptable proportion of the computed value. A practical implementation of the Cholesky algorithm for a digital computer must check for this condition and terminate if need be. If the Cholesky method fails, one can resort to the computationally more expensive QR or SVD decomposition methods.
Besides solving sets of linear equations, the Cholesky decomposition has a further use in econometrics that deserves mention, namely, decomposing the covariance matrix for a set of residuals in the context of a vector autoregression. This sort of analysis was pioneered by Christopher Sims (1980) and quickly became popular. The role of the decomposition is to permit the simulation of the response of a system to a disturbance in any one of the variables, and also to perform an accounting of the proportions of the forecast error variance attributable to disturbances in each of the variables.
SEE ALSO Matrix Algebra
BIBLIOGRAPHY
Golub, Gene H., and Charles F. Van Loan. 1996. Matrix Computations. 3rd ed. Baltimore, MD: Johns Hopkins University Press.
O’Connor, John J., and Edmund F. Robertson. 2005. AndréLouis Cholesky. School of Mathematics and Statistics, University of St. Andrews: MacTutor History of Mathematics archive. http://wwwhistory.mcs.standrews.ac.uk/Biographies/Cholesky.html.
Sims, Christopher. 1980. Macroeconomics and Reality. Econometrica 48 (1): 148.
Turing, Alan M. 1948. RoundingOff Errors in Matrix Processes. Quarterly Journal of Mechanics and Applied Mathematics 1 (1): 287308.
Allin Cottrell
Cite this article
Pick a style below, and copy the text for your bibliography.

MLA

Chicago

APA
"Cholesky Decomposition." International Encyclopedia of the Social Sciences. . Encyclopedia.com. 16 Aug. 2017 <http://www.encyclopedia.com>.
"Cholesky Decomposition." International Encyclopedia of the Social Sciences. . Encyclopedia.com. (August 16, 2017). http://www.encyclopedia.com/socialsciences/appliedandsocialsciencesmagazines/choleskydecomposition
"Cholesky Decomposition." International Encyclopedia of the Social Sciences. . Retrieved August 16, 2017 from Encyclopedia.com: http://www.encyclopedia.com/socialsciences/appliedandsocialsciencesmagazines/choleskydecomposition
Cholesky decomposition
Cholesky decomposition See LU decomposition.
Cite this article
Pick a style below, and copy the text for your bibliography.

MLA

Chicago

APA
"Cholesky decomposition." A Dictionary of Computing. . Encyclopedia.com. 16 Aug. 2017 <http://www.encyclopedia.com>.
"Cholesky decomposition." A Dictionary of Computing. . Encyclopedia.com. (August 16, 2017). http://www.encyclopedia.com/computing/dictionariesthesaurusespicturesandpressreleases/choleskydecomposition
"Cholesky decomposition." A Dictionary of Computing. . Retrieved August 16, 2017 from Encyclopedia.com: http://www.encyclopedia.com/computing/dictionariesthesaurusespicturesandpressreleases/choleskydecomposition