Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
    
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

2 Answers 2

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).

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.