# Hardness and Approximability of Dimension Reduction on the Probability Simplex
## 2 Statement of the Problem and Mathematical Preliminaries  
Let  
\[\mathcal{P}_{n}=\{p=(p_{1},\ldots,p_{n})\mid p_{1}\geq\cdots\geq p_{n}>0,\sum_ {i=1}^{n}p_{i}=1\} \tag{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_{j}}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},\ldots,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., [10; 12; 26]). Additionally, the problem arises also in the area of \"hard clustering\" [27] 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:  
**Problem 1**.: _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), \tag{2}\]  
_where \(D(q\|p)\) is the relative entropy [25], 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 1 comes from the fundamental paper [28], 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 1, we present a simple lower bound on the optimal value.  
**Lemma 1**.: _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). \tag{3}\]  
_where_  
\[lb(p)=\left(\frac{p_{1}}{\sum_{i=1}^{m}p_{i}},\cdots,\frac{p_{m}}{\sum_{i=1}^ {m}p_{i}}\right)\in\mathcal{P}_{m}. \tag{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).\]