Polynomial time approximation for max determinant under partition constraints
Determinant maximization subject to a partition matroid constraint via stable distributions
Data Structures and Algorithms
Summary
This paper looks at the challenge of picking groups of vectors to make a certain matrix property called the determinant as large as possible, while following some picking rules. The authors designed an algorithm that finds a good enough solution quickly, even when the best possible one is very hard to compute. Their method builds on earlier mathematical tools and adds a new step involving special random numbers to make computations easier. This helps find approximate solutions that were previously only estimated without knowing how to pick the vectors. The work focuses on balancing mathematical accuracy with practical computation time.
What this means in practice
- •For machine learning engineers: Select diverse feature subsets efficiently to improve model robustness under combinatorial constraints.
- •For signal processing teams: Approximate optimal sensor placement for maximizing coverage volumes under group constraints.
Authors
Yihang Sun, Jan Vondrak
Abstract
Given vectors $v_i \in {\mathbb R}^d$, we consider the problem of choosing a set $I$ independent in a partition matroid in order to maximize the determinant $\det (\sum_{i \in I} v_i v_i^T)$. Our main result is a polynomial-time approximation algorithm that finds a solution of value $det ( \sum_{i \in I} v_{i} v_{i}^T) \geq e^{-O(d)} OPT$, where $OPT = \max_{I^*} det ( \sum_{i \in I^*} v_{i} v_{i}^T)$. For partition matroids of rank $m \leq d$, we give a similar result for approximating the $m$-dimensional volume spanned by the chosen vectors, within a factor of $e^{O(m)}$. This matches earlier known algorithms that estimate the optimal value but do not find the corresponding solution, up to a constant in the exponent. Similar to these estimation algorithms, our algorithm is based on the saddle-point relaxation proposed by Nikolov and Singh. A new ingredient is a randomized transformation based on $1/2$-stable distributions, which converts the saddle-point relaxation into a more convenient multilinear relaxation.