Sampling matrices from Harish-Chandra–Itzykson–Zuber densities with applications to Quantum inference and differential privacy

DOI10.1145/3406325.3451094MaRDI QIDQ6065261zbMATH OpenOpenAlexWikidataFDO

Authors Jonathan Leake, Colin McSwiggen, Nisheeth K. Vishnoi

Publication date 14 November 2023

Published in Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

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

zbMATH Keywords

density matricesdifferential privacyexponential densitylow-rank approximationsampling from matrix manifoldsunitary orbits

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Abstract: Given two $nimesn$ Hermitian matrices $Y$ and $Lambda$, the Harish-Chandra-Itzykson-Zuber (HCIZ) distribution on the unitary group $extU(n)$ is $e^{exttr(ULambda{U}^{\ast }Y)}dmu(U)$, where $mu$ is the Haar measure on $extU(n)$. The density $e^{exttr(ULambda{U}^{\ast }Y)}$ is known as the HCIZ density. Random unitary matrices distributed according to the HCIZ density are important in various settings in physics and random matrix theory. However, the basic question of efficient sampling from the HCIZ distribution has remained open. We present two efficient algorithms to sample matrices from distributions that are close to the HCIZ distribution. The first algorithm outputs samples that are $xi$-close in total variation distance and requires polynomially many arithmetic operations in $log1/xi$ and the number of bits needed to encode $Y$ and $Lambda$. The second algorithm comes with a stronger guarantee that the samples are $xi$-close in infinity divergence, but the number of arithmetic operations depends polynomially on $1/xi$, the number of bits needed to encode $Y$ and $Lambda$, and the differences of the largest and the smallest eigenvalues of $Y$ and $Lambda$. HCIZ densities can also be viewed as exponential densities on $extU(n)$-orbits, and these densities have been studied in statistics, machine learning, and theoretical computer science. Thus our results have the following applications: 1) an efficient algorithm to sample from complex versions of matrix Langevin distributions studied in statistics, 2) an efficient algorithm to sample from continuous max-entropy distributions on unitary orbits, which implies an efficient algorithm to sample a pure quantum state from the entropy-maximizing ensemble representing a given density matrix, and 3) an efficient algorithm for differentially private rank-$k$ approximation, with improved utility bounds for $k>1$.

Cited in

(2)

• On the computability of continuous maximum entropy distributions with applications
• Deterministically approximating the volume of a Kostka polytope

This page was built for publication: Sampling matrices from Harish-Chandra–Itzykson–Zuber densities with applications to Quantum inference and differential privacy

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