Majorization Algorithms for Correlation Matrix Approximation

Dan Simon
Department of Electrical and Computer Engineering
Cleveland State University
Cleveland, Ohio

The approximation of an input matrix by a correlation matrix is a fundamental problem in applied mathematics. A correlation matrix is a symmetric positive semidefinite matrix with unit diagonal. Also, any symmetric positive semidefinite matrix with unit diagonal is a correlation matrix. Sometimes it is also desired that the correlation matrix be rank-deficient. Applications of this problem occur in finance, resource allocation, industrial process monitoring, image processing, reduced order state estimation, and quality function deployment.

Suppose we want to find a correlation matrix of a given rank that is as close as possible to some input matrix, subject to the constraint that specified elements in the approximating matrix are zero. Our optimality criterion is the weighted Frobenius norm of the approximation error, and we use a constrained majorization algorithm to solve the problem. Although many correlation matrix approximation approaches have been proposed, this specific problem, with the rank specification and the zero-elements constraint, has not been studied before now.

The input matrix is nominally a correlation matrix, but for a variety of reasons it might not be positive semidefinite. First, the data used to generate the matrix might be incomplete, or might contain noise and outliers that pollute the matrix. Second, the data used to generate the matrix might be asynchronous. Third, the matrix might be adjusted by humans on the basis of intuition. All of these factors, and possibly others, could give rise to a matrix that is not positive semidefinite, but that humans intend to use as a correlation matrix. This gives rise to the problem of finding a correlation matrix that is as close as possible to the given indefinite matrix.

This web page makes available available a paper and an m-file that can be run in the MATLAB environment that demonstrates a new approach to constrained correlation matrix approximation. M-files are written in a very high-level language that can be easily read, almost like pseudo code. The m-file is contained in the following zip file.

Corr.zip - 71 kilobytes

If you download the zip file to your hard drive by clicking on the above link, then unzip the file (using, for example, WinZip), you can run unconstrained and constrained majorization algorithms for correlation matrix approximation and reproduce the results in reference .  If you don't have software to unzip the file, you can download a free evaluation version of WinZip from www.winzip.com.

References

D. Simon and J. Abell, A Majorization Algorithm for Constrained Correlation Matrix Approximation, Linear Algebra and its Applications, vol. 432, no. 5, pp. 1152-1164, February 15, 2010 - pdf, 148 KB