Études systématiques de la somme des polynômes quadratiques au carré

Je me demande s'il existe des études systématiques de sommes de formes quadratiques au carré, similaires aux formes quadratiques, qui se reflètent pratiquement dans la décomposition des valeurs propres (qui a une énorme implication pratique). Quelques exemples liés à l'importance de la question.

1. Analyses en composantes principales (ACP) . Étant donné un ensemble de points trouver l'ensemble des axes u 1 , ... u m , écrit comme matrice U ∈ R n x R m , et les projections ξ 1 , ... , ξ k , ξ ∘ ∈ R m qui minimise la variance inexpliquée, c'est-à-dire résout le problème d'optimisation quartique suivant$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$

   Par la magie de la symétrie, il a la solution par décomposition de valeurs singulières

2. ACP généralisée . Identique à PCA, mais il existe maintenant une matrice de précision associée à chaque x i observable . Le problème devient plus compliqué$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$

   (lorsque tous les sont une matrice d'identité, ce problème est équivalent à l'ACP, lorsque A i = A j , ∀ i , j et en diagonale, il est pondéré PCA). Ce problème peut également être résolu en temps polynomial via une programmation semi-définie (SDP) - Puisque la solution a la forme de sommes de carrés, par NZ Shor (1987) c'est un problème convexe, et la thèse de Parillo (2000) donne une pratique moyen de le calculer via SDP $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$ ne peut pas être représenté comme une somme de carrés de polynômes quadratiques, au-delà de cela.

Je me demande si quelqu'un a fait des études systématiques de polynômes représentables par la somme des carrés des polynômes quadratiques.

À ma connaissance, aucune étude de ce type n’existe; en outre, sans quelques avancées non triviales dans la technologie des problèmes de somme des carrés (SOS), il n'est pas actuellement clair quel serait l'avantage immédiat d'une telle étude. (Je vais me concentrer sur la connexion SOS car, pour autant que je sache, c'est la meilleure façon de résoudre ces problèmes généraux.) ces problèmes. Je vais étayer ma réclamation de plusieurs façons, j'espère que les gens trouveront utile ..

Premièrement, pour les problèmes les plus élémentaires du type que vous discutez, la connexion SVD offre un bien meilleur solveur que la boîte noire SOS; en particulier, ce dernier construit un SDP avec des termes , où est le nombre total de variables dans le problème d'optimisation de la source (par exemple, le nombre total d'éléments dans toutes les matrices inconnues; pour voir où j'ai obtenu ces chiffres, voir la conférence 10 du cours de Pablo Parrilo de 2006: http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-972-algebraic-techniques-and-semidefinite-optimization -spring-2006 / lecture-notes / lecture_10.pdf ). C'est un SDP que vous ne voudriez jamais résoudre (le temps d'exécution dépend de comme$\binom{n+2}{2}$$n$$n$$n^{6}$en utilisant un solveur de point intérieur?), en particulier par rapport à la vitesse ridicule d'un solveur SVD (en utilisant une notation cohérente, SVD sera quelque chose comme ; vous pouvez effacer mes calculs en suivant la nombre de colonnes, de lignes et de rang cible, mais c'est un désastre, peu importe comment vous rectifiez ma négligence). Dans cette veine, si vous avez conçu un algorithme spécialisé pour résoudre les problèmes SOS où le degré maximum au sein d'un polynôme est de deux: ce serait étonnant, puis le type d'enquête que vous recherchez aurait beaucoup de valeur.$\mathcal O(n^{1.5})$

Deuxièmement, puisque la formulation de base de ces problèmes est hors de la fenêtre, on peut se demander si certaines variantes de ces problèmes sont bien gérées par les solveurs SOS. Comme exemple important, considérons le problème NMF (factorisation matricielle non négative), où les inconnues matricielles sur lesquelles vous optimisez (dans votre formulation ci-dessus) doivent maintenant avoir des entrées non négatives. Malheureusement, si vous prenez le SDP standard utilisé pour résoudre ces problèmes (voir par exemple les notes de Pablo Parrilo ci-dessus), il n'y a aucun moyen d'introduire ces contraintes. (Et comme certaines formulations des problèmes résultants sont NP-difficiles, vous construisez maintenant un schéma d'approximation; c'est-à-dire que cela peut devenir désagréable.) En outre, des travaux récents ont exploité la structure polynomiale de ce problème pour construire des solveurs avec certains garanties: voirhttp://arxiv.org/abs/1111.0952 par Arora, Ge, Kannan et Moitra. Ils construisent quelques algorithmes, mais lorsqu'ils résolvent un problème NMF "exact" (où il y a une factorisation exacte, c'est-à-dire un donnant la valeur objective 0), ils n'utilisent pas de solveur SOS: ils utilisent un solveur vérifiant la faisabilité de "semi -algebraic sets ", un problème d'optimisation beaucoup plus difficile qui permet les types de contraintes que NMF soulève, mais maintenant avec un temps de fonctionnement exponentiel.

Quoi qu'il en soit, pour résumer et donner une autre perspective; puisque SOS est afaik le seul résolveur pour les problèmes de quartique dont vous parlez (c'est-à-dire, je ne pense pas qu'il existe un résolveur de quartique spécialisé), j'ai discuté de la façon dont ces solveurs ont de meilleures alternatives pour les types de problèmes de quartique dont les gens se soucient. Pour utiliser efficacement les outils SOS ici, vous devez soit créer un solveur incroyable pour le cas quartique (polynômes internes de degré au plus 2), soit vous devez trouver un moyen d'ajouter des contraintes à ces problèmes. Sinon, la connexion aux problèmes SOS, bien que fascinante, ne vous donne pas grand-chose.

Vous mentionnez également que vous êtes surpris que la littérature que vous avez trouvée ne fasse pas ce lien. Je pense que cela est principalement dû à la nouveauté des solveurs SOS pratiques (même si la considération abstraite des problèmes SOS remonte très loin), et ce que j'ai dit ci-dessus. En fait, quand j'ai trouvé les solveurs SOS pour la première fois, c'était via les notes et les papiers de Parrilo, et je me suis également demandé, "pourquoi ne parle-t-il pas de problèmes de type PCA"? Ensuite, j'ai vérifié les faits ci-dessus et j'ai beaucoup froncé les sourcils. Je pense que c'est aussi un mauvais signe que Parrilo lui-même n'ait pas, pour autant que je sache, évoqué ces problèmes en dehors de la référence que vous mentionnez dans sa thèse (en attendant, il a des articles sur diverses extensions, et j'ai beaucoup de respect pour son travail dans ces domaines: il a dû penser à plusieurs reprises à ces problèmes spécifiques.http://arxiv.org/abs/1111.1498 ).