EllZeroTrendFiltering

This package solves the problem of piecewise linear, continuous, approximation subject to either a hard limit or a regularization penalty on the number of break points. An exact solution is obtained using dynamic program over piecewise quadratic function, which avoids the combinatorial complexity of a naive approach.

Mathematical Description

We want to find a piecewise linear, continuous function with few segments, where I is the set of breakpoints, and Y are the values of the function at those breakpoints. This problem can be formulated as a constrained problem

where M is the number of segments, or as a regulartized problem

These problems can be solved for a discrete set of points g using

I, Y, v = fit_pwl_constrained(g, M)
I, Y, v = fit_pwl_regularized(g, ζ)

where the resulting function satisfies f(I[k]) = Y[k], or for a general function g: ℝ ⟶ ℝ with

I, Y, v = fit_pwl_constrained(g, t, M)
I, Y, v = fit_pwl_regularized(g, t, ζ)

where t is the set of possible breakpoints and the resulting function satisfies f(t[I[k]]) = Y[k].

Example: Constrained approximation

Find best continouous piecewise approximations with up to M segments

using EllZeroTrendFiltering, Plots
#Get sample data
N = 400
data = snp500_data()[1:N]

#Find solutions to the constrained problem, with up to M=10 segments
M = 10
Ivec, Yvec, fvec = fit_pwl_constrained(data, M)

#Plot original data
plot(data, l=:black, lab = "SNP500")
#Plot solution with 5 segments
plot!(Ivec[5], Yvec[5], l=2, m=:circle, lab="m=5, cost = $(round(fvec[5],digits=3))")
#Plot solution with 10 segments
plot!(Ivec[M], Yvec[M], l=2, m=:circle, lab="m=$M, cost = $(round(fvec[M],digits=3))")

Example: Regularization

Find best continouous piecewise approximations with cost ζ per breakpoint.

using EllZeroTrendFiltering, Plots

g(x) = sin(x) + 0.5sin(3.5x) + 0.5sin(5.1x)
t = range(0, stop=2π, length=201)

plot(g, t, l=(2,:black), lab="sin(x) + 0.5sin(3.5x) + 0.5sin(5.1x)")
for ζ ∈ [0.1, 0.002]
    # Minimize ∫(f(x)-g(x))²dx + ζ⋅||d²f/dx²||₀
    # Will automatically integrate the function to compute the costs
    I, Y, cost = fit_pwl_regularized(g, t, ζ)

    plot!(t[I], Y, l=2, m=:circle, lab = "l2-norm=$(round(cost,digits=3)), zeta=$ζ")
end
plot!() # Show plot