Assume I have a data set $ { \left\{ {x}_{i} \right\} }_{i = 1}^{N} $ which represents the value of each data point.
For each data we have its features $ {f}_{i} \in {\mathbb{R}}^{d} $.

The model I came for the data is $ \arg \min_x {\left( x - \sum_{j \neq i} {w}_{ij} {x}_{j} \right)}^{2} $, where $ {w}_{i, j} = \exp \left( -\frac{1}{2} {\left( {f}_{i} - {f}_{j} \right)}^{T} C \left( {f}_{i} - {f}_{j} \right) \right) $.
This model is idealization of the data, namely ideally the data would have obeyed this law yet it doesn't due to perturbations in data.

Yet the model is correct only if the the correct Mahalanobis Distance Matrix $ C $ is chosen (We don't need its inverse, so lets stick with $ C $).

So if I have a set of data and a set of features of the data, how can I find the matrix $ C $ which minimizes the model?

Formally, what I'm looking for given the data set $ { \left\{ \left( {x}_{i}, {f}_{i} \right) \right\}}_{i = 1}^{N} $:

$$ \arg \min_{C} {\sum_{i = 1}^{N} \left( {x}_{i} - \sum_{j \neq i} exp \left( -\frac{1}{2} {\left( {f}_{i} - {f}_{j} \right)}^{T} C \left( {f}_{i} - {f}_{j} \right) \right) {x}_{j} \right)}^{2} $$

Question: Is it a convex optimization problem?
Is it any other defined problem type I can find and read about?
How would you solve it?

I'm using MATLAB.


The problem is not convex, as one can verify using the simplest possible choice: $N=2, d=1$ and with data $x_1=x_2=1, f_1=1, f_2=0$. In that case, your objective function is $$ F(C) = 2\left(1-\exp(-C/2)\right)^2. $$ Plotting this function shows that it is not convex.


Your Answer

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

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