This paper, authored by Chenyang Yuan and Pablo A. Parrilo, explores the intersection of non-convex optimization and combinatorial matrix theory. It provides a new lens through which to view the "permanent" of a matrix—a notoriously difficult value to compute—by relating it to the problem of maximizing products of linear forms.
TL;DR
The authors demonstrate that a convex relaxation for maximizing products of linear forms is equivalent to a known relaxation for the permanent of Hermitian positive semidefinite (HPSD) matrices. By applying a randomized rounding strategy and bounding the rank of the optimal solution, they achieve a tighter multiplicative approximation factor for the permanent than previously known.
What Problem Does This Paper Address?
In linear algebra, the determinant is easy to compute, but its cousin, the permanent, is #P-hard (essentially "very hard") even for simple matrices. The permanent is defined similarly to the determinant but without the alternating signs. For Hermitian positive semidefinite (HPSD) matrices—matrices that are the complex equivalent of "symmetric and positive"—the permanent has important applications in quantum information and physics.
Because exact computation is impossible for large matrices, researchers look for approximations. Previous work established a "simply exponential" approximation factor. This paper aims to tighten that gap. Simultaneously, it tackles the problem of maximizing a product of linear forms over a complex sphere, a non-convex optimization problem that is interesting in its own right for signal processing and geometry.
Methods
The authors bridge these two problems using the following approach:
- Convex Relaxation: They take the non-convex problem (maximizing the product of linear forms) and formulate a "natural" convex relaxation. They then prove this relaxation is mathematically equivalent to a known relaxation for the HPSD permanent.
- Randomized Rounding: To move from the "relaxed" solution back to a feasible vector on the complex sphere, they use a constructive randomized rounding algorithm. They sample from a complex multivariate Gaussian distribution and normalize the result.
- Rank Optimization: A crucial step involves the rank of the optimal solution ($P^*$) to the convex program. Using existing theorems on low-rank solutions for linear matrix inequalities, they show that one can always find an optimal solution with rank $r \leq O(\sqrt{n})$.
- Analytical Bounds: By applying Jensen's inequality and properties of the Gamma distribution (specifically the digamma function), they derive a new lower bound for the approximation factor that depends on this rank $r$.
Datasets
This is a theoretical paper and does not use standard external datasets (like ImageNet). Instead, the authors use:
- Synthetic Random Matrices: They evaluate their findings using 50 random instances of matrices drawn from the Gaussian orthogonal ensemble. These were used to experimentally observe the rank of the optimal solution $P^*$ as the matrix size $n$ increases.
Key Insights and Ideas
- The Rank-Approximation Link: The most significant insight is that the quality of the permanent approximation is tied to the rank of the solution to the convex relaxation. Previous bounds essentially assumed a "worst-case" full rank ($n$). By proving the rank can be restricted to $O(\sqrt{n})$, the authors mathematically "squeeze" the error bound.
- Equivalence of Relaxations: The paper shows that two seemingly different problems—one from optimization and one from matrix theory—share the same underlying convex structure.
- A New "Van der Waerden" Conjecture: The authors propose a new conjecture (Conjecture 5.1) suggesting that the exact solution to the product-of-linear-forms problem is a tighter relaxation of the permanent than the convex version. They show this is an analog to the famous van der Waerden conjecture for doubly stochastic matrices.
Key Results
- Improved Approximation Factor: The authors prove a new multiplicative approximation factor of $\frac{n!}{n^n} e^{-nL_r}$, where $L_r$ is a term related to the $r$-th harmonic number.
- Multiplicative Improvement: Because $r \approx \sqrt{n}$, this represents an $e^{O(\sqrt{n})}$ improvement over the previous state-of-the-art factor (which used a constant Euler-Mascheroni $\gamma$ in place of $L_r$).
- Experimental Validation: Numerical experiments (Figure 1) showed that for random matrices, the rank of the optimal solution is actually much lower than the theoretical $O(\sqrt{n})$ limit, suggesting the approximation might be even better in practice than the proof guarantees.
Limitations and Future Work
- Computational Hardness of $r(A)$: While the authors provide a relaxation, they acknowledge that they do not yet have a formal proof for the computational hardness of finding the exact maximum of the product of linear forms ($r(A)$).
- Proving the Conjecture: The paper leaves the proof of Conjecture 5.1 (the tighter relaxation) as an open challenge. They note that while the lower bound is proven, the upper bound remains elusive.
- Specific Matrix Classes: Future work could involve finding concrete bounds on the rank for specific structured matrices, which would lead to even tighter, specialized approximation factors.
Summary updated