title: Algorithmically correcting noisy distance measurements between data points on a number line
body: <p>I have an application where I have data points <code>x</code> that can be mapped to a number line. However, I don't know what their value on the number line is. Fortunately, I don't need to know <em>exactly</em> what their values are, I just need to know what the distances between the points are (i.e. the 0-point on the number line is arbitrary, and it can be reflected without affecting anything).</p>
  
  <p>I have as input a set of transitive distance measurements <code>D[i,j]</code> between the points. Additionally, the distance measurements are oriented (i.e. <code>D[i,j] = -D[j,i]</code>, with <code>D[i,j] &gt; 0</code> indicating that <code>x[i]</code> is further to the right on the number line than <code>x[j]</code>).</p>
  
  <p>First challenge: I don't have all of the values of <code>D</code>, but I do have some control over which values I obtain. </p>
  
  <p>Ideally, this wouldn't be that big of a problem because I could choose the pairs <code>[i,j]</code> so that <code>D</code> forms a spanning tree (interpreting it as an adjacency matrix of a graph) and then the distance between <code>x[i]</code> and <code>x[j]</code> would be the path length of the walk between nodes <code>i</code> and <code>j</code> on the tree. Unfortunately...</p>
  
  <p>Second challenge: the distance measurements are noisy. In most cases, the noise is small. However, in rare cases the distance measurements are WILDLY inaccurate.</p>
  
  <p>So. The problem. I would like to use multiple distance measurements between the data points to denoise these noisy distance measurements. Here's my wish list, some of which may turn out to be infeasible:</p>
  
  <ul>
  <li>An algorithm that maps the points in <code>x</code> to the number line (with an arbitrary 0-point) so that there is a single, unambiguous, transitive distance between any <code>x[i]</code> and <code>x[j]</code>, and it is clear which one is to the right of the other.</li>
  <li>The algorithm works with a graph <code>D</code> that is sparse, but not a tree. Perhaps it has the property that there are at least 2 paths between any two nodes.</li>
  <li>Because the multiple paths through <code>D</code> between two points represent different prospective distance measurements, use some loss function that minimizes the difference of the inter-data point distances in the projection to some integrated value of the distances implied by <code>D</code>. </li>
  <li>The algorithm uses a loss function that saturates for high values. This would take care of the case where the distances are very inaccurate, but I'm worried it would also make the problem non-convex. L1 penalty might be good enough.</li>
  </ul>
  
  <p>My first thought was to look into the multidimensional scaling literature since it's concerned with distance-preserving embeddings, but I don't think my problem is posed correctly. MDS seems to assume that you have a single, unambiguous distance measurement between each point. That's not my set up.</p>
  
  <p>I'm interested in any literature or algorithms people can point me to, whether for some aspect of this problem, or for a similar problem, or for roughly the same problem. Thanks!</p>