Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
I think that the Johnson-Lindenstrauss lemma is relevant: en.wikipedia.org/wiki/Johnson%E2%80%93Lindenstrauss_lemma –  Jonas Meyer Dec 9 '10 at 18:32
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. –  Rahul Dec 10 '10 at 17:14
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. –  Asaf Karagila Jan 9 '11 at 18:27

1 Answer 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.

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.