Minimizar $\| A - B \|_F^2$ a $B x = v$

Question

$$\begin{array}{ll} \text{minimize} & \| A - B \|_F^2\\ \text{subject to} & B x = v\end{array}$$

donde $B$ $m \times n$ matriz y $x$ $n$- vector donde cada elemento es $1/n$ (con un promedio de vector). En términos simples, quiero encontrar la 'más cerca' de la matriz de a $A$ que tiene un nuevo promedio a lo largo de las filas.

Ahora yo podría estar completamente fuera como esta es la primera vez tratando de resolver un problema, pero pensé que podría hacer algo como esto. Por favor me llevara a través de los pasos finales y si mi idea es completamente errónea, hágamelo saber por qué y qué debía hacer.

Aquí está mi intento hasta ahora:

$$\text{Trace}\left[(A-B) (A-B)^{\mathsf{T}}\right]$$

Tenía la esperanza de que podría utilizar el método de Lagrange.

Estas son las identidades que he encontrado útil:

$$\frac{\partial \text{Trace}[x]}{\partial x}=\text{Trace}\left[\frac{\partial X}{\partial x}\right]$$

$$\text{Trace}[A+B]=\text{Trace}[A]+\text{Trace}[B]$$

$$\frac{\partial X^{\mathsf{T}}}{\partial x}=\left(\frac{\partial X}{\partial x}\right)^{\mathsf{T}}$$

Así que este es el problema que pensé podría ser la manera de resolverlo:

$$\text{Trace}\left[(A-B) (A-B)^{\mathsf{T}}\right]-\lambda (B x-v)$$

Encontrar el gradiente(por favor, hágamelo saber si estoy equivocado) y el ajuste a cero y resolver para transpuesta de B I get:

$B^{\mathsf{T}}=A^{\mathsf{T}}+\frac{\lambda x}{2}$

Sin embargo, creo que lo que he hecho está mal o hay algo que me estoy perdiendo porque ahora B es una matriz de + un vector por lo que puedo ver, por lo que las dimensiones no funciona.

Por desgracia, yo estoy fuera de mi profundidad y he empezado a leer sobre la optimización y cómo resolver problemas similares, pero necesito una respuesta a esta rápidamente.

Estoy feliz por los comentarios, mejoras, correcciones que sería útil para otras personas.

Muchas gracias por cualquier comentario!

Answer 1

Al principio se ve bien. Sin embargo, tenga en cuenta que necesita un multiplicador de Lagrange por restricción. Por lo tanto necesita un % de vector $\lambda$.

La función a minimizar es $$\operatorname{tr}(A^T-B^T)(A-B) - \lambda^T (B x -v). $ $

Tomando el gradiente con respecto a los $B$, llegamos a $$2 (B-A)- \lambda x^T =0. $ $

Podemos solucionar esto $B$ con el resultado $$ B = A + \frac12 \lambda x^T\;.$ $

El multiplicador de Lagrange tiene que determinar que se cumplen las restricciones, por ejemplo, $$B x = Ax + \frac12 \lambda x^Tx = v\;.$ $ esto conduce a $$ \lambda = \frac{2}{x^T x}(v -Ax)$ $ y así a la solución explícita $$ B = A + \frac{1}{\Vert x \Vert^2} (v -Ax) x^T $ $

Answer 2

Encontrar ortogonal de matrices $U,V$ tal que $V^{-1}x\sim e_1$, $Uv\sim e_1$. Como $ \|A-B\|_2=\|U(A-B)V\|_2$, ahora queremos encontrar $B'=UBV$ $B'e_1=\lambda e_1$ tal que $\|A-B\|_2$ es minimizado, donde $A'=UAV$. En la primera columna de $B'$ está determinada únicamente mientras que todas las otras entradas de $B'$ son gratuitas para nuestros gustos, podemos hacer que todas las entradas de $B'$ de columnas $2,\ldots, n$ iguales a las correspondientes entradas de $A'$. Por lo tanto $B'y=A'y$ todos los $y\perp e_1$.

Desplegando este resultado a la original de matrices, podemos ver que $By=Ay$ todos los $y\perp x$. Por lo tanto $B$ debe ser de la forma $$B=A+wx^T$$ donde $w$ se ajusta a la garantía de $Bx=v$. De $$v=Bx=Ax+wx^Tx=Ax+\|x\|^2w,$$ nos encontramos con $w=\frac1{\|x\|^2}(v-Ax)$ y así, finalmente, llegar a $$B = A+\frac{(v-Ax)x^T}{\|x\|^2}. $$

Answer 3

Encontrar la solución general de la restricción lineal. Será el de mínimos cuadrados de la solución, además de una contribución desde el espacio nulo $$\eqalign{ Bx y= v \cr B &= vx^+ + C(I-xx^+) \cr }$$ where $x^+$ is the pseudoinverse of $x$ and $C$ es una matriz arbitraria.

Al sustituir esta expresión para $B$ de los rendimientos de un problema sin restricciones en términos de $C$ $$\eqalign{ \phi &= \|B-a\|_F^2 = (B-A):(B-A) \cr d\phi &= 2(B-A):dB \cr Y= 2(B-A):dC(I-xx^+) \cr Y= 2(B-A)(I-xx^+):dC \cr \frac{\partial\phi}{\partial C} &= 2(B-A)(I-xx^+) \cr }$$ Establecer el gradiente a cero y resolver para C $$\eqalign{ B(I-xx^+) &= A(I-xx^+) \cr vx^+(I-xx^+) + C(I-xx^+)(I-xx^+) &= A(I-xx^+) \cr C(I-xx^+) &= A(I-xx^+) \cr }$$ Sustituir esto en la paramétricas expresión para $B$ $$\eqalign{ B &= vx^+ + C(I-xx^+) \cr y= vx^+ + A(I-xx^+) \cr Y= A + (v-Ax)x^+ \cr }$$ Tenga en cuenta que para un vector, podemos escribir una expresión explícita para la pseudoinverse $$x^+ = \frac{x^T}{x^Tx}$$ La cosa buena acerca de este enfoque, es que se mantiene cuando los vectores $(x,v)$ son reemplazadas por las matrices de $(X,V)$.

En la de arriba, la traza/Frobenius producto es indicado por un signo de dos puntos, es decir, $$A:B = {\rm tr}(A^TB)$$

Answer 4

Una cosa que se podría utilizar es el hecho de que cada fila es independiente, es decir, para la fila vectores $a_i,b_i$ puede minimizar $(a_i-b_i)^2:b_i\cdot \textbf 1=nv_i$ por separado.

Podemos utilizar el método de lagrange directamente en cada elemento escalar para obtener $$b{ij}=a{ij}+v_i-\overline{a_i}$ $

donde $\overline{a_i}$ es el promedio de la fila $a_i$. O como una matriz,

$$B=A+\textbf{1}^T(v-Ax)$$

Answer 5

Puede reescribir $\bf Bx=v$ $${\bf B}=\min_{\bf B}{|{\bf Bx-v}|_F^2}$ $

con la igualdad cuando (y sólo cuando) esta norma es igual a 0. Así que puede Agregar a la función de costo

$${\bf B}=\min_{\bf B}{|{\bf A-B}|_F^2+\lambda|{\bf Bx-v}|_F^2}$$

El mayor $\lambda$ el más importante para cumplir con la restricción de tema.

Y entonces finalmente expresar la multiplicación de la matriz con productos de Kroneckery Vectorización.