User emchristiansen - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-24T06:05:29Z http://mathoverflow.net/feeds/user/24144 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/106836/distances-on-generalizations-of-the-symmetric-group Distances on generalizations of the symmetric group emchristiansen 2012-09-10T17:42:54Z 2012-09-11T04:18:43Z <p>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.</p> <p>The Cayley distance and other distances on permutations ($S_n$) are quite useful in applied machine learning; see the beginning of <a href="http://www.maths.qmul.ac.uk/~pjc/preprints/sd.pdf" rel="nofollow">this paper</a> 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.</p> <p>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 &lt;= B &lt;= G and B &lt;= R &lt;= G are equally valid. So if I don't choose the rankings consistently, identical pixels may have nonzero distance (breaking a metric axiom). </p> <p>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 &lt;= R &lt;= B and G &lt;= B &lt;= R, which differ by one swap. However, the stable sorts are R &lt;= G &lt;= B and G &lt;= B &lt;= R, which has a Cayley distance of two.</p> <p>Finally, my questions: 1) <strong>What generalization of $S_n$ are there that explicitly account for repeated elements?</strong> 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. [<code>[1]</code>, [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) <strong>For a given generalization, what are some common distances on it?</strong></p> http://mathoverflow.net/questions/98546/hamming-distance-approximates-cayley-distance-on-permutations-citation-wanted Hamming distance approximates Cayley distance on permutations: citation wanted emchristiansen 2012-06-01T07:16:09Z 2012-06-01T20:42:39Z <p>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 <a href="http://www.liga.ens.fr/~deza/papers/voldpapers/huang/huangperm.pdf" rel="nofollow">http://www.liga.ens.fr/~deza/papers/voldpapers/huang/huangperm.pdf</a> for more information if needed. Let H(x, y) denote the Hamming distance, and C(x, y) denote Cayley distance</p> <p>It appears the following holds: For every x, y, we have C(x, y) &lt;= H(x, y) &lt;= 2 * C(x, y).</p> <p>I'm looking for a citation for the above relationship. Thanks!</p> http://mathoverflow.net/questions/98546/hamming-distance-approximates-cayley-distance-on-permutations-citation-wanted/98556#98556 Answer by emchristiansen for Hamming distance approximates Cayley distance on permutations: citation wanted emchristiansen 2012-06-01T09:10:33Z 2012-06-01T09:10:33Z <p>This fact is stated in <a href="http://arxiv.org/abs/1202.0932v1" rel="nofollow">http://arxiv.org/abs/1202.0932v1</a></p> http://mathoverflow.net/questions/106836/distances-on-generalizations-of-the-symmetric-group Comment by emchristiansen emchristiansen 2012-09-10T20:23:10Z 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. http://mathoverflow.net/questions/106836/distances-on-generalizations-of-the-symmetric-group Comment by emchristiansen emchristiansen 2012-09-10T20:20:26Z 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?