Source-linked AI summary
The positive semidefinite Grothendieck problem with rank constraint
Jop Briet, Fernando Mario de Oliveira Filho, Frank Vallentin
TL;DR
For fixed n, exact polynomial-time solution of SDP_n is unknown, while its unrestricted-rank relaxation is polynomial-time solvable. The paper develops a Wishart-based rounding scheme from SDP∞ to SDP_n. The resulting approximation ratio is optimal under the unique games conjecture.
Problem
For fixed n, polynomial-time exact solvability of SDP_n is unknown, while its unrestricted-rank relaxation SDP∞ can be solved in polynomial time.
Source: §1 · pp. 2–3Method
The paper analyzes a Wishart-based randomized rounding scheme that converts an optimal SDP∞ solution into a feasible SDP_n solution.
Source: Our results · p. 3, §2 · p. 4Results
The algorithm achieves γ(n), and under UGC no polynomial-time algorithm can approximate SDP_n with a ratio greater than γ(n)+ε for ε independent of m.
Source: Our results · p. 4Takeaways & Limitations
The rounding analysis is presented as potentially useful in other contexts, including approximating low-dimensional geometric embeddings.
Source: Our results · p. 3The stated Laplacian-case condition requires A_ij=0 for every j=1,...,n.
Source: §6 · p. 11
Abstract
from arXiv · showhide
Given a positive integer n and a positive semidefinite matrix A = (A_{ij}) of size m x m, the positive semidefinite Grothendieck problem with rank-n-constraint (SDP_n) is maximize \sum_{i=1}^m \sum_{j=1}^m A_{ij} x_i \cdot x_j, where x_1, ..., x_m \in S^{n-1}. In this paper we design a polynomial time approximation algorithm for SDP_n achieving an approximation ratio of \gamma(n) = \frac{2}{n}(\frac{\Gamma((n+1)/2)}{\Gamma(n/2)})^2 = 1 - \Theta(1/n). We show that under the assumption of the unique games conjecture the achieved approximation ratio is optimal: There is no polynomial time algorithm which approximates SDP_n with a ratio greater than \gamma(n). We improve the approximation ratio of the best known polynomial time algorithm for SDP_1 from 2/\pi to 2/(\pi\gamma(m)) = 2/\pi + \Theta(1/m), and we show a tighter approximation ratio for SDP_n when A is the Laplacian matrix of a graph with nonnegative edge weights.
1 Introduction
The introduction defines SDP_n as a rank-constrained positive semidefinite Grothendieck problem and contrasts it with a polynomially solvable semidefinite relaxation. It frames approximation of SDP_n as an open algorithmic question for fixed n.
1 Introduction
- SDP_n optimizes over unit vectors in R^n, whose inner-product matrix has rank n.The objective is a positive-semidefinite quadratic form specified by A.Source: §1 · p. 2
- For n=1, SDP_1 includes MAX CUT: with A a graph Laplacian, its value coincides with the maximum cut value, making it NP-hard.Source: §1 · p. 2
- The vector problem can be reformulated as a semidefinite program with an additional constraint that X has rank at most n.Source: §1 · p. 2
- For fixed n, no polynomial-time algorithm is known to solve SDP_n, and it is not known whether SDP_n is NP-hard when n≥2.Source: §1 · p. 2
- The unrestricted-rank relaxation SDP∞ is polynomial-time solvable, and prior work bounds its relation to SDP_1 by a factor of 2/π.Source: §1 · p. 3
- For SDP_1, prior work gives a 2/π approximation ratio, with UGC ruling out any constant improvement independent of m.Source: §1 · p. 3
Our results
The paper analyzes a rounding algorithm for rank-constrained positive semidefinite Grothendieck problems, improves approximation guarantees, and establishes a UGC hardness threshold. It also gives a tighter guarantee when the matrix is a graph Laplacian with nonnegative edge weights.
Our results
- The rounding analysis uses the Wishart distribution, while a positive-type-function refinement slightly improves the constant used in the UGC hardness result.The authors identify the rounding analysis as potentially useful for low-dimensional geometric embeddings.Source: Our results · p. 3
- A randomized polynomial-time approximation algorithm for SDP_n achieves “this ratio”; the listed values of γ(n) include γ(2)=π/4=0.78539… and γ(3)=8/(3π)=0.84882….Source: Our results · p. 4
- The paper slightly improves inequality (1) and gives a polynomial-time SDP1 algorithm achieving the improved ratio.Source: Our results · p. 4
- Under the unique games conjecture, no polynomial-time algorithm approximates SDP_n with ratio greater than γ(n) + ε for any ε independent of m.This makes the achieved ratio optimal under the stated assumption.Source: Our results · p. 4
- For a graph Laplacian with nonnegative edge weights, SDP_n admits a better approximation ratio than in the general setting.Source: Our results · p. 4
2 Rounding schemes and functions of positive type
The rounding scheme maps an optimal SDP∞ solution to feasible vectors for SDP_n using a randomized Gaussian projection and normalization. Its analysis uses positive-type functions, with a dimension-dependent refinement for SDP1.
2 Rounding schemes and functions of positive type
- The randomized rounding maps an optimal SDP∞ solution to feasible SDP_n vectors, and for n = 1 it agrees with the Goemans–Williamson scheme.It draws a Gaussian matrix and normalizes each projected vector.Source: §2 · pp. 4–5
- The rounding expectation is a positive-type function on S∞, meaning its inner-product matrix is positive semidefinite for any finite set of unit vectors.Schoenberg’s characterization is invoked to analyze this property.Source: §2 · pp. 5–6
- For n ≥ 2 the first series coefficient is γ(n), while for n = 1 a dimension-dependent positive-type function refines the analysis.The n = 1 expansion has first coefficient 2/π.Source: §2 · p. 6
3 Analysis of the approximation algorithm
The section establishes positive type for the rounding expectation and computes its first series coefficient using a Wishart-distribution representation. That coefficient gives the approximation ratio γ(n).
3 Analysis of the approximation algorithm
- The rounding expectation En is analyzed as a positive-type function for S∞.The section uses orthogonal invariance to reduce the calculation to unit vectors parameterized by their inner product.Source: §3 · p. 6
- The first coefficient f1 in the series expansion of En is γ(n), yielding the approximation ratio for the rounding scheme.The calculation represents a two-vector Gram matrix using a Wishart distribution with p = n and q = 2.Source: §3 · pp. 6–8
4 Improved analysis
The section improves the SDP1 analysis by choosing the largest dimension-specific coefficient that preserves positive type on S^(m−1). This yields a polynomial-time approximation ratio of (2/π)c(m), where c(m) = 1/γ(m).
4 Improved analysis
- For SDP1, the Section 2 algorithm’s approximation ratio improves from 2/π to (2/π)c(m), where c(m) is chosen so t ↦ 2/π(arcsin t − c(m)t) is of positive type for S^{m−1}.Source: §4 · p. 9
- c(m) = 1/γ(m) is the largest coefficient for which arcsin t − c(m)t remains positive type on S^(m−1).The coefficient is obtained from the ratio of inner products with t under the section’s function-space inner product.Source: §4 · pp. 9–10
5 Hardness of approximation
The hardness argument turns an SDP_n approximation into an SDP1 approximation by applying the rounding scheme to its vectors. The unique games conjecture then bounds the achievable SDP_n ratio by γ(n).
5 Hardness of approximation
- If a polynomial-time algorithm achieves ratio ρ for SDP_n, rounding its approximate solution gives an SDP1 algorithm with ratio at least (2ρ)/(πγ(n)).The argument applies the rounding scheme to vectors from the SDP_n solution.Source: §5 · p. 10
- Under the unique games conjecture, the SDP1 hardness result implies that no polynomial-time SDP_n algorithm can achieve a ratio ρ greater than γ(n).The proof uses positive semidefiniteness of both A and the matrix arising from the rounding argument.Source: §5 · p. 10
6 The case of Laplacian matrices
The algorithm’s approximation ratio improves under a structural condition on A that includes graph Laplacians with nonnegative edge weights. The section gives the n=1 case and numerical values for n=2 and n=3.
6 The case of Laplacian matrices
- A tighter approximation ratio applies when A satisfies the stated structural condition, which includes Laplacians of weighted graphs with nonnegative edge weights.The argument uses a standard Goemans–Williamson approach.Source: §6 · pp. 10–11
- For n=1, the ratio is v(1) = 0.8785..., with its minimum attained at t0 = −0.689....This case corresponds to the Goemans–Williamson MAX CUT approximation algorithm.Source: §6 · p. 11
- For n=2, v(2) = 0.9349... at t0 = −0.617...; for n=3, v(3) = 0.9563... at t0 = −0.584....These values were computed numerically.Source: §6 · p. 11