Systematic studies of sum of quadratic polynomials squared

Question

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

   $$ \arg\min_{u_1,\dots, u_n,\\ \xi_1,\dots, \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

   $$ \arg\min_{u_1,\dots, u_n,\\ \xi_1,\dots, \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.

Answer 1

To the best of my knowledge, there is no such study; furthermore, without some nontrivial advances in the technology of sum-of-squares (SOS) problems, it is not currently clear what the immediate benefit of such a study would be. (I'll focus on the SOS connection since that, as far as I know, is the best way to solve these general quartic problems.) This statement should be taken in a positive light: I believe there is a lot of research depth surrounding these problems. I'll substantiate my claim in a few ways, hopefully in ways people find useful..

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.

Secondly, since the basic formulation of these problems is out of the window, one may wonder if certain variants of these problems are well handled by SOS solvers. As an important example, consider the NMF (non-negative matrix factorization) problem, where the matrix unknowns you are optimizing over (in your above formulation) must now have non-negative entries. Unfortunately, if you take the standard SDP used to solve these problems (see for instance Pablo Parrilo's notes from above), there's no way to introduce those constraints. (And since some formulations of the resulting problems are NP-hard, you would now be building an approximation scheme; i.e., this can get nasty.) Furthermore, there is recent work that exploited the polynomial structure of this problem to build solvers with some guarantees: see http://arxiv.org/abs/1111.0952 by Arora, Ge, Kannan, and Moitra. They build a few algorithms, however when they solve an "exact" NMF problem (where there is an exact factorization, i.e., one giving objective value 0), they do not use a SOS solver: they use a solver checking feasibility of "semi-algebraic sets", a much more difficult optimization problem which allows the kinds of constraints which NMF raises, but now with exponential running time.

Anyway, to summarize and give some further perspective; since SOS is afaik the only solver for the quartic problems you speak of (i.e., I don't think there is a specialized quartic solver), I've discussed how these solvers have better alternatives for the kinds of quartic problems people care about. To effectively use SOS tools here, you would either have to build some amazing solver for the quartic case (inner polynomials of degree at most 2), or you would have to find some way to add constraints to these problems. Otherwise, the connection to SOS problems, while fascinating, does not give you much.

You also mention that you are surprised that the literature you have found does not make this connection. I think that is mostly due to the newness of practical SOS solvers (even though abstract consideration of SOS problems goes back very far), and what I said above. In fact, when I first found SOS solvers, it was via Parrilo's notes and papers, and I similarly wondered, "why isn't he talking about PCA-type problems"? Then I checked the above facts and frowned a lot. I think it's also a bad sign that Parrilo himself has not, as far as I can tell/skim, discussed these problems outside the reference you mention in his thesis (meanwhile, he has papers on various extensions, and I have a lot of respect for his work in these field: he must have thought about these specific quartic problems many times.. okay I just checked and found a related negative result by him and some colleagues, which has some connections in its introduction: http://arxiv.org/abs/1111.1498 ).