Let suppose we have two vectors u, v $\in \mathbb{R}^n$ and we want a function that returns $0$ if the ordering of the elements of both vectors are the same or a positive number otherwise, where the larger the number of order mismatches the larger the positive value. We want that the highest values of the vector u place in the same positions of the highest values in vector v.
For example: Lets say that u = {3.2, 1.5, -3, 0} and v={-2.1, 1, 1.1, -0.5}, so the rank of these vectors are (descending order): $r_u$={1,2,4,3} and $r_v$={4,2,1,3}. So, in this case we have two matches {2,3} and two mismatches {1,4}. Another point is that the highest value of the vectors u and v is in the mismatch set, then in this case the penalization should be harder than a mismatch in lower values.
The simplest way to do that is by calculating the rank of each vector, $r_u$ and $r_v$, and then compute the $L_2$-norm, for example, of the difference between these ranks:
$f(r_u,r_v) = \|r_u-r_v\|^2_2$.
However, since this function is a term of my optimization problem, at each iteration of the optimization algorithm it will be necessary to recalculate the ranks of these vectors, once both vectors are parameters to be learned and they are going to change every iteration. So, this approach can be very expensive, computationally speaking.
Another option is by counting the number of concordant pairs (http://en.wikipedia.org/wiki/Concordant_pair) of the vectors, however we need to recount the number of concordant (or discordant) pairs at each iteration.
Does anybody has faced with a similar problem?