Source-linked AI summary
Efficient Algorithms for Subdeterminant Maximization under Partition Matroids
Nikhil Bansal, Yuze Xu
TL;DR
Under partition constraints, finding a maximum-determinant principal submatrix had a k^O(k) algorithmic approximation despite an e^k estimation guarantee. The paper rounds the geometric max-min relaxation using a continuous potential-driven process, obtaining a polynomial-time randomized exp(-O(k)) approximation that matches the estimation guarantee up to O(1) factors in the exponent.
Problem
For a PSD matrix and a partition matroid, the goal is to find a feasible base maximizing the principal submatrix determinant, while the best known algorithmic approximation was k^O(k) despite an e^k estimation guarantee.
Source: §1 · pp. 1–2Method
The algorithm starts from the geometric max-min relaxation and uses a potential-driven process to reduce support before rounding to an integral solution.
Source: §1.1 · p. 2Results
The polynomial-time randomized algorithm returns a base with determinant at least exp(-O(k)) times optimum with probability at least 3/4, matching the best estimation guarantee up to O(1) factors in the exponent.
Source: §1.1 · p. 2Takeaways & Limitations
Continuous-space modification of the relaxation provides an approach to bypass the k^O(k) barrier of exchange-based methods.
Source: §1.1 · p. 2, §1 · p. 2The continuous process description ignores convergence and running-time issues, and may require ever smaller steps near a degenerate point; the paper gives a discrete version separately.
Source: §3 · p. 12
Abstract
from arXiv · showhide
We consider the determinant maximization problem under partition constraints: Given an $n\times n$ PSD matrix A and a partition matroid $M$ on $[n]$, find a base $S$ of $M$ that maximizes $\det(A_{S,S})$. We give an $e^{O(k)}$-approximation algorithm to find such a set $S$, where $k$ is the rank of $M$. This improves upon the current $k^{O(k)}$-approximation, and matches the current $e^k$-estimation guarantee, up to $O(1)$ factors in the exponent. Our algorithm is based on rounding the geometric max-min relaxation due to Nikolov-Singh'2016, using a continuous potential-driven process, and several new structural and analytic properties of this relaxation.
1 Introduction
Partition-constrained subdeterminant maximization had a k^O(k) algorithmic approximation, even though the geometric max-min relaxation estimates the optimum within e^k. This paper gives a polynomial-time randomized e^O(k)-approximation and develops a continuous potential-driven rounding process to obtain it.
1 Introduction
- The prior partition-matroid algorithmic approximation was k^O(k), leaving a substantial gap from the e^k estimation guarantee.The paper identifies an exp(O(k)) approximation as an important target.Source: §1 · pp. 1–2
1.1 Our Result
- The partition-matroid algorithm achieves a polynomial-time randomized exp(-O(k)) approximation with probability at least 3/4, matching the best estimation guarantee up to O(1) factors in the exponent.The input matrix has rank d and the matroid rank satisfies k ≤ d.Source: §1.1 · p. 2
- The method starts from the Nikolov–Singh geometric max-min relaxation and continuously reduces support to O(k), losing at most O(k) in log-relaxation value before rounding.The final rounding uses the algorithm of [ESV17].Source: §1.1 · p. 2, §1.2 · p. 3
- The continuous-space approach is presented as a way to bypass the k^O(k) barrier of exchange-based methods.The paper also notes that those cycle-exchange methods cannot beat that bound.Source: §1.1 · p. 2, §1 · p. 2
- A potential tracks support reduction and objective value, yielding either first-order improvement or, when leverage scores are bounded, a second-order ascent direction.Degeneracies are handled by splitting the problem into smaller instances, and the process is discretized for polynomial running time.Source: §1.1 · p. 2, §1.2 · p. 3
1.2 Technical Overview
- The overview handles degenerate points by splitting the problem into lower-dimensional instances without losing objective value.At such points the inner minimizer may not exist.Source: §1.2 · p. 3
2 The Geometric Program
This section develops a geometric relaxation for partition-constrained volume maximization and establishes its saddle structure, support, derivative, and decomposition properties. It also gives objective-preserving structural reductions and methods for finding tight or violated constraints, providing tools for later algorithmic work.
2 The Geometric Program
- The problem is to choose a capacity-respecting transversal maximizing squared volume; the paper reduces to rank-r instances with r parts of capacity one.For positive-volume solutions, replacing each capacity-b part by b identical rank-one parts preserves the problem; k<d is deferred to Section C.Source: §2 · p. 4
2.1 Naive Convex Relaxation
- The naive log-determinant relaxation can have an unbounded gap, while Nikolov and Singh address the example by product-one rescaling of part contributions.With r=2 and M arbitrarily large, an integral determinant is at most M^2, whereas the fractional point has determinant Ω(M^4); rescaling makes the fractional matrix at most 2MI.Source: §2.1 · p. 5
2.2 Saddle Geometric Relaxation
- Nikolov and Singh’s [NS16] geometric relaxation introduces positive part scalings constrained to have product one, yielding a concave-in-x, convex-in-z saddle program solvable by standard convex–concave methods.The convexity in z follows from a Cauchy–Binet log-sum-exp representation; an inner minimizer may fail to exist at degenerate x.Source: §2.2 · pp. 5–6
2.4 Nondegenerate supports
- The inner infimum is attained at a unique minimizer exactly when the support is nondegenerate, and its minimizer has a quantitative norm bound.When every supported coordinate is at least α, the bound is ∥z(x)∥2 ≤ √r log(C(x)/cmin(x)); consequently, the norm is polynomially bounded in r, log(1/α), and input bit complexity.Source: §2.4 · p. 10
2.5 Exact tight-set split
- A tight set of parts splits a degenerate instance into lower-dimensional subinstances using the span of its vectors and projection onto the orthogonal complement, without loss in objective value.The relaxation and each supported integral transversal decompose across the two subinstances.Source: §2.5 · p. 10
- Deleting zero coordinates, contracting singleton parts, and splitting along proper tight sets preserve the objective value.These steps depend only on the support of x; zero-coordinate deletions occur at most O(n) times, while splits and singleton contractions occur only O(d) times.Source: §2.5 · p. 12
- Tight or violated Hall-type inequalities can be found by submodular minimization or, more simply, by matroid intersection.The function g(S) = ρ(S) − |S| is submodular because ρ is a linear-matroid rank function and |S| is modular.Source: §2.5 · p. 12
3 Continuous Process
The continuous process reduces the relaxation’s support while maintaining progress in its objective, using a potential function to identify ascent directions. Once the support is O(r), terminal rounding gives an exp(O(r)) loss.
3 Continuous Process
- The continuous process seeks local directions that increase L(x) = F(x) + Φ(x) while the support is large, splitting degenerate points into lower-dimensional instances.Its continuous description omits convergence and running-time issues; it may require ever-smaller steps near degeneracy and need not reach a degenerate point finitely.Source: §3 · p. 12
3.1 The Potential Function
- The potential p is highly convex on [0, 1/H], while p(s) and p′(s) remain bounded independently of H; tiny coordinates satisfy 0 < x_i ≤ 1/(2H).Although the second derivative is discontinuous at s = 1/H, the argument only uses p′′(s) for s ≤ 1/(2H).Source: §3.1 · pp. 12–13
3.2 Progress Argument
- More than (2H + 4)r active coordinates guarantee a first- or second-order ascent direction, and the total loss in log-objective F is at most O(r).The argument uses first-order progress or leverage control, then a dimension-counting null-Schur direction on tiny coordinates; −r ≤ Φ ≤ 0 bounds the loss, while exact contractions and tight-set splits preserve the relaxation value.Source: §3.2 · pp. 13–14
3.3 Terminal rounding
- Once the support is O(r), the ESV17 randomized polynomial-time rounding algorithm yields a base with probability at least 3/4.For residual support m = O(r), the product of part sizes is O(1)^r, so terminal rounding incurs only an exp(O(r)) loss.Source: §3.3 · p. 15
4 Polynomial-time Discrete Dynamics
Section 4 converts the continuous compression argument into a polynomial-time finite-step algorithm, using the potential L(x) = F(x) + Φ(x), a shared floor and deletion threshold, and a probability interpretation of derivatives to analyze progress and deletion. The algorithm terminates after polynomially many arithmetic iterations and returns a transversal whose determinant is at least exp(−O(d)) times the optimum integral value, with a bounded second-order move that stays in the quadratic region unless a coordinate reaches the floor.
4 Polynomial-time Discrete Dynamics
- The finite-step analysis uses a shared inverse-polynomial floor and deletion threshold τ = 1/(104dn), avoiding direct stability analysis of Γ−1.The same τ is the computational floor and the threshold for deleting coordinates.Source: §4 · p. 15
4.1 Initialization
- Initialization solves the relaxation, removes singleton and proper exact tight parts and zero coordinates, then restricts the optimizer to the floor with negligible loss.For x in Δr, the restriction guarantees F(y) ≥ F(x) + r log(1 − nτ).Source: §4.1 · pp. 15–16
4.2 A Concave Surrogate for L and Progress
- At the next point y, either ∥y−x∥₂≥1/(5H) and L increases by at least 1/(50H), or otherwise ℓᵢ(y)≤3 for every i∈E; large moves occur only O(r) times since Φ≤r.Source: §4.2 · pp. 16–17
4.3 Deleting small coordinates
- Over at most n deletions, the total loss in F is O(nrτ) ≪ 1 and negligible; renormalizing part a by 1/(1−τ) only increases F.Source: §4.3 · pp. 17–18
4.4 Probabilistic interpretation of derivatives
- The Cauchy–Binet distribution expresses derivatives through expectations, covariances, and variances, providing the probabilistic dictionary used in the finite-step analysis.At the balanced point, the expected part-count for each part is 1.Source: §4.4 · p. 19
4.5 Bounding F in null-Schur direction via Gibbs lower bound
- For feasible null-Schur directions with η(δ) = 0, the finite-step bound applies for |t| ≤ 1/(4rK0), using a tilted distribution and a Gibbs lower bound.Here K0 = maxi in supp(x) |δi|/xi, and η is computed at x.Source: §4.5 · pp. 20–21
4.6 Second Order Progress
- After rebalancing certifies bounded leverage and floor coordinates are deleted, either a component has small support or a finite null-Schur step yields inverse-polynomial progress.The stated conditions include active coordinates above τ, leverage at most 3, and more than 4r small coordinates for the progress alternative.Source: §4.6 · p. 22
- The second-order step takes length at most c1τ^3/r^3 and stays in the quadratic region unless it stops when a coordinate reaches the floor τ.The length bound ensures the step satisfies t ≤ 1/(4rK0), so Lemma 4.5 applies.Source: §4.6 · p. 23
4.7 The Final Algorithm
- The process terminates after polynomially many arithmetic iterations, with polynomially many large rebalancing and null-Schur steps and at most n deletions.Large rebalancing steps increase L by 1/(50H), while finite null-Schur steps that do not hit the floor increase it by at least c2τ^6/d^6 = 1/poly(n, d).Source: §4.7 · p. 23
- The final transversal has determinant at least exp(−O(d)) times the optimum integral value.Exact contractions and tight-set splits combine the residual determinants with the accumulated log-value.Source: §4.7 · p. 24
A A barrier for cycle exchanges
A Hadamard-based example shows that an ℓ-local optimum under partition constraints can be far from the best transversal. The construction extends the local-improvement barrier of [BLP+22] to exchanges involving up to ℓ parts.
A A barrier for cycle exchanges
- The example extends [BLP+22] from single-part exchanges to exchanges involving up to ℓ parts.The cited earlier example considered ℓ = 1.Source: A A barrier for cycle exchanges · p. 25
- Each of the d partition parts has rank 1, and the standard transversal selects the corresponding standard basis vector from each part.The construction uses a d × d Hadamard matrix and its columns to form the competing transversal.Source: A A barrier for cycle exchanges · p. 25
- (d/(2ℓ))^d: the all-Hadamard transversal has determinant at least this factor larger than the standard transversal.The standard transversal is a strict local optimum for every exchange involving at most ℓ parts.Source: A A barrier for cycle exchanges · p. 25
B Proof of Terminal Rounding
The terminal rounding proof first samples a fractional point with a determinant close to the maximum with probability at least 3/4, then rounds each block greedily to a vertex. A block-exposure argument supplies the anti-concentration bound used for the sampling guarantee.
B Proof of Terminal Rounding
- With probability at least 3/4, the sampled point U has |D(U)| ≥ e^-4r Dmax.The block variables are sampled independently and uniformly from [-1, 1].Source: B Proof of Terminal Rounding · pp. 25–26
- Conditioning on all but a coordinate with largest coefficient bounds the probability of a small linear form, yielding an exponential tail after reparameterization.Setting η = e^-s gives a tail bound of at most e^-s, which is integrated to obtain the expectation bound.Source: B Proof of Terminal Rounding · p. 26
- The exposure process tracks the maximum determinant over future vertex blocks as sampled blocks are revealed.It starts at Dmax and ends at |D(U)|; Markov's inequality is used to obtain the stated result.Source: B Proof of Terminal Rounding · p. 26
- Greedy block rounding chooses the coefficient with largest absolute value at each step, losing at most a factor m_t deterministically for block t.The determinant is linear in each block variable when the other blocks are fixed.Source: B Proof of Terminal Rounding · pp. 25–27
C The case of k ≤d
For k ≤ d, the objective becomes the squared k-dimensional volume of the selected vectors rather than the determinant of a singular matrix. The proof extends by using a degree-s elementary symmetric objective on each residual component, with total losses O(k).
C The case of k ≤d
- When k < d, the selected-vector matrix is singular, so the objective is the squared k-dimensional volume instead of its determinant.The volume is expressed through the degree-k elementary symmetric polynomial of the associated positive semidefinite matrix.Source: C The case of k ≤d · p. 27
- By Cauchy–Binet, the squared k-dimensional volume equals the sum of squares of all k × k minors of the selected-vector matrix.Source: C The case of k ≤d · p. 27
- In a residual component with s remaining parts, the proof replaces the determinant objective with a degree-s elementary symmetric objective, keeping total losses O(k).The residual vectors may have ambient dimension larger than s, while the objective degree remains s.Source: C The case of k ≤d · p. 27
C.1 The syms scaling relaxation
The syms scaling relaxation extends the determinant relaxation to the elementary symmetric polynomial objective, with exact values on integral transversals and concavity in x. Its balance identity and geometric interpretation support analysis under partition constraints.
C.1 The syms scaling relaxation
- The syms scaling relaxation is exact on integral transversals and concave in x.Its proof uses exactness under product-one scalings and concavity of log syms on the positive semidefinite cone.Source: §C.1 · p. 28
- At the constrained minimizing scaling, each partwise derivative equals 1, yielding the partwise balance identity.The derivatives are equal at a constrained minimizer, and their sum is s by homogeneity.Source: §C.1 · p. 28
- Exact singleton contractions and tight-set splits decompose volume into a base volume in the spanned subspace and a projected height.This is the geometric meaning of the corresponding degeneracy and splitting operations.Source: §C.1 · p. 28
C.2 The calculus via the Cauchy–Binet distribution
The Cauchy–Binet distribution on s-subsets expresses the relaxation’s derivatives through subset statistics, including coordinate marginals, part counts, and directional changes.
C.2 The calculus via the Cauchy–Binet distribution
- The distribution’s coordinate marginals satisfy xiℓi = Prµx[i ∈ T], and each part has expected count 1.These identities connect syms-leverage scores and the balanced partwise scaling to the subset distribution.Source: §C.2 · p. 28
- The directional derivative is Eµxσδ, while the fixed-scaling second derivative is Varµx(σδ) − EµxA2,δ.The second-derivative identity applies at fixed z.Source: §C.2 · p. 28
- Mixed derivatives and the z-Hessian are covariances of part counts Ra with σδ and with other part counts, respectively.Specifically, ηa(δ) = Covµx(Ra, σδ) and Γab = Covµx(Ra, Rb).Source: §C.2 · p. 28
- Bx(δ) is EµxA2,δ − Varµx(σδ), and its coordinate direction satisfies Bx(ei) = ℓ2i.The lemma also supplies an additional identity for Bx.Source: §C.2 · p. 29
C.3 Compression Argument
The compression argument combines a capped potential with progress and leverage bounds, then deletes small coordinates and rounds the compressed support. The terminal rounding loses an exp(O(k)) factor because the support is O(k).
C.3 Compression Argument
- The capped potential L(x) = Gs(x) + Φ(x) tracks the relaxation and support reduction, with −s ≤ Φ(x) ≤ 0.The potential is the sum of p(xi) over coordinates, and the residual component has rank s.Source: §C.3 · p. 29
- Either a unit tangent direction gives DL(x)[δ] > 1/2, or every active coordinate has leverage score at most 3.The finite rebalancing lemma also gives the same leverage bound after a small step, while a large step increases L by a fixed amount.Source: §C.3 · pp. 29–30
- When more than 4s small coordinates remain, dimension counting gives a feasible direction with Bx(δ) ≤ 18.The direction preserves part constraints and satisfies η(δ) = 0.Source: §C.3 · p. 30
- Deleting a coordinate with xi = τ and ℓi ≤ 3 incurs at most O(s2τ) relaxation loss and O(τ) potential change.For τ = 1/poly(n,d), total deletion loss is negligible compared with the final O(k) log-loss; the balanced-certificate argument also transfers without dependence on ambient dimension.Source: §C.3 · p. 30
- The terminal rounding loses an exp(O(k)) factor because the compressed support is O(k).Multiplying the residual determinant by exact factors accumulated during contractions gives the final result.Source: §C.3 · p. 30