4
$\begingroup$

Suppose we have a countable set of objects $\{x_i|i \in [1..m]\}$ in a metric space $(\mathbb R^n,d_n)$ and a map ($F$) mapping the objects to objects in a metric space $(\mathbb R^1,d_1)$. For each pair of objects we can define an error:

$$ e_{ij} = \frac{d_m(x_i,x_j)}{d_1(F(x_i),F(x_j))} $$

Let $e_{ii}$ be 1.

It is obvious that we can define the countable set in a way that any projection has an error ($e_{ij}\ne 1$) at least for one pair of objects.

But for given set of objects we can define the map trying to minimize the errors.

I had met this problem developing a web site's rating system based on several criteria. At the moment I use the following algorithm for calculating F (images of objects):

  1. select random $\{y_i|i \in [1..m]\}$ set in space $(\mathbb R^1,d_1)$ and think that $y_i=F(x_i)$ where F is defining map
  2. for each dot calculate $\delta_i=\sum\limits_{j}k\frac{1}{2}e_{ij}(y_i-y_j)$ where $k$ is a parameter ($0 \le k \le 1$) and them change items in the set $y_i \to y_i + \delta_i$

I repeat the step two over and over several times, but at each step I make the parameter $k$ smaller.

I infer this algorithm from physics intuition: if two objects are too close they push away, if they are too far away they attract and $k$ is a resistance of an environment.

I want to get deeper knowledge about this problem, so could you provide me some links to articles and literature about it or the official name of the problem.

  • 4
    I think that the Johnson-Lindenstrauss lemma is relevant: http://en.wikipedia.org/wiki/Johnson%E2%80%93Lindenstrauss_lemma2010-12-09
  • 0
    A nitpick: the error you've defined is always decreased if you scale all $F(x_i)$ by a large constant. It's clear what you mean, however: you don't want to *minimize* $e_{ij}$ but to make them close to 1.2010-12-10
  • 0
    A minor point about the terminology, it seems that $\{x_i | i\in [1,\cdots,m]\}$ is finite. While in many cases people say countable they mean "finite or countably infinite", it is better to say finite when your set is explicitly finite.2011-01-09

1 Answers 1

1

Your problem is almost exactly multidimensional scaling: given a set of $n$ objects with given dissimilarities $\delta_{ij}$, find $n$ corresponding points $y_i$ in a low-dimensional space such that $\lVert y_i - y_j\rVert \approx \delta_{ij}$. I'm not intimately familiar with this area, but the Wikipedia article mentions a number of algorithms you could look at. You should be aware that there will often be many locally optimal configurations for a given problem.

However, multidimensional scaling is typically used for visualization applications, where you want to map your data to 2 or 3 dimensions and see what objects are similar to each other. I'm not sure how you plan to use it for computing ratings, because replacing all $y_i$ with $-y_i$ is exactly as good a solution but will turn low ratings into high ratings and vice versa.