Systematyczne badania sumy kwadratowych wielomianów podniesione do kwadratu

Zastanawiam się, czy istnieją systematyczne badania sum kwadratowych form kwadratowych, podobnych do form kwadratowych, co praktycznie znajduje odzwierciedlenie w rozkładzie wartości własnych (co ma ogromne praktyczne implikacje). Kilka przykładów związanych ze znaczeniem pytania.

1. Analizy głównych składników (PCA) . Biorąc pod uwagę zestaw punktów$x_i \in \mathbb{R^n}, i=1..k$ znajdź zestaw osi $u_1$, ... $u_m$, zapisane jako macierz $U \in \mathbb{R^n x R^m}$i prognozy $\xi_1$, ..., $\xi_k, \xi_{\circ} \in \mathbb{R^m}$ która minimalizuje niewyjaśnioną wariancję, tj. rozwiązuje następujący problem kwartalnej optymalizacji

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

   Dzięki magii symetrii rozwiązanie polega na pojedynczym rozkładzie wartości

2. Uogólnione PCA . Taki sam jak PCA, ale teraz istnieje precyzyjna matryca$A_i \in \mathbb{R^n x R^n}$ związane z każdym możliwym do zaobserwowania $x_i$. Problem staje się bardziej skomplikowany

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

   (gdy wszystko $A_i$ są matrycy tożsamości problem ten jest równoważny z PCA, kiedy $A_i = A_j, \forall i,j$, a przekątna jest ważona PCA). Problem ten można również rozwiązać w czasie wielomianowym za pomocą programowania półokreślonego (SDP) - Ponieważ rozwiązanie ma postać sum kwadratów, według NZ Shora (1987) jest to problem wypukły, a teza Parillo (2000) daje praktyczne sposób na obliczenie go za pomocą SDP$\square$

W podejściu SDP kwartalny wielomian jest zapisywany jako suma kwadratowych wielomianów podniesionych do kwadratu. Dlatego bardzo ważne jest, aby wiedzieć, jaki rodzaj wielomianów kwadratowych można zapisać jako sumę kwadratowych form kwadratowych (przez analogię do funkcji kwadratowej można je nazwać postaciami kwadratowymi). Większość literatury, z którą się spotkałem, zatrzymuje się w punkcie, w którym uważają, że minimum kwartalnego wielomianu$p= \sum_k^n (x_k^2-1) + (a^T x)^2, a \in \mathbb{Z^n}$ jest problem z kodowaniem partycji i nie ma argumentów dlaczego $p$ poza tym nie może być reprezentowana jako suma kwadratów wielomianów kwadratowych.

Zastanawiam się, czy ktokolwiek uczynił systematyczne badania wielomianów reprezentowalnymi przez sumę kwadratów kwadratowych wielomianów.

Według mojej najlepszej wiedzy nie ma takich badań; ponadto, bez pewnych niebanalnych postępów w technologii problemów z sumą kwadratów (SOS), nie jest obecnie jasne, jaka byłaby bezpośrednia korzyść z takiego badania. (Skoncentruję się na połączeniu SOS, ponieważ o ile mi wiadomo, jest to najlepszy sposób na rozwiązanie tych ogólnych problemów kwartycznych.) To stwierdzenie należy przyjąć w pozytywnym świetle: uważam, że istnieje wiele głębszych badań wokół te problemy. Potwierdzę swoje roszczenie na kilka sposobów, miejmy nadzieję, w sposób, w jaki ludzie uznają je za przydatne.

Po pierwsze, w przypadku najbardziej podstawowych problemów omawianego typu połączenie SVD daje znacznie lepsze rozwiązanie niż czarna skrzynka SOS; w szczególności ten ostatni konstruuje SDP z$\binom{n+2}{2}$ warunki, gdzie $n$jest całkowitą liczbą zmiennych w problemie optymalizacji źródła (na przykład całkowitą liczbą elementów we wszystkich nieznanych macierzach; aby zobaczyć, skąd je otrzymałem, zobacz wykład 10 z kursu Pablo Parrilo z 2006 r .: http://ocw.mit. edu / kursy / elektrotechnika i informatyka / 6-972-techniki algebraiczne i optymalizacja półfinałów-wiosna-2006 / wykład-notatki / wykład_10.pdf ). To jest SDP, którego nigdy nie chciałbyś rozwiązać (czas działania zależy od$n$ tak jak $n^{6}$ używasz wewnętrznego solvera punktowego?), zwłaszcza w porównaniu z absurdalną szybkością solvera SVD (stosując spójną notację, SVD będzie przypominać $\mathcal O(n^{1.5})$; możesz odrzucić moje obliczenia, śledząc liczbę kolumn, wierszy i rangi docelowej, ale to katastrofa bez względu na to, jak naprawisz moje zaniedbanie). W tym duchu, jeśli zaprojektowałeś wyspecjalizowany algorytm do rozwiązywania problemów SOS, w których maksymalny stopień w dowolnym wielomianu wynosi dwa: byłoby to niesamowite, a wtedy rodzaj poszukiwanej ankiety miałby dużą wartość.

Po drugie, ponieważ podstawowe sformułowanie tych problemów jest poza oknem, można się zastanawiać, czy niektóre warianty tych problemów są dobrze obsługiwane przez solwery SOS. Jako ważny przykład weźmy pod uwagę problem NMF (nieujemne rozkładanie macierzy), w którym nieznane macierze, nad którymi optymalizujesz (w powyższym sformułowaniu) muszą mieć teraz zapisy nieujemne. Niestety, jeśli weźmiesz standardowego SDP użytego do rozwiązania tych problemów (patrz na przykład notatki Pablo Parrilo z góry), nie ma możliwości wprowadzenia tych ograniczeń. (A ponieważ niektóre sformułowania wynikających z tego problemów są trudne dla NP, należy teraz budować schemat aproksymacji; tzn. Może to być nieprzyjemne.) Ponadto, ostatnio pracowano nad strukturą wielomianową tego problemu, aby budować solwery z niektórymi gwarancje: patrzhttp://arxiv.org/abs/1111.0952 przez Arora, Ge, Kannan i Moitra. Budują kilka algorytmów, jednak kiedy rozwiązują „dokładny” problem NMF (gdzie istnieje dokładna faktoryzacja, tj. Taka, która daje wartość celu 0), nie używają solwera SOS: używają solwera sprawdzającego wykonalność „semi” -sety algebraiczne ”, o wiele trudniejszy problem optymalizacji, który dopuszcza rodzaje ograniczeń, które podnosi NMF, ale teraz z wykładniczym czasem działania.

W każdym razie, aby podsumować i dać trochę dalszej perspektywy; ponieważ SOS jest afaik jedynym rozwiązaniem problemów kwartycznych, o których mówisz (tzn. nie sądzę, że istnieje wyspecjalizowany quartic solver), omówiłem, w jaki sposób te solwery mają lepsze alternatywy dla problemów kwartycznych, na których ludzie się troszczą. Aby efektywnie korzystać z narzędzi SOS tutaj, musiałbyś albo zbudować niesamowity solver dla przypadku kwartalnego (wewnętrzne wielomiany stopnia co najwyżej 2), albo musiałbyś znaleźć sposób na dodanie ograniczeń dla tych problemów. W przeciwnym razie połączenie z problemami SOS, choć fascynujące, nie daje wiele.

Wspominasz również, że jesteś zaskoczony, że znaleziona literatura nie ma tego związku. Myślę, że wynika to głównie z nowości praktycznych solverów SOS (mimo że abstrakcyjne rozpatrywanie problemów SOS sięga bardzo daleko) i tego, co powiedziałem powyżej. W rzeczywistości, kiedy po raz pierwszy znalazłem solwery SOS, było to za pośrednictwem notatek i dokumentów Parrilo, i podobnie zastanawiałem się, „dlaczego on nie mówi o problemach typu PCA”? Potem sprawdziłem powyższe fakty i zmarszczyłem brwi. Myślę, że to również zły znak, że sam Parrilo, o ile mogę powiedzieć / przejrzeć, nie omawiał tych problemów poza odniesieniem, o którym wspomniałeś w swojej pracy (tymczasem ma dokumenty na różne rozszerzenia i mam duży szacunek za swoją pracę w tej dziedzinie: musiał wiele razy przemyśleć te specyficzne problemy kwartalne ...http://arxiv.org/abs/1111.1498 ).