I am looking for any suitable trick how to effectively compute moving window (length w) median. I know of course the movmedian function, but I need strictly recurrent native MATLAB function working sample by sample.
My naive solution, which is equivalent to the
output_median = movmedian(input_x,[w-1,0])
is as follows:
rng(‘default’)
% number of samples
N = 25;
% moving median windows length
w = 5;
% init history buffer and median
x_hist = rand;
med_new = x_hist;
% init input x vector
input_x = zeros(1,N);
input_x(1) = x_hist;
% init output median vector of length N
output_median = zeros(1,N);
output_median(1) = med_new;
for i = 2:N
x_new = rand;
[med_new,x_hist] = moving_median(x_hist,x_new,w);
input_x(i) = x_new;
output_median(i) = med_new;
end
where function moving_median is here:
function [med_new,x_hist] = moving_median(x_hist,x_new,w)
% Old length of history
wo = length(x_hist);
% Update history
x_hist = [x_hist(max(1,wo-w+2):wo),x_new]; % Grow history until size w, then append new x and remove oldest x
med_new = median(x_hist);
end
Any idea how to make this algorithm more effective (faster) a still strictly recurrent?

Target use case should works with window length:
w ~ 1e3 – 1e4 (!!!)

Additional notes:
fast moving median computing is always based on advanced data structures use like Heap or Queues, etc.
some sort-structure information could be stored in these structures and used at the next sample step to significant speed-up median computing
similar approach is used in movmedian function, but this function is not directly applicable on running-data streamI am looking for any suitable trick how to effectively compute moving window (length w) median. I know of course the movmedian function, but I need strictly recurrent native MATLAB function working sample by sample.
My naive solution, which is equivalent to the
output_median = movmedian(input_x,[w-1,0])
is as follows:
rng(‘default’)
% number of samples
N = 25;
% moving median windows length
w = 5;
% init history buffer and median
x_hist = rand;
med_new = x_hist;
% init input x vector
input_x = zeros(1,N);
input_x(1) = x_hist;
% init output median vector of length N
output_median = zeros(1,N);
output_median(1) = med_new;
for i = 2:N
x_new = rand;
[med_new,x_hist] = moving_median(x_hist,x_new,w);
input_x(i) = x_new;
output_median(i) = med_new;
end
where function moving_median is here:
function [med_new,x_hist] = moving_median(x_hist,x_new,w)
% Old length of history
wo = length(x_hist);
% Update history
x_hist = [x_hist(max(1,wo-w+2):wo),x_new]; % Grow history until size w, then append new x and remove oldest x
med_new = median(x_hist);
end
Any idea how to make this algorithm more effective (faster) a still strictly recurrent?

Target use case should works with window length:
w ~ 1e3 – 1e4 (!!!)

Additional notes:
fast moving median computing is always based on advanced data structures use like Heap or Queues, etc.
some sort-structure information could be stored in these structures and used at the next sample step to significant speed-up median computing
similar approach is used in movmedian function, but this function is not directly applicable on running-data stream I am looking for any suitable trick how to effectively compute moving window (length w) median. I know of course the movmedian function, but I need strictly recurrent native MATLAB function working sample by sample.
My naive solution, which is equivalent to the
output_median = movmedian(input_x,[w-1,0])
is as follows:
rng(‘default’)
% number of samples
N = 25;
% moving median windows length
w = 5;
% init history buffer and median
x_hist = rand;
med_new = x_hist;
% init input x vector
input_x = zeros(1,N);
input_x(1) = x_hist;
% init output median vector of length N
output_median = zeros(1,N);
output_median(1) = med_new;
for i = 2:N
x_new = rand;
[med_new,x_hist] = moving_median(x_hist,x_new,w);
input_x(i) = x_new;
output_median(i) = med_new;
end
where function moving_median is here:
function [med_new,x_hist] = moving_median(x_hist,x_new,w)
% Old length of history
wo = length(x_hist);
% Update history
x_hist = [x_hist(max(1,wo-w+2):wo),x_new]; % Grow history until size w, then append new x and remove oldest x
med_new = median(x_hist);
end
Any idea how to make this algorithm more effective (faster) a still strictly recurrent?

Target use case should works with window length:
w ~ 1e3 – 1e4 (!!!)

Additional notes:
fast moving median computing is always based on advanced data structures use like Heap or Queues, etc.
some sort-structure information could be stored in these structures and used at the next sample step to significant speed-up median computing
similar approach is used in movmedian function, but this function is not directly applicable on running-data stream moving, median MATLAB Answers — New Questions

​