Systematische Untersuchungen der Summe der quadratischen Polynome im Quadrat

Ich frage mich, ob es systematische Studien zu Summen quadratischer Formen im Quadrat gibt, ähnlich den quadratischen Formen, die sich praktisch in der Eigenwertzerlegung widerspiegeln (was enorme praktische Auswirkungen hat). Einige Beispiele bezogen sich auf die Bedeutung der Frage.

1. Hauptkomponentenanalysen (PCA) . Wenn eine Menge von Punkten die Menge von Achsen u 1 , ... u m , geschrieben als Matrix U ∈ R n x R m , und Projektionen ξ 1 , ... , ξ k , ξ ∘ ∈ R m das minimiert unerklärte Varianz, das heißt das folgende Optimierungsproblem lösen quartic$x_i \in \mathbb{R^n}, i=1..k$$u_1$$u_m$$U \in \mathbb{R^n x R^m}$$\xi_1$$\xi_k, \xi_{\circ} \in \mathbb{R^m}$

   $\mathop{argmin} \limits_{u_1,.., u_n,\ \xi_1, .., \xi_k} \sum \limits_{i} \left( U^T \xi_i - x_i \right)^2$

   Durch die Magie der Symmetrie hat es die Lösung durch Singularwertzerlegung

2. Generalisierte PCA . Wie PCA, aber jetzt gibt es eine Präzisionsmatrix die jedem beobachtbaren x i zugeordnet ist . Das Problem wird komplizierter$A_i \in \mathbb{R^n x R^n}$$x_i$

   $\mathop{argmin} \limits_{u_1,.., u_n,\ \xi_1, .., \xi_k} \sum \limits_{i} \left( A_i U^T \xi_i - x_i \right)^2$

   (Wenn alle eine Identitätsmatrix sind, ist dieses Problem äquivalent zu PCA, wenn A i = A j , ∀ i , j und diagonal ist, wird es PCA gewichtet). Dieses Problem kann auch in Polynomzeit durch semi-definitive Programmierung (SDP) gelöst werden. Da die Lösung die Form von Quadratsummen hat, handelt es sich nach NZ Shor (1987) um ein konvexes Problem, und die Parillo-These (2000) gibt ein praktisches Möglichkeit, es über SDP zu berechnen $A_i$$A_i = A_j, \forall i,j$$\square$

$p= \sum_k^n (x_k^2-1) + (a^T x)^2, a \in \mathbb{Z^n}$$p$ kann darüber hinaus nicht als Summe von Quadraten quadratischer Polynome dargestellt werden.

Ich frage mich, ob jemand systematische Studien von Polynomen durch die Summe der Quadrate quadratischer Polynome darstellbar gemacht hat.

Nach meinem besten Wissen gibt es keine solche Studie; Darüber hinaus ist ohne einige nicht triviale Fortschritte in der Technologie der Quadratsummenprobleme (SOS) derzeit nicht klar, welchen unmittelbaren Nutzen eine solche Studie haben würde. (Ich werde mich auf die SOS-Verbindung konzentrieren, da dies meines Wissens der beste Weg ist, um diese allgemeinen Quartalsprobleme zu lösen.) Diese Aussage sollte positiv bewertet werden: Ich glaube, es gibt viel Forschungstiefe diese Probleme. Ich werde meine Behauptung auf einige Arten begründen, hoffentlich auf eine Weise, die die Leute nützlich finden.

$\binom{n+2}{2}$$n$$n$$n^{6}$$\mathcal O(n^{1.5})$

Zweitens kann man sich fragen, ob bestimmte Varianten dieser Probleme von SOS-Lösern gut behandelt werden, da die Grundformulierung dieser Probleme außerhalb des Fensters liegt. Betrachten Sie als wichtiges Beispiel das NMF-Problem (Non-Negative Matrix Factorization), bei dem die Matrix-Unbekannten, über die Sie (in Ihrer obigen Formulierung) optimieren, jetzt nicht negative Einträge haben müssen. Wenn Sie das Standard-SDP verwenden, das zur Lösung dieser Probleme verwendet wird (siehe beispielsweise die Notizen von Pablo Parrilo von oben), gibt es leider keine Möglichkeit, diese Einschränkungen einzuführen. (Und da einige Formulierungen der resultierenden Probleme NP-hart sind, würden Sie jetzt ein Approximationsschema erstellen, dh dies kann unangenehm werden.) Darüber hinaus gibt es neuere Arbeiten, die die Polynomstruktur dieses Problems ausnutzten, um mit einigen Lösern zu erstellen Garantien: siehehttp://arxiv.org/abs/1111.0952 von Arora, Ge, Kannan und Moitra. Sie bauen einige Algorithmen auf, aber wenn sie ein "genaues" NMF-Problem lösen (bei dem es eine genaue Faktorisierung gibt, dh eine mit dem Zielwert 0), verwenden sie keinen SOS-Löser: Sie verwenden einen Löser, der die Machbarkeit von "semi" überprüft -algebraische Mengen ", ein viel schwierigeres Optimierungsproblem, das die Art von Einschränkungen zulässt, die NMF aufwirft, aber jetzt mit exponentieller Laufzeit.

Wie auch immer, um zusammenzufassen und eine weitere Perspektive zu geben; Da SOS afaik der einzige Löser für die Quartalsprobleme ist, von denen Sie sprechen (dh ich glaube nicht, dass es einen speziellen Quartic Solver gibt), habe ich diskutiert, wie diese Löser bessere Alternativen für die Arten von Quartalsproblemen haben, die die Menschen interessieren. Um SOS-Tools hier effektiv zu nutzen, müssten Sie entweder einen erstaunlichen Löser für den Quartikfall erstellen (innere Polynome mit einem Grad von höchstens 2), oder Sie müssten einen Weg finden, um diesen Problemen Einschränkungen hinzuzufügen. Ansonsten gibt Ihnen die Verbindung zu SOS-Problemen, obwohl sie faszinierend ist, nicht viel.

Sie erwähnen auch, dass Sie überrascht sind, dass die Literatur, die Sie gefunden haben, diesen Zusammenhang nicht herstellt. Ich denke, das liegt hauptsächlich an der Neuheit praktischer SOS-Löser (obwohl die abstrakte Betrachtung von SOS-Problemen sehr weit zurückreicht) und an dem, was ich oben gesagt habe. Als ich zum ersten Mal SOS-Löser fand, geschah dies über Parrilos Notizen und Papiere, und ich fragte mich in ähnlicher Weise: "Warum spricht er nicht über Probleme vom Typ PCA?" Dann überprüfte ich die obigen Fakten und runzelte viel die Stirn. Ich denke, es ist auch ein schlechtes Zeichen, dass Parrilo selbst, soweit ich das beurteilen / überfliegen kann, diese Probleme nicht außerhalb der Referenz diskutiert hat, die Sie in seiner These erwähnt haben (mittlerweile hat er Artikel über verschiedene Erweiterungen, und ich habe großen Respekt für seine Arbeit auf diesem Gebiet: Er muss viele Male über diese spezifischen Quartierprobleme nachgedacht haben.http://arxiv.org/abs/1111.1498 ).