I have the following multiple dimensional scaling (MDS) minimization problem in vectors $v_1, v_2, \dots, v_n \in \mathbb R^2$

$$\min_{v_1, v_2, \dots, v_n} \sum_{i,j} \left( \|v_i - v_j\| - d_{i,j} \right)^2$$

which I wish to solve numerically using gradient descent. I know all the values of $d_{i,j}$.

I am confused because the input to gradient descent is just a vector, but for this problem it is $n$ vectors. I've come across scant information about a gradient-matrix and matrix calculus but I don't understand enough to see how this is analgous with vector calculus and hence gradient descent.

  1. Is solving this minimization problem via gradient descent possible and why?
  2. How else could I solve this minimization problem numerically for $v_1, v_2 \dots, v_n$?
  • $\begingroup$ Hint #1: try to re-write the objective using the Frobenius norm with distance matrices. Hint #2: anytime you are trying to project from a high dimensional space to a fixed lower dimensional one, think SVD/Eigendecomposition. $\endgroup$ – Nicholas Mancuso Nov 8 '16 at 6:20

Just concatenate all of the variables into a single, long vector. In your case, you'll have a $2n$-dimensional vector:

$$v = (v_{1,x},v_{1,y},v_{2,x},v_{2,y},\dots,v_{n,x},v_{n,y})$$

where $v_{i,x}$ is the x-coordinate of $v_i$ and $v_{i,y}$ is the y-coordinate of $v_i$. Now treat this as a function of $v$, i.e.,

$$f(v) = \sum_{i,j} (||v_i - v_j|| - d_{i,j})^2$$

This gives you an objective function $f: \mathbb{R}^{2n} \to \mathbb{R}$, which you can try to maximize. For instance, you can apply the gradient descent method to $f$ (after computing the partial derivatives of $f$).

That said: for your particular problem, gradient descent might not work very well, unless you happen to have a starting point (initial value for $v_1,\dots,v_n$) that is close to the optimum value. There might be many local optima that gradient descent could get stuck in. The only way to know for sure is to experiment with a bit and see what happens.


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.