# Is there a continuous {permutation,duplicate,translation,stretch}-invariant function on ordered sets of vectors that returns a vector?

Is there any example of such a function $f$, preferably one defined on all $V^n$ and all positive integers $n$ where $V$ is some vector space? It must satisfy the following:

1. $f(T) = f(\sigma(T))$ for any $T \in V^n$ and permutation $\sigma$
2. $f((X,t,t)) = f((X,t))$ for any (possibly empty) sequence $X$ and $t \in V$
3. $f(a+T) = a+f(T)$ for any $T \in V^n$ and $a \in V$ where $a+(t,...,u) = (a+t,...,a+u)$
4. $f(B*T) = B*f(T)$ for any $T \in V^n$ and diagonal matrix $B$ where $B*(t,...,u) = (B*t,...,B*u)$
5. $f$ is continuous on $V^n$ for each positive integer $n$

If there is no closed form, an algorithm to approximate it will be good enough.

The reason I am looking for such a function is that I want to find a way to determine the most probable original vector given a set of samples where some samples could be dependent on others. In another field it is called textual criticism but the criteria used there are extremely subjective, whereas I believe this model uses objective criteria and the results are reproducible, if this function exists in the first place. Permutation invariance and duplicate invariance are necessary to exclude identical copies (like those of internet-myths). Translation and stretch invariance seem to be logical requirements as well. If $f$ does not exist, can a proof be shown? Thanks a lot!

-
I don't understand condition 2, as I don't see what elements of $V^n$ are $(X,t,t)$ and $(x,t)$. Can you elaborate on this please? –  Alex Becker Dec 27 '11 at 6:52
@Alex: He probably means a function on the set of all finite sequences of vectors, rather than a function on $V^n$. –  Zhen Lin Dec 27 '11 at 7:18
@Zhen: Ah, that makes sense. User213820: If this is the case, you should edit your question to replace $V^n$ with $\bigoplus\limits_{n=1}^\infty V$. –  Alex Becker Dec 27 '11 at 7:22
I still think condition 2 needs clarification. If OP explains what he meant by this notation it would be best for all of us. –  Patrick Da Silva Dec 27 '11 at 7:26
Discard duplicates and take the mean? That satisfies all your criteria. –  Rahul Dec 27 '11 at 7:43

Let us first consider the one-dimensional case, $V = \mathbb R$. Let $T = (x_1, x_2, \ldots, x_n)$ be the points sorted in ascending order with duplicates discarded, and $I = [x_1, x_n]$ be their convex hull. Associate each point $x_i$ with its Voronoi cell, that is, the interval of points in $I$ closer to it that to any other $x_j$. Define $f$ to be a weighted average of the $x_i$, with the weights being the length $\ell_i$ of the corresponding cell, $$f((x_1,x_2,\ldots,x_n)) = \frac{\sum_{i=1}^n\ell_ix_i}{\sum_{i=1}^n\ell_i}.$$

To show that this construction satisfies (2) and (5) even though we discarded exact duplicates, we only need to show that as two or more points simultaneously approach the same value, say $x^*$, the value of $f$ approaches its value with the points replaced with a single point at $x^*$. This follows from the fact that the total size of the corresponding Voronoi cells approaches the size of the cell that a single point at $x^*$ would have.

Since you only care about diagonal matrices $B$, you can apply this procedure independently to each coordinate axis of $V$.

-
P.S. The idea of weighting by Voronoi cells came to me by analogy with natural neighbor interpolation, which is a very interesting interpolation scheme for scattered data and has many nice properties. –  Rahul Dec 27 '11 at 22:11
Very interesting idea. Applied independently to each coordinate axis, it does not solve the problem I originally started with, as I would expect two points with one identical coordinate but distinct other coordinates to influence the function towards them in that coordinate as compared to if their other coordinates were identical. I am not sure what is the best way to state such a behaviour. Do you think Voronoi cells within a bounding box in the whole space $V^n$ will work? It seems to intuitively. –  user21820 Dec 28 '11 at 0:46
@user21820, I see what you mean. Unfortunately, Voronoi cells in $\mathbb R^n$ are not invariant to non-uniform scaling, so it would not satisfy condition (4). Going by your latest comment, if you want the solution to be invariant to arbitrary non-uniform stretching (e.g. stretching the 2D plane along the (1,1) direction), and not just axis-aligned stretching, then $B$ should be a symmetric positive definite matrix, not necessarily a diagonal one. In that case, my answer does not work either. –  Rahul Dec 28 '11 at 1:02
Oh. Do you have any other geometry-based ideas? At first I tried to find some kind of geometric centre but the internet is not a very easy place to search.. –  user21820 Dec 28 '11 at 9:18
Wait, I do not think I need non-axis-aligned stretching. It is just that a coordinate of the output should not be independent of the other coordinates of the inputs, because clearly the closer two samples are (for some to-be-specified norm), the more likely they are dependent, either one on the other or both copied from the same source, thus they should have a lower total weight than if they were very different samples. In this case, do you think weighting each point by the $k$th-root of the volume of its Voronoi cell will work? –  user21820 Dec 28 '11 at 9:41

Your reason to want to find such a function, topped with Rahul's comment that says "Discard duplicates and take the mean" made me think of other such functions with a statistical background. Obviously the "Discard duplicates and take the mean" function does the job. But are there others? I thought about "Discarding duplicates and taking the variance of the vector $(v_1, \dots, v_n) \in V^n$ seen as a sample". That works too.

Note also that the set of all functions satisfying your properties is a convex space, because we've just shown it is non-empty, and given two functions $f$, $g$ that satisfy it, you can see that $\alpha f + (1-\alpha) g$ is in your function space also, for every $\alpha \in [0,1]$ (here I am assuming that $\alpha \times f(T)$ makes sense, thus the image of this function would need to be some subset of the complex numbers) or even better, for every $\alpha \in \mathbb R$ (i.e. it would be an affine space). I just thought I'd notice that.

Hope that helps,

-
Discarding duplicates and taking the mean does not satisfy condition 5, which I added after Rahul suggested it. If I understood your "taking the variance" correctly, it does not satisfy condition 4, right? –  user21820 Dec 28 '11 at 0:51
Aw. I said variance but I meant in the first place to say standard deviation. But again that would not work since $\sqrt{ B^2}$ doesn't make sense for every matrix. Sorry if my answer was a little lame. I'll let my answer there though, seeing mistakes can sometimes be fruitful. –  Patrick Da Silva Dec 28 '11 at 1:06
Doesn't matter, but do you have any other statistics-based ideas? I searched for both geometric and statistical methods but failed to find any.. All those that I found were not duplicate-invariant and most assume that there is no dependency between samples. –  user21820 Dec 28 '11 at 9:26
I can only guess one such function if the vector space is $V = \mathbb R$ : the maximum function and the minimum function obviously work, since those functions are invariant under permutations, do not care about duplicates, and adding the vector $(a,\dots,a)$ just translates the minimum/maximum. Continuity is trivial. =) –  Patrick Da Silva Dec 28 '11 at 16:43
I meant that I originally wanted $f$ to be a weighted sum of the input points where the weights are continuous functions, but thought it might be preferable to have only conditions on $f$ alone, so I included condition 4. If I remove condition 4, I would want the original condition to be satisfied. If we take the maximum in each coordinate, the resulting $f$ unfortunately cannot be expressed as a weighted sum of the input points where the weights are continuous functions, because they must each be 0 or 1 even in the 1-dimensional case. If $f$ is such a sum, I only need conditions 1,2,5. –  user21820 Dec 31 '11 at 3:25