User emchristiansen - MathOverflow

Distances on generalizations of the symmetric group

2012-09-10T17:42:54Z

I'm a computer vision student, and I'm looking for some symmetric group literature guidance. I'm going to provide some context, and finally ask two questions.

The Cayley distance and other distances on permutations ($S_n$) are quite useful in applied machine learning; see the beginning of this paper for some examples of distances on $S_n$. Typically, such distances are used when the absolute intensities of measurements are meaningless, but the relative intensities are meaningful. For example, if I wanted to compare the colors of pixels in a natural scene from an RGB image, I would not directly consider the absolute values of the R, G, and B components, as such values are sensitive to lighting. Instead, I would consider the differences in the ratios of R to G, R to B, etc. In the extreme case, I might only care about the ranking of the intensities of the color channels. The ranking is a permutation, so I could compare colors using a permutation distance.

This approach falls down when there is ambiguity in the ranking, as the ambiguity is a source of noise. For example, for a purely green pixel (R = 0, G = 255, B = 0), the rankings R <= B <= G and B <= R <= G are equally valid. So if I don't choose the rankings consistently, identical pixels may have nonzero distance (breaking a metric axiom).

Even if I choose rankings consistently (say I choose the unique stable sort), weird behavior can arise; consider the pixels {0, 0, 255} and {255, 0, 0}. In the "spirit" of the Cayley distance, these pixels should have a distance of one: swap the R and B channels. This corresponds to the sorts G <= R <= B and G <= B <= R, which differ by one swap. However, the stable sorts are R <= G <= B and G <= B <= R, which has a Cayley distance of two.

Finally, my questions: 1) What generalization of $S_n$ are there that explicitly account for repeated elements? To give a flavor of what I'm asking for, one possible generalization could replace the single-row representation of a permutation, e.g. [1, 3, 4, 2], with a single row of rows representation, e.g. [[1], [3, 4], [2]]. This latter representation would represent the sorts for [100, 255, 127, 127]. Of course, people smarter than myself will have thought about this and come up with a better solution. 2) For a given generalization, what are some common distances on it?

Hamming distance approximates Cayley distance on permutations: citation wanted

2012-06-01T07:16:09Z

Suppose we have two permutations x and y, represented as rank vectors. The Hamming distance between them is the number of entries in the two vectors which disagree. The Cayley distance is the minimum number of transpositions necessary to map x to y. See http://www.liga.ens.fr/~deza/papers/voldpapers/huang/huangperm.pdf for more information if needed. Let H(x, y) denote the Hamming distance, and C(x, y) denote Cayley distance

It appears the following holds: For every x, y, we have C(x, y) <= H(x, y) <= 2 * C(x, y).

I'm looking for a citation for the above relationship. Thanks!

Answer by emchristiansen for Hamming distance approximates Cayley distance on permutations: citation wanted

2012-06-01T09:10:33Z

This fact is stated in http://arxiv.org/abs/1202.0932v1

Comment by emchristiansen

2012-09-10T20:23:10Z

Douglas, I don't understand your comment. The underlying measurements are probably from a nice set like the integers, not something on which only a strict weak ordering exists. Perhaps you meant a strict weak ordering could be defined for the generalized permutations? But an ordering isn't what I'm after.

Comment by emchristiansen

2012-09-10T20:20:26Z

Sue, I think you're right that I'm not talking about a group. Instead, I think it's a monoid, with e.g. [[1], [2], [3]] the identity element for sorts of 3 elements. Since it doesn't have inverses, the standard recipe for computing the Cayley distance breaks down: for permutations $a$ and $b$, the Cayley distances is $n - C(a \cdot b^{-1})$, where $C(x)$ is the number of cycles in $x$. Is this a fatal flaw?