¿La optimización de PCA es convexa?

La función objetivo del Análisis de Componentes Principales (PCA) es minimizar el error de reconstrucción en la norma L2 (ver sección 2.12 aquí . Otra vista está tratando de maximizar la varianza en la proyección. También tenemos una excelente publicación aquí: ¿Cuál es la función objetivo de PCA? ? )

Mi pregunta es que es la optimización de PCA convexa? (Encontré algunas discusiones aquí , pero desearía que alguien pudiera proporcionar una buena prueba aquí en CV).

No, las formulaciones habituales de PCA no son problemas convexos. Pero pueden transformarse en un problema de optimización convexo.

La idea y la diversión de esto es seguir y visualizar la secuencia de transformaciones en lugar de solo obtener la respuesta: se basa en el viaje, no en el destino. Los principales pasos en este viaje son

1. Obtenga una expresión simple para la función objetivo.

2. Amplíe su dominio, que no es convexo, en uno que sí lo sea.

3. Modifique el objetivo, que no es convexo, en uno que lo sea, de una manera que obviamente no cambia los puntos en los que alcanza sus valores óptimos.

Si observa de cerca, puede ver los multiplicadores SVD y Lagrange al acecho, pero son solo un espectáculo secundario, allí por interés paisajístico, y no comentaré más sobre ellos.

---

La formulación estándar de PCA que maximiza la varianza (o al menos su paso clave) es

$$\text{Maximize }f(x)=\ x^\prime \mathbb{A} x\ \text{ subject to }\ x^\prime x=1\tag{*}$$

donde la matriz A es una matriz simétrica, semidefinida positiva construida a partir de los datos (generalmente su suma de cuadrados y matriz de productos, su matriz de covarianza o su matriz de correlación).$n\times n$$\mathbb A$

(De manera equivalente, podemos tratar de maximizar el objetivo sin restricciones . No solo es una expresión desagradable, ya no es una función cuadrática, sino que graficar casos especiales mostrará rápidamente que no es una función convexa , o bien. Por lo general, se observa que esta función es invariante bajo los cambios de escala x → λ x y luego se reduce a la formulación restringida ( ∗ ) .)$x^\prime \mathbb{A} x / x^\prime x$$x\to \lambda x$$(*)$

Cualquier problema de optimización puede formularse de manera abstracta como

Encuentre al menos una que haga que la función f : X → R sea lo más grande posible.$x\in\mathcal{X}$$f:\mathcal{X}\to\mathbb{R}$

Recuerde que un problema de optimización es convexo cuando disfruta de dos propiedades separadas:

1. El dominio es convexo. $\mathcal{X}\subset\mathbb{R}^n$ Esto se puede formular de muchas maneras. Una es que siempre que e y ∈ X y 0 ≤ λ ≤ 1 , λ x + ( 1 - λ ) y ∈ X también. Geométricamente: siempre que dos puntos finales de una mentira segmento de línea en X , toda la mentiras segmento en X .$x\in\mathcal{X}$$y\in\mathcal{X}$$0 \le \lambda \le 1$$\lambda x + (1-\lambda)y\in\mathcal{X}$$\mathcal X$$\mathcal X$

2. La función es convexa. $f$ Esto también se puede formular de muchas maneras. Una es que siempre que e y ∈ X y 0 ≤ λ ≤ 1 , f ( λ x + ( 1 - λ ) y ) ≥ λ f ( x ) + ( 1 - λ ) f ( y ) . (Necesitábamos $x\in\mathcal{X}$$y\in\mathcal{X}$$0 \le \lambda \le 1$

   $$f(\lambda x + (1-\lambda)y) \ge \lambda f(x) + (1-\lambda) f(y).$$ $\mathcal X$ser convexo para que esta condición tenga sentido.) Geométricamente: siempre que sea ​​cualquier segmento de línea en X , la gráfica de f (restringida a este segmento) se encuentra arriba o en el segmento que conecta ( x , f ( x ) ) y ( y , f ( y ) ) en R n + 1 .$\bar{xy}$$\mathcal X$$f$$(x,f(x))$$(y,f(y))$$\mathbb{R}^{n+1}$

   El arquetipo de una función convexa es localmente parabólico en todas partes con coeficiente principal no positivo: en cualquier segmento de línea se puede expresar en la forma con un ≤ $y\to a y^2 + b y + c$$a \le 0.$

Una dificultad con es que X es la esfera unitaria S n - 1 ⊂ R n , que definitivamente no es convexa. $(*)$$\mathcal X$$S^{n-1}\subset\mathbb{R}^n$ Sin embargo, podemos modificar este problema incluyendo vectores más pequeños. Esto se debe a que cuando escalamos por un factor λ , f se multiplica por λ 2 . Cuando 0 < x ′ x < 1 , podemos escalar x hasta la longitud de la unidad multiplicándola por λ = 1 / $x$$\lambda$$f$$\lambda^2$$0 \lt x^\prime x \lt 1$$x$, aumentando asífpero permaneciendo dentro de la bola unitariaDn={x∈ R n∣x′x≤1}. Por lo tanto, reformulemos(∗)como$\lambda=1/\sqrt{x^\prime x} \gt 1$$f$ $D^n = \{x\in\mathbb{R}^n\mid x^\prime x \le 1\}$$(*)$

$$\text{Maximize }f(x)=\ x^\prime \mathbb{A} x\ \text{ subject to }\ x^\prime x\le1\tag{**}$$

Su dominio es que claramente es convexo, por lo que estamos a medio camino. Queda por considerar la convexidad de la gráfica de f .$\mathcal{X}=D^n$$f$

Una buena forma de pensar sobre el problema incluso si no tiene la intención de realizar los cálculos correspondientes, es en términos del Teorema espectral. $(**)$ Dice que por medio de una transformación ortogonal , puede encontrar al menos una base de R n en la que A es diagonal: es decir,$\mathbb P$$\mathbb{R}^n$$\mathbb A$

$$\mathbb {A = P^\prime \Sigma P}$$

$\Sigma$$\mathbb{P}$$\mathbb A$$x\to x^\prime \mathbb{A} x$

$\mathbb A$$\Sigma$$\mathbb P$

$$\sigma_1 \ge \sigma_2 \ge \cdots \ge \sigma_n \ge 0.$$

$x=\mathbb{P}^\prime y$$x$$y=\mathbb{P}x$$f$

$$f(y) = y^\prime \mathbb{A} y = x^\prime \mathbb{P^\prime A P} x = x^\prime \Sigma x = \sigma_1 x_1^2 + \sigma_2 x_2^2 + \cdots + \sigma_n x_n^2.$$

$\mathcal X$$\sigma_i$

$(**)$$x^\prime x = 1$$\sigma_1$$f$$\mathcal{X}$$f$$f$$\sigma_1$

$$g(y) = f(y) - \sigma_1 y^\prime y.$$

$\sigma_1$$f$$g$$f$$\mathcal X$

$-\sigma_1$$-\sigma_1 y^\prime y$$\mathbb P$$y^\prime y = x^\prime x$$x$$g$

$$g(y) = \sigma_1 x_1 ^2 + \cdots + \sigma_n x_n^2 - \sigma_1(x_1^2 + \cdots + x_n^2) = (\sigma_2-\sigma_1)x_2^2 + \cdots + (\sigma_n - \sigma_1)x_n^2.$$

$\sigma_1 \ge \sigma_i$$i$$g$$g$$x_2=x_3=\cdots=x_n=0$$x^\prime x=1$$x_1=\pm 1$$y = \mathbb{P} (\pm 1,0,\ldots, 0)^\prime$$\mathbb P$

$g$$\partial D^n=S^{n-1}$$y^\prime y = 1$$f$$g$$\sigma_1$$g$$f$$D^n$$f$$g$

No.

$k$$M$

$\hat{X} = \underset{rank(X) \leq k}{argmin} \| M - X\|_F^2$

$\|\cdot\|_F$

Aunque la norma es convexa, el conjunto sobre el que está optimizado no es convexo.

---

Una relajación convexa del problema de PCA se llama aproximación convexa de bajo rango

$\hat{X} = \underset{\|X\|_* \leq c}{argmin} \| M - X\|_F^2$

( es la norma nuclear . es la relajación convexa del rango, al igual que es la relajación convexa del número de elementos distintos de cero para los vectores) ‖ ⋅ ‖ $\|\cdot\|_*$$\|\cdot\|_1$

Puede ver Aprendizaje estadístico con dispersión , capítulo 6 (descomposiciones de matriz) para más detalles.

Si está interesado en problemas más generales y cómo se relacionan con la convexidad, consulte Modelos generalizados de bajo rango .

Descargo de responsabilidad: las respuestas anteriores hacen un trabajo bastante bueno al explicar cómo la PCA en su formulación original no es convexa, pero puede convertirse en un problema de optimización convexa. Mi respuesta solo está dirigida a esas pobres almas (como yo) que no están tan familiarizadas con la jerga de las Esferas de la Unidad y las SVD, lo cual es, por cierto, bueno saber.

Mi fuente son estas notas de clase del profesor Tibshirani

Para que un problema de optimización se resuelva con técnicas de optimización convexa, hay dos requisitos previos.

1. La función objetivo tiene que ser convexa.
2. Las funciones de restricción también deben ser convexas.

La mayoría de las formulaciones de PCA implican una restricción en el rango de una matriz.

$rank(X) = k,$$J_{11}$$J_{22}$