论文标题
来自Harish-Chandra-Itzykson-Zuber的采样矩阵，并应用于量子推理和差异隐私
Sampling Matrices from Harish-Chandra-Itzykson-Zuber Densities with Applications to Quantum Inference and Differential Privacy
论文作者
论文摘要
给定两个$ n \ times n $ hermitian矩阵$ y $和$λ$，harish-chandra-itzykson-zuber（hciz）在单一组$ \ text {u}（u} $ as $ e^{\ e^{\ text {tr}（tr}（uλu^*y）n $ she， $ \ text {u}（n）$。密度$ e^{\ text {tr}（uλu^*y）} $称为HCIZ密度。根据HCIZ密度分布的随机统一矩阵在物理和随机基质理论的各种环境中很重要。但是，来自HCIZ分布的有效抽样的基本问题仍然开放。我们提出了两种有效的算法，以从接近HCIZ分布的分布中采样矩阵。第一个算法输出的样本为$ξ$ close的总变化距离，并且在$ \ log 1/ξ$中需要多个算术操作，并且编码$ y $和$λ$所需的位数。第二种算法具有更强的保证，即无限差异的样品是$ξ$ close，但是算术操作的数量在多个一级取决于$ 1/ξ$，编码$ y $ $ $ $和$λ$所需的位数，以及最大的$ y $ y $ $ y和$ y和$ y的差异。 HCIZ密度也可以看作是$ \ text {u}（n）$ orbits上的指数密度，并且这些密度已在统计，机器学习和理论计算机科学中进行了研究。因此，我们的结果具有以下应用：1）从统计研究中研究的矩阵兰格文分布的复杂版本的样本的有效算法用于差异私有排名的算法-K $近似，并提高了$ k> 1 $的实用性界限。
Given two $n \times n$ Hermitian matrices $Y$ and $Λ$, the Harish-Chandra-Itzykson-Zuber (HCIZ) distribution on the unitary group $\text{U}(n)$ is $e^{\text{tr}(UΛU^*Y)}dμ(U)$, where $μ$ is the Haar measure on $\text{U}(n)$. The density $e^{\text{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 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 $ξ$-close in total variation distance and requires 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, but 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 $\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 rank-$k$ approximation, with improved utility bounds for $k>1$.
