Ist die PCA-Optimierung konvex?

12

Die objektive Funktion der Hauptkomponentenanalyse (PCA) ist die Minimierung des Rekonstruktionsfehlers in der L2-Norm (siehe Abschnitt 2.12 hier) . Eine andere Ansicht versucht, die Varianz bei der Projektion zu maximieren. Wir haben auch hier einen ausgezeichneten Beitrag: Was ist die objektive Funktion der PCA? ? ).

Meine Frage ist, dass die PCA-Optimierung konvex ist? (Ich habe hier einige Diskussionen gefunden , aber ich wünschte, jemand könnte hier im Lebenslauf einen netten Beweis erbringen).

Haitao Du
quelle
3
Nein. Sie maximieren eine konvexe Funktion (unter Bedingungen).
user603
5
Ich denke, Sie müssen genau definieren, was Sie unter "PCA-Optimierung" verstehen. Eine Standardformulierung besteht darin, zu maximieren xAx, wobei xx=1 . Das Problem ist, dass Konvexität nicht einmal Sinn macht: Die Domäne xx=1 ist eine Kugel, kein euklidischer Raum.
Whuber
1
@whuber danke für deinen Kommentar, ich kann die Frage aufgrund begrenzter Kenntnisse möglicherweise nicht klären. Ich kann auf einige Antworten warten, die mir dabei helfen, die Frage gleichzeitig zu klären.
Haitao Du
3
Ich würde Sie auf jede Definition von "konvex" verweisen, mit der Sie vertraut sind. Enthalten sie nicht alle ein Konzept von Punkten im Bereich einer Funktion, die "zwischen" anderen Punkten liegt? Dies ist insofern zu beachten, als Sie daran erinnert werden, die Geometrie der Domäne einer Funktion sowie etwaige algebraische oder analytische Eigenschaften der Funktionswerte zu berücksichtigen. In diesem Licht fällt mir ein, dass die varianzmaximierende Formulierung leicht modifiziert werden kann, um die Domäne konvex zu machen: einfach xx1 anstelle von xx=1 . Die Lösung ist die gleiche - und die Antwort wird ganz klar.
Whuber

Antworten:

17

Nein, die üblichen Formulierungen von PCA sind keine konvexen Probleme. Sie können jedoch in ein konvexes Optimierungsproblem umgewandelt werden.

Die Einsicht und der Spaß daran besteht darin, die Abfolge der Transformationen zu verfolgen und zu visualisieren, anstatt nur die Antwort zu erhalten: Sie liegt in der Reise, nicht im Ziel. Die Hauptschritte auf diesem Weg sind

  1. Erhalten Sie einen einfachen Ausdruck für die Zielfunktion.

  2. Vergrößern Sie seine nicht konvexe Domäne in eine solche.

  3. Ändern Sie das nicht konvexe Ziel in eines, das offensichtlich die Punkte, an denen es seine optimalen Werte erreicht, nicht verändert.

Wenn Sie genau hinschauen, können Sie die SVD- und Lagrange-Multiplikatoren lauern sehen - aber sie sind nur eine Nebenschau, da für landschaftliches Interesse, und ich werde sie nicht weiter kommentieren.


Die standardmäßige varianzmaximierende Formulierung von PCA (oder zumindest dessen Schlüsselschritt) ist

(*)Maximize f(x)= xAx  subject to  xx=1

wobei die Matrix A eine symmetrische, positiv-semidefinite Matrix ist, die aus den Daten aufgebaut ist (üblicherweise ihre Summe aus Quadraten und Produktmatrix, ihre Kovarianzmatrix oder ihre Korrelationsmatrix).n×nA

(Entsprechend können wir versuchen, das nicht beschränkte Ziel zu maximieren . Dies ist nicht nur ein unangenehmerer Ausdruck - es ist keine quadratische Funktion mehr -, sondern die grafische Darstellung von Sonderfällen zeigt schnell, dass es keine konvexe Funktion ist Normalerweise beobachtet man, dass diese Funktion bei Neuskalierungen x λ x invariant ist und reduziert sie dann auf die eingeschränkte Formulierung ( ) .)xAx/xxxλx()

Jedes Optimierungsproblem kann abstrakt formuliert werden als

Finden Sie mindestens ein , das die Funktion f : XR so groß wie möglich macht.xXf:XR

Denken Sie daran, dass ein Optimierungsproblem konvex ist, wenn es zwei separate Eigenschaften aufweist:

  1. Die Domäne ist konvex. XRn Dies kann auf viele Arten formuliert werden. Eine ist, dass, wann immer und y X und 0 λ 1 , λ x + ( 1 - λ ) y xXyX0λ1 auch. Geometrisch: wenn zwei Endpunkte eines Liniensegments liegen in X , das gesamte Segment liegt in X .λx+(1λ)yXXX

  2. Die Funktion ist konvex. f Dies kann auch auf viele Arten formuliert werden. Einer ist , dass , wenn und y X und 0 λ 1 , f ( λ x + ( 1 - λ ) y ) λ f ( x ) + ( 1 - λ ) f ( y ) . (Wir brauchten XxXyX0λ1

    f(λx+(1λ)y)λf(x)+(1λ)f(y).
    X für diesen Zustand sein , um konvex zu machen beliebigen Sinn.) Geometrisch: Wann immer ein Liniensegment in X istxy¯X , liegt der Graph von (wie auf dieses Segment beschränkt) über oder auf dem Verbindungssegment ( x , f ( x ) ) und ( y , f ( y ) ) in R n + 1 .f(x,f(x))(y,f(y))Rn+1

    Der Archetyp einer konvexen Funktion ist lokal überall parabolisch mit nicht positivem Leitkoeffizienten: Auf jedem Liniensegment kann er in der Form y a y 2 + ausgedrückt werden mit a 0 .yay2+by+ca0.

Eine Schwierigkeit bei ist, dass X die Einheitskugel S n - 1R n ist , die entschieden nicht konvex ist. ()XSn1Rn Wir können dieses Problem jedoch ändern, indem wir kleinere Vektoren einbeziehen. Das liegt daran, dass wenn wir mit einem Faktor λ skalieren , f mit λ 2 multipliziert wird . Wenn 0 < x ' x < 1 ist , können wir skalierenxλfλ20<xx<1 durch Multiplizieren mit λ = 1 / auf Einheitslängex, wodurchErhöhungfaber innerhalb der Einheitskugel bleibtDn={x R n|x'x1}. Lasst uns also()umformulierenalsλ=1/xx>1f Dn={xRnxx1}()

(**)Maximize f(x)= xAx  subject to  xx1

Seine Domäne ist was eindeutig konvex ist, also sind wir auf halber Strecke. Es bleibt die Konvexität des Graphen von f zu berücksichtigen .X=Dnf

Ein guter Weg, um über das Problem nachzudenken - auch wenn Sie nicht vorhaben, die entsprechenden Berechnungen durchzuführen - ist der Spektralsatz. () Es heißt, dass man mittels einer orthogonalen Transformation mindestens eine Basis von R n finden kann, in der A diagonal ist:PRnA

A=PΣP

wobei alle nicht diagonalen Einträge von Null sind. Eine solche Wahl von P kann so verstanden werden, dass sie überhaupt nichts an A ändert, sondern nur die Art und Weise, wie Sie es beschreiben : Wenn Sie Ihren Standpunkt drehen, werden die Achsen der Ebenenhyperseiten der Funktion x x A x (welche waren immer Ellipsoide) mit den Koordinatenachsen ausgerichtet.ΣPAxxAx

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

σ1σ2σn0.

If we let x=Py be the new coordinates x (entailing y=Px), the function f is

f(y)=yAy=xPAPx=xΣx=σ1x12+σ2x22++σnxn2.

Diese Funktion ist definitiv nicht konvex! Sein Graph sieht aus wie ein Teil eines Hyperparaboloids: An jedem Punkt im Inneren von führt die Tatsache, dass alle σ i nicht negativ sind, dazu, dass es sich eher nach oben als nach unten kräuselt . Xσi

Allerdings können wir uns wenden in ein konvexes Problem mit einer sehr nützlicher Technik. () Das Wissen , dass die maximal auftreten wird , wo , lassen Sie sich die Konstante subtrahiert σ 1 aus F , zumindest für die Punkte an der Grenze von X . Dadurch werden die Positionen von Punkten auf der Grenze, an denen f optimiert wird, nicht geändert , da alle Werte von f auf der Grenze um denselben Wert σ 1 gesenkt werden . Dies schlägt vor, die Funktion zu untersuchenxx=1σ1fXffσ1

g(y)=f(y)σ1yy.

This indeed subtracts the constant σ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 X.

Let's examine what has happened with this sleight-of-hand of replacing σ1 by σ1yy. Because P is orthogonal, yy=xx. (That's practically the definition of an orthogonal transformation.) Therefore, in terms of the x coordinates, g can be written

g(y)=σ1x12++σnxn2σ1(x12++xn2)=(σ2σ1)x22++(σnσ1)xn2.

Because σ1σi for all i, each of the coefficients is zero or negative. Consequently, (a) g is convex and (b) g is optimized when x2=x3==xn=0. (xx=1 then implies x1=±1 and the optimum is attained when y=P(±1,0,,0), which is--up to sign--the first column of P.)

Let's recapitulate the logic. Because g is optimized on the boundary Dn=Sn1 where yy=1, because f differs from g merely by the constant σ1 on that boundary, and because the values of g are even closer to the values of f on the interior of Dn, the maxima of f must coincide with the maxima of g.

whuber
quelle
4
+1 Very nice. I edited to fix one formula to what I think you intended (but please check). Apart from that, I found the sentence "That won't change any boundary values at which f is optimized" to be confusing at first, because the boundary values do change: you are subtracting σ1. Maybe it makes sense to reformulate a bit?
amoeba says Reinstate Monica
@amoeba Right on all counts; thank you. I have amplified the discussion of that point.
whuber
2
(+1) In your answer, you seem to define a convex function to be what most people would consider to be a concave function (perhaps since a convex optimization problem has a convex domain and a concave function over which a maximum is computed (or a convex function over which a minimum is computed))
user795305
2
@amoeba It's a subtle argument. Note, however, that the new maxima--those of g--are found to occur only on the boundary. That rules out your counterexamples. Another point worth noting is that in the end we don't really care whether new local (or even global) maxima happen to show up in the interior of X, because we are originally concerned only about local maxima on its boundary. We are therefore free to alter f in any way that will not make any of those local boundary maxima move or disappear.
whuber
2
Yes, I agree. It does not matter how f is modified on the inside, if the resulting g is "convex" and happens to have maxima on the boundary. Your g does happen to have maxima on the boundary, and this makes the whole argument work. Makes sense.
amoeba says Reinstate Monica
6

No.

Rank k PCA of matrix M can be formulated as

X^=argminrank(X)kMXF2

(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

X^=argminXcMXF2

( is nuclear norm. it's convex relaxation of rank - just like 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.

Jakub Bartczuk
quelle
1

Disclaimer: The previous answers do a pretty good job of explaining how PCA in its original formulation is non-convex but can be converted to a convex optimization problem. My answer is only meant for those poor souls (such as me) who are not so familiar with the jargon of Unit Spheres and SVDs - which is, btw, good to know.

My source is this lecture notes by Prof. Tibshirani

For an optimization problem to be solved with convex optimization techniques, there are two prerequisites.

  1. The objective function has to be convex.
  2. The constraint functions should also be convex.

Most formulations of PCA involve a constraint on the rank of a matrix.

In these type of PCA formulations, condition 2 is violated. Because, the constraint that rank(X)=k, is not convex. For example, let J11, J22 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.

kasa
quelle
Could you please explain what "X" refers to and why there is any constraint on its rank? This doesn't correspond with my understanding of PCA, but perhaps you are thinking of a more specialized version in which only k principal components are sought.
whuber
Yeah, X is the transformed (rotated) data matrix. In this formulation, we seek matrices that are at least of rank k. You can refer to the link in my answer for a more accurate description.
kasa