Title :
A perceptron-like online algorithm for tracking the median
Author :
Bylander, Tom ; Rosen, Bruce
Author_Institution :
Div. of Comput. Sci., Texas Univ., San Antonio, TX, USA
Abstract :
We present an online algorithm for tracking the median of a series of values. The algorithm updates its current estimate of the median by incrementing or decrementing a fixed value, which is analogous to perceptron updating. The median value of a sequence minimizes the absolute loss, i.e., the sum of absolute deviations. The analysis shows that the worst-case absolute loss of our algorithm is comparable to the absolute loss of any sequence of target medians, given restrictions on how much the target can change per trial
Keywords :
estimation theory; mathematics computing; minimisation; real-time systems; time series; absolute deviations; absolute loss; estimation theory; median tracking; online median algorithm; perceptron updating; time series; Algorithm design and analysis; Computer science; Fetal heart rate; Heart rate; Performance analysis; Probability distribution; Sampling methods; Sorting; Statistical distributions; Time series analysis;
Conference_Titel :
Neural Networks,1997., International Conference on
Conference_Location :
Houston, TX
Print_ISBN :
0-7803-4122-8
DOI :
10.1109/ICNN.1997.614292
