¿Cómo resolver mínimos cuadrados minimización de exceso determinado sistema orthonormal restricción?

Question

Me gustaría encontrar la rectangular matriz $X \in \mathbb{R}^{n \times k}$ que resuelve el siguiente problema de minimización:

$$ \mathop{\text{minimizar }}_{X \in \mathbb{R}^{n \times k}} \left\| A X - B \right\|_F^2 \quad \text{ objeto } X^T X = I_k $$

donde $A \in \mathbb{R}^{m \times n}$ $B \in \mathbb{R}^{m \times k}$ se dan. Esta parece ser una forma de la ortogonales Procrustes problema, pero yo estoy errado en mi caso al $X$ es no cuadrada y $n \gg k$$m > n$.

Con optimismo, estoy en busca de una solución que implique la descomposición de valor singular de un pequeño $k \times k$ matriz, pero yo no estoy viendo. Me interesa especialmente el caso cuando $$A = \left(\begin{array}{c} D_1 \\ D_2\end{array}\right) \in \mathbb{R}^{2n \times n}$$ and $D_1,D_2$ are rank-sufficient diagonal matrices. This is to say that a solution involving $D_1^{-1}$ and $D_2^{-1}$ would be acceptable. The closest I've come (using "Thin SVD" on $$ Y) es:

$$ Y = (A^TA)^{-1}(A^T B) \\ Y = U \Sigma V^T \\ X = UV^T $$

claramente $X^T X = I_k$, pero

1. No he convencido a mí misma de que este es el minimizer,
2. esto implica que la inversión de un enorme $n \times n$ matriz (tal vez inevitable y no es tan malo en la pila de diagonal caso anterior, cuando $(A^TA)^{-1} = (D_1^2 + D_2^2)^{-1}$, y
3. esto implica s.v.d. de una gran rectangular $n \times k$ matriz.

Es correcto esto y tan bueno como se pone? O, ¿hay una solución más eficiente?

Answer 1

Su propuesta de solución no es correcta. Vamos a considerar el caso más sencillo: $m=n$, $k=1$, y $A$ es invertible. Entonces, nuestro problema es $$\min_{x\in\mathbb R^n} \|Ax-b\|^2\quad\text{s.t.}\quad \|x\|^2=1.$$ El conjunto $\{x:\|x\|^2=1\}$ es la unidad de la esfera, por lo que la transforma set $\{Ax:\|x\|^2=1\}$ es un elipsoide, y queremos encontrar el punto de $Ax$ en este elipsoide más cercano a $b\in\mathbb R^n$.

Su propuesta de solución se reduce a $y = A^{-1}b$$x = y/\|y\|$. A continuación,$Ax = b/\|A^{-1}b\|$, es decir, la propuesta de su punto más cercano se obtiene por una simple reducción $b$ a mentir sobre el elipsoide. Debe quedar claro que, en general, este no es el punto más cercano a $b$.

Lo siento, no tengo una buena respuesta para saber cómo encontrar la solución correcta.

Answer 2

Tenemos el siguiente problema de optimización en el alto de la matriz $\mathrm X \in \mathbb R^{n \times k}$

$$\begin{array}{ll} \text{minimize} & \| \mathrm A \mathrm X - \mathrm B \|_{\text{F}}^2\\ \text{subject to} & \mathrm X^\top \mathrm X = \mathrm I_k\end{array}$$

donde altos matrices $\mathrm A \in \mathbb R^{m \times n}$ $\mathrm B \in \mathbb R^{m \times k}$ se dan. Deje que el Lagrangiano de ser

$$\mathcal L (\mathrm X, \Lambda) := \frac 12 \| \mathrm A \mathrm X - \mathrm B \|_{\text{F}}^2 + \frac 12 \langle \Lambda , \mathrm X^\top \mathrm X - \mathrm I_k \rangle$$

Tomando las derivadas parciales y encontrar en donde se desvanecen, obtenemos dos ecuaciones de matrices

$$\begin{array}{rl} \mathrm A^\top \mathrm A \, \mathrm X + \mathrm X \left(\dfrac{\Lambda + \Lambda^\top}{2}\right) &= \mathrm A^\top \mathrm B\\ \mathrm X^\top \mathrm X &= \mathrm I_k \end{array}$$

De izquierda multiplicar ambos lados de la primera ecuación de matriz por $\mathrm X^\top$ y el uso de $\mathrm X^\top \mathrm X = \mathrm I_k$, obtenemos

$$\mathrm X^\top \mathrm A^\top \mathrm A \, \mathrm X + \left(\dfrac{\Lambda + \Lambda^\top}{2}\right) = \mathrm X^\top \mathrm A^\top \mathrm B$$

Usando un argumento similar al utilizado por Pedro Schönemann en su 1966 papel, tenga en cuenta que el lado izquierdo de la matriz de la ecuación anterior es la adición de dos simétrica de las matrices. Por lo tanto, el lado derecho también debe ser simétrico, el cual se produce la siguiente lineal de la ecuación de matriz

$$\mathrm X^\top \mathrm A^\top \mathrm B = \mathrm B^\top \mathrm A \, \mathrm X$$

Si $\rm X$ eran cuadrados y ortogonal, entonces podríamos usar Schönemann del enfoque para resolver el lineal de la matriz de la ecuación anterior. Por desgracia, $\rm X$ es alto y sólo semi-ortogonales. Tenemos $k^2$ ecuaciones lineales en $n k$ incógnitas. Por lo tanto, tenemos, al menos, $n k - k^2 = k (n-k)$ grados de libertad.

En resumen, tenemos $k^2$ ecuaciones lineales y $k^2$ ecuaciones cuadráticas en la $n k$ entradas de $\rm X$

$$\begin{array}{rl} \mathrm X^\top \mathrm A^\top \mathrm B - \mathrm B^\top \mathrm A \, \mathrm X &= \mathrm O_k\\ \mathrm X^\top \mathrm X &= \mathrm I_k\end{array}$$

Por desgracia, no es obvio para mí cómo resolver estas ecuaciones.

Answer 3

Sólo para añadir otra observación: la búsqueda de una solución a su problema es equivalente a encontrar las matrices de $U_{n\times k}$$V_{k\times k}$, y una matriz diagonal $D$, de tal manera que $U^TU = I$, $V^TV = I$, y \begin{equation} A^TB = UDV^T + A^TAUV^T, \tag{1} \end{equation} en el que caso de $X = UV^T.$

Curiosamente, esto también es cierto cuando se $n=k$. En este caso, si $$A^TB = \mathcal{U}\Sigma\mathcal{V}^T$$ es la descomposición de valor singular de a$A^TB$, $D$ está dado por la descomposición espectral $$\Sigma - \mathcal{U}^TA^TA\mathcal{U} = RDR^T,$$ y $U = \mathcal{U}R, V = \mathcal{V}R.$

Esta solución no funciona al $n>k$, pero la ecuación (1) anterior, se parece mucho a algún tipo generalizado de la descomposición de valor singular, así que tal vez hay esperanza...

Como una práctica de stop-gap estaría tentado a tratar de iteración de punto fijo $$A^TB - A^TAU_i V_i^T = U_{i+1}D_{i+1}V_{i+1}^T.$$