14,148,895 members
See more:
Consider the graph in this image: Graph.PNG (42.7 KB)

It's a data series whose values (y axis) generally increase over time (x axis) but with quite prominent local maxima and minima along the way. Think of it as a stock price graph on a bad hair day.

At some point the dips down to the local minima aren't as pronounced and the entire graph tilts up. If you draw a line connecting the bottoms of each dip you see a clear point where the graph suddenly goes steeper.

Is there an algorithm that can identify that point reliably?

What I have tried:

1. Smoothing out the data by taking a rolling average and calculating the second derivative. When that hits a threshold we have the point. This seems a bit hit and miss

2. Finding the local minima, constructing a graph from those points, and then doing the second derivative thing.

3. Constructing two trend lines starting from either end of the graph. When the slope of the trend line strays outside a small threshold just continue the line forward and backward using the current slope. Where these two lines cross is the point I want.

I'm guessing this is a solved problem but haven't been able to find anything yet.
Posted
Updated 2-Mar-18 18:00pm
Patrice T 3-Mar-18 0:14am

Shouldn't you cross post in Algorithm discussion ?

## Solution 1

I'd approach it as a constrained optimisation. Take two (intersecting) straight lines. Anchor one at the start point (probably mean of the first "few" points, or an arbitrary stab of the pen), the other similarly at the end. Allow the two slopes to vary (maybe with an extra constraint of (0 < left slope < right slope) and minimise the least squares difference from your raw data. I don't know what package I'd throw it at; maybe something in the Maple class.

Refining the thought bubble somewhat...
Let the intersection point wander round the "lower triangle". (Makes it easier to decide which line to fit a point to); either Monte Carlo it or do a more focused optimisation. Or even do a brute force grid search. I'm guessing the computational effort is in the femto-bitcoin realm.

Cheers,
Peter
v2
Chris Maunder 3-Mar-18 11:30am

Interesting. Taking the combined least squares difference of the two lines, one anchored from the start, one at the end, and both terminating at their intersection would certainly give a workable solution. Seems a little brute force, but I'll give it a try.
Peter_in_2780 3-Mar-18 16:50pm

While I appreciate mathematical elegance as much as anyone, my engineering mindset takes over when there is a specific problem to be attacked.

Top Experts
Last 24hrsThis month
 OriginalGriff 170 Richard MacCutchan 130 phil.o 105 lmoelleb 50 Gerry Schmitz 44
 OriginalGriff 4,286 Richard MacCutchan 1,845 Patrice T 1,292 phil.o 1,048 Gerry Schmitz 992