# On emergent conformal symmetry near the photon ring

Bin Chen1,2,3, Yehui Hou1, and Zezhou Hu1

###### Abstract

In this note we revisit the emergent conformal symmetry in the near-ring
region of warped spacetime. In particular, we propose a novel construction of
the emergent near-ring $sl(2,R)_{\text{QNM}}$ symmetry. We show that each
eikonal QNM family falls into one highest-weight representation of this
algebra, and $sl(2,R)_{\text{QNM}}$ can be related to the near-ring isometry
group $sl(2,R)_{\text{ISO}}$ in a simple way. Furthermore we find that the
coherent state space of $sl(2,R)_{\text{QNM}}$ can be identified with the
phase space of the photon ring.

1School of Physics, Peking University, No.5 Yiheyuan Rd, Beijing 100871, P. R.
China
2Collaborative Innovation Center of Quantum Matter, No.5 Yiheyuan Rd, Beijing
100871, P. R. China
3Center for High Energy Physics, Peking University, No.5 Yiheyuan Rd, Beijing
100871, P. R. China

##  1 Introduction

The conformal symmetry plays an important role in studying black hole physics.
In AdS3/CFT2 correspondence, the entropy of the BTZ black hole could be
computed microscopically from the asymptotic growth of highly excited states
in dual CFT2[1]. Moreover, the frequencies of the quasinormal modes of the BTZ
black hole appear exactly as the poles in the retarded Green function of the
perturbations in the dual CFT2[2, 3]. These two correspondences are essential
in the subsequent investigations on the holographic pictures of higher-
dimensional black holes[4, 5] (see a nice review[6]) and warped black holes[7,
8, 9, 10, 11, 12]. Especially, for the higher dimensional black holes, the
conformal symmetry does not present itself explicitly. In the case of Kerr
black hole, the symmetry either appears only in the isometry of the near
horizon geometry of extreme Kerr (NHEK) [13] or emerges as the hidden
conformal symmetry in the low frequency scattering[14, 15].

In the past few years, following the release of the black hole images taken by
the Event Horizon Telescope (EHT) collaborations[16], the physics encoded in
the images has been intensely studied. Of particular interests is the black
hole photon ring, which has a subring structure. This subring structure
displays universal properties of the black holes, which are insensitive to the
environment around the black holes[17, 18, 19, 20, 21]. The photon ring is
produced by the unstably bound orbits of photons. Under a perturbation, the
photons on the orbit could escape to infinity after orbiting many times. It
turns out that these null trajectories provide eikonal approximations to the
quasi-normal modes (QNMs)[22, 23, 24, 25, 26].

Very recently, the holography of the photon ring was proposed in [27]. It was
shown that in the near-ring region of both Schwarzschild and Kerr black holes,
there emerges a hidden conformal symmetry, referred to as
$sl(2,R)_{\text{PR}}$, acting on the photon trajectories111For an earlier
discussion on the hidden conformal symmetry on the photon ring, see [28]..
More precisely, the $sl(2,R)_{\text{PR}}$ algebra can be constructed via
Poisson bracket in the phase space. On the other hand, considering the
massless wave propagation in the near-ring region, the wave equation reduces
to the Schrödinger equation with an upside-down harmonic potential, which has
a well-known conformal symmetry $sl(2,R)_{\text{QNM}}$. It turned out that the
$sl(2,R)_{\text{QNM}}$ algebra could be constructed by Heisenberg algebra and
the quasi-normal modes (QNMs) in the near-ring region can be described in a
Fock space. The eikonal QNMs fall into the highest-weight representations of
$sl(2,R)_{\text{QNM}}$, similar to the discussions on the BTZ black hole[2]
and on the warped black holes[29, 30, 31]. However, it is perplexing that the
entire QNMs constructed in [27] are decomposed into two highest-weight
representations of $sl(2,R)_{\text{QNM}}$, with one tower of descendants
having even overtone numbers and the other having odd overtone numbers.

In a more recent work, the study was generalized to the warped $AdS_{3}$
geometry[32], which is similar to the NHEK geometry and has an exact
$sl(2,R)_{\text{ISO}}$ isometry group. It was showed that the
$sl(2,R)_{\text{PR}}$ algebra in the phase space can be induced from
$sl(2,R)_{\text{ISO}}$ by simply contracting the Killing vectors with the
momentum of the photon. The entire eikonal QNM spectrum can be constructed by
using the $sl(2,R)_{\text{ISO}}$ symmetry as well. However, because each QNM
overtone family has two hightest-weight representations of
$sl(2,R)_{\text{QNM}}$ in the near-ring region, the $sl(2,R)_{\text{QNM}}$
symmetry constructed from the Heisenberg algebra failed to match the
$sl(2,R)_{\text{ISO}}$ symmetry.

In this note, we present a novel way to construct $sl(2,R)_{\text{QNM}}$ in
the near-ring region. For simplicity, our construction focus on the warped
$AdS_{3}$ black hole, but it can be applied to the near-ring regions of four-
dimensional black holes as well. We show that within our construction the
entire eikonal QNMs spectrum is described by only one highest-weight
representation and consequently the newly constructed $sl(2,R)_{\text{QNM}}$
match with the $sl(2,R)_{\text{ISO}}$ symmetry nicely. Moreover, we show that
there is an exact correspondence between the near-ring QNMs and the points in
the PR phase space, which may allow us to further identify the trajectories in
PR phase space with the coherent states of $sl(2,R)_{\text{QNM}}$.

##  2 Constructions of $sl(2,R)_{\text{PR}}$

For simplicity, we show our construction in a warped $AdS_{3}$ spacetime. The
metric of a warped $AdS_{3}$ black hole is of the form

$ds^{2}=l^{2}\left[\frac{-dT^{2}+dx^{2}}{\sinh^{2}x}+\Lambda^{2}\left(d\phi+\frac{dT}{\tanh
x}\right)^{2}\right],$ (2.1)

where $l$ is the (warped) $AdS_{3}$ radius, $T$ and $x$ are the time and
radial coordinates, respectively. The parameter $\Lambda$ is the warping
factor.

The null geodesics in the above spacetime are described by the phase space
$\\{x^{\mu},p_{\mu}\\}$, $x^{\mu}=T,x,\phi$, with a constrained Hamiltonian,
$\mathcal{H}=\frac{1}{2}g^{\mu\nu}p_{\mu}p_{\nu}=0$. The Hamilton equations
are

$\\{x^{\mu},\mathcal{H}\\}=\dot{x}^{\mu}\,,\quad\\{p_{\mu},\mathcal{H}\\}=\dot{p}_{\mu}\,.$
(2.2)

The “dot” represents the total derivative of the affine parameter. Since the
metric does not depend on $T$ and $\phi$, there are two constants of motion,
i.e., the energy and angular momentum, $H=-p_{T}$, $L=p_{\phi}$. The motion in
$x$-direction can be written as

$\big{(}\frac{l}{\sinh{x}}\big{)}^{2}\dot{x}=\pm_{x}H\sqrt{V(x)},$ (2.3)

where $\pm_{x}$ denotes the sign of $\dot{x}$, and the radial potential reads

$V(x)=(1+\lambda\coth{x})^{2}-\frac{\lambda^{2}}{\Lambda^{2}\sinh^{2}{x}}\geq
0.$ (2.4)

We have introduced a dimensionless impact parameter, $\lambda=L/H$. The photon
orbits are given by

$V(x)=V^{\prime}(x)=0.$ (2.5)

These give the double roots of the potential which are the unstable bound
photon orbits. Solving these equations, we get

$\hat{x}_{\pm}=\pm\tanh^{-1}{\sqrt{1-\frac{1}{\Lambda^{2}}}}\,,\quad\hat{\lambda}_{\pm}=\mp\frac{1}{\sqrt{1-\frac{1}{\Lambda^{2}}}}\,.$
(2.6)

Hence, we assume $\Lambda$ to be greater than $1$ to ensure the existence of
photon bound orbits. From now on, we will only consider the outer orbit. For
simplicity, we write $\hat{\lambda}=\hat{\lambda}_{+}$, $\hat{x}=\hat{x}_{+}$.

The null geodesics can also be described by introducing a new variable

$\Psi=\int
d\phi+H\int\bigg{[}\coth{x}(1+\lambda\coth{x})-\frac{\lambda}{\Lambda^{2}\sinh^{2}{x}}\bigg{]}\frac{dx}{\sqrt{V(x)}}\,.$
(2.7)

Then, $(T,H,\Psi,L)$ form a reduced phase space, with symplectic form
$dH\wedge dT+dL\wedge d\Psi$. The equations of motion are

$\dot{T}=\\{T,H\\}=1\,,\quad\dot{\Psi}=\\{\Psi,H\\}=0\,,\quad\dot{L}=\\{L,H\\}=0\,.$
(2.8)

To describe the deviation from the photon orbit, we define

$\hat{H}=H-L/\hat{\lambda}\,.$ (2.9)

The photon orbit has $\hat{H}=0$. As in [27, 32], the relation
$\\{T,H\\}=\\{T,\hat{H}\\}=1$ can be used to construct a $sl(2,R)$ algebra,
which is generated by

$H_{+}=\hat{H}\,,\quad H_{0}=-\hat{H}T\,,\quad H_{-}=\hat{H}T^{2}\,,$ (2.10)

with the commutation relation

$[H_{p},H_{q}]=(p-q)H_{p+q}\,,\qquad(p,q=+,0,-).$ (2.11)

Here, the quantity of physical interest is $T\hat{H}$. To see this, define a
finite action of $A$ on $B$ as

$\displaystyle e^{-\alpha A}Be^{\alpha
A}\equiv\sum_{n}\frac{(-\alpha)^{n}}{n!}\operatorname{ad}_{A}^{n}B\,,\quad\operatorname{ad}_{A}B\equiv\\{A,B\\}$
(2.12)

with $A,B$ both coordinates (or their functions) in the phase space. The
action of $T\hat{H}$ on $\hat{H}$ is

$e^{-\alpha T\hat{H}}\hat{H}e^{\alpha T\hat{H}}=e^{-\alpha}\hat{H},$ (2.13)

so $e^{-\alpha H_{0}}$ is a finite dilation, leading to the attraction towards
the photon bound orbit if $\alpha\char 62\relax 0$. The above construction was
the one in[27].

However, the construction of the $sl(2,R)$ algebra is not unique. Based on the
relation $\\{T,\hat{H}\\}=1$, there exist the following constructions of
$sl(2,R)$ algebra as well,

$\displaystyle H_{+}=T\,,\quad H_{0}=T\hat{H}\,,\quad H_{-}=T\hat{H}^{2}\,,$
(2.14)

or

$\displaystyle H_{+}=\frac{1}{2}T^{2}\,,\quad
H_{0}=\frac{1}{2}T\hat{H}\,,\quad H_{-}=\frac{1}{2}\hat{H}^{2}\,,$ (2.15)

and the automorphism of $sl(2,R)$

$\displaystyle H_{\pm}\rightarrow H_{\mp},\,\ H_{0}\rightarrow-H_{0}.$ (2.16)

Note that all the constructions above have $H_{0}\propto T\hat{H}$. Moreover,
all the constructions satisfy the same constraint

$H_{0}^{2}=H_{+}H_{-}.$ (2.17)

Thus, the phase space $(T,H)$ can be described by three generators
$(H_{+},H_{0},H_{-})$ with the constraint (2.17).

In addition, the relation $\\{\Psi,L\\}=1$ also leads to similar constructions
of $sl(2,R)$ algebra. For example, there is

$H_{+}=\hat{L},\,\ H_{0}=-\hat{L}\Psi,\,\ H_{-}=\hat{L}\Psi^{2}$ (2.18)

with $\hat{L}=L-\tilde{\lambda}H=-\tilde{\lambda}\hat{H}$ also describing the
deviation from the photon orbit, which has $\hat{L}=0$. Here, the dilation
operator is $\Psi\hat{L}$, since under a finite action, we have

$e^{-\alpha\Psi\hat{L}}\hat{L}e^{\alpha\Psi\hat{L}}=e^{-\alpha}\hat{L}\,.$
(2.19)

The reason for the existence of two schemes, Eq (2.13) and Eq (2.19), is that
the photon orbit is parameterized only by the impact parameter, $\lambda=L/H$.

##  3 Novel construction of $sl(2,R)_{\text{QNM}}$

In this section, we discuss the properties of near-ring QNMs introduced in
[32], and give a novel construction of the $sl(2,R)_{\text{QNM}}$ algebra of
the QNM spectrum. Although the construction here is in warped $AdS_{3}$
spacetime, it depends solely on the photon ring and near-ring region and can
be applied to four-dimensional Schwarzschild and Kerr black holes.

The isometry group of the warped $AdS_{3}$ spacetime Eq. (2.1) is generated by
the following Killing vectors

$\displaystyle\mathcal{L}_{0}=-\partial_{T}\,,$ (3.1)
$\displaystyle\mathcal{L}_{\pm}=e^{\pm T}(-\cosh x\partial_{T}\mp\sinh
x\partial_{x}+\sinh x\partial_{\phi})\,,$
$\displaystyle\mathcal{W}_{0}=\partial_{\phi}\,.$

The first three vectors generate the $sl(2,R)$ algebra, referred to as
$sl(2,R)_{\text{ISO}}$,

$[\mathcal{L}_{p},\mathcal{L}_{q}]=(p-q)\mathcal{L}_{p+q}\,,\qquad(p,q=+,0,-).$
(3.2)

For a minimally coupled free scalar field $\Phi(T,x,\phi)$ in the warped
spacetime, its equation of motion is

$\nabla^{2}\Phi=-\frac{1}{l^{2}}\left[-\mathcal{L}_{0}^{2}+\frac{\mathcal{L}_{+}\mathcal{L}_{-}+\mathcal{L}_{-}\mathcal{L}_{+}}{2}+\left(1-\frac{1}{\Lambda^{2}}\right)\mathcal{W}_{0}^{2}\right]\Phi=0\,,$
(3.3)

where the Laplacian is actually rewritten in terms of the Casimirs and thus
commutes with the Lie-derivative of Eq. (3.1). Hence, the isometric symmetry
is retained in the solution space of $\Phi$. As the translations along $T$ and
$\phi$ are obvious Killing vectors, the eigenfunctions can be labeled by the
eigenvalues of the operators $\mathcal{L}_{0}$ and $\mathcal{W}_{0}$,

$\Phi(T,\phi,x)=e^{im\phi}e^{(-i\hat{\omega}_{R}+\hat{\omega}_{I})T}\psi(x)\,,$
(3.4)

where $m=0,\pm 1,\pm 2...$ is the angular quantum number, and
$\hat{\omega}=\hat{\omega}_{R}+i\hat{\omega}_{I}$ is the complex frequency.

As shown in [32], the QNMs require the ingoing condition at the horizon
$x\rightarrow+\infty$, and outgoing condition at infinity $x\rightarrow 0$.
The conditions are satisfied by the highest-weight representation of
$sl(2,R)_{\text{ISO}}$,

$\Phi_{mn}(T,\phi,x)=e^{im\phi}e^{-(i\hat{\omega}_{R}+\frac{1}{2}+n)T}\psi_{mn}(x)\,,$
(3.5)

where $n=0,1,2...$ is the overtone number, and

$\hat{\omega}_{R}=-m\sqrt{1-\frac{1}{\Lambda^{2}}-\frac{1}{4m^{2}}}.$ (3.6)

Despite the fact that $\hat{\omega}_{R}$ is negative here, it does not affect
our discussion. The fundamental mode $\Phi_{m0}$ has the highest weight, and
is annihilated by $\mathcal{L}_{+}$,

$\mathcal{L}_{0}\Phi_{m0}=\hat{h}\Phi_{m0}=\bigg{(}\frac{1}{2}+i\hat{\omega}_{R}\bigg{)}\Phi_{m0}\,,\quad\mathcal{L}_{+}\Phi_{m0}=0\,,$
(3.7)

and the descendants $\Phi_{mn}(n\char 62\relax 0)$ can be obtained from
$\Phi_{m0}$ by acting $\mathcal{L}_{-}$ on successively,

$\Phi_{mn}\propto\mathcal{L}_{-}^{n}\Phi_{m0}\,.$ (3.8)

From now on, we consider the eikonal limit of QNMs. The eikonal QNMs have
$|m|\gg 1$ and take a simple form as

$\Phi_{mn}=e^{-(n+\hat{h})T}e^{im\phi+imx}(\sinh x)^{\hat{h}}(\cosh
x+\hat{\lambda}\sinh x)^{n},$ (3.9)

where the highest weight $\hat{h}$ is

$\hat{h}=1/2+i\hat{\omega}_{R}\,,\quad\hat{\omega}_{R}\approx
m\hat{\Omega}\,,$ (3.10)

with $\hat{\Omega}=\hat{\lambda}^{-1}=-\sqrt{1-\Lambda^{-2}}$ being the
angular velocity of the (outer) photon orbit. Then, we focus on the “near-ring
region”, defined by

$\displaystyle|\delta x|\ll 1\,,$ (3.11)
$\displaystyle|m/\hat{\omega}_{R}-\hat{\lambda}|\ll 1\,,$
$\displaystyle|\hat{\omega}_{R}|\gg 1\,,$

where $\delta x=x-\hat{x}_{+}$. In the warped $AdS_{3}$ spacetime, the last
two conditions requirs $|m|\gg 1$. Note that in the near-ring region, the
eikonal limit holds only if $|\hat{\omega}_{R}|\delta x^{2}\gg 1$, which is
the requirement that in this small region, the wavefront is still rapidly
changing [33]. In this case, the eikonal QNMs in Eq. (3.9) become

$\Phi^{\text{(NR)}}_{mn}\approx
c_{0}e^{-(n+\hat{h})T}e^{im\phi}\left(-\frac{\delta
x}{\sinh\tilde{x}}\right)^{n}e^{-\frac{i}{2}m\hat{\Omega}k\delta x^{2}},$
(3.12)

where $k=(\Lambda^{2}-1)^{-1}$,
$c_{0}=e^{im\tilde{x}}(\sinh{\tilde{x}})^{im\hat{\Omega}}$. The symbol “NR”
denotes the near-ring approximation. To check that the $sl(2,R)_{\text{ISO}}$
still exists under such approximation, we act the Lie-derivatives on the QNMs
in Eq. (3.12) and find

$\displaystyle\mathcal{L}_{0}\Phi^{\text{(NR)}}_{mn}=(n+\hat{h})\Phi^{\text{(NR)}}_{mn}\,,$
(3.13)
$\displaystyle\mathcal{W}_{0}\Phi^{\text{(NR)}}_{mn}=im\Phi^{\text{(NR)}}_{mn}\,,$
$\displaystyle\mathcal{L}_{+}\Phi^{\text{(NR)}}_{mn}\approx
n\Phi^{\text{(NR)}}_{mn-1}\,,$
$\displaystyle\mathcal{L}_{-}\Phi^{\text{(NR)}}_{mn}\approx
2im\hat{\Omega}\Phi^{\text{(NR)}}_{mn+1}\,.$

In the last two equations, we have expanded $\delta x$ in $\mathcal{L}_{\pm}$
and used $|m|\gg 1$, $|\hat{\omega}_{R}|\delta x^{2}\gg 1$.

In addition to the isometry survived, in the near-ring region the equation of
motion Eq. (3.3) has an emergent conformal symmetry. To see this, we define
the creation and annihilation operators as222Here, our definitions are
slightly different from article [32] for convenience. $a_{\mp}$,

$\displaystyle a_{-}$
$\displaystyle=\frac{e^{-T}}{\sqrt{2k\hat{\omega}_{R}}}(i\partial_{x}+k\hat{\omega}_{R}\delta
x)\,,$ (3.14) $\displaystyle a_{+}$
$\displaystyle=\frac{e^{T}}{\sqrt{2k\hat{\omega}_{R}}}(\partial_{x}+ik\hat{\omega}_{R}\delta
x)\,,$

which satisfy the Heisenberg algebra, $[a_{+},a_{-}]=1$. With the ansatz
$\Phi=e^{im\phi}e^{(-i\hat{\omega}_{R}+\hat{\omega}_{I})T}\psi(x)$, the
equation of motion in the near-ring region becomes

$\bigg{(}a_{-}a_{+}+\frac{1}{2}\bigg{)}\psi(x)=-\hat{\omega}_{I}\psi(x)\,.$
(3.15)

Hence, QNMs in near-ring region form a Fock space. There is a single vacuum
annihilated by $a_{+}$, which is exactly the fundamental mode in Eq. (3.12),

$\Phi_{m0}^{\text{(NR)}}\propto e^{-\frac{i}{2}k\hat{\omega}_{R}\delta
x^{2}},\hskip 12.91663pt\hat{\omega}_{I}=-\frac{1}{2},$ (3.16)

and the descendants are obtained by acting the creation operators on the
vacuum, $\Phi_{mn}^{\text{(NR)}}\propto a_{-}^{n}\Phi_{m0}^{\text{(NR)}}$. The
highest-weight condition ensures that the successive states are not-divergent
or not having a pole in the near-ring region. Then, note that

$a_{+}\left(\delta x^{n}e^{-\frac{i}{2}m\hat{\Omega}k\delta
x^{2}}\right)=\frac{e^{T}}{\sqrt{2k\hat{\omega}_{R}}}n\delta
x^{n-1}e^{-\frac{i}{2}m\hat{\Omega}k\delta x^{2}},$ (3.17)

which is consistent with the third equation in Eq. (3.13), up to a overall
factor. Therefore, a connection can be built by

$\mathcal{L}_{+}\sim L_{+}=\hat{s}a_{+},$ (3.18)

where $\hat{s}$ is a constant to be determined. Comparing Eq. (3.17) with the
action of $\mathcal{L}_{+}$ in Eq. (3.13), we have

$\mathcal{L}_{+}\Phi^{\text{(NR)}}_{mn}\approx n\Phi^{\text{(NR)}}_{mn-1}\sim
L_{+}\Phi^{\text{(NR)}}_{mn}=-\frac{n\hat{s}}{\sinh{\tilde{x}}\sqrt{2k\hat{\omega}_{R}}}\Phi^{\text{(NR)}}_{mn-1},$
(3.19)

where we have used the third relation in Eq. (3.17) and Eq. (3.12). Thus, we
can determine $\hat{s}$,

$\hat{s}\approx-\sinh{\tilde{x}}\sqrt{2k\hat{\omega}_{R}}\,.$ (3.20)

Based on this, we would like to propose a new construction of $sl(2,R)$
algebra by using the creation and the annihilation operators.

In [27], the authors provided a construction of $sl(2,R)$, which involved two
representations with the highest weight $1/4$ and $3/4$ respectively. These
two towers of modes must be interwoven to form the entire QNMs. We aim to
solve this perplexing “two towers” problem in the following construction.
Firstly, by defining $\mathcal{N}(L_{\pm})$ to be the number of $a_{-}$ minus
the number of $a_{+}$ in $L_{\pm}$, we require

$\mathcal{N}(L_{-})=+1\,,\quad\mathcal{N}(L_{+})=-1\,.$ (3.21)

And $L_{0}$ should be of the form $a_{-}a_{+}+\hat{h}$ to satisfy the
$sl(2,R)$ algebra

$[L_{0},L_{p}]=-pL_{p}\,,\qquad(p=+,-)\,.$ (3.22)

Adding $\hat{h}$ to the expression of $L_{0}$ is to give the correct highest
weight. Then, by virtue of the Heisenberg algebra, we can always write the
generators as

$\displaystyle L_{+}$ $\displaystyle=F(a_{-}a_{+})a_{+}\,,$ (3.23)
$\displaystyle L_{0}$ $\displaystyle=a_{-}a_{+}+\hat{h}\,,$ $\displaystyle
L_{-}$ $\displaystyle=a_{-}G(a_{-}a_{+})\,,$

where $F(a_{-}a_{+}),G(a_{-}a_{+})$ are two functions constrained by

$[L_{+},L_{-}]=2L_{0}.$ (3.24)

Acting both sides of Eq.(3.24) on the state $\Phi^{(\text{NR})}_{mn}$, we
obtain

$(n+1)F(n)G(n)-nF(n-1)G(n-1)=2(n+\hat{h}).$ (3.25)

The general solution of the difference equation for $nF(n-1)G(n-1)$ is

$nF(n-1)G(n-1)=n^{2}-n+2\hat{h}n+C\,,$ (3.26)

where $C$ is a constant. The boundary condition at $n=0$ gives $C=0$.
Therefore, in the space spanned by $\\{\Phi^{(\text{NR})}_{mn}\\}$, the two
functions satisfy

$F(a_{-}a_{+})G(a_{-}a_{+})=a_{-}a_{+}+2\hat{h}.$ (3.27)

Therefore, the generators Eq. (3.23) form an $sl(2,R)$ algebra, denoted as
$sl(2,R)_{\text{QNM}}$. So far, the construction has nothing to do with the
eikonal limit. However, we expect $L_{\pm}$ to raise and lower the overtone
numbers of $\\{\Phi^{\text{(NR)}}_{mn}\\}$, in the same way as
$sl(2,R)_{\text{ISO}}$. Comparing Eq. (3.13) with Eq. (3.18), we set

$F(x)=\hat{s}\,,\,\ G(x)=\hat{s}^{-1}(x+2\hat{h})\,.$ (3.28)

Therefore, we have the $sl(2,R)_{\text{QNM}}$ algebra generated by

$\displaystyle L_{+}=\hat{s}a_{+}\,,$ (3.29) $\displaystyle
L_{0}=a_{-}a_{+}+\hat{h}\,,$ $\displaystyle
L_{-}=\hat{s}^{-1}(a_{-}^{2}a_{+}+2\hat{h}a_{-})\,.$

Acting $L_{0}$ and $L_{-}$ to the QNMs in Eq. (3.12), we have

$\displaystyle L_{0}\Phi^{\text{(NR)}}_{mn}$
$\displaystyle=(n+\hat{h})\Phi^{\text{(NR)}}_{mn}=\mathcal{L}_{0}\Phi^{\text{(NR)}}_{mn},$
$\displaystyle L_{-}\Phi^{\text{(NR)}}_{mn}$
$\displaystyle=\hat{s}^{-1}\frac{2m\hat{\Omega}k}{\sqrt{2k\hat{\omega}_{R}}}(-\sinh{\tilde{x}})(a_{-}a_{+}+2\hat{h}-1)\Phi^{\text{(NR)}}_{mn+1}$
$\displaystyle\approx(2\hat{h}+n)\Phi^{\text{(NR)}}_{mn+1}\approx
2im\hat{\Omega}\Phi^{\text{(NR)}}_{mn+1}=\mathcal{L}_{-}\Phi^{\text{(NR)}}_{mn}.$

Hence, in our construction, the isometry and the emergent conformal symmetry
in the near-ring region are completely equivalent, when acting on the eikonal
QNMs,

$sl(2,R)_{\text{ISO}}\Phi^{\text{(NR)}}_{mn}\simeq
sl(2,R)_{\text{QNM}}\Phi^{\text{(NR)}}_{mn}\,.$ (3.30)

In conclusion, the entire solution space of near-ring QNMs can be generated by
the highest weight representation

$\Phi^{\text{(NR)}}_{mn}\approx\left(\frac{1}{2im\hat{\Omega}}\right)^{n}L^{n}_{-}\Phi^{\text{(NR)}}_{m0}\,,\quad
n=0,1,2...$ (3.31)

which satisfy

$L_{0}\Phi^{\text{(NR)}}_{mn}=(n+\hat{h})\Phi^{\text{(NR)}}_{mn}\,,\quad\quad
L_{+}\Phi^{\text{(NR)}}_{mn}\approx n\Phi^{\text{(NR)}}_{mn-1}\,.$ (3.32)

The key point in the construction is the creation of the highest-weight
representation from a single mode Eq. (3.16).

##  4 Correspondence between QNMs and PR phase space

In [32], by noticing that the $sl(2,R)_{\text{PR}}$ construction of Eq. (2.13)
is a simple deformation of $sl(2,R)_{\text{ISO}}$, the authors expect to
connect $sl(2,R)_{\text{PR}}$ to $sl(2,R)_{\text{QNM}}$. In this section, we
propose a direct connection between the phase space of the photon ring and the
coherent state space of $sl(2,R)_{\text{QNM}}$.

The space of the highest weight representation of $sl(2,R)_{\text{QNM}}$ is
spanned by $\\{\Phi^{(\text{NR})}_{mn}\\}$. For convenience, we denote
$\Phi^{(\text{NR})}_{m0}$ as $|0\rangle$ where we have suppressed the angular
quantum number. With the help of the Baker-Campbell-Hausdorff (BCH) formula, a
generic element of $SL(2,R)_{\text{QNM}}$ group can be rewritten as333This
must be true in the neighborhood of the identity operator. $e^{\theta
L_{-}}e^{AL_{0}}e^{BL_{+}}$. Such an element acting on the vacuum leads to

$|A,\theta\rangle=e^{\theta
L_{-}}e^{AL_{0}}e^{BL_{+}}|0\rangle=e^{\hat{h}A+\theta L_{-}}|0\rangle\,.$
(4.1)

Since $|m|\gg 1$, if we evaluate $L_{-}$ as $2\hat{s}^{-1}\hat{h}a_{-}$, then
$L_{+}|A,\theta\rangle\approx 2\hat{h}\theta|A,\theta\rangle$, and
$|A,\theta\rangle$ can be interpreted as the coherent states of the Heisenberg
algebra. Then, the transformation of $|A,\theta\rangle$ under the action of
$SL(2,R)_{\text{QNM}}$ is

$\displaystyle e^{\alpha L_{+}}|A,\theta\rangle$
$\displaystyle=\left|A-2\ln|1-\alpha\theta|,\frac{\theta}{1-\alpha\theta}\right\rangle,$
(4.2) $\displaystyle e^{\alpha L_{0}}|A,\theta\rangle$
$\displaystyle=\left|A+\alpha,e^{\alpha}\theta\right\rangle,$ $\displaystyle
e^{\alpha L_{-}}|A,\theta\rangle$
$\displaystyle=\left|A,\theta+\alpha\right\rangle.$

Therefore, the space spanned by the coherent states $\\{|A,\theta\rangle\\}$
also forms a representation of $SL(2,R)_{\text{QNM}}$.

On the other hand, the actions of $SL(2,R)_{\text{PR}}$ on the phase space
$(H_{+},H_{0},H_{-})$ can give a similar transformation. By defining
$A^{\prime}=-\ln{H_{-}}$, $\theta^{\prime}=H_{0}/H_{-}$, one finds that as
long as the phase space satisfies the constrain $H_{0}^{2}=H_{+}H_{-}$, the
following equations hold

$\displaystyle e^{-\alpha H_{+}}\theta^{\prime}e^{\alpha H_{+}}$
$\displaystyle=\frac{\theta^{\prime}}{1-\alpha\theta^{\prime}},$ (4.3)
$\displaystyle e^{-\alpha H_{0}}\theta^{\prime}e^{\alpha H_{0}}$
$\displaystyle=e^{\alpha}\theta^{\prime},$ $\displaystyle e^{-\alpha
H_{-}}\theta^{\prime}e^{\alpha H_{-}}$ $\displaystyle=\theta^{\prime}+\alpha,$
$\displaystyle e^{-\alpha H_{+}}A^{\prime}e^{\alpha H_{+}}$
$\displaystyle=A^{\prime}-2\ln\left(1-\alpha\theta^{\prime}\right),$
$\displaystyle e^{-\alpha H_{0}}A^{\prime}e^{\alpha H_{0}}$
$\displaystyle=A^{\prime}+\alpha,$ $\displaystyle e^{-\alpha
H_{-}}A^{\prime}e^{\alpha H_{-}}$ $\displaystyle=A^{\prime}.$

These equations describe the phase space flow under $H_{+}$, $H_{-}$ and
$H_{0}$, which is consistent with Eq. (B.7-B.9) in [32]. Comparing (4.2) with
(4.3), we find that the parameters $(A,\theta)$ and
$(A^{\prime},\theta^{\prime})$ transform exactly in the same way under
$SL(2,R)_{\text{QNM}}$ and $SL(2,R)_{\text{PR}}$, respectively, with $\alpha$
being the transformation parameter varying along the flow. Hence, it is
natural to propose that the coherent states of $SL(2,R)_{\text{QNM}}$ exactly
correspond to the points in the phase space. More precisely, a coherent state
denoted by $(A,\theta)$ and a point $\left({H_{0}},{H_{-}}\right)$ in the
phase spaces can be related by

$\displaystyle A\sim-\ln H_{-}\,,\quad\theta\sim\frac{H_{0}}{H_{-}}\,,$ (4.4)

or equivalently,

$\displaystyle H_{0}\sim\theta e^{-A}\,,\quad H_{-}\sim e^{-A}\,.$ (4.5)

Note that only positive $H_{-}$ involves in such correspondence. The
correspondence above can be concluded by a formal expression,

$\mathcal{T}|A,\theta\rangle=|T[A],T[\theta]\rangle.$ (4.6)

where $\mathcal{T}$ stands for any operator of $SL(2,R)_{\text{QNM}}$ and the
$T[\cdot]$ is the associated transformation on the parameters $(A,\theta)$
given by (4.3).

Since the correspondence between these two different systems has been built,
we can further consider what happens to a curve in the phase space. A general
curve in the phase space can be described by

$f(H_{0},H_{-})=0.$ (4.7)

We can use the correspondence to obtain a curve in the space of coherent
states

$\tilde{f}(A,\theta)=f(\theta e^{-A},e^{-A})=0.$ (4.8)

The curve defines a state as

$|\psi\rangle\equiv\int e^{-A}dA\wedge
d\theta\delta(\tilde{f}(A,\theta))|A,\theta\rangle.$ (4.9)

It can be checked that $e^{-A}dA\wedge d\theta$ is $SL(2,R)$ invariant, i.e.,

$e^{-T[A]}dT[A]\wedge dT[\theta]=e^{-A}dA\wedge d\theta.$ (4.10)

Then a curve $\tilde{f}(A,\theta)=0$ transforms to a curve described by
$\tilde{f}(T^{-1}[A],T^{-1}[\theta])=0$, which in turn defines a state as

$\displaystyle T[|\psi\rangle]\equiv$ $\displaystyle\int e^{-A}dA\wedge
d\theta\delta(\tilde{f}(T^{-1}[A],T^{-1}[\theta]))|A,\theta\rangle$ (4.11)
$\displaystyle=$ $\displaystyle\int e^{-T[A]}dT[A]\wedge
dT[\theta]\delta(\tilde{f}(A,\theta))|T[A],T[\theta]\rangle$ $\displaystyle=$
$\displaystyle\int e^{-A}dA\wedge
d\theta\delta(\tilde{f}(A,\theta))\mathcal{T}|A,\theta\rangle$
$\displaystyle=$ $\displaystyle\mathcal{T}|\psi\rangle.$

In this sense, Eq.(4.9) establish an exact correspondence between the curves
in phase space and QNMs. With the help of Eq. (4.9), we can further
investigate the corresponding state with a null geodesic.

##  5 Discussions

In this note, we discuss the realizations of the emergent conformal symmetries
near the photon ring of a warped black hole. There are three types of
conformal symmetries[32]: the isometry $sl(2,R)_{\text{ISO}}$, the emergent
one $sl(2,R)_{\text{PR}}$ in the phase space of the photon ring, and the other
emergent one $sl(2,R)_{\text{QNM}}$ in the equation of motion of scattering in
the near region. We managed to find a new construction of
$sl(2,R)_{\text{QNM}}$, which provides more transparent relations with
$sl(2,R)_{\text{ISO}}$ and $sl(2,R)_{\text{PR}}$. We showed that when acting
on the eikonal QNMs, the newly constructed $sl(2,R)_{\text{QNM}}$ is the same
as $sl(2,R)_{\text{ISO}}$, even though the two constructions are different.
Consequently the entire eikonal QNMs fall into the highest weight
representations of $sl(2,R)_{\text{QNM}}$ or equivalently of
$sl(2,R)_{\text{ISO}}$. We also showed that there is a correspondence between
the space of the coherent state of $sl(2,R)_{\text{QNM}}$ and the phase space
of photon ring.

In our study, we focus on the warped spacetime in three dimensions. As
discussed in the article[27], the near-ring QNMs have emergent conformal
symmetry in both the Schwarzschild and the Kerr black holes. The novel
construction of the $sl(2,R)_{\text{QNM}}$ is algebraic and can be applied to
the four-dimensional black hole as well.

For the Schwarzschild black holes, the null geodesics are labeled by a single
impact parameter, $\lambda=L/H$. Thus, Eq. (2.13) and Eq. (2.19) can be
generalized to Schwarzschild black holes to construct $sl(2,R)_{\text{PR}}$
algebra. These two schemes provide the same attraction flows toward the photon
bound orbit. Moreover, there exists a correspondence between the coherent
state space and the PR phase space for the Schwarzschild black hole.

However, for the Kerr black holes, two impact parameters are involved in the
photon ring, which are $\lambda=L/H$, $\eta=Q/H^{2}$ with $Q$ the Carter
constant. Hence, the construction of $sl(2,R)_{\text{PR}}$ in Kerr black holes
necessarily requires the participation of the canonical pair $(T,H)$, which
gives the right attraction flows towards the photon orbits, as shown in Fig.2
in [27]. Besides, as the PR phase space in Kerr is of six dimension, how to
establish the correspondence is an interesting question.

## Acknowledgments

The work is in part supported by NSFC Grant No. 11735001, 12275004.

## References

  * [1] A. Strominger, “Black hole entropy from near horizon microstates,” JHEP 02 (1998) 009, arXiv:hep-th/9712251.
  * [2] D. Birmingham, I. Sachs, and S. N. Solodukhin, “Conformal field theory interpretation of black hole quasinormal modes,” Phys. Rev. Lett. 88 (2002) 151301, arXiv:hep-th/0112055.
  * [3] D. Birmingham, I. Sachs, and S. N. Solodukhin, “Relaxation in conformal field theory, Hawking-Page transition, and quasinormal normal modes,” Phys. Rev. D 67 (2003) 104026, arXiv:hep-th/0212308.
  * [4] M. Guica, T. Hartman, W. Song, and A. Strominger, “The Kerr/CFT Correspondence,” Phys. Rev. D 80 (2009) 124008, arXiv:0809.4266 [hep-th].
  * [5] I. Bredberg, T. Hartman, W. Song, and A. Strominger, “Black Hole Superradiance From Kerr/CFT,” JHEP 04 (2010) 019, arXiv:0907.3477 [hep-th].
  * [6] G. Compère, “The Kerr/CFT correspondence and its extensions,” Living Rev. Rel. 15 (2012) 11, arXiv:1203.3561 [hep-th].
  * [7] K. A. Moussa, G. Clement, and C. Leygnac, “The Black holes of topologically massive gravity,” Class. Quant. Grav. 20 (2003) L277–L283, arXiv:gr-qc/0303042.
  * [8] D. Anninos, W. Li, M. Padi, W. Song, and A. Strominger, “Warped AdS(3) Black Holes,” JHEP 03 (2009) 130, arXiv:0807.3040 [hep-th].
  * [9] B. Chen and Z.-b. Xu, “Quasi-normal modes of warped black holes and warped AdS/CFT correspondence,” JHEP 11 (2009) 091, arXiv:0908.0057 [hep-th].
  * [10] B. Chen, B. Ning, and Z.-b. Xu, “Real-time correlators in warped AdS/CFT correspondence,” JHEP 02 (2010) 031, arXiv:0911.0167 [hep-th].
  * [11] B. Chen and B. Ning, “Self-Dual Warped AdS3 Black Holes,” Phys. Rev. D 82 (2010) 124027, arXiv:1005.4175 [hep-th].
  * [12] W. Song and A. Strominger, “Warped AdS3/Dipole-CFT Duality,” JHEP 05 (2012) 120, arXiv:1109.0544 [hep-th].
  * [13] J. M. Bardeen and G. T. Horowitz, “The Extreme Kerr throat geometry: A Vacuum analog of AdS(2) x S**2,” Phys. Rev. D 60 (1999) 104030, arXiv:hep-th/9905099.
  * [14] A. Castro, A. Maloney, and A. Strominger, “Hidden Conformal Symmetry of the Kerr Black Hole,” Phys. Rev. D 82 (2010) 024008, arXiv:1004.0996 [hep-th].
  * [15] B. Chen, J. Long, and J.-j. Zhang, “Hidden Conformal Symmetry of Extremal Black Holes,” Phys. Rev. D 82 (2010) 104017, arXiv:1007.4269 [hep-th].
  * [16] Event Horizon Telescope Collaboration, K. Akiyama et al., “First M87 Event Horizon Telescope Results. I. The Shadow of the Supermassive Black Hole,” Astrophys. J. Lett. 875 (2019) L1, arXiv:1906.11238 [astro-ph.GA].
  * [17] S. E. Gralla, D. E. Holz, and R. M. Wald, “Black Hole Shadows, Photon Rings, and Lensing Rings,” Phys. Rev. D 100 no. 2, (2019) 024018, arXiv:1906.00873 [astro-ph.HE].
  * [18] M. D. Johnson et al., “Universal interferometric signatures of a black hole’s photon ring,” Sci. Adv. 6 no. 12, (2020) eaaz1310, arXiv:1907.04329 [astro-ph.IM].
  * [19] S. E. Gralla and A. Lupsasca, “Observable shape of black hole photon rings,” Phys. Rev. D 102 no. 12, (2020) 124003, arXiv:2007.10336 [gr-qc].
  * [20] S. E. Gralla, A. Lupsasca, and D. P. Marrone, “The shape of the black hole photon ring: A precise test of strong-field general relativity,” Phys. Rev. D 102 no. 12, (2020) 124004, arXiv:2008.03879 [gr-qc].
  * [21] E. Himwich, M. D. Johnson, A. Lupsasca, and A. Strominger, “Universal polarimetric signatures of the black hole photon ring,” Phys. Rev. D 101 no. 8, (2020) 084020, arXiv:2001.08750 [gr-qc].
  * [22] V. Ferrari and B. Mashhoon, “New approach to the quasinormal modes of a black hole,” Phys. Rev. D 30 (1984) 295–304.
  * [23] B. Mashhoon, “Stability of charged rotating black holes in the eikonal approximation,” Phys. Rev. D 31 no. 2, (1985) 290–293.
  * [24] V. Cardoso, A. S. Miranda, E. Berti, H. Witek, and V. T. Zanchin, “Geodesic stability, Lyapunov exponents and quasinormal modes,” Phys. Rev. D 79 no. 6, (2009) 064016, arXiv:0812.1806 [hep-th].
  * [25] H. Yang, D. A. Nichols, F. Zhang, A. Zimmerman, Z. Zhang, and Y. Chen, “Quasinormal-mode spectrum of Kerr black holes and its geometric interpretation,” Phys. Rev. D 86 (2012) 104006, arXiv:1207.4253 [gr-qc].
  * [26] P.-C. Li, T.-C. Lee, M. Guo, and B. Chen, “Correspondence of eikonal quasinormal modes and unstable fundamental photon orbits for a Kerr-Newman black hole,” Phys. Rev. D 104 no. 8, (2021) 084044, arXiv:2105.14268 [gr-qc].
  * [27] S. Hadar, D. Kapec, A. Lupsasca, and A. Strominger, “Holography of the Photon Ring,” arXiv:2205.05064 [gr-qc].
  * [28] B. Raffaelli, “Hidden conformal symmetry on the black hole photon sphere,” JHEP 03 (2022) 125, arXiv:2112.12543 [gr-qc].
  * [29] B. Chen and J. Long, “Hidden Conformal Symmetry and Quasi-normal Modes,” Phys. Rev. D 82 (2010) 126013, arXiv:1009.1010 [hep-th].
  * [30] B. Chen, J.-j. Zhang, and J.-d. Zhang, “Quasi-normal Modes and Hidden Conformal Symmetry of Warped dS3 Black Hole,” Phys. Rev. D 84 (2011) 124039, arXiv:1110.3991 [hep-th].
  * [31] B. Chen and J.-j. Zhang, “Quasi-normal Modes of Extremal Black Holes from Hidden Conformal Symmetry,” Phys. Lett. B 699 (2011) 204–210, arXiv:1012.2219 [hep-th].
  * [32] D. Kapec, A. Lupsasca, and A. Strominger, “Photon Rings Around Warped Black Holes,” arXiv:2211.01674 [gr-qc].
  * [33] B. F. Schutz and C. M. Will, “BLACK HOLE NORMAL MODES: A SEMIANALYTIC APPROACH,” Astrophys. J. Lett. 291 (1985) L33–L36.


###### Abstract

Dimension reduction is a technique used to transform data from a high-
dimensional space into a lower-dimensional space, aiming to retain as much of
the original information as possible. This approach is crucial in many
disciplines like engineering, biology, astronomy, and economics. In this
paper, we consider the following dimensionality reduction instance: Given an
$n$-dimensional probability distribution $p$ and an integer $m<n$, we aim to
find the $m$-dimensional probability distribution $q$ that is the closest to
$p$, using the Kullback–Leibler divergence as the measure of closeness. We
prove that the problem is strongly NP-hard, and we present an approximation
algorithm for it.

###### keywords:

dimension reduction; NP-completeness; approximation; bin packing;
Kullback–Leibler divergence

Hardness and Approximability of Dimension Reduction on the Probability Simplex
Roberto Bruno Roberto Bruno

##  1 Introduction

Dimension reduction B ; SVM14  is a methodology for mapping data from a high-
dimensional space to a lower-dimensional space, while approximately preserving
the original information content. This process is essential in fields such as
engineering, biology, astronomy, and economics, where large datasets with
high-dimensional points are common.

It is often the case that the computational complexity of the algorithms
employed to extract relevant information from these datasets depends on the
dimension of the space where the points lie. Therefore, it is important to
find a representation of the data in a lower-dimensional space that still
(approximately) preserves the information content of the original data, as per
given criteria.

A special case of the general issue illustrated before arises when the
elements of the dataset are $n$-dimensional probability distributions, and the
problem is to approximate them by lower-dimensional ones. This question has
been extensively studied in different contexts. In AKMV15 ; Ca+ , the authors
address the problem of dimensionality reduction on sets of probability
distributions with the aim of preserving specific properties, such as pairwise
distances. In Go , Gokhale considers the problem of finding the distribution
that minimizes, subject to a set of linear constraints on the probabilities,
the “discrimination information” with respect to a given probability
distribution. Similarly, in GT , Globerson et al. address the dimensionality
reduction problem by introducing a nonlinear method aimed at minimizing the
loss of mutual information from the original data. In Le , Lewis explores
dimensionality reduction for reducing storage requirements and proposes an
approximation method based on the maximum entropy criterion. Likewise, in ad ,
Adler et al. apply dimensionality reduction to storage applications, focusing
on the efficient representation of large-alphabet probability distributions.
More closely related to the dimensionality reduction that we deal with in this
paper are the works COHEN ; CLW ; V12 ; cicalese_short_vectors . In COHEN ;
CLW , the authors address task scheduling problems where the objective is to
allocate tasks of a project in a way that maximizes the likelihood of
completing the project by the deadline. They formalize the problem in terms of
random variables approximation by using the Kolmogorov distance as a measure
of distance and present an optimal algorithm for the problem. In contrast, in
V12 , Vidyasagar defines a metric distance between probability distributions
on two distinct finite sets of possibly different cardinalities based on the
Minimum Entropy Coupling (MEC) problem. Informally, in the MEC, given two
probability distributions $p$ and $q$, one seeks to find a joint distribution
$\phi$ that has $p$ and $q$ as marginal distributions and also has minimum
entropy. Unfortunately, computing the MEC is NP-hard, as shown in
KOVACEVIC2015369 . However, numerous works in the literature present efficient
algorithms for computing couplings with entropy within a constant number of
bits from the optimal value cicalese2019minimum ; compton2022tighter ;
compton2023minimum ; li2021efficient ; sokota2024computing . We note that
computing the coupling of a pair of distributions can be seen as essentially
the inverse of dimension reduction. Specifically, given two distributions $p$
and $q$, one constructs a third, larger distribution $\phi$, such that $p$ and
$q$ are derived from $\phi$ or, more formally, aggregations of $\phi$. In
contrast, the dimension reduction problem addressed in this paper involves
starting with a distribution $p$ and creating another, smaller distribution
that is derived from $p$ or, more formally, is an aggregation of $p$.

Moreover, in V12 , the author demonstrates that, according to the defined
metric, any optimal reduced-order approximation must be an aggregation of the
original distribution. Consequently, the author provides an approximation
algorithm based on the total variation distance, using an approach similar to
the one we will employ in Section 4. Similarly, in cicalese_short_vectors ,
Cicalese et al. examine dimensionality reduction using the same distance
metric introduced in V12 . They propose a general criterion for approximating
$p$ with a shorter vector $q$, based on concepts from Majorization theory, and
provide an approximation approach to solve the problem.

We also mention that analogous problems arise in scenario reduction Ru , where
the problem is to (best) approximate a given discrete distribution with
another distribution with fewer atoms in compressing probability distributions
Ga  and elsewhere CLW2 ; PU ; PP . Moreover, we recommend the following survey
for further application examples Me .

In this paper, we study the following instantiation of the general problem
described before: Given an $n$-dimensional probability distribution
$p=(p_{1},\ldots,p_{n})$, and $m<n$, find the $m$-dimensional probability
distribution $q=(q_{1},\ldots,q_{m})$ that is the closest to $p$, where the
measure of closeness is the well-known relative entropy KL  (also known as
Kullback–Leibler divergence). In Section 2, we formally state the problem. In
Section 3, we prove that the problem is strongly NP-hard, and in Section 4, we
provide an approximation algorithm returning a solution whose distance from
$p$ is at most 1 plus the minimum possible distance.

##  2 Statement of the Problem and Mathematical Preliminaries

Let

$\mathcal{P}_{n}=\\{p=(p_{1},\dots,p_{n})\mid p_{1}\geq\dots\geq
p_{n}>0,\sum_{i=1}^{n}p_{i}=1\\}$ (1)

be the $(n-1)$-dimensional probability simplex. Given two probability
distributions $p\in\mathcal{P}_{n}$ and $q\in\mathcal{P}_{m}$, with $m<n$, we
say that $q$ is an aggregation of $p$ if each component of $q$ can be
expressed as the sum of distinct components of $p$. More formally, $q$ is an
aggregation of $p$ if there exists a _partition_
$\Pi=(\Pi_{1},\ldots,\Pi_{m})$ of $\\{1,\ldots,n\\}$ such that
$q_{i}=\sum_{j\in\Pi_{i}}p_{j}$, for each $i=1,\ldots,m$. Notice that the
aggregation operation corresponds to the following operation on random
variables: Given a random variable $X$ that takes value in a finite set
$\mathcal{X}=\\{x_{1},\ldots,x_{n}\\}$, such that $\Pr\\{X=x_{i}\\}=p_{i}$ for
$i=1,\ldots,n$, any function $f:\mathcal{X}\mapsto\mathcal{Y}$, with
$\mathcal{Y}=\\{y_{1},\dots,y_{m}\\}$ and $m<n$, induces a random variable
$f(X)$ whose probability distribution $q=(q_{1},\ldots,q_{m})$ is an
aggregation of $p$. Dimension reduction in random variables through the
application of deterministic functions is a common technique in the area
(e.g., La ; V12 ; COHEN ). Additionally, the problem arises also in the area
of “hard clustering” KMN  where one seeks a deterministic mapping $f$ from
data, generated by an r.v. $X$ taking values in a set $\mathcal{X}$, to
“labels” in some set $\mathcal{Y}$, where typically
$|\mathcal{Y}|\ll|\mathcal{X}|$.

For any probability distribution $p\in\mathcal{P}_{n}$ and an integer $m<n$,
let us denote by $\mathcal{A}_{m}(p)$ the set of all $q\in\mathcal{P}_{m}$
that are aggregations of $p$. Our goal is to solve the following optimization
problem:

Given $p\in\mathcal{P}_{n}$ and $m<n$, find $q^{*}\in\mathcal{A}_{m}(p)$ such
that

$\min_{q\in\mathcal{A}_{m}(p)}D(q\|p)=D(q^{*}\|p),$ (2)

where $D(q\|p)$ is the relative entropy KL , given by

$D(q\|p)=\sum_{i=1}^{m}q_{i}\log{\frac{q_{i}}{p_{i}}},$

and the logarithm is of base $2$.

An additional motivation to study Problem 2 comes from the fundamental paper
Shore , in which the principle of minimum relative entropy (called therein
minimum cross entropy principle) is derived in an axiomatic manner. The
principle states that, of the distributions $q$ that satisfy given constraints
(in our case, that $q\in\mathcal{A}_{m}(p)$), one should choose the one with
the least relative entropy “distance” from the prior $p$.

Before establishing the computational complexity of the Problem 2, we present
a simple lower bound on the optimal value.

For each $p\in\mathcal{P}_{n}$ and $q\in\mathcal{P}_{m}$, $m<n$, it holds that

$D(q\|p)\geq D(lb(p)\|p)=-\log\left(\sum_{i=1}^{m}p_{i}\right).$ (3)

where

$lb(p)=\left(\frac{p_{1}}{\sum_{i=1}^{m}p_{i}},\dots,\frac{p_{m}}{\sum_{i=1}^{m}p_{i}}\right)\in\mathcal{P}_{m}.$
(4)

###### Proof.

Given an arbitrary $p\in\mathcal{P}_{n}$, one can see that

$D(lb(p)\|p)=-\log\left(\sum_{i=1}^{m}p_{i}\right).$

Moreover, for any $p\in\mathcal{P}_{n}$ and $q\in\mathcal{P}_{m}$, the Jensen
inequality applied to the $\log$ function gives the following:

$-D(q||p)=\sum_{i=1}^{m}q_{i}\log\frac{p_{i}}{q_{i}}\leq\log\left(\sum_{i=1}^{m}p_{i}\right).$

∎

##  3 Hardness

In this section, we prove that the optimization problem (2) described in
Section 1 is strongly NP-hard. We accomplish this by reducing the problem from
the 3-Partition problem, a well-known strongly NP-hard problem Gar , described
as follows.

3-Partition: Given a multiset $S=\\{a_{1},\dots,a_{n}\\}$ of $n=3m$ positive
integers for which $\sum_{i=1}^{n}a_{i}=mT$, for some $T$, the problem is to
decide whether $S$ can be partitioned into $m$ triplets such that the sum of
each triple is exactly $T$. More formally, the problem is to decide whether
there exist $S_{1},\dots,S_{m}\subseteq S$ such that the following conditions
hold:

$\displaystyle\sum_{a\in S_{j}}a$ $\displaystyle=T,\quad\forall
j\in\\{1,\dots,m\\},$ $\displaystyle S_{i}\cap S_{j}$
$\displaystyle=\emptyset,\quad\forall i\neq j,$
$\displaystyle\bigcup_{i=1}^{m}S_{i}$ $\displaystyle=S,$
$\displaystyle|S_{i}|$ $\displaystyle=3,\quad\forall i\in\\{1,\dots,m\\}.$

The 3-Partition problem can be reduced in polynomial time to the problem of
finding the aggregation $q^{*}\in\mathcal{P}_{m}$ of some
$p\in\mathcal{P}_{n}$, for which

$D(q^{*}\|p)=\min_{q\in\mathcal{A}_{m}(p)}D(q\|p).$

###### Proof.

The idea behind the following reduction can be summarized as follows: given an
instance of 3-Partition, we transform it into a probability distribution $p$
such that the lower bound $lb(p)$ is an aggregation of $p$ if and only if the
original instance of 3-Partition admits a solution. Let an arbitrary instance
of 3-Partition be given, that is, let $S$ be a multiset
$\\{a_{1},\dots,a_{n}\\}$ of $n=3m$ positive integers with
$\sum_{i=1}^{n}a_{i}=mT$. Without loss of generality, we assume that the
integers $a_{i}$ are ordered in a non-increasing fashion. We construct a valid
instance $p$ of our Problem 2 as follows. We set $p\in\mathcal{P}_{n+m}$ as
follows:

$p=\left(\underbrace{\frac{1}{m+1},\dots,\frac{1}{m+1}}_{m\mbox{ \footnotesize
times}},\frac{a_{1}+2T}{(m+1)7mT},\dots,\frac{a_{n}+2T}{(m+1)7mT}\right).$ (5)

Note that $p$ is a probability distribution. In fact, since $n=3m$, we have

$\sum_{i=1}^{n}\frac{a_{i}+2T}{(m+1)7mT}=\frac{1}{(m+1)7mT}\left(\sum_{i=1}^{n}(a_{i}+2T)\right)=\frac{7mT}{(m+1)7mT}=\frac{1}{m+1}.$

Moreover, from (4) and (5), the probability distribution
$lb(p)\in\mathcal{P}_{m}$ associated to $p$ is as follows:

$lb(p)=\left(\frac{p_{1}}{\sum_{j=1}^{m}p_{j}},\dots,\frac{p_{m}}{\sum_{j=1}^{m}p_{j}}\right)=\left(\frac{1}{m},\dots,\frac{1}{m}\right).$
(6)

To prove the theorem, we show that the starting instance of 3-Partition is a
Yes instance if and only if it holds that

$\min_{q\in\mathcal{A}_{m}(p)}D(q\|p)=\log\frac{m+1}{m},$ (7)

where $p$ is given in (5).

We begin by assuming the given instance of 3-Partition is a Yes instance, that
is, there is a partition of $S$ into triplets $S_{1},\dots,S_{m}$ such that

$\sum_{a_{i}\in S_{j}}a_{i}=T,\quad\forall j\in\\{1,\dots,m\\},$ (8)

and we show that $\min_{q\in\mathcal{A}_{m}(p)}D(q\|p)=\log\frac{m+1}{m}$. By
Lemma 2, (5), and equality (6), we have

$\min_{q\in\mathcal{A}_{m}(p)}D(q\|p)\geq
D(lb(p)\|p)=\sum_{i=1}^{m}\frac{1}{m}\log\frac{1/m}{1/(m+1)}=\log\frac{m+1}{m}.$
(9)

From (8), we have

$\displaystyle\sum_{a_{i}\in S_{j}}\frac{a_{i}+2T}{(m+1)7mT}$
$\displaystyle=\frac{T}{(m+1)7mT}+\sum_{a_{i}\in S_{j}}\frac{2T}{(m+1)7mT}$
$\displaystyle=\frac{T}{(m+1)7mT}+\frac{6T}{(m+1)7mT}$
$\displaystyle=\frac{1}{(m+1)m},\qquad\forall j\in\\{1,\dots,m\\}.$ (10)

Let us define $q^{\prime}\in\mathcal{P}_{m}$ as follows:

$q^{\prime}=\left(\frac{1}{m+1}+\sum_{a_{i}\in
S_{1}}\frac{a_{i}+2T}{(m+1)7mT},\dots,\frac{1}{m+1}+\sum_{a_{i}\in
S_{m}}\frac{a_{i}+2T}{(m+1)7mT}\right),$ (11)

where, by (10),

$\sum_{a_{i}\in S_{j}}\frac{a_{i}+2T}{(m+1)7mT}=\frac{1}{(m+1)m},\quad\forall
j\in\\{1,\dots,m\\}.$ (12)

From (12) and from the fact that $S_{1},\ldots,S_{m}$ are a partition of
$\\{a_{1},\ldots,a_{n}\\}$, we obtain $q^{\prime}\in\mathcal{A}_{m}(p)$, that
is, $q^{\prime}$ is a valid aggregation of $p$ (cfr., (5)). Moreover,

$q^{\prime}=\left(\frac{1}{m},\dots,\frac{1}{m}\right),$

and $D(q^{\prime}\|p)=\log\frac{m+1}{m}$. Therefore, by (9) and that
$q^{\prime}\in\mathcal{A}_{m}(p)$, we obtain

$\min_{q\in\mathcal{A}_{m}(p)}D(q\|p)=\log\frac{m+1}{m},$

as required.

To prove the opposite implication, we assume that $p$ (as given in (5)) is a
Yes instance, that is,

$\min_{q\in\mathcal{A}_{m}(p)}D(q\|p)=\log\frac{m+1}{m}.$ (13)

We show that the original instance of 3-Partition is also a Yes instance, that
is, there is a partition of $S$ into triplets $S_{1},\dots,S_{m}$ such that

$\sum_{a_{i}\in S_{j}}a_{i}=T,\quad\forall j\in\\{1,\dots,m\\}.$ (14)

Let $q^{*}$ be the element in $\mathcal{A}_{m}(p)$ that achieves the minimum
in (13). Consequently, we have

$\displaystyle\log\frac{m+1}{m}$
$\displaystyle=D(q^{*}\|p)=\sum_{i=1}^{m}q^{*}_{i}\log\frac{q^{*}_{i}}{p_{i}}=\sum_{i=1}^{m}q^{*}_{i}\log\frac{1}{p_{i}}-H(q^{*})$
$\displaystyle=\log(m+1)-H(q^{*})\qquad(\mbox{from (\ref{defp}))},$ (15)

where $H(q^{*})=-\sum_{i=1}^{m}q^{*}_{i}\log q^{*}_{i}$ is the Shannon entropy
of $q^{*}$. From (15), we obtain that $H(q^{*})=\log m$; hence,
$q^{*}=(1/m,\ldots,1/m)$ (see Cov , Thm. 2.6.4). Recalling that
$q^{*}\in\mathcal{A}_{m}(p)$, we obtain that the uniform distribution

$\left(\frac{1}{m},\dots,\frac{1}{m}\right)$ (16)

is an aggregation of $p$. We note that the first $m$ components of $p$, as
defined in (5), cannot be aggregated among them to obtain (16), because
$2/(m+1)>1/m$, for $m>2$. Therefore, in order to obtain (16) as an aggregation
of $p$, there must exist a partition $S_{1},\dots,S_{m}$ of
$S=\\{a_{1},\ldots,a_{n}\\}$ for which

$\frac{1}{m+1}+\sum_{a_{i}\in
S_{j}}\frac{a_{i}+2T}{(m+1)7mT}=\frac{1}{m},\quad\forall j\in\\{1,\dots,m\\}.$
(17)

From (17), we obtain

$\sum_{a_{i}\in S_{j}}\frac{a_{i}+2T}{(m+1)7mT}=\frac{1}{m(m+1)},\quad\forall
j\in\\{1,\dots,m\\}.$ (18)

From this, it follows that

$2T|S_{j}|+\sum_{a_{i}\in S_{j}}a_{i}=7T,\quad\forall j\in\\{1,\dots,m\\}.$
(19)

We note that, for (19) to be true, there cannot exist any $S_{j}$ for which
$|S_{j}|\neq 3$. Indeed, if there were a subset $S_{j}$ for which $|S_{j}|\neq
3$, there would be at least a subset $S_{k}$ for which $|S_{k}|>3$. Thus, for
such an $S_{k}$, we would have

$2T|S_{k}|+\sum_{a_{i}\in S_{k}}a_{i}\geq 8T+\sum_{a_{i}\in S_{k}}a_{i}>7T,$

contradicting (19). Therefore, it holds that

$|S_{j}|=3,\quad\forall j\in\\{1,\dots,m\\}.$ (20)

Moreover, from (19) and (20), we obtain

$\sum_{a_{i}\in S_{j}}a_{i}=7T-2T|S_{j}|=T,\quad\forall j\in\\{1,\dots,m\\}.$
(21)

Thus, from (21), it follows that the subsets $S_{1},\ldots,S_{m}$ give a
partition of $S$ into triplets, such that

$\sum_{a_{i}\in S_{j}}a_{i}=T,\quad\forall j\in\\{1,\dots,m\\}.$

Therefore, the starting instance of 3-Partition is a Yes instance. ∎

##  4 Approximation

Given $p\in\mathcal{P}_{n}$ and $m<n$, let $OPT$ denote the optimal value of
the optimization problem (2), that is

$OPT=\min_{q\in\mathcal{A}_{m}(p)}D(q\|p).$ (22)

In this section, we design a greedy algorithm to compute an aggregation
$\overline{q}\in\mathcal{A}_{m}(p)$ of $p$ such that

$D(\overline{q}\|p)<OPT+1.$ (23)

The idea behind our algorithm is to see the problem of computing an
aggregation $q\in\mathcal{A}_{m}(p)$ as a bin packing problem with
“overstuffing” (see DOP  and references therein quoted), which is a bin
packing where overfilling of bins is possible. In the classical bin packing
problem, one is given a set of items, with their associated weights, and a set
of bins with their associated capacities (usually, equal for all bins). The
objective is to place all the items in the bins, trying to minimize a given
cost function.

In our case, we have $n$ items (corresponding to the components of $p$) with
weights $p_{1},\dots,p_{n}$, respectively, and $m$ bins, corresponding to the
components of $lb(p)$ (as defined in (4)) with capacities
$lb(p)_{1},\dots,lb(p)_{m}$. Our objective is to place all the $n$ components
of $p$ into the $m$ bins without exceeding the capacity $lb(p)_{j}$ of each
bin $j$, $j=1,\ldots,m$, by more than $(\sum_{i=1}^{m}p_{i})lb(p)_{j}$. For
such a purpose, the idea behind Algorithm 1 is quite straightforward. It
behaves like a classical First-Fit bin packing: to place the $i^{th}$ item, it
chooses the first bin $j$ in which the item can be inserted without exceeding
its capacity by more than $(\sum_{i=1}^{m}p_{i})lb(p)_{j}$. In the following,
we will show that such a bin always exists and that fulfilling this objective
is sufficient to ensure the approximation guarantee (23) we are seeking.

1\. Compute
$lb(p)=(p_{1}/\sum_{j=1}^{m}p_{j},\dots,p_{m}/\sum_{j=1}^{m}p_{j})$;

2\. Let $lb_{j}^{i}$ be the content of bin $j$ after the first $i$ components
of $p$ have been placed ($lb_{j}^{0}=0$ for each $j\in\\{1,\dots,m\\}$);

3\. For $i=0,\dots,n-1$

Let $j$ be the smallest bin index for which holds that

$lb_{j}^{i}+p_{i+1}<(1+\sum_{j=1}^{m}p_{j})lb(p)_{j}$, place $p_{i+1}$ into
the $j$-th bin:

$lb_{j}^{i+1}=lb_{j}^{i}+p_{i+1},$

$lb_{k}^{i+1}=lb_{k}^{i}$, for each $k\neq j$;

4\. Output $\overline{q}=(lb_{1}^{n},\ldots,lb_{m}^{n})$.

Algorithm 1 GreedyApprox

The step 3 of GreedyApprox operates as in the classical First-Fit bin packing
algorithm. Therefore, it can be implemented to run in $O(n\log m)$ time, as
discussed in hochba1997 . In fact, each iteration of the loop in step 3 can be
implemented in $O(\log m)$-time by using a balanced binary search tree with
height $O(\log m)$ that has a leaf for each bin and in which each node keeps
track of the largest remaining capacity of all the bins in its subtree.

GreedyApprox computes a valid aggregation $\overline{q}\in\mathcal{A}_{m}(p)$
of $p\in\mathcal{P}_{n}$. Moreover, it holds that

$D(\overline{q}\|lb(p))<\log\left(1+\sum_{j=1}^{m}p_{j}\right).$ (24)

###### Proof.

We first prove that each component $p_{i}$ of $p$ is placed in some bin. This
implies that $\overline{q}\in\mathcal{A}_{m}(p)$.

For each step $i=0,\dots,m-1$, there is always a bin in which the algorithm
places $p_{i+1}$. In fact, the capacity $lb(p)_{j}$ of bin $j$ satisfies the
relation:

$lb(p)_{j}=\frac{p_{j}}{\sum_{\ell=1}^{m}p_{\ell}}>p_{j},\quad\forall
j\in\\{1,\dots,m\\}.$

Let us consider an arbitrary step $m\leq i<n$, in which the algorithm has
placed the first $i$ components of $p$ and needs to place $p_{i+1}$ into some
bin. We show that, in this case also, there is always a bin $j$ in which the
algorithm places the item $p_{i+1}$, without exceeding the capacity
$lb(p)_{j}$ of the bin $j$ by more than
$(\sum_{\ell=1}^{m}p_{\ell})lb(p)_{j}$.

First, notice that in each step $i$, $m\leq i<n$, there is at least a bin $k$
whose content $lb_{k}^{i}$ does not exceed its capacity $lb(p)_{k}$; that is,
for which $lb_{k}^{i}<lb(p)_{k}$ holds. Were this the opposite, for all bins
$j$, we would have $lb_{j}^{i}\geq lb(p)_{j}$; then, we would also have

$\sum_{j=1}^{m}lb_{j}^{i}\geq\sum_{j=1}^{m}lb(p)_{j}=1.$ (25)

However, this is not possible since we have placed only the first $i<n$
components of $p$, and therefore, it holds that

$\sum_{j=1}^{m}lb_{j}^{i}=\sum_{j=1}^{i}p_{j}<\sum_{j=1}^{n}p_{j}=1,$

contradicting (25). Consequently, let $k$ be the smallest integer for which
the content of the $k$-th bin does not exceed its capacity, i.e., for which
$lb_{k}^{i}<lb(p)_{k}$. For such a bin $k$, we obtain

$\displaystyle\left(1+\sum_{j=1}^{m}p_{j}\right)lb(p)_{k}$
$\displaystyle=lb(p)_{k}+\left(\sum_{j=1}^{m}p_{j}\right)lb(p)_{k}$
$\displaystyle=lb(p)_{k}+\left(\sum_{j=1}^{m}p_{j}\right)\frac{p_{k}}{\sum_{j=1}^{m}p_{j}}$
$\displaystyle=lb(p)_{k}+p_{k}$ $\displaystyle>lb_{k}^{i}+p_{k}\hskip
28.45274pt\mbox{(since $lb(p)_{k}>lb_{k}^{i}$)}$ $\displaystyle\geq
lb_{k}^{i}+p_{i+1}\hskip 28.45274pt\mbox{(since $p_{k}\geq p_{i+1}$)}.$ (26)

Thus, from (4), one derives that the algorithm places $p_{i+1}$ into the bin
$k$ without exceeding its capacity $lb(p)_{k}$ by more than
$(\sum_{j=1}^{m}p_{j})lb(p)_{k}$.

The reasoning applies to each $i<n$, thus proving that GreedyApprox correctly
assigns each component $p_{i}$ of $p$ to a bin, effectively computing an
aggregation of $p$. Moreover, from the instructions of step 3 of GreedyApprox,
the output is an aggregation
$\overline{q}=(\overline{q}_{1},\ldots,\overline{q}_{m})\in\mathcal{A}_{m}(p)$,
for which the following crucial relation holds:

$\overline{q}_{i}<\left(1+\sum_{j=1}^{m}p_{j}\right)lb(p)_{i},\quad\forall
i\in\\{1,\dots,m\\}.$ (27)

Let us now prove that
$D(\overline{q}\|lb(p))<\log\left(1+\sum_{j=1}^{m}p_{j}\right)$. We have

$\displaystyle D(\overline{q}\|lb(p))$
$\displaystyle=\sum_{i=1}^{m}\overline{q}_{i}\log\frac{\overline{q}_{i}}{lb(p)_{i}}$
$\displaystyle<\sum_{i=1}^{m}\overline{q}_{i}\log\frac{(1+\sum_{j=1}^{m}p_{j})lb(p)_{i}}{lb(p)_{i}}\hskip
28.45274pt\mbox{(from (\ref{eq:invariante}))}$
$\displaystyle=\log\left(1+\sum_{j=1}^{m}p_{j}\right).$

∎

We need the following technical lemma to show the approximation guarantee of
GreedyApprox. Let $q\in\mathcal{P}_{m}$ and $p\in\mathcal{P}_{n}$ be two
arbitrary probability distributions with $m<n$. It holds that

$D(q\|p)=D(q\|lb(p))+D(lb(p)\|p),$ (28)

where
$lb(p)=(lb(p)_{1},\ldots,lb(b)_{m})=(p_{1}/\sum_{i=1}^{m}p_{i},\dots,p_{m}/\sum_{i=1}^{m}p_{i})$.

###### Proof.

$\displaystyle D(q\|p)$
$\displaystyle=\sum_{i=1}^{m}q_{i}\,\log\frac{q_{i}}{p_{i}}=\sum_{i=1}^{m}q_{i}\,\log\frac{q_{i}}{p_{i}\,\frac{\sum_{j=1}^{m}p_{j}}{\sum_{j=1}^{m}p_{j}}}$
$\displaystyle=\sum_{i=1}^{m}q_{i}\,\log\frac{q_{i}}{\frac{p_{i}}{\sum_{j=1}^{m}p_{j}}}+\sum_{i=1}^{m}q_{i}\,\log\frac{1}{\sum_{j=1}^{m}p_{j}}$
$\displaystyle=\sum_{i=1}^{m}q_{i}\,\log\frac{q_{i}}{lb(p)_{i}}+\sum_{i=1}^{m}q_{i}\,\log\frac{1}{\sum_{j=1}^{m}p_{j}}\hskip
28.45274pt\mbox{(since $lb(p)_{i}=p_{i}/\sum_{j=1}^{m}p_{j}$)}$
$\displaystyle=D(q\|lb(p))+\log\frac{1}{\sum_{j=1}^{m}p_{j}}=D(q\|lb(p))+D(lb(p)\|p).$

∎

The following theorem is the main result of this section. For any
$p\in\mathcal{P}_{n}$ and $m<n$, GreedyApprox produces an aggregation
$\overline{q}\in\mathcal{A}_{m}(p)$ of $p$ such that

$D(\overline{q}\|p)<OPT+1,$ (29)

where $OPT=\min_{q\in\mathcal{A}_{m}(p)}D(q\|p).$

###### Proof.

From Lemma 1, we have

$D(\overline{q}\|p)=D(\overline{q}\|lb(p))+D(lb(p)\|p),$ (30)

and from Theorem 4, we know that the produced aggregation $\overline{q}$ of
$p$ satisfies the relation

$D(\overline{q}\|lb(p))<\log\left(1+\sum_{j=1}^{m}p_{j}\right).$ (31)

Putting it all together, we obtain:

$\displaystyle D(\overline{q}\|p)$
$\displaystyle=D(\overline{q}\|lb(p))+D(lb(p)\|p)$
$\displaystyle<\log\left(1+\sum_{j=1}^{m}p_{j}\right)+D(lb(p)\|p)\hskip
28.45274pt\mbox{(from (\ref{eq:theorem_result}))}$
$\displaystyle=\log\left(1+\sum_{j=1}^{m}p_{j}\right)-\log\left(\sum_{j=1}^{m}p_{j}\right)$
$\displaystyle<-\log\left(\sum_{j=1}^{m}p_{j}\right)+1\hskip
28.45274pt\mbox{(since $1+\sum_{j=1}^{m}p_{j}<2$)}$ $\displaystyle\leq
OPT+1\hskip 93.89418pt\mbox{(from Lemma \ref{lemma-lb}).}$

∎

##  5 Concluding Remarks

In this paper, we examined the problem of approximating $n$-dimensional
probability distributions with $m$-dimensional ones using the Kullback–Leibler
divergence as the measure of closeness. We demonstrated that this problem is
strongly NP-hard and introduced an approximation algorithm for solving the
problem with guaranteed performance.

Moreover, we conclude by pointing out that the analysis of GreedyApprox
presented in Theorem 4 is tight. Let $p\in\mathcal{P}_{3}$ be

$p=\left(\frac{1}{2}-\epsilon,\frac{1}{2}-\epsilon,2\epsilon\right),$

where $\epsilon>0$. The application of GreedyApprox on $p$ produces the
aggregation $\overline{q}\in\mathcal{P}_{2}$ given by

$\overline{q}=(1-2\epsilon,2\epsilon),$

whereas one can see that the optimal aggregation $q^{*}\in\mathcal{P}_{2}$ is
equal to

$q^{*}=\left(\frac{1}{2}+\epsilon,\frac{1}{2}-\epsilon\right).$

Hence, for $\epsilon\to 0$, we have

$D(\overline{q}\|p)=(1-2\epsilon)\log\frac{1-2\epsilon}{\frac{1}{2}-\epsilon}+2\epsilon\log\frac{2\epsilon}{\frac{1}{2}-\epsilon}\to
1,$

while

$OPT=D(q^{*}\|p)=\left(\frac{1}{2}+\epsilon\right)\log\frac{\frac{1}{2}+\epsilon}{\frac{1}{2}-\epsilon}+\left(\frac{1}{2}-\epsilon\right)\log\frac{\frac{1}{2}-\epsilon}{\frac{1}{2}-\epsilon}\to
0.$

Therefore, to improve our approximation guarantee, one should use a bin
packing heuristic different from the First-Fit as employed in GreedyApprox.
Another interesting open problem is to provide an approximation algorithm with
a (small) multiplicative approximation guarantee. However, both problems
mentioned above would probably require a different approach, and we leave that
to future investigations.

Another interesting line of research would be to extend our findings to
different divergence measures (e.g., Sason  and references quoted therein).

References

## References

  * (1) Burges, C.J. Dimension reduction: A guided tour. _Found. Trends Mach. Learn._ 2010, _2_ , 275–365.
  * (2) Sorzano, C.O.S.; Vargas, J.; Montano, A.P. A survey of dimensionality reduction techniques. _arXiv_ 2014, arXiv:1403.2877.
  * (3) Abdullah, A.; Kumar,R.;McGregor, A.; Vassilvitskii, S.; Venkatasubramanian, S. Sketching, Embedding, and Dimensionality Reduction for Information Spaces. _Artif. Intell. Stat. PMLR_ 2016, _51_ , 948–956.
  * (4) Carter, K.M.; Raich, R.; Finn, W.G.; Hero, A.O., III. Information-geometric dimensionality reduction. _IEEE Signal Process. Mag._ 2011, _28_ , 89–99.
  * (5) Gokhale, D.V. Approximating discrete distributions, with applications. _J. Am. Stat. Assoc._ 1973, _68_ , 1009–1012.
  * (6) Globerson, A.; Tishby, N. Sufficient dimensionality reduction. _J. Mach. Learn. Res._ 2003, _3_ , 1307–1331.
  * (7) Lewis, P.M., II. Approximating probability distributions to reduce storage requirements. _Inf. Control._ 1959, _2_ , 214–225.
  * (8) Adler, A.; Tang, J.; Polyanskiy, Y. Efficient representation of large-alphabet probability distributions. _IEEE Sel. Areas Inf. Theory_ 2022, _3_ , 651–663.
  * (9) Cicalese, F.; Gargano, L; Vaccaro, U. Approximating probability distributions with short vectors, via information theoretic distance measures. In Proceedings of the IEEE International Symposium on Information Theory (ISIT), Barcelona, Spain, 10–15 July 2016; pp. 1138–1142.
  * (10) Cohen, L.; Grinshpoun, T.; Weiss, G. Efficient optimal Kolmogorov approximation of random variables. Artif. Intell. 2024, _329_ , 104086.
  * (11) Cohen, L.; Weiss, G. Efficient optimal approximation of discrete random variables for estimation of probabilities of missing deadlines. _Proc. Aaai Conf. Artif. Intell._ 2019, _33_ , 7809–7815.
  * (12) Vidyasagar, M. A metric between probability distributions on finite sets of different cardinalities and applications to order reduction. _IEEE Trans. Autom. Control._ 2012, _57_ , 2464–2477.
  * (13) Kovačević, M.; Stanojević, I; Šenk, V. On the entropy of couplings. Inf. Comput. 2015, _242_ , 369–382.
  * (14) Cicalese, F.; Gargano, L.; Vaccaro, U. Minimum-entropy couplings and their applications. IEEE Trans. Inf. Theory 2019, _65_ , 3436–3451.
  * (15) Compton, S. A tighter approximation guarantee for greedy minimum entropy coupling. In Proceedings of the IEEE International Symposium on Information Theory (ISIT), Espoo, Finland, 26 June–1 July 2022; pp. 168–173.
  * (16) Compton, S.; Katz, D.; Qi, B.; Greenewald, K.; Kocaoglu, M. Minimum-entropy coupling approximation guarantees beyond the majorization barrier. Int. Conf. Artif. Intell. Stat. 2023, _206_ , 10445–10469.
  * (17) Li, C. Efficient approximate minimum entropy coupling of multiple probability distributions. IEEE Trans. Inf. Theory 2021, _67_ , 5259–5268.
  * (18) Sokota, S.; Sam, D.; Witt, C.; Compton, S.; Foerster, J.; Kolter, J. Computing Low-Entropy Couplings for Large-Support Distributions. _arXiv_ 2024, arXiv:2405.19540.
  * (19) Rujeerapaiboon, N.; Schindler, K.; Kuhn, D.; Wiesemann, W. Scenario reduction revisited: fundamental limits and guarantees. _Math. Program._ 2018, _191_ , 207–242.
  * (20) Gagie, T. Compressing probability distributions. _Inf. Process. Lett._ 2006, _97_ , 133–137.
  * (21) Cohen, L.; Fried, D.; Weiss, G. An optimal approximation of discrete random variables with respect to the Kolmogorov distance. _arXiv_ 2018, arXiv:1805.07535.
  * (22) Pavlikov, K.; Uryasev, S. CVaR distance between univariate probability distributions and approximation problems. _Ann. Oper. Res._ 2018, _262_ , 67–88.
  * (23) Pflug, G.C.; Pichler, A. Approximations for probability distributions and stochastic optimization problems. In _Stochastic Optimization Methods in Finance and Energy: New Financial Products and Energy Market Strategies_ ; Springer: Berlin/Heidelberg, Germany, 2011; pp. 343–387.
  * (24) Melucci, M. A brief survey on probability distribution approximation. _Comput. Sci. Rev._ 2019, _33_ , 91–97.
  * (25) Kullback, S.; Leibler, R.A. On information and sufficiency. _Ann. Math. Stat._ 1951, _22_ , 79–86.
  * (26) Lamarche-Perrin, R.; Demazeau, Y.; Vincent, J.M. The best-partitions problem: How to build meaningful aggregations. In Proceedings of the IEEE/WIC/ACM International Joint Conferences on Web Intelligence (WI) and Intelligent Agent Technologies (IAT), Atlanta, GA, USA, 17–20 November 2013; pp. 399–404.
  * (27) Kearns, M.; Mansour, Y.; Ng, A.Y. An information-theoretic analysis of hard and soft assignment methods for clustering. In _Learning in Graphical Models_ ; Springer: Dordrecht, The Netherlands, 1998; pp. 495–520.
  * (28) Shore, J.; Johnson, R. Axiomatic derivation of the principle of maximum entropy and the principle of minimum cross-entropy. IEEE Trans. Inf. Theory 1980, _26_ , 26–37.
  * (29) Garey, M.; Johnson, D. Strong NP-Completeness results: motivation, examples, and implications. J. ACM 1978, _25_ , 499–508.
  * (30) Cover, T.M.; Thomas, J.A. _Elements of Information Theory_ , 2nd ed.; Wiley-Interscience: Hoboken, NJ, USA, 2006.
  * (31) Dell’Olmo, P.; Kellerer, H.; Speranza, M.; Tuza, Z. A 13/12 approximation algorithm for bin packing with extendable bins. Inf. Process. Lett. 1998, _65_ , 229–233.
  * (32) Coffman, E.G.; Garey, M.R.; Johnson, D.S. Approximation Algorithms for Bin Packing: A Survey. In _Approximation Algorithms for NP-Hard Problems_ ; Hochbaum, D., Ed.; PWS Publishing Co.: Worcester, UK, 1996; pp. 46–93.
  * (33) Sason, I. Divergence Measures: Mathematical Foundations and Applications in Information-Theoretic and Statistical Problems. _Entropy_ 2022, _24_ , 712.