Stability and complexity of mixed discriminants

DOI10.1090/MCOM/3468zbMATH Open1442.15008arXiv1806.05105OpenAlexW2962682472WikidataQ127617609 ScholiaQ127617609MaRDI QIDQ5207439FDOQ5207439

Authors: Alexander Barvinok 

Publication date: 27 December 2019

Published in: Mathematics of Computation (Search for Journal in Brave)

Abstract: We show that the mixed discriminant of $n$ positive semidefinite $nimesn$ real symmetric matrices can be approximated within a relative error $epsilon>0$ in quasi-polynomial $n^{O(lnn-lnepsilon)}$ time, provided the distance of each matrix to the identity matrix in the operator norm does not exceed some absolute constant $gamm{a}_0>0$. We deduce a similar result for the mixed discriminant of doubly stochastic $n$-tuples of matrices from the Marcus - Spielman - Srivastava bound on the roots of the mixed characteristic polynomial. Finally, we construct a quasi-polynomial algorithm for approximating the sum of $m$-th powers of principal minors of a matrix, provided the operator norm of the matrix is strictly less than 1. As is shown by Gurvits, for $m=2$ the problem is $$-hard and covers the problem of computing the mixed discriminant of positive semidefinite matrices of rank 2.

Full work available at URL: https://arxiv.org/abs/1806.05105

Recommendations

• Mathematical Foundations of Computer Science 2005
• A deterministic polynomial-time algorithm for approximating mixed discriminant and mixed volume
• Computing mixed discriminants, mixed volumes, and permanents
• Concentration of the mixed discriminant of well-conditioned matrices
• A deterministic algorithm for approximating the mixed discriminant and mixed volume, and a combinatorial corollary

zbMATH Keywords

algorithmapproximationcomplex zerosmixed discriminantmixed characteristic polynomial

Mathematics Subject Classification ID

Approximation algorithms (68W25) Determinants, permanents, traces, other special matrix functions (15A15) Miscellaneous inequalities involving matrices (15A45) Quadratic and bilinear forms, inner products (15A63)

Cites Work

• Determinantal point processes for machine learning
• A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries.
• Interlacing families. II: Mixed characteristic polynomials and the Kadison-Singer problem
• Title not available (Why is that?)
• Polynomial Time Algorithms to Approximate Permanents and Mixed Discriminants Within a Simply Exponential Factor
• Mathematical Foundations of Computer Science 2005
• A deterministic algorithm for approximating the mixed discriminant and mixed volume, and a combinatorial corollary
• Combinatorics and complexity of partition functions
• An efficient tree decomposition method for permanents and mixed discriminants
• Deterministic polynomial-time approximation algorithms for partition functions and graph polynomials
• The solution of the Kadison-Singer problem
• On the complexity of constrained determinantal point processes

Cited In (4)

• A deterministic algorithm for approximating the mixed discriminant and mixed volume, and a combinatorial corollary
• Mathematical Foundations of Computer Science 2005
• A characterization of the mixed discriminant
• Concentration of the mixed discriminant of well-conditioned matrices

This page was built for publication: Stability and complexity of mixed discriminants

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5207439)