{
  "id": "1701.02119",
  "version": "v1",
  "published": "2017-01-09T10:11:02.000Z",
  "updated": "2017-01-09T10:11:02.000Z",
  "title": "Greedy-Merge Degrading has Optimal Power-Law",
  "authors": [
    "Assaf Kartowsky",
    "Ido Tal"
  ],
  "comment": "5 pages, submitted to ISIT 2017",
  "categories": [
    "cs.IT",
    "math.IT"
  ],
  "abstract": "Consider a channel with a given input distribution. Our aim is to degrade it to a channel with at most L output letters. One such degradation method is the so called \"greedy-merge\" algorithm. We derive an upper bound on the reduction in mutual information between input and output. For fixed input alphabet size and variable L, the upper bound is within a constant factor of an algorithm-independent lower bound. Thus, we establish that greedy-merge is optimal in the power-law sense.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2017-01-09T10:11:02.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "optimal power-law",
      "greedy-merge degrading",
      "upper bound",
      "algorithm-independent lower bound",
      "mutual information"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 5,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}