L'optimisation PCA est-elle convexe?

La fonction objective de l'analyse en composantes principales (ACP) minimise l'erreur de reconstruction dans la norme L2 (voir la section 2.12 ici . Une autre vue essaie de maximiser la variance sur la projection. Nous avons également un excellent article ici: Quelle est la fonction objective de l'ACP ? ).

Ma question est la suivante : l'optimisation PCA est-elle convexe? (J'ai trouvé quelques discussions ici , mais j'aimerais que quelqu'un puisse fournir une belle preuve ici sur CV).

Non, les formulations habituelles de PCA ne sont pas des problèmes convexes. Mais ils peuvent être transformés en un problème d'optimisation convexe.

La perspicacité et le plaisir de cela sont de suivre et de visualiser la séquence de transformations plutôt que de simplement obtenir la réponse: cela réside dans le voyage, pas dans la destination. Les principales étapes de ce voyage sont

1. Obtenez une expression simple pour la fonction objectif.

2. Agrandir son domaine, qui n'est pas convexe, en un qui l'est.

3. Modifier l'objectif, qui n'est pas convexe, en un qui est, d'une manière qui ne change évidemment pas les points auxquels il atteint ses valeurs optimales.

Si vous surveillez de près, vous pouvez voir les multiplicateurs SVD et Lagrange qui se cachent - mais ils ne sont qu'un diaporama, là pour l'intérêt scénique, et je ne les commenterai pas plus loin.

---

La formulation standard de maximisation de la variance de l'ACP (ou au moins son étape clé) est

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

où la matrice A est une matrice symétrique semi-définie positive construite à partir des données (généralement sa somme des carrés et de la matrice des produits, sa matrice de covariance ou sa matrice de corrélation).$n\times n$$\mathbb A$

(De manière équivalente, nous pouvons essayer de maximiser l'objectif non contraint . Non seulement c'est une expression plus désagréable - ce n'est plus une fonction quadratique - mais la représentation graphique de cas spéciaux montrera rapidement que ce n'est pas une fonction convexe On observe généralement que cette fonction est invariante sous les redimensionnements x → λ x puis la réduit à la formulation contrainte ( ∗ ) .)$x^\prime \mathbb{A} x / x^\prime x$$x\to \lambda x$$(*)$

Tout problème d'optimisation peut être formulé de manière abstraite comme

Trouvez au moins un qui rend la fonction f : X → R aussi grande que possible.$x\in\mathcal{X}$$f:\mathcal{X}\to\mathbb{R}$

Rappelons qu'un problème d'optimisation est convexe lorsqu'il bénéficie de deux propriétés distinctes:

1. Le domaine est convexe. $\mathcal{X}\subset\mathbb{R}^n$ Cela peut être formulé de plusieurs façons. L'une est que chaque fois que et y ∈ X et 0 ≤ λ ≤ 1 , λ x + ( 1 - λ ) y ∈ X également. Géométriquement: chaque fois que deux points d'extrémité d'un mensonge de segment de droite en X , les mensonges ensemble de segments dans 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 fonction est convexe. $f$ Cela peut également être formulé de plusieurs façons. La première est que chaque fois que et y ∈ X et 0 ≤ λ ≤ 1 , f ( λ x + ( 1 - λ ) y ) ≥ λ f ( x ) + ( 1 - λ ) f ( y ) . (Nous avions besoin 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$être convexe pour que cette condition ait un sens.) Géométriquement: chaque fois que est un segment de ligne dans X , le graphique de f (limité à ce segment) se trouve au-dessus ou sur le segment de connexion ( x , f ( x ) ) et ( y , f ( y ) ) dans R n + 1 .$\bar{xy}$$\mathcal X$$f$$(x,f(x))$$(y,f(y))$$\mathbb{R}^{n+1}$

   L'archétype d'une fonction convexe est localement partout parabolique avec un coefficient de tête non positif: sur tout segment de droite, il peut s'exprimer sous la forme avec a ≤ $y\to a y^2 + b y + c$$a \le 0.$

Une difficulté avec est que X est la sphère unitaire S n - 1 ⊂ R n , qui n'est décidément pas convexe. $(*)$$\mathcal X$$S^{n-1}\subset\mathbb{R}^n$ Cependant, nous pouvons modifier ce problème en incluant des vecteurs plus petits. En effet, lorsque nous mettons à l'échelle par un facteur λ , f est multiplié par λ 2 . Lorsque 0 < x ′ x < 1 , nous pouvons mettre à l'échelle x jusqu'à la longueur unitaire en le multipliant par λ = 1 / $x$$\lambda$$f$$\lambda^2$$0 \lt x^\prime x \lt 1$$x$, augmentant ainsifmais restant dans la boule unitaireDn={x∈ R n∣x′x≤1}. Reformulons donc(∗)comme$\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{**}$$

Son domaine est qui est clairement convexe, nous sommes donc à mi-chemin. Reste à considérer la convexité du graphe de f .$\mathcal{X}=D^n$$f$

Une bonne façon de penser au problème même si vous n'avez pas l'intention d'effectuer les calculs correspondants - est en termes de théorème spectral. $(**)$ Il dit qu'au moyen d'une transformation orthogonale , vous pouvez trouver au moins une base de R n dans laquelle A est diagonal: c'est-à-dire,$\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$

Non.

$k$$M$

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

($\|\cdot\|_F$

Bien que la norme soit convexe, l'ensemble sur lequel elle est optimisée n'est pas convexe.

---

Une relaxation convexe du problème de l'ACP est appelée approximation convexe de bas rang

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

$\|\cdot\|_*$$\|\cdot\|_1$

Vous pouvez voir Apprentissage statistique avec parcimonie , ch 6 (décompositions matricielles) pour plus de détails.

Si vous êtes intéressé par des problèmes plus généraux et comment ils sont liés à la convexité, voir Modèles de bas rang généralisés .

Avertissement: Les réponses précédentes expliquent très bien comment PCA dans sa formulation d'origine n'est pas convexe mais peut être converti en un problème d'optimisation convexe. Ma réponse ne s'adresse qu'aux pauvres âmes (comme moi) qui ne sont pas si familières avec le jargon des sphères unitaires et des SVD - ce qui est, en fait, bon à savoir.

Ma source est cette note de cours du Prof. Tibshirani

Pour qu'un problème d'optimisation soit résolu avec des techniques d'optimisation convexe, il y a deux conditions préalables.

1. La fonction objectif doit être convexe.
2. Les fonctions de contrainte doivent également être convexes.

La plupart des formulations d'ACP impliquent une contrainte sur le rang d'une matrice.

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