Recursive Computation of Signal Vector Norms

Problem

Some text ... 

\begin{equation} {\bf x}(n) \,\,=\,\, \big[ x(n),\,x(n-1),\,x(n-2),\, ...,\,x(n-N+1)\big]^{\textrm{T}} \label{eq_red_rec_comp_vec_norms_00} \end{equation}

Some text ... 

\begin{equation} \big\| {\bf x}(n)\big\|^2 \,\,=\,\, \sum\limits_{i=0}^{N-1}x^2(n-i) \label{eq_red_rec_comp_vec_norms_01} \end{equation}

 

Recursive Computation

Some text ... 

\begin{equation} \big\| {\bf x}(0)\big\|^2 \,\,=\,\, 0 \label{eq_red_rec_comp_vec_norms_02} \end{equation}

Some text ... 

\begin{equation} \big\| {\bf x}(n)\big\|^2 \,\,=\,\, \big\| {\bf x}(n-1)\big\|^2 + x^2(n) - x^2(n-N)\label{eq_red_rec_comp_vec_norms_03} \end{equation}

Some text ... 

\begin{equation} \big\| {\bf x}(n)\big\|^2 \,\,=\,\, \max\Big\{0,\,\big\| {\bf x}(n-1)\big\|^2 + x^2(n) - x^2(n-N)\Big\} \label{eq_red_rec_comp_vec_norms_04} \end{equation}

 

Mixed Recursive/Iterative Computation

Some text ... 

\begin{equation} N_{\textrm{rec}}(n) \,\,=\,\, \left\{ \begin{array}{ll} 0, & \textrm{if}\,\mod(n,N)\,\equiv\, 0, \\[2mm] N_{\textrm{rec}}(n-1) + x^2(n), & \textrm{else}. \end{array}\right. \label{eq_red_rec_comp_vec_norms_05} \end{equation}

Some text ... 

\begin{equation} \big\| {\bf x}(n)\big\|^2 \,\,=\,\, \left\{ \begin{array}{ll} N_{\textrm{rec}}(n), & \textrm{if}\,\mod(n,N)\,\equiv\, N-1, \\[2mm] \max\Big\{0,\,\big\| {\bf x}(n-1)\big\|^2 + x^2(n) - x^2(n-N)\Big\},& \textrm{else}. \end{array}\right. \label{eq_red_rec_comp_vec_norms_06} \end{equation}

 

Code Example

Different methods of computing vector norms

%**************************************************************************
% Parameters
%**************************************************************************
N            =   128;
Sig_duration = 10000;

%**************************************************************************
% Generate input signal
%**************************************************************************

% Generate white Gaussian noise
sig = single(randn(Sig_duration,1));

% Boost every second 1000 signal values by 60 dB  
for k = 1001:2000:Sig_duration;
    sig(k-1000:k) = sig(k-1000:k) * 1000;
end;

%**************************************************************************
% Compute norms
%**************************************************************************
x_vec               = single(zeros(N,1));
Norm_rec_curr       = single(0);
Norm_rec_curr_lim   = single(0);
N_rec               = single(0);
C_rec               = single(0);
Norm_mixed_curr     = single(0);
N_rec_lim           = single(0);
C_rec_lim           = single(0);
Norm_mixed_lim_curr = single(0);

Norm_double_prec    = zeros(Sig_duration,1);
Norm_iterative      = single(zeros(Sig_duration,1));
Norm_recursive      = single(zeros(Sig_duration,1));
Norm_recursive_lim  = single(zeros(Sig_duration,1));
Norm_mixed          = single(zeros(Sig_duration,1));
Norm_mixed_lim      = single(zeros(Sig_duration,1));

for k = 1:Sig_duration

    %**********************************************************************
    % Update signal vector (not very efficient, but o.k. for here
    %**********************************************************************
    x_new      = sig(k);
    x_old      = x_vec(N);
    x_vec(2:N) = x_vec(1:N-1);
    x_vec(1)   = x_new;
    
    %**********************************************************************
    % Norm in double precicion
    %**********************************************************************
    Norm_double_prec(k) = double(x_vec)' * double(x_vec);
    
    %**********************************************************************
    % Iterative norm (of course, there exixt optimized Matlab functions
    % for this purpose, but that's another "story")
    %**********************************************************************
    for n = 1:N
        Norm_iterative(k) = Norm_iterative(k) + x_vec(n)*x_vec(n);
    end;
    
    %**********************************************************************
    % Recursive norm computation
    %**********************************************************************
    Norm_rec_curr     = Norm_rec_curr + x_new^2 - x_old^2;
    Norm_recursive(k) = Norm_rec_curr;
    
    %**********************************************************************
    % Recursive norm computation
    %**********************************************************************
    Norm_rec_curr_lim     = Norm_rec_curr_lim + x_new^2 - x_old^2;
    Norm_rec_curr_lim     = max(0, Norm_rec_curr_lim);
    Norm_recursive_lim(k) = Norm_rec_curr_lim;  
    
    %**********************************************************************
    % Mixed compuation of the norm
    %**********************************************************************
    Norm_mixed_curr = Norm_mixed_curr + x_new^2 - x_old^2;
    
    C_rec = C_rec + 1;    
    if (C_rec == N)
        C_rec = 0;
    end;
   
    if (C_rec == 0)
        N_rec = 0;
    end;
    N_rec = N_rec + + x_new^2;
    
    if (C_rec == N-1)
        Norm_mixed_curr = N_rec;    
    end;
    
    Norm_mixed(k) = Norm_mixed_curr; 
    
    %**********************************************************************
    % Mixed compuation of the norm with limiation
    %**********************************************************************
    Norm_mixed_lim_curr = Norm_mixed_lim_curr + x_new^2 - x_old^2;
    Norm_mixed_lim_curr = max(0,Norm_mixed_lim_curr);
    
    C_rec_lim = C_rec_lim + 1;    
    if (C_rec_lim == N)
        C_rec_lim = 0;
    end;
   
    if (C_rec_lim == 0)
        N_rec_lim = 0;
    end;
    N_rec_lim = N_rec_lim + + x_new^2;
    
    if (C_rec_lim == N-1)
        Norm_mixed_lim_curr = N_rec_lim;    
    end;
    
    Norm_mixed_lim(k) = Norm_mixed_lim_curr;
    
end;

%**************************************************************************
% Show results
%**************************************************************************
fig = figure(1);
set(fig,'Units','Normalized');
set(fig,'Position',[0.1 0.1 0.8 0.8]);

t = 0:Sig_duration-1;

subplot('Position',[0.07 0.8 0.9 0.17]);
plot(t,10*log10(Norm_double_prec),'b', ...
     t,10*log10(max(0.01, Norm_iterative))+1,'r');
grid on
set(gca,'XTickLabel','');
ylabel('dB')
legend('Norm in double precision', ...
       'Iteratively computed norm (lifted by 1 dB)');
axis([0 Sig_duration-1 0 120]);

subplot('Position',[0.07 0.62 0.9 0.17]);
plot(t,10*log10(Norm_double_prec),'b', ...
     t,10*log10(max(0.01, Norm_recursive))+1,'r');
grid on
set(gca,'XTickLabel','');
ylabel('dB')
legend('Norm in double precision', ...
       'Recursively computed computed norm (lifted by 1 dB)');  
axis([0 Sig_duration-1 0 120]);   

subplot('Position',[0.07 0.44 0.9 0.17]);
plot(t,10*log10(Norm_double_prec),'b', ...
     t,10*log10(max(0.01, Norm_recursive_lim))+1,'r');
grid on
set(gca,'XTickLabel','');
ylabel('dB')
legend('Norm in double precision', ...
       'Recursively computed computed norm with limitation (lifted by 1 dB)');     
axis([0 Sig_duration-1 0 120]);   
   
subplot('Position',[0.07 0.26 0.9 0.17]);
plot(t,10*log10(Norm_double_prec),'b', ...
     t,10*log10(max(0.01, Norm_mixed))+1,'r');
grid on
set(gca,'XTickLabel','');
ylabel('dB')
legend('Norm in double precision', ...
       'Mixed recursively/iteratively computed norm (lifted by 1 dB)');     
axis([0 Sig_duration-1 0 120]);   
   
subplot('Position',[0.07 0.08 0.9 0.17]);
plot(t,10*log10(Norm_double_prec),'b', ...
     t,10*log10(max(0.01, Norm_mixed_lim))+1,'r');
grid on
xlabel('Samples');
ylabel('dB')
legend('Norm in double precision', ...
       'Mixed recursively/iteratively computed norm with limitation (lifted by 1 dB)');   
axis([0 Sig_duration-1 0 120]);   

 

Basic Idea of RED

RED (robust and efficient DSP) is a collection of algorithms that should help engineers to implement basic signal processign tasks in - as the name states - a robust and efficient way. This includes mainly numerical aspects.

 

 

Here you will find soon the chapter on recursive computation of signal vector norms as a single pdf file. If you would like to download all chapters please go to the RED overview page and get the pdf document that contain all chapters from there.

Contact

Prof. Dr.-Ing. Gerhard Schmidt

E-Mail: gus@tf.uni-kiel.de

Christian-Albrechts-Universität zu Kiel
Faculty of Engineering
Institute for Electrical Engineering and Information Engineering
Digital Signal Processing and System Theory

Kaiserstr. 2
24143 Kiel, Germany

Recent News

Jens Reermann Defended his Dissertation with Distinction

On Friday, 21st of June, Jens Reermann defended his research on signals processing for magnetoelectric sensor systems very successfully. After 90 minutes of talk and question time he finished his PhD with distinction. Congratulations, Jens, from the entire DSS team.

Jens worked for about three and a half years - as part of the collaborative research center (SFB) 1261 - on all kinds of signal ...


Read more ...