# Alternative to Choleski Decomposition for Correlation Matrix

Let $\Sigma$ be a correlation matrix, ie. symmetric. The Choleski decompositon gives upper triangular $A$ such that $A^TA = \Sigma$. Instead of upper triangularity, we are looking for $A$ that is not upper triangular, instead having each column sum to the same value and each entry $\ge 0$. I've already managed to get this working in two dimensions with a simple solver, but three and up seem challenging. Is there a known method that would produce the desired matrix?

The goal is to apply a correlation matrix to random vectors with a "balanced" distortion effect on the points, rather than leaving the first vector the same and heavily altering the last few.

-
Hmm, I don't know, whether I've really understood your last sentence. Possibly there are other and better suited criteria with a different notion of "balanced"- for instance some least-square criterion like "equal-sums-of-squares" of the coefficients instead of "equal-sums". Are you sure that "having equal column-sums" is the "balancing" that you want? –  Gottfried Helms Aug 15 '13 at 7:19

For the purposes of this answer I will ignore the condition of constant column sums. You ask for a matrix $A$ with $A^TA = \Sigma$ and $A\geq 0$ element wise. Such a matrix need not exist. For example, its existence would imply that $\Sigma\geq 0$ elementwise. Even if this is the case, testing for existence of such an $A$ is NP-hard: this is the problem of checking whether a matrix is completely positive (see this paper).

-

While the question of positiveness was answered by Noah the other question (of equal column- (or row?) sums in A) can be dealt with the concept of Givens-rotation, where you iteratively rotate pairs of columns (or rows?) to a predefined optimization criterion. The angle for the pairwise column-rotations must then be determined by a criterion which minimizes the the difference of the sums. This should be similar to the centroid-rotation, but where we compute the maximizing criteria in the centroid-rotation we need the minimizing criteria now. Perhaps I can support this with an example later....
[update] I've got the rotation criterion for each elementary Givens-rotation. Let's -for my convenience- assume, that by $\Sigma = A \cdot A^T$ the cholesky-factor $A$ of $\Sigma$ is lower triangular. Then we iterate pairwise column-rotations in $A$ to pairwise and finally to completely equal column-sums. One such pairwise rotation is called "elementary Givens rotation".

The criterion-formula for the sought c as cosine of the rotation-angle and s as sine of the rotation-angle where x denotes the column with the lower index ("to the left") and y denotes the column with the higher index ("to the right") of one pairwise rotation and k goes over all row-indices is: $$\sum_k (x_k \cdot c - y_k \cdot s ) = \sum_k (x_k \cdot s + y_k \cdot c )$$ From this we can compute c and s as $$c \cdot \sum x_k - s \sum y_k = s \cdot \sum x_k + c \cdot \sum y_k \\ c \cdot \sum (x_k - y_k) = s \sum (y_k + x_k) \\ c = { a \over z } \qquad s = { b \over z } \\ \text{where } a=\sum (y_k + x_k) \qquad b=\sum (x_k - y_k) \qquad z = \sqrt{a^2+b^2}$$

Then the (elementary Givens-) rotation of the columns X and Y is $$X' = X\cdot c - Y \cdot s \qquad Y'=X\cdot s + Y \cdot c$$

One iteration-pass is then to apply this computation to all combinations of pairs of columns, where only always the X column means that of the smaller index.
Here is one example with a random correlation matrix, its initial cholesky-factor A and the vector SU containing the column-sums (which shall be made equal by the rotations):

        |   1,0000    0,0000      0,0000      0,0000 |
|   0,7139    0,7003      0,0000      0,0000 |
A=     |   0,9022    0,3439      0,2603      0,0000 |
|   0,5865    0,6970      0,3367      0,2382 |
=====================================
SU=     |   3,2026    1,7412      0,5970      0,2382 |


One rotation on the leftmost columns gives

        |   0,9590    0,2835      0,0000      0,0000 |
|   0,4861    0,8739      0,0000      0,0000 |
A=    |   0,7677    0,5856      0,2603      0,0000 |
|   0,3649    0,8347      0,3367      0,2382 |
==========================================================
SU=    |   2,5777    2,5777      0,5970      0,2382 |


and after 5 complete iteration passes I get

        |   0,7133    0,0320      0,4429      0,5422 |
|   0,4761    0,7200      0,2739      0,4241 |
A=     |   0,5372    0,3850      0,6116      0,4349 |
|   0,1242    0,7138      0,5225      0,4495 |
=========================================================
SU=    |   1,8508    1,8508      1,8508      1,8508 |


where we see, that all column-sums are equal.

-