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. 24 May. 2018 <http://www.encyclopedia.com>.
"Cholesky Decomposition." International Encyclopedia of the Social Sciences. . Encyclopedia.com. (May 24, 2018). http://www.encyclopedia.com/socialsciences/appliedandsocialsciencesmagazines/choleskydecomposition
"Cholesky Decomposition." International Encyclopedia of the Social Sciences. . Retrieved May 24, 2018 from Encyclopedia.com: http://www.encyclopedia.com/socialsciences/appliedandsocialsciencesmagazines/choleskydecomposition
Citation styles
Encyclopedia.com gives you the ability to cite reference entries and articles according to common styles from the Modern Language Association (MLA), The Chicago Manual of Style, and the American Psychological Association (APA).
Within the “Cite this article” tool, pick a style to see how all available information looks when formatted according to that style. Then, copy and paste the text into your bibliography or works cited list.
Because each style has its own formatting nuances that evolve over time and not all information is available for every reference entry or article, Encyclopedia.com cannot guarantee each citation it generates. Therefore, it’s best to use Encyclopedia.com citations as a starting point before checking the style against your school or publication’s requirements and the mostrecent information available at these sites:
Modern Language Association
The Chicago Manual of Style
http://www.chicagomanualofstyle.org/tools_citationguide.html
American Psychological Association
Notes:
 Most online reference entries and articles do not have page numbers. Therefore, that information is unavailable for most Encyclopedia.com content. However, the date of retrieval is often important. Refer to each style’s convention regarding the best way to format page numbers and retrieval dates.
 In addition to the MLA, Chicago, and APA styles, your school, university, publication, or institution may have its own requirements for citations. Therefore, be sure to refer to those guidelines when editing your bibliography or works cited list.
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. 24 May. 2018 <http://www.encyclopedia.com>.
"Cholesky decomposition." A Dictionary of Computing. . Encyclopedia.com. (May 24, 2018). http://www.encyclopedia.com/computing/dictionariesthesaurusespicturesandpressreleases/choleskydecomposition
"Cholesky decomposition." A Dictionary of Computing. . Retrieved May 24, 2018 from Encyclopedia.com: http://www.encyclopedia.com/computing/dictionariesthesaurusespicturesandpressreleases/choleskydecomposition
Citation styles
Encyclopedia.com gives you the ability to cite reference entries and articles according to common styles from the Modern Language Association (MLA), The Chicago Manual of Style, and the American Psychological Association (APA).
Within the “Cite this article” tool, pick a style to see how all available information looks when formatted according to that style. Then, copy and paste the text into your bibliography or works cited list.
Because each style has its own formatting nuances that evolve over time and not all information is available for every reference entry or article, Encyclopedia.com cannot guarantee each citation it generates. Therefore, it’s best to use Encyclopedia.com citations as a starting point before checking the style against your school or publication’s requirements and the mostrecent information available at these sites:
Modern Language Association
The Chicago Manual of Style
http://www.chicagomanualofstyle.org/tools_citationguide.html
American Psychological Association
Notes:
 Most online reference entries and articles do not have page numbers. Therefore, that information is unavailable for most Encyclopedia.com content. However, the date of retrieval is often important. Refer to each style’s convention regarding the best way to format page numbers and retrieval dates.
 In addition to the MLA, Chicago, and APA styles, your school, university, publication, or institution may have its own requirements for citations. Therefore, be sure to refer to those guidelines when editing your bibliography or works cited list.