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

Given two n × n Hermitian matrices Y and Λ, the Harish-Chandra-Itzykson-Zuber (HCIZ) distribution on the unitary group U(n) is e Tr(UΛU * Y ) dµ(U ), where µ is the Haar measure on U(n). The density e Tr(UΛ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 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 ξ-close in the total variation distance and requires at most polynomially many arithmetic operations in log 1/ξ and the number of bits needed to encode Y and Λ. The second algorithm comes with a stronger guarantee that the samples are ξ-close in infinity divergence, however the number of arithmetic operations depends polynomially on 1/ξ, the number of bits needed to encode Y and Λ, and the differences of the largest and the smallest eigenvalues of Y and Λ. HCIZ densities can also be viewed as exponential densities on U(n)-orbits, and in this setting, they have been studied implicitly or explicitly 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 [8, 7] , 2) an efficient algorithm to sample from continuous maximum entropy distributions over unitary orbits [21, 20] , which in turn 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 [6, 18] that comes with improved utility bounds for k > 1. sample from the GT polytope, we use results of [22] for Theorem 1.3 and results of [3] for Theorem 1.4. We give a detailed technical overview of the algorithms and the proofs of Theorems 1.3, 1.4, and 1.5 in Section 3. The formal algorithms and proofs appear in Sections 4 and 6. Rayleigh triangles, Gelfand-Tsetlin polytopes, and unitary orbits In this section we introduce some definitions and facts that we will need in what follows. In particular, we discuss two types of combinatorial objects that are fundamental to the geometry of Hermitian matrices: Rayleigh triangles and Gelfand-Tsetlin polytopes. Definition 2.1 (Rayleigh triangle) For an integer n ≥ 1, a Rayleigh triangle is a triangular array of real numbers R = (R i,j ) 1≤i≤j≤n satisfying the interlacing relations The vector R •,j = (R 1,j , . . . , R j,j ) ∈ R j is called the jth row, and R •,n ∈ R n is called the top row. If we fix R •,n , we can regard the numbers R i,j , j ≤ n -1 as coordinates of a point in R n(n-1)/2 . Note that the indexing for the Rayleigh triangle is different from that of matrix notation: the top row is indexed by n. Definition 2.2 (Gelfand-Tsetlin polytope) Given a vector λ ∈ R n with λ 1 ≥ • • • ≥ λ n , the Gelfand-Tsetlin polytope GT (λ) is the convex polytope in R n(n-1)/2 consisting of all Rayleigh triangles with top row equal to λ. Thus, GT (λ) is the polytope cut out by the interlacing inequalities (6), with R •,n = λ fixed. In other words, the following system of n equalities and n × (n -1) inequalities determines GT (λ):