check alternation maxima minima in matlab

Question

I have written an algorithm that finds the local maxima and minima in a signal.

[id_max, id_min] = find_max_min(signal);

I would like now to check: if the alterantion of maxima and minima is respected

i.e. id_max(1)<id_min(1)<id_max(2)<id_min(2)<... 
we could start with a minimum..this is not known

Suppose that:

 id_max = [1 3 5 7 10 14 20];

 id_min = [2 4 6 8 16 19];

I would like to have 2 vectors missing_max missing_min indicating the location of the missing maxima and minima.

A missing maximum (minimum) occours when between two consecutive minima (maxima) in id_min (id_max) there is not a maximum (minimum).

In this example a maximum is missing in the 7th position of id_max because in id_min there are two consecutive values (16 19) without a maximum between.

Then we have

missing_max = [7]

missing_min = [5]

since

id_max = [1 3 5 7 10 14 X 20];

id_min = [2 4 6 8 X 16 19]; (with X I marked the missing values)

If the alternation is correct the vectors should be empty. Can you suggest an efficient way to do that without for loops?

Thanks in advance

Answer 1

Here's a script that you can adapt to a function if you want:

    id_max = [1 3 5 7 10 14 20];
    id_min = [2 4 6 8 16 19];

    % Group all values, codify extremity (1-max, 0-min), and position
    id_all   = [          id_max,              id_min  ];
    code_all = [ones(size(id_max)), zeros(size(id_min))];
    posn_all = [  1:numel(id_max),     1:numel(id_min) ];

    % Reshuffle the codes and positions according to sorted IDs of min/max
    [~, ix]  = sort(id_all);
    code_all = code_all(ix);
    posn_all = posn_all(ix);

    % Find adjacent IDs that have the same code, i.e. code diff = 0
    code_diff = (diff(code_all)==0);

    % Get the indices of same-code neighbors, and their original positions
    ix_missing_min = find([code_diff,false] & (code_all==1));
    ix_missing_max = find([code_diff,false] & (code_all==0));

    missing_min    = posn_all(ix_missing_min+1);
    missing_max    = posn_all(ix_missing_max+1);

Caveats on IDs:

1. Make sure your id_min and id_max are rows (even if empty);
2. Make sure that at least one of them is not empty;
3. While they need not to be sorted, their values must be unique (within the IDs and across).

Later edit:

New version of the code, based on new explanations about the definition:

    id_max = [1 3 5 7 10 14 20];
    id_min = [2 4 6 8 16 19];
    %id_max = [12 14]
    %id_min = [2 4 6 8 10];

    id_min_ext = [-Inf, id_min];
    id_max_ext = [-Inf, id_max];

    % Group all values, and codify their extremity (1-max, 0-min), and position
    id_all   = [          id_max_ext,              id_min_ext  ];
    code_all = [ones(size(id_max_ext)), zeros(size(id_min_ext))];
    posn_all = [  0:numel(id_max),         0:numel(id_min)     ];

    % Reshuffle the codes and position according to sorted positions of min/max
    [~, ix] = sort(id_all);
    code_all = code_all(ix);
    posn_all = posn_all(ix);

    % Find adjacent IDs that have the same code, i.e. code diff = 0
    code_diff = (diff(code_all)==0);

    % Get the indices of same-code neighbours, and their original positions
    ix_missing_min = find([code_diff,false] & (code_all==1));
    ix_missing_max = find([code_diff,false] & (code_all==0));

    missing_min    = unique(posn_all(ix_missing_min-1))+1;
    missing_max    = unique(posn_all(ix_missing_max-1))+1;

However, the code contains a subtle bug. The bug will be removed by either the person that asked the question, or by me after he/she improves the question in such a way that is really clear what's asked for. :-) Due the fact that we have 2 virtual extremums (one max and one min, at ID = −∞) is possible that the first missing extremum will be marked twice: once at −∞ and once at the first element of the ID list. unique() will take care of that (though is too much of a function call to check if the first 2 elements of an array have the same value)