On multiplicative \(\lambda\)-approximations and some geometric applications (Q2848204)

Consider a finite set \(X\), a measure \(\mu\) on \(\mathcal{P}(X)\) and a family~\(\mathcal{F}\); can one determine/approximate \(\mu\) by a measure~\(\mu^*\) that is supported on a small subset of~\(X\)? The authors prove that, given \(\epsilon\) between \(0\) and~\(1\), one can achieve \((1-\epsilon)\mu(F)\leq\mu^*(F)\leq(1+\epsilon)\mu(F)\) for all \(F\in\mathcal F\) with \(\mu^*\) supported on a set of size \(O(\text{trk}(\mathcal{F})\cdot\log|\mathcal{F}|/\epsilon^2)\), where \(\text{trk}(\mathcal{F})\)~denotes the maximum length of a sequence \(\langle F_i\rangle_i\) in~\(\mathcal F\) with the property that \(F_i\not\subseteq\bigcup_{j<i}F_j\) for all~\(i\). This is applied to problems with a sampling flavour, such as reducing the number of coordinates needed to describe a set in \(\mathbb{R}^n\) with the \(\ell_1\)-metric and estimating the average volume of a set of simplexes from a small sample.