¿Cómo se puede reducir este problema L(2,1) al problema de Procrustes ortogonal?

Question

NOTA: No tome esto muy en serio -- la pregunta en realidad se debe a mi mala lectura $\|y_i - Wx_i\|^2$ como $\|y_i - Wx_i\|_2$, vea la respuesta.

---

Smith et al. en Offline bilingual word vectors, orthogonal transformations and the inverted softmax describen el aprendizaje de una "transformación de alineación" entre incrustaciones de palabras al resolver el problema

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

sobre incrustaciones $x_i$, $y_i$ de diccionarios alineados $X_D$ y $Y_D$. La restricción garantiza la ortogonalidad para hacer que $W$ esté "autoalineado". Este problema se puede escribir bastante fácilmente como

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

Ahora, en lugar de usar descenso de gradientes, afirman que la solución óptima se obtiene analíticamente a través de una SVD:

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

Pero no logro entender por qué esto es válido. La solución SVD, según he descubierto, es la solución del "problema de Procrustes ortogonal" similar con la norma de Frobenius,

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

pero aquí tenemos una norma por entradas diferente:

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

¿Por qué se aplica la misma solución? ¿Es alguna desigualdad de normas que estoy pasando por alto?

(Intenté investigar otras fuentes para este enfoque, pero todas simplemente usan DG o no justifican esta solución de manera más convincente. Véase Xing et al., 2015)

Answer 1

El primer problema de optimización que escribiste no corresponde al que están resolviendo en el documento. Pero, el segundo problema que escribiste sí (ver ecuación 6). La relación entre este problema y el problema ortogonal de Procrustes se explica en el apéndice A.

El problema ortogonal de Procrustes es:

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

donde $\|\cdot\|^2$ es la norma $\ell_2$ al cuadrado. Para establecer una conexión con tu notación, se podría escribir la pérdida en forma de matriz como $\|Y - W X\|_F^2$, donde $\|\cdot\|_F^2$ es la norma de Frobenius al cuadrado, y las matrices $X$ e $Y$ contienen $\{x_i\}$ y $\{y_i\}$ en las columnas.

La distancia euclidiana al cuadrado entre dos vectores está dada por la suma de las normas al cuadrado de los vectores, menos dos veces el producto punto:

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

En este problema particular, $x_i$ e $y_i$ están normalizados. Además, multiplicar por $W$ no cambia la norma, ya que es ortogonal. Por lo tanto, $\|y_i\|^2 = \|W x_i\|^2 = 1$ y:

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

Sustituye esto en el problema ortogonal de Procrustes, y nota que los términos constantes no afectan la solución. Por lo tanto, podemos resolver equivalente:

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

Este es el mismo problema definido en la ecuación 6. Por lo tanto, el problema resuelto en el documento es equivalente al problema ortogonal de Procrustes (en el caso normalizado). Y, la solución de Procrustes usando la SVD se puede utilizar.