1
$\begingroup$

I am trying to approximate a large discreet probability distribution function using a histogram with a small number of entries. I.e., create a piece-wise first-order polynomial approximation for a monotonic function using a minimal number of segments/pieces.

I dont have an extensive background in statistics but I suspect this is a very common problem that was studied/solved already. It must be the most straight-forward and intutitive way to approximate a non-linear function. I am looking for any pointers related to this..


A (more) formal definition of the problem:

  • Input:

    Assume an array is given that contains a finite number of entries y_i. Let PDF = {y_1, ..., y_n} denote this array. Also assume that the number of entries in the array, n = |PDF|, is finite and known. The PDF has the following properties:

     - y_1 >= y_2 >= ... >= y_n 
    
     - y_i \in (0, 1]
    
     - \sum{y_i} = 1
    

    Esentially, this PDF array represents a discreet probability distribution function where the items are already sorted according to their frequency/probability and numbered between 1 ... n. Therefore, PDF represents a monotonically decreasing discreet function.

  • Output:

    Let uniq(PDF) be the number of distinct y_i values in the PDF. Obviously uniq(PDF) <= n. The goal is to find another array PDF' with the same PDF-like properties that approximates the original PDF:

     - y'_1 >= y'_2 >= ... >= y'_n
    
     - y'_i \in (0, 1]
    
     - \sum{y'_i} = 1 and,
    
     - minimal ord(PDF') such that the normalized square error between PDF/PDF' is bounded. 
     This is equivalent to \sum{(y_i-y'_i)^2}/\sum{y_i^2} < given_error_bound.
    

    In other words, all of this means that I want to represent the orginal PDF in the most compact way possible given a certain required level of accuracy.

    For example, the original PDF can have billions of distinct y_i probability entries. I want a new PDF' that has only a few distinct y'_i entries (i.e. in the order of 10) that accurately represents the original PDF and can be expressed as (count, y'_i) pairs.

** Alternative formulations:**

  • Continous PDF equivalent:

    Assume a continous monotonically decreasing function f:[0,1] -> [0, 1] with \int{f(i)} = 1. Find function f':[0,1] -> [0,1] defined by n points (x_1, y_1), ... , (x_n, y_n), x_i < x_i+1, y_i < y_i+1, such that f'(k) = f(x_n), where x_n = max(x_i, x_i <= k) (essentially the original function f is represented by a multi-step function f').

Variations of the problem:

  • The PDF can be replaced with a continous function if this makes the problem easier.

  • The PDF can be replaced with its corresponding CDF (the sum/integral of the PDF), either in the discreet or continous variations. The goal will be now to find a new CDF' that uses n points to interpolate the original CDF.

  • Simplify the problem by assuming that the number of points for the PDF' approximation is fixed/given. How to find the location of these points (i.e., how to distribute these points) such that the total error is minimized?

$\endgroup$
  • $\begingroup$ A histogram isn't piecewise first order, it's a step function (zeroth order). Are you conflating frequency polygon with histogram? $\endgroup$ – Glen_b Sep 29 '14 at 17:23
  • $\begingroup$ I think I did not express myself well enough.. You are right that a PDF/histogram is piecewise zeroth order. However, if you take items/multiple bins together that is not longer the case. $\endgroup$ – Radu Sep 29 '14 at 17:33
  • $\begingroup$ What do you mean by "take multiple bins together"? Unless you're doing something further to the data (such as joining the bin centers, making it something other than a histogram), it's still a histogram and so still zeroth order. If you join the centers of the horizontal pieces with line segments ... you have a frequency polygon, not a histogram. Can you clearly describe what you intend? $\endgroup$ – Glen_b Sep 29 '14 at 17:46
  • 1
    $\begingroup$ Sorry for the premature reply. I am still getting used to the website... My full response: You are right that a PDF/histogram is piecewise zeroth order so my words are inaccurate. I was thinking that the CDF' for the PDF' approximation is composed of multiple straight lines, which translates into a first-order approximation (I am thinking in CDF terms about the problem although is easier to express it in PDF terms). As a side note, a first order interpolation histogram (this might be a frequency polygon as you say) is a more complex form / more general form of this problem. $\endgroup$ – Radu Sep 29 '14 at 17:49
  • 2
    $\begingroup$ To sum it up: (1) I was thinking about the CDF where a zeroth order PDF approximation translates into a first order CDF approximation. (2) Solving the problem for any order (zero, first, etc.) is just as good (for me at least). $\endgroup$ – Radu Sep 29 '14 at 17:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.