LINEAR OPTIMIZATION

In last section, we have described how to estimate the relative time-shift through the non-linear optimization. Although our method has several nice properties, yet it also has a defect: the accuracy of the estimation is limited to the time-sampling interval. This is because data is available only at the integer multiples of the sampling interval. One way to solve the problem is to interpolate data along time axis before the algorithm is applied to it. However, in addition to the cost of interpolation, the computational cost of the non-linear optimization algorithm increases much faster than does the accuracy of the estimation. For example, let k be the ratio of the new sampling interval to the original sampling interval, the computational cost will increases by a factor of k² while the accuracy increases only by a factor of k. Another way is to interpolate the computed objective function. But the solutions obtained by using this method will depend on the choice of interpolation algorithms.

In this section, we will describe an elegant algorithm that does not require heavy computation, and yet has the potential to find the exact solution.