Re: gradient using linear regression

On Oct 18, 3:32 pm, "Arash " <asam...@xxxxxxxxx> wrote:
I have a large array (500,000 samples) that I need to find
the derivative of it for small windows (say every 35
samples). Instead of using the first and last point of the
small window to find derivative, that's how the gradient
function of matlab works, I need to do a linear regression
over the window and take the line slope as the derivative.

Here is my function where x is the input array and L is the
window size. Output y is the derivative of x.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function y = gradient_vec(x,L)

UseLinReg = true;

N = length(x);
if (N <= L)
y = zeros(1,N);
return;
end
L2 = floor(L/2);

if (~UseLinReg)
% for i = L2+1:N-L2
% Range = i-L2:i+L2;
% y(i) = (x(i+L2)-x(i-L2))/(L-1);
% end

y(L2+1:N-L2) = (x(L:N)-x(1:N-L+1))/(L-1);
else
% use linear regression
% need to convert to column vector
if (size(x,1) == 1)
x = x';
end
for i = L2+1:N-L2
t = [i-L2:i+L2]';
%% either use this
% m = polyfit(t,x(t),1);
%% or use this instead
m = [ones(length(t),1) t] \ x(t);
y(i) = m(2);
end
end

y(1:L2) = 0;
y(N-L2:N) = 0;
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

This is painfully slow. Any body has a suggestion of how to
do it faster either by avoiding using loops or some other ways.

Thanks,

What comes to my mind is:
(1) Change x variables so that you always use x1 = 1:L
for every regression of the same length. To convert to
a regression in terms of the actual x, do something like
this:

Given y = a0 + a1*x1
and x1 = x - offset
then y = a0 + a1*(x - offset)
= (a0 -a1*offset) + a1*x

In other words, you have to adjust the constant term
but not the slope.

(2) Use the explicit regression formulas instead of Matlab's
backslash. The reason is that if the x values are fixed,
the terms sum(x) and sum(x^2) can be calculated just
once and reused.

Those formulas are:

a1 = [n*sum(x*y) - sum(x)*sum(y)] / [n*sum(x^2) - sum(x)^2]

a0 = [sum(y) - a1*sum(x)] / n

where n = number of points.

(3) If y was an integer number of windows long, you could
use array operations to calculate all the sums above
at once by reshaping y into a matrix. It would thus be
possible to eliminate the loop.

- Randy

.

Relevant Pages

  • Re: Terminating
    ... posting it too deeply within a series of recurring calls and loops. ... How does this relate to my main window in my SDI? ... <Bob Moore> ...
    (microsoft.public.vc.mfc)
  • Re: Hadnling windows messages when in big loop
    ... www.getdotnetcode.com "Fred Flintstone" wrote in message ... >I have a project, that loops through a lot of wmi queries, and while its>looping, the window will not repaint, I can't move or size the window. ... > I remember having a similar problem back in an excel macro, and I ran a> command that told the application to process windows messages. ...
    (microsoft.public.dotnet.languages.vb)