# Hardness and Approximability of Dimension Reduction on the Probability Simplex
## 1 Introduction  
_Dimension reduction_[1, 2] 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 [3, 4], 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 [5], [PERSON] 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 [6], [PERSON] 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 [7], [PERSON] explores dimensionality reduction for reducing storage requirements and proposes an approximation method based on the maximum entropy criterion. Likewise, in [8], [PERSON] 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 [9, 10, 11, 12]. In [10, 11], 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 [12], [PERSON] 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 [13]. However, numerous works in the literature present efficient algorithms for computing couplings with entropy within a constant number of bits from the optimal value [14; 15; 16; 17; 18]. 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 [12], 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 [9], [PERSON] et al.