title: Identifying local minima in a histogram
body: <p>I'm interested in finding the local minima in a histogram that roughly resembles</p>
  
  <p><img src="https://i.stack.imgur.com/tzxu6.png" alt="enter image description here"></p>
  
  <p>I'd want to find the local minimum at 109.258, and the easiest way to do so would be to identify whether the number of counts at 109.258 is lower than the average number of counts around in some interval around (and including 109.258). It's identifying this interval that's the most difficult part for me.</p>
  
  <p>As for the source of this data, it's a histogram with 100 bins of non-uniform width. Each bin has a value (shown on the x-axis), and a count of the samples falling into that bin (shown on the y-axis). What I'm trying to do is find the "best" place to split the histogram. Each side of the split is propagated down a binary tree, as part of a classification algorithm.</p>
  
  <p>I'm thinking that my best course of action would be to try to fit a curve to this histogram, using something like the <a href="http://en.wikipedia.org/wiki/Levenberg%E2%80%93Marquardt_algorithm" rel="noreferrer">Levenberg-Marquardt algorithm</a> and then to compare the local minima to find the "best" one. A proper measure of "best" would include some indication of the significance of that split, which is measured as the difference between the average counts in the interval to the left and the average of the counts in the interval to the right, and then maybe weight each difference with the number of counts included to get a composite measurement of "best," if that makes sense.</p>
  
  <p>Either way, computational complexity of the algorithm isn't a huge issue, 100 bins is about the maximum number I'd expect to encounter. However, this calculation will be performed once for each sample, so keeping it linear with respect to the number of bins would, of course, be ideal.</p>
  
  <p>By the way, I'm doing everything in C++, and make use of the boost libraries and STL, so nothing is off-limits in that regard.</p>
  
  <p>Any thoughts or insights concerning best practices would be greatly appreciated!</p>