Maximizing determinants under partition constraints
Maximizing determinants under partition constraints
复制标题
最大化分区约束下的行列式
DOI：
10.1145/2897518.2897649
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Mohit Singh
中科院分区：
文献类型：
--
作者：
Aleksandar Nikolov;Mohit Singh
给定一个正半定量矩阵 L（其列和行以集合 U 为索引）和一个分割矩阵 M=（U，I），我们研究的问题是如何选择 M 的基 B，从而使 B 中行和列诱导的 L 子矩阵的行列式最大化。这个问题出现在很多领域，包括机器学习中的行列式点过程、实验设计、地理位置问题、差异理论和计算几何，以模拟包含多样性的子集选择问题。我们的主要成果是给出了该问题的几何凹程序，它能在er+o(r)的系数内逼近最优值，其中r表示分治矩阵M的秩。为了分析舍入算法，我们将算法的解以及松弛的目标值与某个稳定多项式联系起来。为了证明近似保证，我们利用了古尔维茨（Gurvits）在估计双随机矩阵永久性时证明的关于稳定多项式的一般不等式。
Given a positive semidefinte matrix L whose columns and rows are indexed by a set U, and a partition matroid M=(U, I), we study the problem of selecting a basis B of M such that the determinant of the submatrix of L induced by the rows and columns in B is maximized. This problem appears in many areas including determinantal point processes in machine learning, experimental design, geographical placement problems, discrepancy theory and computational geometry to model subset selection problems that incorporate diversity. Our main result is to give a geometric concave program for the problem which approximates the optimum value within a factor of er+o(r), where r denotes the rank of the partition matroid M. We bound the integrality gap of the geometric concave program by giving a polynomial time randomized rounding algorithm. To analyze the rounding algorithm, we relate the solution of our algorithm as well the objective value of the relaxation to a certain stable polynomial. To prove the approximation guarantee, we utilize a general inequality about stable polynomials proved by Gurvits in the context of estimating the permanent of a doubly stochastic matrix.