Vector ranking and transformation matrix

Hello. Suppose we have a vector [1 4 3], here -x1+x2>0, -x1+x3>0 and also x2-x3>0. How can we transform this ranking information into a matrix like [-1 1 0; -1 0 1; 0 1 -1]? Is there a function to realize it? Thank you in advance for your time and help.

[Stalin Samuel]

• Once you evaluate the below details you get the answer
• What is the values of x1,x2,x3 ?
• How do you relate the given vector with ranking information?
• What is the logic behind the final matrix?

[Xia]

Thank you Stalin and your evaluation questions are of key. I'm coding for a stochastic dominance problem and the x is productivity vector or return vector, while y is weight vector to solve for. The ranking of y should be reverse of that of x, even thought we don't know it yet and wanna a solution.

Thanks for your comment.

Answer 1

[Matt J]

n=length(x);
A=nchoosek(1:n,2);
m=size(A,1); 
B=sparse(1:m, A(:,1),1,m,n) - sparse(1:m, A(:,2),1,m,n); 

result=full(bsxfun(@times, sign(B*x), B))

[Xia]

Yes thank you a lot Matt, it exactly gets the result as the for loop. I just tried tic toc and as N goes bigger, this one costs more time and, more than 10 times of the for loop. Seems weird. Anyway thank you very much for this approach!

[Matt J]

See the final line,

 result=full(bsxfun(@times, sign(B*x), B))

Note, B can be reused for different x so long as they are of the same length n.

[Matt J]

I just tried tic toc and as N goes bigger, this one costs more time and, more than 10 times of the for loop.

Not me. I see hundreds fold speed-up over the for-loops with my version for n=100. I get ever faster results if I optimize the final line, getting rid of the full() command

Q=bsxfun(@times, sign(B*x), B);

My timing tests even included the creation of B, which is possibly an inappropriate handicap. Remember, B can be re-used for different x. The for-loops don't give you a similar advantage.

Finally, I'm not sure the for-loop code you presented gives the correct result. For example, with x=[ 2 4 3 1], the loops give me the following Q.

Q =

       0     0     0    -1
       0     0     0    -1
       0     0     0    -1
      -1     0     0     0
      -1     0     0     0
       0     0    -1     0

Why does each row contain only one non-zero element? I thought the idea is that each row tells you which of two x(i) is greater.

[Xia]

>> x=[2 4 3 1]';

tic
T=length(x);
X=[x [1:T]'];
k=sortrows(X);
V=k(:,2);
s=1;Q=zeros(T*(T-1)/2,T);
for i =1:T 
for j =1:T-i 
  Q(s,V(i))=-1;Q(s,V(i+j))=1;s=s+1;
end
end
Q
toc

n=length(x);
A=nchoosek(1:n,2);
m=size(A,1); 
B=sparse(1:m, A(:,1),1,m,n) - sparse(1:m, A(:,2),1,m,n); 
result=full(bsxfun(@times, sign(B*x), B))
toc

Q =

       1     0     0    -1
       0     0     1    -1
       0     1     0    -1
      -1     0     1     0
      -1     1     0     0
       0     1    -1     0

Elapsed time is 0.028108 seconds.

result =

      -1     1     0     0
      -1     0     1     0
       1     0     0    -1
       0     1    -1     0
       0     1     0    -1
       0     0     1    -1

Elapsed time is 0.060459 seconds.

Strange. My version is 2014b. Maybe the difference of hardware?.. Anyway, thank you very much Matt. My idea for the loop is that, using the ranking positions of x and set value. Now we have

1     1                      1   1
4     2   after ranking      3   3
3     3                      4   2

1 and -1 are a pair to set value according to ranking information. That's why I feel strange that no 1 in your Q.

[Matt J]

Hmmm. The discrepancy disappeared after I re-pasted the for-loop code. In any case, here is an improved version for which I see a few factors speed-up over the loops.

    x=randperm(1000).';

    tic
    n=length(x);
    [I,J]=ndgrid(1:n);
    idx=J>I;
    m=nnz(idx);
     B=sparse(1:m,J(idx),1,m,n) - sparse(1:m, I(idx),1,m,n); 

    result=bsxfun(@times, sign(B*x), B);
    toc

    %Elapsed time is 0.685717 seconds.

    tic
    T=length(x);
    X=[x [1:T]'];
    k=sortrows(X);
    V=k(:,2);
    s=1;Q=zeros(T*(T-1)/2,T);
    for i =1:T 
    for j =1:T-i 
      Q(s,V(i))=-1;Q(s,V(i+j))=1;s=s+1;
    end
    end
    toc

    %Elapsed time is 2.316114 seconds.

[Xia]

Impressive improvement Matt, especially for high dimensional vectors.

Thank you very much, for your help!

Answer 2

[Steven Lord]

If you're asking how to convert the inequalities (like -x1 + x2 < 0) into matrix form, I don't know if there's a function to do exactly that but the equationsToMatrix function comes close. You may be able to slightly modify your inequalities so they are equations then use equationsToMatrix to generate the matrices to use as your A, b, Aeq, and beq inputs to the Optimization Toolbox solvers (which is how I'm assuming you're planning to use those matrices.)

[Xia]

Thanks a lot Steven, for your insight. You are absolutely right that I'm intended for the optimization. In fact, I want to maximize x'y, while I know x but the unknown y should have a reverse ranking of x. For example x=[1 4 3] so y1 should be the largest y2 the smallest. I can't get any clue on restrictions on ranking of the LP unknown, that's why I think using ranking information of x would be an alternative. Any idea on this Steven?

Thank you very much for your answer!