# An Autocorrelation Term Method for Curve Fitting

Authors: Louis M. Houston
Journal: ISRN Applied Mathematics
 (2013)

---

## Abstract

The least-squares method is the most popular method for fitting a polynomial curve to data. It is based on minimizing the total squared error between a polynomial model and the data. In this paper we develop a different approach that exploits the autocorrelation function. In particular, we use the nonzero lag autocorrelation terms to produce a system of quadratic equations that can be solved together with a linear equation derived from summing the data. There is a maximum of2M solutions when the polynomial is of degree M. For the linear case, there are generally two solutions. Each solution is consistent with a total error of zero. Either visual examination or measurement of the total squared error is required to determine which solution fits the data. A comparison between the comparable autocorrelation term solution and linear least squares shows negligible difference.


---

## Body

## 1. Introduction

Curve fitting is the process of fitting a curve, in this case a polynomial, to a set of data points. There are different types of curve fitting, but we will discuss only the most popular method, the method of least squares [1].It is assumed that the data consists of fluctuations about an ideal curve. These fluctuations create an error between the polynomial model and the actual data. After computing a total squared error, we can apply calculus to minimize the squared error with respect to the coefficients of the polynomial. This produces a set of  linear equations called the normal equations. The coefficients are derived from solving the normal equations [2].A different approach to the problem is as follows.We propose that the data we are considering consists of a deterministic component and a random component with zero mean. The random component does not correlate with the deterministic component and it does not correlate with itself at nonzero lag. We want to extract only the portion of the data that is correlative at nonzero lag. This requires the computation of nonzero lag autocorrelation terms and produces a system of quadratic equations [3]. After substitution based on a linear equation derived from summing the data, the system of quadratic equations consists of M equations with M unknowns, where M is the degree of the polynomial. This results in a maximum of 2M solutions. Each solution is consistent with a total error between the polynomial and the data that is equal to zero. Either visual examination or measurement of the total squared error is required to determine which solution fits the data.In this paper, we derive the autocorrelation term method and compare it to linear least squares.


## 2. The Autocorrelation Term Method

Consider a set of data(xi,yi)(i=1,2,3,…,N). Characterize the y data as the sum of a polynomial function y(xi) and a discrete, zero-mean random variable [4] Zi:(1)Zi:Ω→ℝ,yi=y(xi)+Zi.
Consequently, we can write
(2)yi+myi=(y(xi+m)+Zi+m)(y(xi)+Zi),=y(xi+m)y(xi)+Zi+my(xi)+Ziy(xi+m)+Zi+mZi,m∈{1,2,…}.
Let N≫m.Summation yields(3)∑i=1N-myi+myi=∑i=1N-my(xi+m)y(xi)
since the cross-correlation [5] and autocorrelation terms with Zi must be zero. The polynomial function of degree M can be written as
(4)y(xi)=a0+a1xi+a2xi2+⋯+aMxiM=∑j=0Majxij.
Therefore, (3) becomes the system of equations:
(5)∑i=1N-myi+myi=∑i=1N-m(∑j=0Majxi+mj)(∑j=0Majxij),m=1,2,…,M.
Using (1), we can write the average
(6)〈yi〉=〈y(xi)+Zi〉=〈y(xi)〉+〈Zi〉.
We know that 〈Zi〉=0, so
(7)〈yi〉=〈y(xi)〉
which implies
(8)∑yi=∑y(xi)
or
(9)∑i=1Nyi=∑i=1N∑j=0Majxij.
There are a maximum of 2M solutions to the system of equations created by (5) and (9) for the coefficients {a0,a1,…,aM}. Observe that the total error, E, is presumed to be zero:
(10)E=∑i=1N(∑j=0Majxij-yi)=0.


## 3. The Least-Squares Straight Line

Before examining the autocorrelation method, it is worth becoming familiar with the special case of fitting a straight line in the least-squares sense. We fit(11)y(x)=a0+a1x
to a set of data (xi,yi)(i=1,2,3,…,N). We have two parameters a0 and a1 and want to minimize the function of two variables (a0 and a1):
(12)F(a0,a1)=∑i=1N[y(xi)-yi]2.
This becomes
(13)F(a0,a1)=∑i=1N[a0+a1xi-yi]2.
Apply the calculus method
(14)∂F(a0,a1)∂a0=2∑(a0+a1xi-yi)=0,∂F(a0,a1)∂a1=2∑(a0+a1xi-yi)xi=0.
Dropping factor 2 and rewriting, we get
(15)a0N+a1∑xi=∑yi,a0∑xi+a1∑xi2=∑xiyi.
Solving these equations for a0 and a1 yields
(16)a0=1N∑yi-1N∑xi(∑xiyi-(1/N)∑yi∑xi∑xi2-((∑xi)2/N)),a1=∑xiyi-(1/N)∑yi∑xi∑xi2-((∑xi)2/N).


## 4. The Autocorrelation Term Method forM=1

ForM=1, system (5) becomes
(17)∑i=1N-1yi+1yi=∑i=1N-1(a0+a1xi+1)(a0+a1xi)=(N-1)a02+(∑i=1N-1(xi+1+xi))a0a1+(∑i=1N-1xi+1xi)a12.
Suppressing the summation limits, we can write
(18)∑yi+1yi=(N-1)a02+(∑(xi+1+xi))a0a1+(∑xi+1xi)a12.
Equation (9) becomes
(19)∑yi=Na0+a1∑xi.
Solving (19) for a0 yields
(20)a0=1N(∑yi-a1∑xi).
Squaring yields
(21)a02=1N2((∑yi)2-2a1∑yi∑xi+a12(∑xi)2).
Now substitute (20) and (21) into (18) and organize the terms:
(22)[(N-1)N2(∑xi)2+(∑xi+1xi)-1N∑(xi+1+xi)(∑xi)]a12+[1N∑(xi+1+xi)(∑yi)-2(N-1)N2∑yi∑xi]×a1+(N-1)N2(∑yi)2-∑yi+1yi=0.
This is in the form of a quadratic equation that we can write as
(23)Aa12+Ba1+C=0,
where, with reference to (22), A is the precursor of a12, B is the precursor of a1, and C is the residual expression.The solutions are the roots(24)a1=-B±B2-4AC2A.a0 is found using (20).


## 5. The Autocorrelation Term Method for Higher Values ofM

The autocorrelation term method for curve fitting with anMth degree polynomial requires the solution of one linear equation and M quadratic equations with M+1 variables which reduces to M quadratic equations with M variables. This can produce 2M solutions [6]. For example, consider the M=2 case. System (5) can be written as
(25)∑yi+1yi=∑(a0+a1xi+1+a2xi+12)(a0+a1xi+a2xi2),∑yi+2yi=∑(a0+a1xi+2+a2xi+22)(a0+a1xi+a2xi2).
Equation (9) can be written as
(26)∑yi=∑(a0+a1xi+a2xi2).
From (26) we can write
(27)a0=1N∑yi-a1N∑xi-a2N∑xi2.
Substitute (27) into (25):
(28)∑yi+1yi=∑(1N∑yi+(xi+1-1N∑xi)a1+(xi+12-1N∑xi2)a2)*(1N∑yi+(xi-1N∑xi)a1+(xi2-1N∑xi2)a2),∑yi+2yi=∑(1N∑yi+(xi+2-1N∑xi)a1+(xi+22-1N∑xi2)a2)*(1N∑yi+(xi-1N∑xi)a1+(xi2-1N∑xi2)a2).
Equations (28) are two quadratic equations in a1 and a2. This can produce four solutions. In general, these types of systems can be solved on a Grobner basis using Buchberger’s algorithm [7].


## 6. A Comparison of the Autocorrelation Term Method to Linear Least Squares

We have constructed synthetic data consisting of the sum of a line and a random variable. The line has an intercept of fifteen and a slope of five. The random variable is Gaussian with a zero mean. The amplitude of the random variable is twenty. There are a total of one hundred equally spaced data points. Figure1 shows the data, the least squares fit, and the autocorrelation term fit for a1=(-B+B2-4AC)/2A. Figure 2 shows the data, the least squares fit, and the autocorrelation term fit for a1=(-B-B2-4AC)/2A. In this example, we find that the quadratic roots are negatives of one another. This occurs because xi=i-1 which implies that B=0. This follows from (22) which for B=0 implies
(29)∑(xi+1+xi)=2(N-1)N∑xi.
This becomes
(30)∑(2i-1)=2(N-1)N∑(i-1)
which reduces to
(31)∑i=1N-1(2i-1)=(N-1)2.Figure 1
An overlay of the data, the least-squares fit, and the autocorrelation term fit fora1=(-B+B2-4AC)/2A.Figure 2
An overlay of the data, the least-squares fit, and the autocorrelation term fit fora1=(-B-B2-4AC)/2A.


## 7. Conclusions

We have derived a method for computing polynomial curve fits to data based on terms from the autocorrelation function. The method producesM quadratic equations with M variables for a polynomial of degree M. The solutions of this system maximally produce 2M curves. Each solution is consistent with a total error between the polynomial and the data that is equal to zero. The proper curve can be selected with either visual examination or measurement of the total squared error. We tested this method with a linear curve fit and compared it to linear least squares. There is negligible difference between the comparable solutions.



---

*Source: 346230-2013-07-24.xml*