Improved log-Sobolev inequalities, hypercontractivity and uncertainty principle on the hypercube

DOI10.1016/J.JFA.2019.108280zbMath1423.60038arXiv1606.07491OpenAlexW2965725349WikidataQ125124495 ScholiaQ125124495MaRDI QIDQ2326494

Alex Samorodnitsky, Yury Polyanskiy

Publication date: 7 October 2019

Published in: Journal of Functional Analysis (Search for Journal in Brave)

Abstract: Log-Sobolev inequalities (LSIs) upper-bound entropy via a multiple of the Dirichlet form (i.e. norm of a gradient). In this paper we prove a family of entropy-energy inequalities for the binary hypercube which provide a non-linear comparison between the entropy and the Dirichlet form and improve on the usual LSIs for functions with small support. These non-linear LSIs, in turn, imply a new version of the hypercontractivity for such functions. As another consequence, we derive a sharp form of the uncertainty principle for the hypercube: a function whose energy is concentrated on a set of small size, and whose Fourier energy is concentrated on a small Hamming ball must be zero. The tradeoff between the sizes that we derive is asymptotically optimal. This new uncertainty principle implies a new estimate on the size of Fourier coefficients of sparse Boolean functions. We observe that an analogous (asymptotically optimal) uncertainty principle in the Euclidean space follows from the sharp form of Young's inequality due to Beckner. This hints that non-linear LSIs augment Young's inequality (which itself is sharp for finite groups).

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

zbMATH Keywords

uncertainty principlecoding theoryHamming spacehypercontractivity

Mathematics Subject Classification ID

Inequalities; stochastic orderings (60E15) Sobolev spaces and other spaces of ``smooth functions, embedding theorems, trace theorems (46E35) Fuzzy sets and logic (in connection with information, communication, or circuits theory) (94D05)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On metric properties of maps between Hamming spaces and related graph homomorphisms
• Superadditivity of Fisher's information and logarithmic Sobolev inequalities
• Modified logarithmic Sobolev inequalities in discrete settings
• Linear programming bounds for codes via a covering argument
• Ultracontractivity and the heat kernel for Schrödinger operators and Dirichlet Laplacians
• On Fourier transforms of functions supported on sets of finite Lebesgue measure
• Hardy-Littlewood theory for semigroups
• On mod \(p\) transversals
• Inequalities in Fourier analysis
• On support properties of Lsup(p)-functions and their Fourier transforms
• On modified logarithmic Sobolev inequalities for Bernoulli and Poisson measures
• A subexponential upper bound for entropy convergence of Markov chains with a spectral gap
• Ricci curvature of finite Markov chains via convexity of the entropy
• On reverse hypercontractivity
• Nazarov's uncertainty principles in higher dimension
• Étude des coefficients de Fourier des fonctions de \(L^ p(G)\)
• Logarithmic Sobolev inequalities for finite Markov chains
• On the similarity of the entropy power inequality and the Brunn- Minkowski inequality (Corresp.)
• Some inequalities satisfied by the quantities of information of Fisher and Shannon
• Entropy inequalities for discrete channels
• Logarithmic Sobolev Inequalities
• New upper bounds on the rate of a code via the Delsarte-MacWilliams inequalities
• Logarithmic Sobolev Inequalities for the Heat-Diffusion Semigroup
• A theorem on the entropy of certain binary sequences and applications--I
• Pitt's Inequality and the Uncertainty Principle
• Generalized Alon--Boppana Theorems and Error-Correcting Codes
• Prolate Spheroidal Wave Functions, Fourier Analysis and Uncertainty - I
• Prolate Spheroidal Wave Functions, Fourier Analysis and Uncertainty - II
• An introduction to the theory of large deviations
• On the optimum of Delsarte's linear program

Related Items (5)

Non-linear log-Sobolev inequalities for the Potts semigroup and applications to reconstruction problems ⋮ Intrinsic dimensional functional inequalities on model spaces ⋮ HWI inequalities in discrete spaces via couplings ⋮ Common Information, Noise Stability, and Their Extensions ⋮ Improved quantum hypercontractivity inequality for the qubit depolarizing channel

This page was built for publication: Improved log-Sobolev inequalities, hypercontractivity and uncertainty principle on the hypercube