# How can this L(2,1) problem be reduced to the orthogonal procrustes problem?

NOTE: Don't take this too serious -- the question is actually due to my misreading $$\|y_i - Wx_i\|^2$$ as $$\|y_i - Wx_i\|_2$$, see the answer.

Smith et al. in Offline bilingual word vectors, orthogonal transformations and the inverted softmax desribe learning an "alignment transformation" between word embeddings by solving the problem

\begin{align} & \min_W \sum_{i=1}^N \|y_i - Wx_i\|_2, \text{ s.t. } W^{T}W = I. \end{align}

over embeddings $$x_i$$, $$y_i$$ from aligned dictionaries $$X_D$$ and $$Y_D$$. The constraint ensures orthogonality to make $$W$$ "self aligned". This problem can be quite easily written as

$$\max_W \sum_{i=1}^N y^T_i W x_i,\quad \text{ s.t. } W^{T}W = I.$$

Now, instead of using gradient descent, they claim that the optimal solution is given analytically through an SVD:

$$W^* = U V^T, \text{ where } U \Sigma V^T = Y^T_D X_D$$

But I cannot make sense of why this is valid. The SVD solution, as I have found out, is the solution of the similar "orthogonal procrustes problem" with the Frobenius norm,

\begin{align} & \min_W \|Y - W X\|_F, \quad \text{ s.t. } W^{T}W = I; \end{align}

but we here have a different entrywise norm:

\begin{align} & \min_W \|Y - W X\|_{2,1}, \quad \text{ s.t. } W^{T}W = I. \end{align}

Why does the same solution apply? Is it some norm inequality I'm missing?

(I tried researching other sources for this approach, but all just either use GD or do not justify this solution any better. Cf. Xing et al., 2015)

• It looks like the norm in your first formula should be squared. See Eq 1 in the linked paper. If so, the whole sum is equivalent to the Frobenius norm. – amoeba says Reinstate Monica Nov 20 '19 at 15:06

## 1 Answer

The first optimization problem you wrote doesn't correspond to the one they're solving in the paper. But, the second problem you wrote does (see equation 6). The relationship between this problem and the orthogonal Procrustes problem is explained in appendix A.

The orthogonal Procrustes problem is:

$$\min_W \sum_{i=1}^n \|y_i - W x_i\|^2 \quad \text{s.t. } \ W^T W = I$$

where $$\|\cdot\|^2$$ is the squared $$\ell_2$$ norm. To draw a connection to your notation, one could equivalently write the loss in matrix form as $$\|Y - W X\|_F^2$$, where $$\|\cdot\|_F^2$$ is the squared Frobenius norm, and the matrices $$X$$ and $$Y$$ contain $$\{x_i\}$$ and $$\{y_i\}$$ on the columns.

The squared Euclidean distance between any two vectors is given by the sum of the squared $$\ell_2$$ norms of the vectors, minus two times the dot product:

$$\|y_i - W x_i\|^2 = \|y_i\|^2 + \|W x_i\|^2 - 2 y_i^T W x_i$$

In this particular problem, $$x_i$$ and $$y_i$$ are normalized. Furthermore, multiplying by $$W$$ doesn't change the norm, since it's orthogonal. Therefore, $$\|y_i\|^2 = \|W x_i\|^2 = 1$$ and:

$$\|y_i - W x_i\|^2 = 2 - 2 y_i^T W x_i$$

Substitute this into the orthogonal Procrustes problem, and note that constant terms don't affect the solution. So, we can equivalently solve:

$$\max_W \sum_{i=1}^n y_i^T W x_i$$

This is the same problem as defined in equation 6. Therefore, the problem solved in the paper is equivalent to the orthogonal Procrustes problem (in the normalized case). And, the Procrustes solution using the SVD can be used.

• Arghhh, I think I just initially misread the square as a subscript indicating the 2-norm :) Appearently I just needed someone to show me out of my tunnel... – phipsgabler Nov 20 '19 at 19:59
• Funny how moving a '2' by a few millimeters on the page can have such a big difference in meaning. Glad it's cleared up. – user20160 Nov 20 '19 at 20:11