Given two n \times n Hermitian matrices Y and \Lambda, the Harish-Chandra--Itzykson--Zuber (HCIZ) density on the unitary group \mathrm{U (n) is e^{ \mathrm{Tr (U\Lambda U^*Y)}d\mu(U)  where \mu is the Haar measure on \mathrm{U (n). (U\Lambda U^*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 how to sample efficiently from the HCIZ density has remained open. The main contribution of this paper is an algorithm to sample a matrix from a distribution that is \varepsilon-close to the given HCIZ density and whose running time depends polylogarithmically on 1/ \varepsilon. Interestingly, HCIZ densities can also be viewed as exponential densities on \mathrm{U (n)-orbits, and in this setting, they have been widely studied . Thus, our result has several direct applications, including polynomial-time algorithms 1)  to sample from  matrix Langevin distributions studied in statistics, 2)  to sample from continuous maximum entropy distributions with applications to quantum inference , and 3)  for differentially private low-rank approximation. The key obstacle in sampling from an HCIZ density is that the domain is an algebraic manifold and the entries of the sample matrix are highly correlated. To overcome this, we consider a mapping that sends each Hermitian matrix X to a natural ordering of the eigenvalues of all leading principal minors of X. The image of each \mathrm{U(n)-orbit under this map is a convex polytope, and the mapping reveals a recursive structure of \mathrm{U}(n)-orbits. Subsequently, we develop efficiently computable determinantal expressions for densities that arise in the intermediate steps of sampling from the polytope. Our proof-technique applies to other compact Lie groups and can be viewed as extending the widely studied notion of self-reducibility.} 
Given two n \times n Hermitian matrices Y and \Lambda, the Harish-Chandra-Itzykson-Zuber (HCIZ) distribution on the unitary group \text{U (n) is e^{ \text{tr (U\Lambda U^*Y)}d\mu(U) , where \mu is the Haar measure on \text{U (n). The density e^{\text{tr(U\Lambda U^*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 \log 1/\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 \text{U (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 (n)-orbit under this map is a convex polytope, and the mapping reveals a recursive structure of \mathrm{U}(n)-orbits. Subsequently, we develop efficiently computable determinantal expressions for densities that arise in the intermediate steps of sampling from the polytope. Our proof-technique applies to other compact Lie groups and can be viewed as extending the widely studied notion of self-reducibility.} rank-k approximation, with improved utility bounds for k>1.
R
Harish-Chandra--Itzykson--Zuber
Harish-Chandra-Itzykson-Zuber
R
density
distribution
R
\mathrm{U
\text{U
R
\mathrm{Tr
\text{tr
A
,
R
\mathrm{U
\text{U
A
The density e^{\text{tr
R
how to sample efficiently
efficient sampling
R
density
distribution
R
The main contribution of this paper is an algorithm to sample a matrix from a distribution that is \varepsilon-close to the given HCIZ density and whose running time depends polylogarithmically
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 \log 1/\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
R
\varepsilon. Interestingly,
\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.
R
\mathrm{U
\text{U
R
in this setting, they have been widely studied . Thus, our result has several direct applications, including polynomial-time algorithms
these densities have been studied in statistics, machine learning, and theoretical computer science. Thus our results have the following applications:
A
an efficient algorithm
A
complex versions of
A
an efficient algorithm
R
maximum entropy distributions with applications to quantum inference
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
A
an efficient algorithm
D
low-rank approximation. The key obstacle in sampling from an HCIZ density is that the domain is an algebraic manifold and the entries of the sample matrix are highly correlated. To overcome this, we consider a mapping that sends each Hermitian matrix X to a natural ordering of the eigenvalues of all leading principal minors of X. The image of each \mathrm{U
A
rank-k approximation, with improved utility bounds for k>1.