I have been working on an optimization problem related to the following function:

$$ y = f(x) = c_{1}(1-e^{-c_{2}(x-x_{0})})^{2}$$

where $c_{1}$, $c_{2}$ and $x_{0}$ are constants. Assume that we have an interval $[x_{a}, x_{b}]$ and then we uniformly sample a number $n$ of points $x_{k}$ from this interval and calculate the corresponding value of $f(x_{k})$ and then we sum over these values, i.e. $\Sigma = \sum_{k=1}^{n}{f(x_{k})}$. We then repeat this sampling process $M$ times. This leaves us with the following system of equations:

\begin{cases} \Sigma_{1} & = \sum_{k=1}^{n}{f(x_{1,k})} & = f(x_{1,1}) + f(x_{1,2}) + \dots f(x_{1,n}) \\ \Sigma_{2} & = \sum_{k=1}^{n}{f(x_{2,k})} & = f(x_{2,1}) + f(x_{2,2}) + \dots f(x_{2,n}) \\ & & \vdots \\ \Sigma_{M} & = \sum_{k=1}^{n}{f(x_{M,k})} & = f(x_{M,1}) + f(x_{M,2}) + \dots f(x_{M, n})\\ \end{cases}

Now, assume that we do not know what $f(x)$ actually looks like and that we want to recreate the function. To do so, we need to solve this system of equations using linear algebra. We can not do this using a continous $f(x)$ so we will have to discretize our interval into $N$ bins with a binwidth of $h$, such that:

\begin{cases} f_{1} & \text{if } x \in [x_a, & x_a+h) \\ f_{2} & \text{if } x \in [x_a+h, & x_a+2h) \\ & \vdots \\ f_{N} & \text{if } x \in [x_a+(N-1)h, & x_b) \\ \end{cases}

If we treat this as a vector $\vec{f} = [f_{1}, f_{2}, \dots, f_{N}]^{T}$ of size ($N$-by-1) and bin all $x_{i,k}$ to their column corresponding to $f_j$ in a matrix $C$ of size ($M$-by-$N$) then we can rewrite our system of equation as:


where $\vec{\Sigma}=[\Sigma_{1}, \Sigma_{2}, \dots, \Sigma_{M}]^{T}$ of size ($M$-by-$1$). Then we use e.g. SVD to approximate $C^{-1}$ to solve for $\vec{f}=C^{-1}\vec{\Sigma}$ to get an idea of what the true $f(x)$ might look like.


I want to know how to bin the interval $[x_{a}, x_{b}]$ and I want to do so by minimizing the error of approximating $f(x)$ using $\vec{f}$. In my real application RAM is a limiting factor (I have several different $f(x)$ I want to estimate at once, making $C^{-1}$ expensive to compute) so I want to have a fixed number of bins. So, given an $N$ number of bins, how do I select the width of each individual bin so that I minimize the error between $f(x)$ and $\vec{f}$? In reality, $x$ is actually Poisson-distributed (and not uniform) and $x$ and $f(x)$ can be very different in orders of magnitude.

What I've tried:

  • Equidistant binning w.r.t. $x$ (best result so far)
  • Equidistant binning w.r.t. $f(x)$
  • Equidistant binning w.r.t. $ln(1+f(x))$
  • Equidistant binning w.r.t. length of curve
  • Binning where the count in each bin is the same for all bins

It does not make sense to me that equidistant binning w.r.t. $x$ (i.e. $h_{1}=h_{2}=\dots=h_{N}$) provides the best results, especially when the $\Delta f(x)$ is so different between the left and the right half of the bin. But when the resolution at the position where the $|f'(x)|$ gets higher then the error around the minimum of $f(x)$ gets significantly higher instead.

How do I select my $H = \{h_{1}, h_{2}, \dots, h_{N}\}$ for all bins and a fixed number of bins $N$?


Here is an example of what $f(x)$ and equidistant binning w.r.t. $x$ and some arbitrary values for $c_{1}$, $c_{2}$ and $x_{0}$ look like. please note that there is no approximation here, just the exact values.

enter image description here



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.