A otimização do PCA é convexa?

A função objetivo da Análise de Componentes Principais (PCA) é minimizar o erro de reconstrução na norma L2 (consulte a seção 2.12 aqui . Outra visão é tentar maximizar a variação na projeção. Também temos um excelente post aqui: Qual é a função objetivo do PCA ? ).

Minha pergunta é que a otimização do PCA é convexa? (Encontrei algumas discussões aqui , mas gostaria que alguém pudesse fornecer uma boa prova aqui no CV).

Não, as formulações usuais de PCA não são problemas convexos. Mas eles podem ser transformados em um problema de otimização convexa.

O insight e a diversão disso é acompanhar e visualizar a sequência de transformações, em vez de apenas obter a resposta: está na jornada, não no destino. Os principais passos nessa jornada são

1. Obtenha uma expressão simples para a função objetivo.

2. Amplie seu domínio, que não é convexo, em um que seja.

3. Modifique o objetivo, que não é convexo, para aquele que é, de uma maneira que obviamente não altera os pontos nos quais atinge seus valores ideais.

Se você vigiar de perto, poderá ver os multiplicadores SVD e Lagrange à espreita - mas eles são apenas uma exibição lateral, para interesse cênico, e não vou comentar mais sobre eles.

---

A formulação padrão de maximização de variância do PCA (ou pelo menos sua etapa principal) é

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

onde o matriz A é um simétrica, matriz positiva-semidefinido construída a partir dos dados (geralmente a sua soma dos quadrados e produtos de matriz, a sua matriz de covariâncias, ou a sua matriz de correlação).$n\times n$$\mathbb A$

(Equivalentemente, podemos tentar maximizar o objetivo irrestrito . Essa expressão não é apenas mais desagradável - ela não é mais uma função quadrática - mas representar graficamente casos especiais mostrará rapidamente que não é uma função convexa Geralmente, observa-se que essa função é invariante sob os redimensionamentos x → λ x e depois a reduz à formulação restrita ( ∗ ) .)$x^\prime \mathbb{A} x / x^\prime x$$x\to \lambda x$$(*)$

Qualquer problema de otimização pode ser formulado abstratamente como

Encontre pelo menos um que torne a função f : X → R a maior possível.$x\in\mathcal{X}$$f:\mathcal{X}\to\mathbb{R}$

Lembre-se de que um problema de otimização é convexo quando possui duas propriedades separadas:

1. The domain $\mathcal{X}\subset\mathbb{R}^n$ is convex. This can be formulated in many ways. One is that whenever $x\in\mathcal{X}$ and $y\in\mathcal{X}$ and $0 \le \lambda \le 1$, $\lambda x + (1-\lambda)y\in\mathcal{X}$ also. Geometrically: whenever two endpoints of a line segment lie in $\mathcal X$, the entire segment lies in $\mathcal X$.

2. A função é convexa. $f$ Isso também pode ser formulado de várias maneiras. Uma é que sempre que e y ∈ X e 0 ≤ λ ≤ 1 , f ( λ x + ( 1 - λ ) y ) ≥ λ f ( x ) + ( 1 - λ ) f ( y ) . (Precisávamos de $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$ sejam convexos em ordem para esta condição de fazer qualquer sentido) Geometricamente:. sempre é qualquer segmento de linha emX, o gráfico def(conforme restrito a esse segmento) fica acima ou no segmento de conexão(x,f(x))e(y,f(y))emRn+1.$\bar{xy}$$\mathcal X$$f$$(x,f(x))$$(y,f(y))$$\mathbb{R}^{n+1}$

   O arquétipo de uma função convexa é localmente em toda a parte parabólica com coeficiente líder não-positiva: em qualquer segmento de linha que pode ser expressa sob a forma com um ≤ $y\to a y^2 + b y + c$$a \le 0.$

Uma dificuldade com é que X é a esfera unitária S n - 1 ⊂ R n , que decididamente não é convexa. $(*)$$\mathcal X$$S^{n-1}\subset\mathbb{R}^n$ No entanto, podemos modificar esse problema incluindo vetores menores. Isso ocorre quando escalamos por um fator λ , f é multiplicado por λ 2 . Quando 0 < x ′ x < 1 , podemos escalar x até o comprimento da unidade multiplicando-o por λ = 1 $x$$\lambda$$f$$\lambda^2$$0 \lt x^\prime x \lt 1$$x$, aumentando assimfmas ficar dentro da bola unidadeDn={x∈ R n|x'x≤1}. Vamos reformular(∗)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{**}$$

Seu domínio é $\mathcal{X}=D^n$ o que claramente é convexo, então estamos no meio do caminho. Resta considerar a convexidade do gráfico de .$f$

Uma boa maneira de pensar sobre o problema mesmo que você não pretenda realizar os cálculos correspondentes - é em termos do Teorema Espectral. $(**)$ Diz que, por meio de uma transformação ortogonal , você pode encontrar pelo menos uma base de R n na qual A é diagonal: ou seja,$\mathbb P$$\mathbb{R}^n$$\mathbb A$

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

onde todas as entradas fora da diagonal de são zero. Essa escolha de P pode ser concebida como algo que não muda nada em A , mas apenas muda como você a descreve : quando você gira seu ponto de vista, os eixos das hipersuperfícies de nível da função x → x ′ A x (que sempre elipsóides) se alinham com os eixos das coordenadas.$\Sigma$$\mathbb{P}$$\mathbb A$$x\to x^\prime \mathbb{A} x$

Since $\mathbb A$ is positive-semidefinite, all the diagonal entries of $\Sigma$ must be non-negative. We may further permute the axes (which is just another orthogonal transformation, and therefore can be absorbed into $\mathbb P$) to assure that

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

If we let $x=\mathbb{P}^\prime y$ be the new coordinates $x$ (entailing $y=\mathbb{P}x$), the function $f$ is

$$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.$$

This function is decidedly not convex! Its graph looks like part of a hyperparaboloid: at every point in the interior of $\mathcal X$, the fact that all the $\sigma_i$ are nonnegative makes it curl upward rather than downward.

However, we can turn $(**)$ into a convex problem with one very useful technique. Knowing that the maximum will occur where $x^\prime x = 1$, let's subtract the constant $\sigma_1$ from $f$, at least for points on the boundary of $\mathcal{X}$. That will not change the locations of any points on the boundary at which $f$ is optimized, because it lowers all the values of $f$ on the boundary by the same value $\sigma_1$. This suggests examining the function

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

This indeed subtracts the constant $\sigma_1$ from $f$ at boundary points, and subtracts smaller values at interior points. This will assure that $g$, compared to $f$, has no new global maxima on the interior of $\mathcal X$.

Let's examine what has happened with this sleight-of-hand of replacing $-\sigma_1$ by $-\sigma_1 y^\prime y$. Because $\mathbb P$ is orthogonal, $y^\prime y = x^\prime x$. (That's practically the definition of an orthogonal transformation.) Therefore, in terms of the $x$ coordinates, $g$ can be written

$$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.$$

Because $\sigma_1 \ge \sigma_i$ for all $i$, each of the coefficients is zero or negative. Consequently, (a) $g$ is convex and (b) $g$ is optimized when $x_2=x_3=\cdots=x_n=0$. ($x^\prime x=1$ then implies $x_1=\pm 1$ and the optimum is attained when $y = \mathbb{P} (\pm 1,0,\ldots, 0)^\prime$, which is--up to sign--the first column of $\mathbb P$.)

Let's recapitulate the logic. Because $g$ is optimized on the boundary $\partial D^n=S^{n-1}$ where $y^\prime y = 1$, because $f$ differs from $g$ merely by the constant $\sigma_1$ on that boundary, and because the values of $g$ are even closer to the values of $f$ on the interior of $D^n$, the maxima of $f$ must coincide with the maxima of $g$.

No.

Rank $k$ PCA of matrix $M$ can be formulated as

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

($\|\cdot\|_F$ is Frobenius norm). For derivation see Eckart-Young theorem.

Though the norm is convex, the set over which it is optimized is nonconvex.

---

A convex relaxation of PCA's problem is called Convex Low Rank Approximation

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

($\|\cdot\|_*$ is nuclear norm. it's convex relaxation of rank - just like $\|\cdot\|_1$ is convex relaxation of number of nonzero elements for vectors)

You can see Statistical Learning with Sparsity, ch 6 (matrix decompositions) for details.

If you're interested in more general problems and how they relate to convexity, see Generalized Low Rank Models.

Isenção de responsabilidade: As respostas anteriores fazem um bom trabalho ao explicar como o PCA em sua formulação original não é convexo, mas pode ser convertido em um problema de otimização convexo. Minha resposta é voltada apenas para aquelas pobres almas (como eu) que não estão tão familiarizadas com o jargão das Esferas Unitárias e SVDs - o que é bom saber.

Minha fonte é esta nota de aula do Prof. Tibshirani

Para que um problema de otimização seja resolvido com técnicas de otimização convexa, existem dois pré-requisitos.

1. A função objetivo deve ser convexa.
2. As funções de restrição também devem ser convexas.

A maioria das formulações de PCA envolve uma restrição na classificação de uma matriz.

Nesse tipo de formulações de PCA, a condição 2 é violada. Porque, a restrição que$rank(X) = k,$ is not convex. For example, let $J_{11}$, $J_{22}$ be 2 × 2 zero matrices with a single 1 in the upper left corner and lower right corner respectively. Then, each of these have rank 1, but their average has rank 2.