recuperar solución primal dual para la terminación de la matriz

Question

Considere el siguiente primal dual de Pes $$ \min\limits_X \; \lVert X \rVert_* : \mathcal{A}(X) = b \qquad \max\limits_z \; b^T z : \lVert \mathcal{A}^*(z) \rVert \leq 1 $$ donde $\lVert X \rVert_* = \sum_{i=1}^{\text{rank}(X)} \sigma_i(X)$ es nuclear de la norma (la suma de los valores singulares), $\lVert X \rVert = \sigma_1(X)$ es el operador de la norma, y $\mathcal{A} : \mathbb{R}^{m, n} \rightarrow \mathbb{R}^p$ es un operador lineal. Nota este problema de instalación viene de (2.7) de http://www.eecs.berkeley.edu/~brecht/papers/07.rfp.lowrank.pdf.

Yo quiero hacer esto muy concreta para el problema de la matriz de finalización. Que es, se nos da $\alpha \in \{1, ..., m\}^{p}$, $\beta \in \{1, ..., n\}^{p}$, y nos pusimos $\mathcal{A}(X)_k = X_{\alpha_k, \beta_k}$$k=1,...,p$. Para el cálculo de la adjoint $\mathcal{A}^*(z)$, vamos a $X \in \mathbb{R}^{m,n}$$z \in \mathbb{R}^{p}$. Entonces $$\langle \mathcal{A}(X), z \rangle = \sum_{k=1}^{p} X_{\alpha_k, \beta_k} z_k = \langle X, \mathcal{A}^*(z) \rangle = \sum_{i=1}^{m} \sum_{j=1}^{n} X_{i,j} (\mathcal{A}^*(z))_{i,j}$$ Por lo tanto, para lograr la igualdad es suficiente para establecer $(\mathcal{A}^*(z))_{\alpha_k, \beta_k} = z_k$ $k = 1,...,p$ $0$ lo contrario (y desde adjoints son únicos sabemos que tiene que ser esto).

Ahora la pregunta: ¿cómo puedo recuperar el valor óptimo $X_{opt}$ de la primitiva, a partir de una solución de $z_{opt}$ de la dual? Para el propósito de esta pregunta, vamos a suponer que la solución a ambos problemas es único y el valor óptimo es finito ( $opt$ ).

Lo que he hecho es este tan lejos. Voy a asumir la fuerte dualidad tiene en todas partes (la Slater condiciones son bastante fácil de comprobar) y se derivan de la doble para ver cuál es la relación entre el primal y dual variables es $$ \begin{align*} \min_{X : \mathcal{A}(X) = b} \lVert X \rVert_* &= \min_{X: \mathcal{A}(X) = b} \max_{Y:\lVert Y \rVert \leq 1} \langle X, Y \rangle = \max_{Y:\lVert Y \rVert \leq 1}\min_{X: \mathcal{A}(X) = b}\langle X, Y \rangle \end{align*} $$ Ahora para resolver el interior de la minimización, me hizo un llamamiento a la dualidad de nuevo, escribir el Lagrangiano como $$ \begin{align*} \mathcal{L}(X, \nu) = \langle X, Y \rangle + \langle \nu, (\mathcal{A}(X) - b) \rangle &= \langle X, Y \rangle + \langle \nu, \mathcal{A}(X) \rangle - \langle \nu , b \rangle \\ &= \langle X, Y \rangle + \langle X, \mathcal{A}^*(\nu) \rangle - \langle \nu , b \rangle \end{align*} $$ Así que la solución para $\min\limits_X \mathcal{L}(X, \nu)$ $$ \min\limits_X \mathcal{L}(X, \nu) = \begin{cases} - \langle \nu, b \rangle &\text{if } Y + \mathcal{A}^*(\nu) = 0 \\ -\infty &\text{o.w.} \end{casos} $$ Para conectar el doble del interior de la minimización de $$ \max_{Y:\lVert Y \rVert \leq 1}\min_{X: \mathcal{A}(X) = b}\langle X, Y \rangle = \max_{Y:\lVert Y \rVert \leq 1}\max_{\nu:Y = -\mathcal{A}^*(\nu)} -\langle \nu, b \rangle $$ que los rendimientos de la doble forma dada en el papel.

Ahora, a partir de esto podemos ver, la solución de la doble nos permite recuperar la $Y_{opt} = \mathcal{A}^*(z_{opt})$ que obtiene el máximo. Pero no estoy seguro de cómo recuperar a$X_{opt}$$Y_{opt}$. Sabemos que (a) $\langle X_{opt}, Y_{opt} \rangle = opt$ y (b) $\mathcal{A}(X_{opt}) = b$. Pero debido a la forma en $\mathcal{A}^*(z)$ obras, $\langle X_{opt}, \mathcal{A}^*(z_{opt}) \rangle = opt$ es una ecuación que implica sólo el $p$ variables de $X_{opt}$ que ya conocemos; el $mn - p$ incógnitas de la deserción. ¿De dónde me salen mal?

Answer 1

Muchos de los métodos iterativos para la solución de la $z$ problema de recuperar efectivamente $X$ como una consecuencia natural. Por ejemplo, si usted fuera a convertir estos problemas a semidefinite programas y resolver con una simétrica primal-dual método, entonces ambos problemas se resuelven simultáneamente, y el primal y dual soluciones normalmente converge al óptimo en la misma proporción. Una de primer orden con el método de Nesterov-estilo de suavizado producirá $X$ como bueno, como Lagrange multipler. Sin embargo, en mi experiencia, con la primera orden de los métodos de la primera variable ($z$ en este caso) convergen más rápidamente que en el dual de ($X$).

Así, en la práctica, no será necesario que por separado recuperarse $X_\text{opt}$$z_\text{opt}$; se acaba de estar allí. Pero si la magia de oracle caído $z_\text{opt}$ en su regazo, de hecho, puede recuperarse $X_\text{opt}$ con un SVD y un sistema lineal a resolver. La derivación a continuación puede ser útil para ayudarle a "normalizar" un casi-óptimo $z$ $X$ obtenido a partir de uno de estos algoritmos. Voy a explicar cómo al final.

A ver qué podemos hacer esto, tenga en cuenta que Cauchy-Schwarz nos dice que para cualquier $X$, $Y$, $$\langle X, Y \rangle \leq \| X \|_* \| Y \|$$ Cuando es la igualdad satisfecho? Es decir, cuando no $$\langle X, Y\rangle = \|X\|_* \|Y\| = \sigma_1(Y) \sum_i \sigma_i(X) \quad ?$$ Mi reclamo: se produce cuando el $X$ $Y$ compartir singular direcciones, y el rango de $X$ no es mayor que la multiplicidad de la primera del singular del vector de $Y$. Es decir, $X=U\Sigma_X V^H$ $Y=U\Sigma_Y V^H$ idénticos $U$$V$, y $$\sigma_i(X) = 0 \quad \forall i ~~\text{s.t.}~~ \sigma_i(Y) < \sigma_1(Y).$$ Si no me creen, tomar algún tiempo para trabajar. También puede ayudar a su intuición pensar en esto como la matriz de la versión del vector de la desigualdad $x^Ty\leq \|x\|_1\|y\|_\infty$.

Ahora vamos a utilizar esto para resolver el problema. En primer lugar, algunos hechos acerca de nuestros modelos:

• El doble problema es estrictamente factible (por ejemplo, $z=0$).
• Si hay al menos una solución a $\mathcal{A}(X)=b$, entonces el problema primal es estrictamente factible así, como sus restricciones son lineales y el objetivo la función no tiene un dominio restringido.
• Por lo tanto una fuerte dualidad se consigue en cualquier caso; y si $\mathcal{A}(X)=b$ tiene un la solución, también tenemos tanto primal y dual logro: existe al menos una óptima primal/dual par $(X_\text{opt},z_\text{opt})$ satisfacción $\|X_\text{opt}\|_*=b^Tz_\text{opt}$.
• Podemos garantizar que $\|\mathcal{A}^*(z_\text{opt})\|=1$. Si esto no fuera el caso de---que es, si $\|\mathcal{A}^*(z_\text{opt})\|=\alpha<1$---a continuación podría escala de $z_\text{opt}$$\alpha^{-1}$, y seguiría siendo viable y lograr un objetivo mayor valor; una contradicción.

Así, dado un óptimo doble valor de $z_\text{opt}$, vamos a $\gamma=b^Tz_\text{opt}$$Y\triangleq\mathcal{A}^*(z_\text{opt})$. Deje $Y=U\Sigma V$ ser el SVD de a $Y$, e $q$ ser la multiplicidad de $\sigma_1(Y)$; es decir, si $q=\max\{i\,|\,\sigma_i(Y)=1\}$. Como señalan acertadamente, tenemos $$\langle X_\text{opt},Y\rangle = \gamma = b^Tz_\text{opt} = \|X_\text{opt}\|_* = \|X_\text{opt}\|_*\|Y\|$$ En otras palabras, $X_\text{opt}$ $Y$ satisfacer las Cauchy Schwarz desigualdad con la igualdad. Por lo tanto, $$X_\text{opt} = \sum_{i=1}^q \sigma_i u_i v_i^H$$ para algunos $\sigma_i$, $i=1,2,\dots q$. La sustitución en el primal restricciones de igualdad nos da $$\sum_{i=1}^q \sigma_i \mathcal{A}(u_iv_i^H) = b, \quad \sum_{i=1}^q \sigma_i = \gamma$$ que es un sistema de $p+1$ ecuaciones y $q$ incógnitas. Cualquier solución de este sistema lineal nos dará los valores singulares de a $\sigma_i$, de los cuales se puede construir $X_\text{opt}$. Una solución debe existir, de lo contrario se estaría en contradicción con la afirmación de que $X_\text{opt}$ es óptimo.

Como ya he dicho, usted puede usar esto para "normalizar" un poco inexacta solución de $X$ obtenido a partir de un método numérico. Por supuesto, usted puede simplemente mirar a los valores singulares de a $X$ y la caída de los que son "muy pequeños". Pero, ¿cómo saber cuán pequeño es pequeño? Una mejor solución es buscar en $Y$, y determinar cómo muchos de sus singulares valores son cercanos a $1$---medida absoluta. Esta medida numérica de la multiplicidad informaremos el rango probable de la verdadera solución a $X_\text{opt}$.