Estimating Maximum by Moments for Functions on Orbits

2002/01/03 by Alexander Barvinok, Barvinok, Alexander
Mathematics · #20C15 #68R05 #68W25 #90C27 #90C30 #Combinatorics (math.CO) #FOS: Mathematics #Optimization and Control (math.OC) #Representation Theory (math.RT) #math.CO #math.OC #math.RT #msc:20C15 #msc:68R05 #msc:68W25 #msc:90C27 #msc:90C30

paper · pdf · doi:10.48550/arxiv.math/0201020

arxiv created 2002/01/03 · arxiv updated 2009/11/30

Abstract

Let G be a compact group acting in a real vector space V. We obtain a number of inequalities relating the Lⁱnfinity norm of a matrix element of the representation of G with its L^p norm for p<infinity. We apply our results to obtain approximation algorithms to find the maximum absolute value of a given multivariate polynomial over the unit sphere (in which case G is the orthogonal group) and for the multidimensional assignment problem, a hard problem of combinatorial optimization (in which case G is the symmetric group).

Related

• Moment maps and Riemannian symmetric pairs
• Max filtering with reflection groups
• Group-invariant max filtering
• Connecting optimization with spectral analysis of tri-diagonal matrices
• On the Computability of Continuous Maximum Entropy Distributions: Adjoint Orbits of Lie Groups