Óptima simétrica aproximación de fila-1

Question

Quiero encontrar a $\mathbf{x}$ que minimiza $\|A-\mathbf{x}\mathbf{x}'\|^2$ donde $\|\cdot\|$ es la norma de Frobenius. Diferenciando con respecto a $\mathbf{x}$ y ajuste de a $\mathbf{0}$, me sale

$$\mathbf{x}\mathbf{x}'\mathbf{x}=A \mathbf{x}$$

Alguna idea de cómo proceder en el futuro?

(Por petición, aquí es como yo lo hice la derivada) Deje $J=\|A-\mathbf{x}\mathbf{x}'\|^2=\text{tr}(Y'Y)$ donde $Y=A-\mathbf{x}\mathbf{x}'$

Para calcular derivadas del uso de la técnica de las diferencias como en Magnus,Neudecker y aquí $$dY(\mathbf{x})=-2\mathbf{x} \mathbf{dx}'$$ $$dJ(Y)=\text{tr}(2Y'dY)$$ sustituir la definición de $dY$ $Y$ hacia arriba, simplifica para obtener $$dJ(\mathbf{x})=-4 \text{tr}((A-\mathbf{x}\mathbf{x}')'\mathbf{x}\mathbf{dx}')=4\mathbf{x}'(\mathbf{x}\mathbf{x}'-A)'\mathbf{dx}$$ La última expresión es una forma canónica a partir de la cual la derivada puede ser identificado como la expresión antes de $\mathbf{dx}$, haciendo la transposición y la configuración de a $\mathbf{0}$ da la ecuación anterior.

Answer 1

Sus cálculos no parece totalmente correcto. Como $Y=A-xx'$, $dY=-dxx'-xdx'$. Por lo tanto \begin{align*} dJ&=\operatorname{tr}\,(Y+dY)'(Y+dY)-\operatorname{tr}\,Y'Y\\ &=\operatorname{tr}\,(Y-dxx'-xdx')'(Y-dxx'-xdx')-\operatorname{tr}\,Y'Y\\ &=\operatorname{tr}\,(-Y'dxx' -Y'xdx' - xdx'Y - dxx'Y)\\ &=\operatorname{tr}\,(-x'Y'dx -x'Ydx - x'Y'dx - x'Ydx)\\ &=\operatorname{tr}\,\left\{-2x'(Y+Y')dx\right\}. \end{align*} Por lo tanto $J'(x) = -2x'(Y+Y') = -2x'(A+A'-2xx') = -2x'(A+A')+4\|x\|^2x'$. En realidad, los cálculos pueden ser mucho más fácil si usted reescribir $J(x)$ \begin{align} J(x)&=\operatorname{tr}\{(A-xx')'(A-xx')\} =\operatorname{tr}(AA' -xx'A - A'xx' + xx'xx')\\ &=\|A\|^2 - 2\operatorname{tr}\left(x'\frac{A+A'}{2}x\right) + \|x\|^4\tag{1} \end{align} a la derecha en el comienzo. A partir de esta reformulación es inmediato que $J'(x)$ y la extrema de $J$ sólo dependen de la Hermitian parte $H=\frac{(A+A')}{2}$ $A$ pero no $A$ sí.

Para encontrar los puntos críticos de $J$,$J'(x)=0$. A continuación, llegamos $x'H=\|x\|^2x'$. En otras palabras, $x=0$ o si $x\not=0$, $x$ es un autovector correspondiente a un positivo autovalor $\|x\|^2$$H$. Así puede encontrar todos los eigenpairs $(\lambda,v)$$H$, ignorar el valor no positivo de autovalores y, a continuación, establezca $x=\frac{\pm\lambda^{1/2}}{\|v\|}v$ (el signo no importa, ya que se anulan a sí mismo en el producto $xx'$). El vector cero y estos autovectores de a $H$ son los puntos críticos de $J$ modulo de simetría. Conéctelos a $(1)$, vemos que el mínimo global de $J$ está dado por \begin{cases} \|A\|^2-\lambda_\max(H)^2 &\ \text{ if } \lambda_\max(H)>0,\\ \|A\|^2&\ \text{ otherwise}. \end{casos}

Answer 2

Me gustaría mostrar cómo la norma puede ser dividida como la suma de las simétrica (Hermitian) y el sesgo simétrica (skew Hermitian).

Deje $A = H + S$$H = H^*$$S = -S^*$. Entonces \begin{align} \left(H+S\right)\left(H+S\right)^* &= HH^* + HS^* + SH^* + SS^* \\ &=HH^* -HS + SH + SS^*\\ \end{align} Desde el cíclica de la propiedad de seguimiento, $\operatorname{Trace}(HS) = \operatorname{Trace}(SH)$, y la media de los términos cancelar en la norma.

Así tenemos $$\Vert A \Vert^2 = \Vert H+S \Vert^2 = \Vert H \Vert^2 + \Vert S \Vert^2$$

La adición de $\mathbf{x}\mathbf{x}'$, a continuación, sólo afecta a la parte simétrica, ya que es simétrica. Por lo tanto, el problema original puede ser simplificado con el uso completo de la simetría, incluso si $A$ sí no es simétrica, como Dineshdileep señaló.

Answer 3

Esta es una respuesta parcial, pero completando debe ser directa.

Definir la parte simétrica de $A$ $H=(A+A^T)/2$ y el sesgo de simetría parte como $S=(A-A^T)/2$. A continuación, para cualquier matriz simétrica $X$, tenemos la identidad \begin{align} ||A-X||_F^2=||H-X||_F^2+||S||_F^2 \end{align} Para demostrarlo, sustituto $A=H+S$. Ahora, utilice el hecho de $||B||_F^2=trace(B^TB)$ para cualquier matriz $B$ (tome $B=A-X$), y también el uso de $H=H^T$, $S=-S^T$.

Por lo tanto, encontrar la más cercana simétrica $X$ $A$es lo mismo que encontrar el más cercano a $X$ a la parte simétrica $H$$A$. En su caso, usted tiene restricciones adicionales en $X$. Usted necesita $X$ a ser el rango uno y positivo-semidefinite que luego va a hacer $X=xx^T$ algunos $x$. Por favor, lea lo siguiente. El resto debe ser fácil de averiguar. Voy a ser la actualización es cuando tengo tiempo.

Mejor (no es necesario simétrica) clasificación-una aproximación

Usted está tratando de encontrar el mejor rango-una aproximación de la matriz dada $A$. Si el SVD de a$A=U\Sigma V^T$, $A_1=\sigma_1u_1v_1^T $ donde $u_1$ $v_1$ corresponden a la izquierda y a la derecha vectores singulares correspondientes a los mayores de singular valor $\sigma_1$, es el mejor rango-una aproximación. Esto es una cosa estándar y la prueba se puede encontrar en cualquier libro de texto estándar que explica enfermedad vesicular porcina. Pero si usted está interesado en encontrar la respuesta usando la diferenciación, entonces yo no estoy seguro de cómo me puede ayudar.