Consider the task that we want to compute the Euclidean distance between two vectors $\mathbf{a}$ and $\mathbf{b}$, where the vectors are noisy sample from some measurement. Our goal is to get an unbiased estimate of the distance, i.e. the distance should be largely independent of noise. Using the classical Euclidean distance is not working in this case, as the Euclidean distance between the vectors $\mathbf{a}$ and $\mathbf{b}$ will be non-zero even when the true underlying vectors $\mathbf{a}$ and $\mathbf{b}$ are identical (due to noise).

In this case, we can compute the cross-validated (squared) Euclidean distance between $\mathbf{a}$ and $\mathbf{b}$ from two independent measurements $M$ and $M'$:

$d^2_{\mathrm{Euclidean, cross-validated}} = (\mathbf{a-b})(\mathbf{a'-b'})^T$

The idea is that the projection of the distance vectors between the two measurements (by means of the dot product) cancels out presumably orthogonal noise components of the vectors. So that helps to get unbiased estimates for the Euclidean distance. [Edit: assuming that the noise has mean zero, thanks Dougal]

My question is: could we achieve a similar unbiased cross-validated measure also for the Manhattan distance[1]?

[1] https://en.wikipedia.org/wiki/Taxicab_geometry

To be clear, the (non-cross-validated) Manhattan distance is defined as follows:

$d_{\mathrm{Manhattan, \textbf{non-}cross-validated}} = \sum\limits_i \left|a_i-b_i\right|$

  • 4
    $\begingroup$ There are different names for it, L1 distance/norm, taxicap, etc. I could change the name to whatever name is most familiar to users $\endgroup$ – monade Mar 30 '17 at 14:55
  • 1
    $\begingroup$ Whatever to call it, the type of distance certainly is known here. In my field the most common name is Manhattan distance though. $\endgroup$ – monade Mar 30 '17 at 14:57
  • 6
    $\begingroup$ @MichaelChernick, just because you don't know what it is doesn't mean it's off topic here. $\endgroup$ – GoF_Logistic Mar 30 '17 at 14:59
  • 1
    $\begingroup$ Is the model: You observe $X = \{x_i\}_{i=1}^n$. $\newcommand{\ex}{\varepsilon_1} \newcommand{\ey}{\varepsilon_2} \newcommand{\ux}{\upsilon_1} \newcommand{\uy}{\upsilon_2}$ You can estimate $f(X) = a + \varepsilon(X)$, $g(X) = b + \upsilon(X)$; you split $X$ into $X_1 \cup X_2$ and do \begin{align} (f(X_1) &- g(X_1))^T (f(X_2) - g(X_2)) \\&= (a - b + \ex - \ux)^T (a - b + \ey - \uy) \\&= (a - b)^T (a - b) + (\ex - \ux)^T (a - b) + (a - b)^T (\ey - \uy) + (\ex - \ux)^T (\ey - \uy) ,\end{align} which has mean $\lVert a - b\rVert^2$ if the noises have mean zero? $\endgroup$ – Dougal Mar 30 '17 at 15:20
  • 1
    $\begingroup$ Are you looking specifically for an approach for $L_1$ that splits into two parts, or just anything of a similar spirit? $\endgroup$ – Dougal Mar 30 '17 at 15:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.