1
$\begingroup$

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 any other defined problem type I can find and read about?
How would you solve it?

I'm using MATLAB.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ This answer is simply incorrect. It is indeed convex but you need to define your range for $C$. Clearly, this function has a global minimum point as $C = 0$ and $F(0) = 0$ and in the range of $[-1,1]$, it is convex. See it here: wolframalpha.com/input/?i=plot+2*%281-exp%28-x%2F2%29%29%5E2+from+-1+to+1. Sorry for awful link, you need to copy it and paste it in your browser. $\endgroup$
    – Mithridates the Great
    Commented Jan 12, 2020 at 18:23
  • $\begingroup$ @AloneProgrammer: Maybe so, but that restriction is not stated in the original problem. Furthermore, $C$ is supposed to represent a Mahalanobis distance for which I also can't see why it should be restricted to an interval with upper bound 1. Finally, what would be the generalization of your restriction to an interval for the original problem, in which $C$ is a matrix? $\endgroup$
    – Wolfgang Bangerth
    Commented Jan 13, 2020 at 4:51
  • $\begingroup$ I don't have any insist on $[-1,1]$ interval, I'm just saying this objective function might have a global minimum and probably in a really small range around that global minimum, this objective function might be convex, but I didn't implement it yet with for example CVXPY. $\endgroup$
    – Mithridates the Great
    Commented Jan 13, 2020 at 13:25
  • 2
    $\begingroup$ @AloneProgrammer: Well, yes, every smooth optimization problem is convex around non-degenerate minima :-) That's the second order sufficient condition. $\endgroup$
    – Wolfgang Bangerth
    Commented Jan 13, 2020 at 17:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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