Integration and Optimization of Multivariate Polynomials by Restriction onto a Random Subspace |
| |
Authors: | Alexander Barvinok |
| |
Institution: | (1) Department of Mathematics, University of Michigan, Ann Arbor, MI 48109-1043, USA |
| |
Abstract: | We consider the problem of efficient integration of an n-variate polynomial with respect to the Gaussian measure in ℝn and related problems of complex integration and optimization of a polynomial on the unit sphere. We identify a class of n-variate
polynomials f for which the integral of any positive integer power fp over the whole space is well approximated by a properly scaled integral over a random subspace of dimension O(log n). Consequently,
the maximum of f on the unit sphere is well approximated by a properly scaled maximum on the unit sphere in a random subspace
of dimension O(log n). We discuss connections with problems of combinatorial counting and applications to efficient approximation
of a hafnian of a positive matrix. |
| |
Keywords: | Polynomials Integration Wick formula Algorithms Random subspaces Gaussian measure |
本文献已被 SpringerLink 等数据库收录! |