{
  "id": "1404.1425",
  "version": "v4",
  "published": "2014-04-05T03:43:28.000Z",
  "updated": "2018-03-11T05:16:22.000Z",
  "title": "Density Estimation via Discrepancy Based Adaptive Sequential Partition",
  "authors": [
    "Dangna Li",
    "Kun Yang",
    "Wing Hung Wong"
  ],
  "comment": "Binary Partition, Star Discrepancy, Density Estimation, Mode Seeking, Level Set Tree",
  "categories": [
    "stat.ML"
  ],
  "abstract": "Given $iid$ observations from an unknown absolute continuous distribution defined on some domain $\\Omega$, we propose a nonparametric method to learn a piecewise constant function to approximate the underlying probability density function. Our density estimate is a piecewise constant function defined on a binary partition of $\\Omega$. The key ingredient of the algorithm is to use discrepancy, a concept originates from Quasi Monte Carlo analysis, to control the partition process. The resulting algorithm is simple, efficient, and has a provable convergence rate. We empirically demonstrate its efficiency as a density estimation method. We present its applications on a wide range of tasks, including finding good initializations for k-means.",
  "revisions": [
    {
      "version": "v3",
      "updated": "2014-04-23T05:20:54.000Z",
      "title": "Density Estimation via Adaptive Partition and Discrepancy Control",
      "abstract": "Given iid samples from some unknown continuous density on hyper-rectangle $[0, 1]^d$, we attempt to learn a piecewise constant function that approximates this underlying density nonparametrically. Our density estimate is defined on a binary split of $[0, 1]^d$ and built up sequentially according to discrepancy criteria; the key ingredient is to control the discrepancy adaptively in each sub-rectangle to achieve overall bound. We prove that the estimate, even though simple as it appears, preserves most of the estimation power. By exploiting its structure, it can be directly applied to some important pattern recognition tasks such as mode seeking and density landscape exploration, we demonstrate its applicability through simulations and examples.",
      "journal": null,
      "doi": null,
      "authors": [
        "Kun Yang",
        "Wing Hung Wong"
      ]
    },
    {
      "version": "v4",
      "updated": "2018-03-11T05:16:22.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "density estimation",
      "discrepancy control",
      "adaptive partition",
      "achieve overall bound",
      "important pattern recognition tasks"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2014arXiv1404.1425Y"
    }
  }
}