Abstract
We study the convex relaxation of a polynomial optimization problem, maximizing a product of linear forms over the complex sphere. We show that this convex program is also a relaxation of the permanent of Hermitian positive semidefinite (HPSD) matrices. By analyzing a constructive randomized rounding algorithm, we obtain an improved multiplicative approximation factor to the permanent of HPSD matrices, as well as computationally efficient certificates for this approximation. We also propose an analog of van der Waerden's conjecture for HPSD matrices, where the polynomial optimization problem is interpreted as a relaxation of the permanent.
Introduction
In linear algebra, the determinant is computationally efficient to evaluate, but its counterpart, the permanent, is #P-hard even for simple matrices. The permanent of Hermitian positive semidefinite (HPSD) matrices—the complex analogue of symmetric positive semidefinite matrices—is of particular interest due to its applications in quantum information theory and physics. Given the computational hardness, research has focused on finding tight multiplicative approximations.
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 perspective on the HPSD permanent by relating it to the problem of maximizing products of linear forms over the complex sphere.
Methods and Convex Relaxation
The authors bridge these two domains through a multi-step approach:
- Equivalence of Relaxations: They demonstrate that a natural convex relaxation for maximizing products of linear forms is mathematically equivalent to a known relaxation for the permanent of HPSD matrices.
- Randomized Rounding: To obtain a feasible vector on the complex sphere from the relaxed solution, they utilize a constructive randomized rounding algorithm. This involves sampling from a complex multivariate Gaussian distribution and subsequent normalization.
- Rank Optimization: A critical component of their analysis is the rank of the optimal solution ($P^*$) to the convex program. By applying existing results on low-rank solutions for linear matrix inequalities, they prove that an optimal solution with rank $r \leq O(\sqrt{n})$ always exists.
- Analytical Bounds: Using Jensen's inequality and properties of the Gamma distribution (specifically the digamma function), they derive a new lower bound for the approximation factor that is explicitly dependent on this rank $r$.
Improved Approximation Results
The primary insight of this work is that the quality of the permanent approximation is intrinsically tied to the rank of the solution to the convex relaxation. While previous bounds assumed a worst-case full rank ($n$), proving that the rank can be restricted to $O(\sqrt{n})$ allows for a significantly tighter error bound.
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. Given that $r \approx \sqrt{n}$, this represents an $e^{O(\sqrt{n})}$ improvement over previous state-of-the-art factors that utilized the constant Euler-Mascheroni $\gamma$ instead of $L_r$.
Experimental Validation
The theoretical findings were evaluated using synthetic random matrices drawn from the Gaussian orthogonal ensemble. These experiments aimed to observe the behavior of the rank of the optimal solution $P^*$ as the matrix size $n$ increases.
As illustrated in Figure 1, the experimental average rank of the optimal solution is consistently much lower than the theoretical $O(\sqrt{n})$ limit. This suggests that in practice, the approximation factor may be even tighter than the established theoretical guarantees.
Discussion and Future Work
The paper also proposes a new conjecture (Conjecture 5.1), suggesting that the exact solution to the product-of-linear-forms problem provides a tighter relaxation of the permanent than the convex version. This serves as an analog to the van der Waerden conjecture for doubly stochastic matrices.
While the work provides a significant improvement in approximation factors, several open questions remain. The computational hardness of finding the exact maximum of the product of linear forms ($r(A)$) is not yet formally proven. Furthermore, proving the proposed conjecture and identifying concrete rank bounds for specific structured matrix classes remain areas for future research.
Summary updated