Concept

Interpolating function 𝑓 can be define as linear combination of basis functions

𝑓(𝑡)=𝑛𝑗=1𝑥𝑗𝜙𝑗(𝑡)

Fourier basis

comprising sines and coses. For example a set of basis functions with 𝑛=2𝑘 in [0,2𝜋]:

[𝜙1(𝑡)𝜙2(𝑡)𝜙𝑛(𝑡)] [cos(0)cos(1𝑡)cos(𝑘𝑡)sin(𝑡)cos(2𝑡)cos((𝑘1)𝑡)]

Monomial basis (bad)

𝜙𝑗(𝑡)=𝑡𝑗1

specifically for this one, we need to use Vandermonde matrix to solve. It require 𝑂(𝑛3) to solve. Considering the bad performance and unstable, we should use other instead.

Newton Basis

𝜙𝑗(𝑥)=𝑗1𝑖=0(𝑥𝑥𝑖)