pj


Total Posts: 3059 
Joined: Jun 2004 


How to fill them? Does anybody has ideas, papers, references?

Нас ебут, а мы крепнем... 



kr

Founding Member NP Raider

Total Posts: 3561 
Joined: Apr 2004 


assume a factor model of lower dimension and that the residuals are uncorrelated, then try to best fit your existing matrix to this model using some kind of intelligent norm
i.e. imagine you have a 10x10 matrix of assets
X_i = u_i . Z^1_t + v_i . Z^2_t + sqrt(1  u_i^2  v_i^2) . W^i_t
where the Z^j's are common to all processes and the W^i's are assumed jointly independent. This identifies a subspace of the matrix of much smaller dimension. Anyhow, based on how much is missing, choose an appropriate # of factors, project your matrix onto the variety, and use that nowfullyspecified matrix. 
my bank got pwnd 


Nonius

Founding Member Nonius Unbound

Total Posts: 11828 
Joined: Mar 2004 


this will be coming out in a paper of mine (along with a friend).....called "The Riemannian Geometry of Correlation".
you can compute a space contained in n*(n1)/2 Euclidean Space which serves as the constraint for correlation matrices. this turns out, as KR alluded to, to be a semialgebraic variety. It is defined by looking at the interior of a surface defined by the solution of a polynomial in the correlation values. the polynomial arises naturally by setting the coefficient of the constant term in the characteristic polynomial of the matrix equal to zero.
then, you fix the intersection of the above described space with an affine linear subspace defined by your known correlations. that is, if you know two out of 3 correlations in a 3x3 case, then, that means you have a line that intersects three dim space that I had FDAX graph in the software section (it is also the glowing halo around my head, minus the three "ears")....the interesection of this line with the space tells you what values your unknown correlation can take. then, from here, you could do a number of things...you could be conservative and choose something that maximizes/minimizes a quantitiy subject to being constrained to the intersected space...or, you could take an "average" over values in that space....or, you could let the correlation wiggle around in that space...
anyway, maybe this is too abstract for now, but I'll firm it up later. 
The enemy of my enemy is my enemy. 




Hi Nonius,
Could you please send this paper to me (sounds interesting)?
Thanks.

I am the dark one, the widower; the unconsoled,
The prince of Aquitaine at his stricken tower:
My sole star is dead, and my constellated lute
Bears the black sun of the melancolia.



Nonius

Founding Member Nonius Unbound

Total Posts: 11828 
Joined: Mar 2004 


well, it is only 1/3 written, but it is all in my head. basically it uses some sheah done by Dick Palais et Al on Orbit Spaces, plus a bag of Nonius tricks. I'll send to everyone when done. 
The enemy of my enemy is my enemy. 



pj


Total Posts: 3059 
Joined: Jun 2004 


Well well well,
Nonius, Your ramblings are way too abstract to implement. Unless we could connect Your brain to the software I've the honour to develop. I'm afraid You'll refuse it. Not talking about the technical problems. KR, Your way wouldn't satisfy the clients. If they have inputted some bloody correlation value it shouldn't be changed unless there is some valid reason to do it. Although the idea about fitting factors seems to be quite promisng. (More about it later, I'll post my findings someday (if there will be any)).
Now one friend of mine proposed the following hack.
The uninputted values are initially set to zero. Then 1) One calculates the eigen decomposition PDP^1 (D is diagonal with the eigenvalues as the entries). 2) Sets negative eigenvalues (entries in the diagonal matrix D) to zero. Gets a matrix D'. 3) 'Reconstitutes' the matrix PD'P^1 (BTW, it's the NumeriX package way, they stop there and use the 'reconstituted' matrix as the correlation matrix uninforming their poor clients (unless they ask specifically) that it is indeed different from the original one). (I hope it is not their trade secret. They were quite reluctant to tell me that one.)
4) Reinstate the supplied values back and
5) Iterate until one gets a valid correlation matrix.
He claims that it had converged all the times he'd tried. As I'm almost sure that those 0.1% (?) cases when the method (if) should fail to converge will be inputted by the users (and my boss) at once, I'm reluctant to accept his proposal.
Maybe this sparks some ideas in NP collective unconsciousness? 
Нас ебут, а мы крепнем... 


Nonius

Founding Member Nonius Unbound

Total Posts: 11828 
Joined: Mar 2004 


whatever dude, if you took a few minutes to understand what I wrote, then you could map the abstraction to reality and possibly learn something....oh well, phuck it. 
The enemy of my enemy is my enemy. 



pj


Total Posts: 3059 
Joined: Jun 2004 


How much time is "a few minutes"? I've reread Your thing a few time after Your last post... It's too abstract and I do not now how to implement it in a reasonable amount of time. Sorry...

Нас ебут, а мы крепнем... 


Nonius

Founding Member Nonius Unbound

Total Posts: 11828 
Joined: Mar 2004 


1. Take the correlation matrix with all of the entries known and those unknown left as variables.
2. Compute the characteristic polynomial of the matrix. This is the polynomial given by
Det(CLam*Id).
3. this computation leads to a polynomial with coefficients that depend on a) known correlations and b) unknown correlations. In other words, the coefficients are polynomials in the unknown correlations.
4. Look at the zeroth order coefficient of this polynomial. Set it equal to zero. This solution set (with the constraint that values are less than one in abs value) defines the boundary between allowable values and unallowable values for your matrix to be pos def, since, for solutions equal to zero, you have eigenvalues that are zero. The interior of this zero set plus the boundary, which is bounded by the way, comprises the total set of unknown correlations that are allowable.
this is cleaner, can be done with mathematica, and does not give rise to the random type of answer that is described by your friend.
is that clear enough? 
The enemy of my enemy is my enemy. 



pj


Total Posts: 3059 
Joined: Jun 2004 


Sorry Nonius,
Now it's absolutely unclear. Why the zeroth term of the characteristic polynomial of the correlation matrix has to be zero? For example, if i take a matrix 1 0 0 1
which is a (trivial) correlation matrix I get its characteristic polynomial equal lambda^22lambda+1. So the neither of its terms is equal to zero.
What do I get wrong?

Нас ебут, а мы крепнем... 


Nonius

Founding Member Nonius Unbound

Total Posts: 11828 
Joined: Mar 2004 


(1lam)^2rho^2=0
implies
1rho^2=0
bounds the range of corr...so, in two by two, the constraint is corr is between 1 and 1....
questions? 
The enemy of my enemy is my enemy. 



pj


Total Posts: 3059 
Joined: Jun 2004 


Got it. StOOpid me. (crawling back into my cave) Thank You 
Нас ебут, а мы крепнем... 


Nonius

Founding Member Nonius Unbound

Total Posts: 11828 
Joined: Mar 2004 


don't tell that little trick to everyone.....let's reserve it only for NPers...... 
The enemy of my enemy is my enemy. 



pj


Total Posts: 3059 
Joined: Jun 2004 


One more question ... Where did You get this neat thing from? What is the theorem it's founded on?
Still, if a matrice is 10x10, well it's my problem... 
Нас ебут, а мы крепнем... 


Nonius

Founding Member Nonius Unbound

Total Posts: 11828 
Joined: Mar 2004 


this is a result of Nonius. probably Adam knew it as well.
if you have 1000000x1000000 and all but 2 corrs are known, it reduces to a polynom in 2 variables.....of course, you'd have to figure out the polynom, but, that could be symbolically calculated by something like Mathematica. 
The enemy of my enemy is my enemy. 



nsande


Total Posts: 611 
Joined: Apr 2004 


Is there a difference between setting the zeroth order (in lambda) term in
Det(Clambda*Id)=0 to zero and just saying Det(C)=0 ?

"The measure of our intellectual capacity is the capacity to feel less and less satisfied with our answers to better and better problems."
C.W. Churchman



Nonius

Founding Member Nonius Unbound

Total Posts: 11828 
Joined: Mar 2004 


Det(C)=0 does not give you a decomposition of the characteristic polynomial...you need that lambda in there.... 
The enemy of my enemy is my enemy. 



Shoom


Total Posts: 10 
Joined: May 2005 


Nonius,
As I understand the zeroes order coefficient of the polynomial is the product of its roots. Therefore setting this coefficient equal to zero defines the boundary between the case with odd number of negative roots and the case with even number of negative roots, which doesn't guarantee that all roots are non negative.
Am I missing something? 



Nonius

Founding Member Nonius Unbound

Total Posts: 11828 
Joined: Mar 2004 


in order for the characteristic polynomial to have a zero eigenvalue, the zeroth term must be identically zero. 
The enemy of my enemy is my enemy. 



nsande


Total Posts: 611 
Joined: Apr 2004 


Having nonzero eigenvalues is not the same as having positive eigenvalues.
I believe that the surface defined by setting zeroth order of charactristic polynomial to zero splits the space of real symmetric matrices into a number of disjoint sets. You need some way of picking the one that has only positive eigenvalues.
How do you do that? 
"Like the ski resort full of girls hunting for husbands and husbands hunting for girls, the situation is not as symmetrical as it might seem. "
Alan Lindsay Mackay



mj


Total Posts: 1030 
Joined: Jun 2004 

 

Nonius

Founding Member Nonius Unbound

Total Posts: 11828 
Joined: Mar 2004 


Nsande,
I am not saying that the zero set determines the condition of pos semi def. I am saying that a section of that zero set is the boundary of a semialgebraic variety such that the interior plus boundary defines the condition of pos semi def. the section in question contains the point 0. all of this will be explained, in the context of geometry of orbit spaces in our paper.
Nonius

The enemy of my enemy is my enemy. 


Shoom


Total Posts: 10 
Joined: May 2005 


the interior plus boundary defines the condition of pos semi def
Does the interior correpond to the zeroth order coefficient being positive? 




Nonius

Founding Member Nonius Unbound

Total Posts: 11828 
Joined: Mar 2004 


Yes. basically, the space of pos semi def matrices with unit diagonals, ie corr mats, is naturally identified with an orbit space of an action of the orthogonal group on a product of spheres. Orbit spaces of smooth actions of compact groups are stratifications (disjoint unions of manifolds each of which is a base space of a fiber bundle) and have the structure of a semiaglebraic variety, ie, they are solutions of polynomial inequalities.
in the case of corr mats, the polynomials are the coeffs of the characteristic polynom.... 
The enemy of my enemy is my enemy. 



Dear Nonius,
I've a couple of question. ( I'm not familiar at all with geomery so please apologize).
What i understand is by taking the 0th order of your polynome and equal it to 0 you are looking for the 0 eigen values. I think you do not have to consider the characteristic polynome of your matrix the determinant is enough (product of the eigenvalues). So I take the case of a corr matrix (dim 3) and analytically study it. First I obtain as you suggested something which look like a sphere (in fact bounded by two spheres and I evaluated the upper bound sqrt(3) and the lower one sqrt(3)/2). So first I was amazed because my space is splitted into two sub spaces with one containing only positive def matrix (am I wrong??) and the other one matrix with at least one negative eigenvalue (thereby it's not too difficult I think to complete my matrix). In this example I only consider the 1 on the diagonale and the other values as unknowns.
The thing that bothers me (in fact not too much), is that if I've one known value for my corr matris is above sqrt(3) (my limit radius) then it's impossible to design a corr matrix am I wrong ?
Furthermore I really do not understand your explanations (but I'm too dumb and I really have to work on geometry seems very interesting ). Nevertheless it appears that if you always obtain something you can bound by two sphere (dimension n) then you could choose the lower one as limit of your space (because 0 is always inside the space of pos def matrix) and choose you missing values in the sphere. It's not very smart but I think it works.
On another hand if you want an eigenvalue equal to zero exactly you need to be exactly on the sphere (in fact it's not a sphere a potato ? ) and I think it's more tricky to implement. But you could want to have this property to put into light portfolios with a perfect replication. I think it could be interesting to study the existence of these 0 eigen values...

I am the dark one, the widower; the unconsoled,
The prince of Aquitaine at his stricken tower:
My sole star is dead, and my constellated lute
Bears the black sun of the melancolia.



