# Methods to Estimate Optimal Distance Measure for Multidimensional Data Set

My problem at hand pertains to choosing a distance measure for use in locally weighted regression. In my particular problem, I have a data set that is upwards of 10 dimensions, where the variables have different units (think distances, speeds, angles).

The way I am formulating the problem is along the following lines:

First, given some matrix $M$, we will compute a local Least Square solution, given some local set of data about $\textbf{x}$ defined as $\lbrace \left(\textbf{x}_i, y_i\right)\rbrace_{i=1}^N$, using the following:

$$\beta^*(\textbf{x},M) = \text{arg}\min_{\beta} \frac{1}{2N} \sum_{i=1}^N \text{d}(\textbf{x}_i,\textbf{x},M) \left(f(\textbf{x}_i, \beta) - y_i\right)^2$$

Given that:

\begin{align} \text{d}(\textbf{u},\textbf{v},M) &= \sqrt{(\textbf{u}-\textbf{v})^TM^TM(\textbf{u}-\textbf{v})}\\ f(\textbf{x},M) &= \sum_{j=1}^p\beta_j(\textbf{x},M)\phi_j(\textbf{x}) \end{align}

Then, we wish to find $M$ such that this solution is minimized at a set of separate training points, $\lbrace \left(\hat{\textbf{x}}_i,\hat{y}_i \right) \rbrace_{i=1}^P$, defined as:

\begin{align} M^{*} &= \arg \min_{M} \frac{1}{2P} \sum_{i=1}^P \left(f(\hat{\textbf{x}}_i, \beta^*(\hat{\textbf{x}}_i,M)) - \hat{y}_i\right)^2 \end{align}

where $\text{d}(\cdot,\cdot,\cdot)$ is the distance measure for the data set based on some weighting matrix $M$, $\mathbf{\beta}_j(\textbf{x},M)$ is the $j^{th}$ term in the local least square coefficient solution based on some weighting matrix $M$, and $\phi_j$ is the $j^{th}$ basis function used to represent the unknown function locally. The whole point of this is to construct a distance measure that can be used with a whole dataset $D$ and allow for an efficient and accurate non-parametric representation. Note as well that this distance measure would come into play using a KD-Tree for finding the local dataset used in the local Least Square solution.

Based on this formulation, the optimization problem for $M^*$ appears non-convex, so I would like to know if there's any other approaches that might be better? I haven't had much success thus far finding any information, though I might not know the right thing to search for.

I want to note that I actually have tried scaling each term of the vector, based on the variance in its possible values, and this did not really work robustly enough. I should also note for the angular measurements, I actually find the smallest signed angle difference in the $(\textbf{u}-\textbf{v})$ operation (ie $359^o-6^o=-7^o)$.

• can you clarify how $d$ is being used? Oct 1 '17 at 7:55
• @TolgaBirdal I have updated the formulation a bit so it should be more clear how this procedure should work and the issue I am trying to solve. Oct 1 '17 at 14:51
• What are the actual units, what's "local" ? Or do you want to regress a small, representative subset of the data ? See LOESS, Local regression Jul 1 '18 at 10:40