In many practical situations, there is a need of calculating intermediate values by given data values, so that both the given and the original values are defined by a certain function unknown to us. It is assumed that the unknown function is meeting a certain criteria, such as being continuously differentiable. Normally, such problems are solved by approximation of the assumed function using other functions meeting the desired criteria. In many cases, however, the functions are needed only to produce the resulting set of values. In and of themselves, they would have no further use afterwards. That fact is at the base of the proposed algorithmic approach. Instead of searching for approximating functions, the assumed function would be approximated by a set of values calculated iteratively. When enough values have been calculated to achieve the desired resulting set, the process can be terminated. In terms of signal processing, the proposed algorithm is, in fact, an algorithm of resampling which produces smoothed approximated values. As such, I name it SRALG (Smoothing-Resampling Algorithm). It has been tested and proved effective in a number of real computational problems, especially when the initial data error is known in advance and can be used to calculate the coefficient of smoothing (see the deviation calculation below). Algorithm (single iteration):
It is easily seen that the iterations of the algorithm above are designed in a manner which insures that the limit of all such iterations would be continuously differentiable. Among the merits of the proposed algorithm are its simplicity, both for understanding and in terms of calculation time, the principle lack of artifacts caused by the usage of approximating functions of any particular kind, and the ease with which it may be generalized to be used in an n-dimensional space. A special feature of SRALG is that it leaves unchanged a point which lies in the middle of a line segment defined by its neighbors, which is natural in the context of smoothing. This feature can be utilized during creation of other algorithms based on SRALG, such as my own SRALG-Based Interpolation Algorithm.
D.Grilikhes, PhD |
MATLAB realization of one iteration of SRALG
function Y = iterSRALG( X,k )
% iterSRALG(X,k) Computes one iteration of SRALG
% on the siquense of points X(i,:)
% with the smoothig coefficient k.
% In this implementation, we assume that the points belong to
% some multi-dimentional space. k is assumed to be between 0 and 1.
% D.Grilikhes April 07, 2013
% Copyright 2013 Dmitry Grilikhes
Y = zeros(size(X,1)*2-1, size(X,2));
Y(1,:) = X(1,:);
Y(2,:)=(X(1,:)+X(2,:))/2;
for i = 2:(size(X,1)-1)
Y(2*(i-1)+1,:)=X(i,:)*(1-k/2)+k*(X(i-1,:)+X(i+1,:))/4;
Y(2*(i-1)+2,:)=(X(i,:)+X(i+1,:))/2;
end
Y(size(X,1)*2-2,:) = (X(end,:)+X(end-1,:))/2;
Y(size(X,1)*2-1,:) = X(end,:);
end
Fig.1 Iterations of SRALG
Fig.1 SRALG in 3D
Matrix representation
In some cases it could be useful to realize SRALG as a sequense of matrix operations. It is trivial because of simplicity of representation of one SRALG iteration as multiplication below.
where X1,X2,...Xn - are the data vectors in some vector space, and the matrix has n columns and 2n-1 rows.
It is very simple to calculate the deviation of each point from the original data point. In each iteration it shifts along the same line, towards the middle between its "neighbors" with the same coefficient k/2, so that the distance between it and this middle point becomes (1-k)/2. As a result, we have a geometric progression and can simply calculate the "shift" of point Xi after n iterations:
,where X1,X2,...Xn - are data vectors in some vector space,
and the deviation of the point from its original will be limited by the limit below
.