# Systematic studies of sum of quadratic polynomials squared

I'm wondering if there exists systematic studies of sums of quadratic forms squared, similar to the quadratic forms, which is practically reflected in eigenvalue decomposition (that has huge practical implication). Couple of examples related to the importance of the question.

1. Principal component analyses (PCA). Given a set of points $x_i \in \mathbb{R^n}, i=1..k$ find the set of axes $u_1$, ... $u_m$, written as matrix $U \in \mathbb{R^n x R^m}$, and projections $\xi_1$, ..., $\xi_k, \xi_{\circ} \in \mathbb{R^m}$ that minimizes unexplained variance, i.e. solve the following quartic optimization problem

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

By the magic of symmetry it has the solution by singular value decomposition

2. Generalized PCA. Same as PCA, but now there is a precision matrix $A_i \in \mathbb{R^n x R^n}$ associated with each observable $x_i$. The problem becomes more complicated

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

(when all $A_i$ are identity matrix this problem is equivalent to PCA, when $A_i = A_j, \forall i,j$, and diagonal it is weighted PCA ). This problem can also be solved in polynomial time via semi-definite programming (SDP) -- Since the solution has the form of sums of squares, by NZ Shor (1987) it is convex problem , and Parillo thesis (2000) gives a practical way to compute it via SDP $\square$

In SDP approach the quartic polynomial is written as a sum of quadratic polynomials squared. Therefore, it is of major importance to know what kind of quartic polynomials can be written as a sum of quadratic forms squared (by the analogy to biquadratic function they can be called biquadratic forms). Most of the literature, I've encountered stop at the point where they find that the minimum of quartic polynomial $p= \sum_k^n (x_k^2-1) + (a^T x)^2, a \in \mathbb{Z^n}$ is encoding partition problem, and there are no arguments why $p$ cannot be represented as a sum of squares of quadratic polynomials, beyond that.

I'm wondering if anyone made systematic studies of polynomials representable by the sum of squares of quadratic polynomials.

Firstly, for the most basic problems of the type you discuss, the SVD connection gives a much better solver than the SOS black box; in particular, the latter constructs an SDP with $\binom{n+2}{2}$ terms, where $n$ is the total number of variables in the source optimization problem (for instance, the total number of elements in all unknown matrices; to see where I got these numbers, see lecture 10 from Pablo Parrilo's 2006 course: http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-972-algebraic-techniques-and-semidefinite-optimization-spring-2006/lecture-notes/lecture_10.pdf ). This is an SDP you would never want to solve (running time depends on $n$ as $n^{6}$ using an interior point solver?), especially when compared with the ridiculous speed of an SVD solver (using consistent notation, SVD will be something like $\mathcal O(n^{1.5})$; you can de-fudge my computations by tracking the number of columns, rows, and target rank, but it's a disaster no matter how you rectify my negligence). Along this vein, if you designed a specialized algorithm to solve SOS problems where the max degree within any polynomial is two: this would be amazing, and then the sort of survey you seek would have lots of value.