Back to Search
Start Over
Greedy Algorithms for Optimal Distribution Approximation
- Source :
- Entropy 2016, 18(7), 262
- Publication Year :
- 2016
-
Abstract
- The approximation of a discrete probability distribution $\mathbf{t}$ by an $M$-type distribution $\mathbf{p}$ is considered. The approximation error is measured by the informational divergence $\mathbb{D}(\mathbf{t}\Vert\mathbf{p})$, which is an appropriate measure, e.g., in the context of data compression. Properties of the optimal approximation are derived and bounds on the approximation error are presented, which are asymptotically tight. It is shown that $M$-type approximations that minimize either $\mathbb{D}(\mathbf{t}\Vert\mathbf{p})$, or $\mathbb{D}(\mathbf{p}\Vert\mathbf{t})$, or the variational distance $\Vert\mathbf{p}-\mathbf{t}\Vert_1$ can all be found by using specific instances of the same general greedy algorithm.<br />Comment: 5 pages
- Subjects :
- Computer Science - Information Theory
Subjects
Details
- Database :
- arXiv
- Journal :
- Entropy 2016, 18(7), 262
- Publication Type :
- Report
- Accession number :
- edsarx.1601.06039
- Document Type :
- Working Paper
- Full Text :
- https://doi.org/10.3390/e18070262