Rank Ordering of Large Heterogeneous Data

George J. Miel
University of Nevada
Miel@cleanhead.cs.unlv.edu

Abstract

A problem of interest in quantitative finance deals with establishing a ranking of elements of a given set based on pairwise comparisons of the elements. Applications of this nature include investment planning, portfolio evaluation, resource allocation, and others. We deal with computational issues that arise for a type of model based on rank deficient least squares when the data set is very large and heterogeneous.

Consider a graph with n nodes and m directed arcs, with , in which each node represents an item with a numerical measure of worth attached to it, and where an arc from node j to node k means that the two items have been pairwise compared. Each row of the incidence matrix C has exactly two nonzero entries, with -1 in column j and +1 in column k indicating that there is an arc from node j to node k. If is the worth of the j-th item and denotes the observed difference in worth attached to the i-th paired comparison then the overdetermined system

 

asks to estimate the worths knowing pairwise differences of observed performances represented by the arcs of the graph. One can show that in the corresponding normal system

 

the matrix has rank n-q where q is the number of connected components of the graph. Diverse methods are available for finding the general least squares solution of the system (1). However the computation can be carried out more efficiently by solving at most q nonsingular systems of smaller sizes.

The case with q=1, when the graph is fully connected, can be handled as follows: replace anyone equation of the normal system (2) by an appropriate equation

thus getting a full-rank auxilliary system

 

whose unique solution can then be used to get the general solution. Theorem. If the graph is connected and the auxilliary equation satisfies then the matrix is nonsingular and the set of least squares solution of Cx=d is given by

where and is an arbitrary scalar. The arbitrary vector shows that since the general solution depends on observed differences of worths it is invariant to an additive shift. In the general case with rank n-q, there will be q linearly independent arbitrary vectors. If the system (3) is extremely large, a promising means of solution for some applications, is to apply a Discrete Wavelet Transform (DWT) so as to make a large fraction of coefficients so small as to be negligible, and then use a specialized algorithm for sparse systems. In other words, if the matrix A compresses well under a transform D, the sparse system

 

where and , is solved to get the desired (approximate) solution .

The incidence matrix C is stored as two integer m-vectors MINUS and PLUS whose j-th elements denote the column index of -1 and +1 respectively in the j-th row of C. Use of the outer product yields a remarkably simple algorithm for evaluating the matrix :

 
      

for ¯j=1:m do:

		   

		   

		   

		   

		   

		   

enddo

The vector is evaluated with a similar algorithm also based on the outer product.

The above algorithm points to useful properties of the matrix A. The diagonal elements are nonnegative and the off-diagonal elements are nonpositive. The element is the total number of arcs to or from node i whereas , is the number of arcs between nodes i and k. These properties of A combined with a labelling procedure from graph theory yield an efficient algorithm for identifying the components of the graph.

Putting the pieces together, the general least squares solution to the system (1) is determined as follows. The matrix A is computed and it is then used in the labelling procedure to partition the n nodes of the graph into q components with items respectively. Observe that . A component with consists of an isolated node which has not been compared with any other node. Items in separate components are also non-rankable. For each component with , form an system of rank by extracting proper elements from A and b, replace one equation of this system by an appropriate auxilliary equation in order to get a nonsingular system , solve this system using a conventional algorithm such as factorization followed by front/back substitution, or if is extremely large use a DWT to get a sparse system followed by an appropriate solver, and then apply the theorem to get the general least squares solution.