Derivado de la nuclear de la norma

Question

Estoy tratando de tomar la derivada de la nuclear de la norma con respecto a su argumento.

nuclear norma se define de la siguiente manera:

$$\|x\|_*=\mathrm{tr}(\sqrt{x^Tx})$$

Estoy tratando de calcular:

$$\frac{\partial \|x\|_*}{\partial x}$$

Tenga en cuenta que $\|x\|_*$ es una norma y es convexa. Estoy usando esto para coordinar descenso algoritmo de optimización.

Gracias por tu ayuda.

Answer 1

Como dije en mi comentario, en un convexo de la configuración de optimización, uno normalmente no uso de la derivada/subgradiente de la central nuclear de norma función. Es, después de todo, nondifferentiable, y como tal no puede ser utilizado en el estándar de las aproximaciones en descenso (aunque sospecho que algunas de las personas probablemente han aplicado semismooth métodos).

Aquí hay dos métodos alternativos para el "manejo" de la central nuclear de norma.

Semidefinite de programación. Podemos utilizar la siguiente identidad: la nuclear norma desigualdad $\|X\|_*\leq y$ se satisface si y sólo si existen matrices simétricas $W_1$, $W_2$ la satisfacción de $$\begin{bmatrix} W_1 & X \\ X^T & W_2 \end{bmatrix} \succeq 0, ~ \mathop{\textrm{Tr}}W_1 + \mathop{\textrm{Tr}}W_2 \leq 2 y$$ Aquí, $\succeq 0$ debe ser interpretada en el sentido de que el $2\times 2$ bloque de la matriz es positiva semidefinite. Debido a esta transformación, usted puede manejar nuclear norma minimización o límites superiores en la central nuclear de norma en cualquier semidefinite programación de la configuración. Por ejemplo, teniendo en cuenta algunas restricciones de igualdad $\mathcal{A}(X)=b$ donde $\mathcal{A}$ es un operador lineal, usted podría hacer esto: $$\begin{array}{ll} \text{minimize} & \|X\|_* \\ \text{subject to} & \mathcal{A}(X)=b \end{array} \quad\Longleftrightarrow\quad \begin{array}{ll} \text{minimize} & \tfrac{1}{2}\left( \mathop{\textrm{Tr}}W_1 + \mathop{\textrm{Tr}}W_2 \right) \\ \text{subject to} & \begin{bmatrix} W_1 & X \\ X^T & W_2 \end{bmatrix} \succeq 0 \\ & \mathcal{A}(X)=b \end{array}$$ Mi software de CVX utiliza esta transformación para implementar la función norm_nuc, pero cualquier semidefinite software de programación puede manejar esto. Una desventaja de este método es que semidefinite de programación puede ser costoso; y si $m\ll n$ o $n\ll m$, ese gasto se agrava, ya que el tamaño de la lineal de la matriz de la desigualdad es $(m+n)\times (m+n)$.

Proyectada/proximal de los gradientes. Considere los siguientes problemas relacionados con: $$\begin{array}{ll} \text{minimize} & \|\mathcal{A}(X)-b\|_2^2 \\ \text{subject to} & \|X\|_*\leq \delta \end{array} \quad$$ $$\text{minimize} ~~ \|\mathcal{A}(X)-b\|_2^2+\lambda\|X\|_*$$ Ambos de estos problemas trazar curvas de equilibrio: como $\delta$ o $\lambda$ es variada, de generar un equilibrio entre la $\|\mathcal{A}(X)-b\|$$\|X\|_*$. En un sentido muy real, estos problemas son equivalentes: para un valor fijo de $\delta$, no va a ser un correspondiente valor de $\lambda$ que produce el exacto mismo valor de $X$ (al menos en el interior de la compensación de la curva). Así que vale la pena considerar estos problemas juntos.

El primero de estos problemas se puede resolver utilizando un gradiente proyectado enfoque. Este enfoque se alterna entre el gradiente de pasos en el buen objetivo y proyecciones de nuevo en el conjunto factible $\|X\|_*\leq \delta$. La proyección paso requiere ser capaz de calcular $$\mathop{\textrm{Proj}}(Y) = \mathop{\textrm{arg min}}_{\{X\,|\,\|X\|_*\leq\delta\}} \| X - Y \|$$ que se puede hacer en aproximadamente el costo de una sola enfermedad vesicular porcina, además de algunos $O(n)$ operaciones.

El segundo modelo puede ser resuelto mediante un proximal gradiente de enfoque, que está muy estrechamente relacionado con proyectada gradientes. En este caso, se alterna entre la toma de gradiente de pasos en la suave parte, seguido por una evaluación de la proximal de la función $$\mathop{\textrm{Prox}}(Y) = \mathop{\textrm{arg min}}_X \|X\|_* + \tfrac{1}{2}t^{-1}\|X-Y\|^2$$ donde $t$ es de un tamaño de paso. Esta función también puede ser calculada con una sola enfermedad vesicular porcina y algunos umbralización. Es en realidad más fácil de implementar que la proyección. Por esa razón, la parte proximal del modelo es preferible el modelo de proyección. Cuando usted tiene la opción, resolver el modelo más fácil!

Me animo a hacer una búsqueda en la literatura sobre proximal gradiente de métodos, y la energía nuclear norma problemas en particular. De hecho, hay un poco de trabajo que hay sobre esto. Por ejemplo, estas notas de la conferencia de Laurent El Ghaoui en Berkeley hablar de la parte proximal del método de gradiente y de introducir el prox función nuclear normas. Mi software TFOCS incluye tanto la nuclear norma de la proyección y la proximidad de la función. Usted no tiene que utilizar este software, pero usted puede buscar en las implementaciones de prox_nuclear y proj_nuclear para algunos consejos.

Answer 2

Comience con la descomposición SVD de a $x$:

$$x=U\Sigma V^T$$

A continuación, $$\|x\|_*=tr(\sqrt{x^Tx})=tr(\sqrt{(U\Sigma V^T)^T(U\Sigma V^T)})$$

$$\Rightarrow \|x\|_*=tr(\sqrt{V\Sigma U^T U\Sigma V^T})=tr(\sqrt{V\Sigma^2V^T})$$

Por la circularidad de la traza:

$$\Rightarrow \|x\|_*=tr(\sqrt{V^TV\Sigma^2})=tr(\sqrt{V^TV\Sigma^2})=tr(\sqrt{\Sigma^2})=tr(|\Sigma|)$$

donde $|\Sigma|$ es la matriz del elemento sabio de los valores absolutos de $\Sigma$.

Por lo tanto nuclear norma también puede ser definida como la suma de los valores absolutos de la descomposición de valor singular de la matriz de entrada.

Ahora, tenga en cuenta que la función valor absoluto no es derivable en cada punto de su dominio, pero usted puede encontrar un subgradiente.

$$\frac{\partial \|x\|_*}{\partial x}=\frac{\partial tr(|\Sigma|)}{\partial x}=\frac{ tr(\partial|\Sigma|)}{\partial x}$$

Usted debe encontrar a $\partial|\Sigma|$. Desde $\Sigma$ es diagonal, el subdifferential conjunto de $|\Sigma|$: $\partial|\Sigma|=|\Sigma|\Sigma^{-1}\partial\Sigma$, ahora tenemos:

$$\frac{\partial \|x\|_*}{\partial x}=\frac{ tr(|\Sigma|\Sigma^{-1}\partial\Sigma)}{\partial x}$$ (I)

Así que debemos encontrar el $\partial\Sigma$.

$x=U\Sigma V^T$, por lo tanto: $$\partial x=\partial U\Sigma V^T+U\partial\Sigma V^T+U\Sigma\partial V^T$$

Por lo tanto:

$$U\partial\Sigma V^T=\partial x-\partial U\Sigma V^T-U\Sigma\partial V^T$$

$$\Rightarrow U^TU\partial\Sigma V^TV=U^T\partial xV-U^T\partial U\Sigma V^TV-U^TU\Sigma\partial V^TV$$

$$\Rightarrow U^TU\partial\Sigma V^TV=U^T\partial xV-U^T\partial U\Sigma V^TV-U^TU\Sigma\partial V^TV$$

$$\Rightarrow \partial\Sigma =U^T\partial xV-U^T\partial U\Sigma - \Sigma\partial V^TV$$

Se puede demostrar que los $-U^T\partial U\Sigma - \Sigma\partial V^TV=0$ (Sugerencia: diagonal antisimétrica y matrices, me salto la prueba aquí.), por lo tanto:

$$\partial\Sigma =U^T\partial xV$$

Por la sustitución en (I):

$$\frac{\partial \|x\|_*}{\partial x}=\frac{ tr(|\Sigma|\Sigma^{-1} \partial\Sigma)}{\partial x}=\frac{ tr(|\Sigma|\Sigma^{-1}U^T\partial xV)}{\partial x}=\frac{ tr(V|\Sigma|\Sigma^{-1}U^T\partial x)}{\partial x}=(V|\Sigma|\Sigma^{-1}U^T)^T$$

Por lo tanto, usted puede utilizar $U\Sigma^{-1}|\Sigma|V^T$ como el subgradiente.

Espero que esto ayude!

EDIT: Por $\Sigma^{-1}$, me refiero a la de Moore-Penrose de pseudo-inversa de a $\Sigma$, por lo tanto si $sign(\Sigma)$ es el elemento sabio signo de las componentes de la diagonal de a $\Sigma$, (cualquier valor entre -1 y 1 para los ceros en la diagonal), entonces el subdifferential es: $$U sign(\Sigma)V^T$$

Answer 3

Usted puede utilizar este buen resultado para la diferencial de la traza $$\eqalign { d\,\mathrm{tr}(f(A)) y= f'(a^T):dA \cr }$$ para escribir $$\eqalign { d\,\mathrm{tr}((x^Tx)^{\frac {1} {2}}) &= \frac {1} {2} (x^Tx)^{-\frac {1} {2}}:d(x^Tx) \cr &= \frac {1} {2} (x^Tx)^{-\frac {1} {2}}:(dx^T x + x^T, dx) \cr y= x(x^Tx)^{-\frac {1} {2}}: dx \cr }$$ Dando la derivada como $$\eqalign { \frac {\partial\|x\|_*} {\partial x} &= x(x^Tx)^{-\frac {1} {2}} \cr }$$ Otro buen resultado (este es de Higham) $$\eqalign { Un\,f(B\A) y= f(A\B)\,Un \cr }$$ los rendimientos de una expresión alternativa con (potencialmente) de dimensiones más pequeñas $$\eqalign { \frac {\partial\|x\|_*} {\partial x} &= (x\,x^T)^{-\frac {1} {2}}x \cr }$$

Mientras que la raíz cuadrada de $x^Tx$ ciertamente existe, la inversa no. Así que usted puede ser que necesite algún tipo de regularización, por ejemplo, $$\eqalign { \frac {\partial\|x\|_*} {\partial x} &= x(x^Tx+\varepsilon I)^{-\frac {1} {2}} \cr }$$

Answer 4

Por supuesto, $n:x\in M_{n,p}\rightarrow tr(\sqrt{x^Tx})$ puede derivar en $x$ s.t. $x^Tx$ es invertible, es decir, en el caso genérico al $n\geq p$ (si $n\leq p$, entonces considere el $tr(\sqrt{xx^T})$). El resultado de greg es correcta ; sin embargo, su prueba no es claro y que reescribir por comodidad.

Si $A$ es simétrica $>0$, $f:A\rightarrow \sqrt{A}$ es una matriz de función (cf. el Higham del libro sobre este tema) ; si $g$ es una matriz de una función y $\phi:A\rightarrow tr(g(A))$, entonces su derivada es $D\phi_A:K\rightarrow tr(g'(A)K)$. Deje $A=x^Tx$. Por lo tanto $Dn_x:H\rightarrow tr(f'(A)(H^Tx+x^TH))=tr((f'(A)^Tx^T+f'(A)x^T)H)$. Entonces el gradiente de $n$$\nabla(n)(x)=x(f'(A)+f'(A)^T)=2xf'(A)=x(x^Tx)^{-1/2}$.

Como Alt hizo, podemos utilizar la descomposición SVD y nos encontramos con $\nabla(n)(x)=U\Sigma (\Sigma^T\Sigma)^{-1/2}V^T$ ($=UV^T$ si $n=p$). Recordar a Alt que la diagonal de $\Sigma$$\geq 0$.

Answer 5

¿Qué acerca de la $|| M ||_{F} = \mathrm{Trace}(M^{T}M)$?