Matriz más cercano en conjunto matriz doblemente estocástica

Question

Supongamos $\mathcal{D}_N$ denotar una $N\times N$ doblemente estocástica de la matriz, dado cualquier elemento $M\in \mathcal{D}_N$ , la descomposición de valor singular para $M$ $$ M=USV'$$

donde $U$ $V$ dos $N\times N$ ortogonal de la matriz y $S$ $N \times N$ matriz diagonal

Deje $P$ 'más cercano' ortogonal de la matriz de a $M$, es decir,$P=\arg\min_{X\in\mathcal{O}}||X-M||_F^2$,$\mathcal{O}$ representa el $N\times N$ ortogonal de la matriz de conjunto. Nota $P$ puede no ser único. En este caso, podemos elegir cualquiera de la misma. En conclusión acerca de $P$ $P=UV'$ donde $U$ $V$ son definidos anteriormente(aunque puede no ser única, sólo hemos de elegir cualquiera de ellos)

$M_1 \in \mathcal{D}_N$, que es 'más cercano' a $P$. Más específicamente

$$ M_1 = \arg\min_{X\in\mathcal{D}} ||X - P||_F ^2 $$ Del mismo modo, Si $M_1$ no es única, podemos elegir cualquiera de ella(Esto no debería ocurrir en realidad. Ya podemos imaginarlo como una "pelota" aproximación a un 'polygon', sólo debería tener un mínimo)

Mi pregunta es :

La instrucción: $M_1=M$ si y sólo si $M$ es una matriz de permutación

Hace esta declaración siempre es cierto?

En realidad, si $M$ es una permutación de la matriz, $M_1=M$, esto es obvio, ya $S=I$, e $P=M$. Sin embargo, hace otra dirección siempre es cierto? Si es así, cómo probar esto, de lo contrario, ¿cómo dar un contra-ejemplo?

Gracias por cualquier sugerencia!

Answer 1

A menos que se especifique alguna condición de la fijación de un único descomposición de valor singular que desea utilizar, su $P$ no está bien definida para los no-permutación doblemente estocástica de las matrices.

Por ejemplo, $$ \frac12\,\begin{bmatrix}1&1\\ 1&1\end{bmatrix}=\begin{bmatrix}1/\sqrt2&-1/\sqrt2\\1/\sqrt2&1/\sqrt2\end{bmatrix} \begin{bmatrix}1&0\\ 0&0\end{bmatrix} \begin{bmatrix}1/\sqrt2&1/\sqrt2\\-1/\sqrt2&1/\sqrt2\end{bmatrix} $$ es una descomposición de valor singular que le daría $P=I_2$.

Pero también tenemos

$$ \frac12\,\begin{bmatrix}1&1\\ 1&1\end{bmatrix}=\begin{bmatrix}1/\sqrt2&1/\sqrt2\\1/\sqrt2&-1/\sqrt2\end{bmatrix} \begin{bmatrix}1&0\\ 0&0\end{bmatrix} \begin{bmatrix}1/\sqrt2&1/\sqrt2\\-1/\sqrt2&1/\sqrt2\end{bmatrix} $$ y ahora $$ P=\begin{bmatrix}1/\sqrt2&1/\sqrt2\\1/\sqrt2&-1/\sqrt2\end{bmatrix} \begin{bmatrix}1/\sqrt2&1/\sqrt2\\-1/\sqrt2&1/\sqrt2\end{bmatrix} =\begin{bmatrix}0&1\\ 1&0\end{bmatrix} $$

Answer 2

Yo no se exactamente que llegar a su pregunta. Pero la solución para el problema de optimización que se busca siempre es una matriz de permutación. Esto se desprende de la del teorema de birkhoff. El birkhoff del teorema establece que cada doblemente estocástica de la matriz es una combinación convexa de la permutación de matrices. Por lo tanto, la permutación de matrices de la forma de las esquinas de la convexo conjunto de todos los doblemente estocástica de las matrices. La función objetivo que tenemos aquí es una función convexa. Así, el mínimo debe ser alcanzado en uno de los puntos de esquina, que son todas las matrices de permutación.