quickselectFSnw

quickselectFSnw extends quickselectFSw to negative weights

expand all in page

Syntax

  • kD =quickselectFSnw(D,W)example
  • kD =quickselectFSnw(D,W,p)example
  • [kD , kW ]=quickselectFSnw(___)example
  • [kD , kW , kstar]=quickselectFSnw(___)example
  • [kD , kW , kstar, varargout]=quickselectFSnw(___)example

Description

quickselectFSnw introduces the approach of Arce (1998) in quickselectFSw, to cope with possible negative weights in array W. The input/output arguments are the same of quickselectFSw. If the weights are all positive, the overhead for the extra checks required by Arce (1998) is almost negligible, especially when the sample size is large (~10^6).

example

kD =quickselectFSnw(D, W)

example

kD =quickselectFSnw(D, W, p) quickselectFSnw with negative weights.

example

[kD , kW ] =quickselectFSnw(___) quickselectFSnw with negative weights - example 2.

example

[kD , kW , kstar] =quickselectFSnw(___)

example

[kD , kW , kstar, varargout] =quickselectFSnw(___)

Examples

expand all

  • p    = 0.5;
X    = [-0.3 ; 0.1; 2.1 ; 0.3; 0.233333333; 0.366666667; 0.1; 0.3; -0.871428571; -0.85 ];
W    = [-0.25; 0.5; 0.25; 0.5; 0.75; 0.75; 1.25; 1.5; -1.75; -2 ];
[swm, swwm , kstar, XWS] = quickselectFSnw(X,W,p);		
rows_in_X = find(X==swm & swwm==swwm);

  • quickselectFSnw with negative weights.

    • Execution with separate calls. The example is taken from Arce (1998). 

    p    = 0.5;
A    = [-2 2 -1 3 6];
W    = [0.1 0.2 0.3 -0.2 0.1];
% Arce(1998) step 1a: take the sign of weights
sW   = sign(W);
% Arce(1998) step 1b: take the absolute value of the weights
absW = abs(W);
% Arce(1998) step 1c: take the "W-signed" observations 
sWA  = sW .* A;
% Arce(1998) step 2: compute the weighted median of sWA with weights absW 
[swm, swwm , kstar] = quickselectFSw(sWA,absW,p);
% Step 3: retrieve the weighted median and corresponding weight
%         with the right original sign
%   3a: index of weighted median and corrisponding weight 
kstar_AW = find(sWA==swm & absW==swwm);
%   3b: final weighted median, with the initial sign 
wm       = sW(kstar_AW) * swm;
%   3c: the weight of the weighted median, with the initial sign
wwm      = W(kstar_AW);
% Same result obtained with quickselectFSnw
[swm1, swwm1 , kstar1] = quickselectFSnw(A,W,p);

  • quickselectFSnw with negative weights - example 2.

    • This is another case with negative weights taken from Arce (2002). 

    % Note that the sample now is even, then Arce (2002) takes the mean of
% two middle values with an approach that uses sorting, which is 
% therefore less efficient than applying twice quickselectFSnw and
% taking the mean of the two middle order statistics.
p    = 0.5;
A    = [-2 2 -1 3 6 8];
W    = [0.2 0.4 0.6 -0.4 0.2 0.2];
% Arce(1998) step 1a: take the sign of weights
sW   = sign(W);
% Arce(1998) step 1b: take the absolute value of the weights
absW = abs(W);
% Arce(1998) step 1c: take the "W-signed" observations 
sWA  = sW .* A;
% Arce(1998) step 2: compute the weighted median of sWA with weights absW 
[swm, swwm , kstar] = quickselectFSw(sWA,absW,p);
% Step 3: retrieve the weighted median and corresponding weight
%         with the right original sign
%   3a: index of weighted median and corrisponding weight 
kstar_AW = find(sWA==swm & absW==swwm);
%   3b: final weighted median, with the initial sign 
wm       = sW(kstar_AW) * swm;
%   3c: the weight of the weighted median, with the initial sign
wwm      = W(kstar_AW);
% Same result obtained with quickselectFSnw
[swm1, swwm1 , kstar1] = quickselectFSnw(A,W,p);

    Input Arguments

    expand all

    D — Input data. Vector.

    A vector containing a set of $n$ data elements.

    Data Types: double

    W — Weights. Vector.

    The vector contains a set of $n$ arbitrary weights.

    Data Types: double

    Optional Arguments

    p — 100pth percentile ($0<p<1$). Scalar.

    A number between 0 and 1 indicating the fraction of total weights that should be considered in partitioning the associated input data. Default is p=0.5, leading to the weighted median.

    Example: p,0.2

    Data Types: double

    Output Arguments

    expand all

    kD —weighted order statistic in D. Scalar

    Element kstar in vector D ($D(k^{*})$), for which we have $\sum_{i=1}^{k^{*}-1} w_i<=p$ and $\sum_{j=k^{*}+1}^{n} w_j<=1-p$.

    kW —weight associated to kD. Scalar

    Element kstar in vector W. The weight partition around kW is optimal in the sense that the sum of the weights on its left is as close as possible to $p$ and those on its right account for the remaining $1-p$.

    kstar —the index of kD in D and of kW in W. Scalar

    It is the position of the weighted order statistic in the internal data and weight vectors, that is $D(k^{*})$ and $W(k^{*})$.

    varargout —Ds : Output vector. Array

    At the and of the computation the vector [D(:) , W(:)] is appropriately partitioned around kstar. It is returned ordered in the interval (1:kstar-1,:). Remark: this operation sorts only part of the array, but it can still slow down the algorithm.

    More About

    expand all

    Additional Details

    The approach by Arce (1998) consists in the application of a standard algorithm for the weighted median to a data vector consisting in the "W-signed" observations (sign(W) .* D) weighted by the absolute values of the original weights (abs(W)). Therefore, in principle, it is possible to use quickselectFSw after the simple transformation of the input arrays;

    then, the weighted median position in the original arrays is the same of the one found by quickselectFSw on the transformed ones (the arguments in MATLAB are passed by value, therefore the input arrays do not change).

    This is shown in the examples below.

    Function quickselectFSnw follows a more elegant approach: it introduces a boolean array representing the sign of the original weights and uses a cmputationally efficient way to keep track of their position during the swaps (it uses the 'xor' operator to check if the weights to swap have different sign, and the 'not' to emulate a swap).

    Given that, in general, the potential presence of negative weights depends on the applicaation and is therefore known in advance, we decided to embed the new general approach in a copy of quickselectFSw to not introduce in the original function operations that may slow down computation in the standard positive weights case.

    As for quickselectFSw, we also provide the mex counterpart starting from code written in FORTRAN in collaboration with Ian Barrodale. The mex file is quickselectFSnwmex.

    References

    Arce, G.R. (1998), A general weighted median filter structure admitting negative weights, "IEEE Transactions on Signal Processing, doi:

    10.1109/78.735296", vol. 46, no. 12, pp. 3195-3205.

    Arce, G.R. (2002), Recursive Weighted Median Filters Admitting Negative Weights and Their Optimization, IEEE Transactions on Signal Processing, Vol. 48, No. 3, pp. 768-779.

    Azzini, I., Perrotta, D. and Torti, F. (2023), A practically efficient fixed-pivot selection algorithm and its extensible MATLAB suite, "arXiv, stat.ME, eprint 2302.05705"

    See Also

    This page has been automatically generated by our routine publishFS