Step detection

from microarray data, (b) cosmic ray intensity from a neutron monitor, (c) rotation speed against time of R. Sphaeroides flagellar motor, and (d) red pixel intensity from a single scan line of a digital image. In statistics and signal processing, step detection (also known as step smoothing, step filtering, shift detection, jump detection or edge detection) is the process of finding abrupt changes (steps, jumps, shifts) in the mean level of a time series or signal. It is usually considered as a special case of the statistical method known as change detection or change point detection. Often, the step is small and the time series is corrupted by some kind of noise, and this makes the problem challenging because the step may be hidden by the noise. Therefore, statistical and/or signal processing algorithms are often required. The step detection problem occurs in multiple scientific and engineering contexts, for example in statistical process control (the control chart being the most directly related method), in exploration geophysics (where the problem is to segment a well-log recording into stratigraphic zones ), in genetics (the problem of separating microarray data into similar copy-number regimes ), and in biophysics (detecting state transitions in a molecular machine as recorded in time-position traces ).…

from microarray data, (b) cosmic ray intensity from a neutron monitor, (c) rotation speed against time of R. Sphaeroides flagellar motor, and (d) red pixel intensity from a single scan line of a digital image. In statistics and signal processing, step detection (also known as step smoothing, step filtering, shift detection, jump detection or edge detection) is the process of finding abrupt changes (steps, jumps, shifts) in the mean level of a time series or signal. It is usually considered as a special case of the statistical method known as change detection or change point detection. Often, the step is small and the time series is corrupted by some kind of noise, and this makes the problem challenging because the step may be hidden by the noise. Therefore, statistical and/or signal processing algorithms are often required. The step detection problem occurs in multiple scientific and engineering contexts, for example in statistical process control (the control chart being the most directly related method), in exploration geophysics (where the problem is to segment a well-log recording into stratigraphic zones ), in genetics (the problem of separating microarray data into similar copy-number regimes ), and in biophysics (detecting state transitions in a molecular machine as recorded in time-position traces ). For 2D signals, the related problem of edge detection has been studied intensively for image processing. Here, x i for i = 1, ...., N is the discrete-time input signal of length N, and m i is the signal output from the algorithm. The goal is to minimize H[m] with respect to the output signal m. The form of the function \scriptstyle \Lambda determines the particular algorithm. For example, choosing: \Lambda = \frac12 \left|x_i-m_j\right|^2 I(i-j=0) + \gamma\left|m_i-m_j\right| I(i-j=1) where I(S) = 0 if the condition S is false, and one otherwise, obtains the total variation denoising algorithm with regularization parameter \gamma . Similarly: \Lambda=\min \left\{\frac12 \left|m_i-m_j\right|^2,W\right\} leads to the mean shift algorithm, when using an adaptive step size Euler integrator initialized with the input signal x. Here W > 0 is a parameter that determines the support of the mean shift kernel. Another example is: \Lambda = \frac{1-\exp(-\beta|m_i-m_j|^2/2)}{\beta} \cdot I(|i-j|\le W) leading to the bilateral filter, where \scriptstyle \beta>0 is the tonal kernel parameter, and W is the spatial kernel support. Yet another special case is: \Lambda= \frac12 \left|x_i-m_j\right|^2 I(i-j=0) + \gamma \left|m_i-m_j\right|^0 I(i-j=1) specifying a group of algorithms that attempt to greedily fit 0-degree splines to the signal. Here, \scriptstyle \left|x\right|^0 is defined as zero if x = 0, and one otherwise. Many of the functionals in equation ( ) defined by the particular choice of \scriptstyle \Lambda are convex: they can be minimized using methods from convex optimization. Still others are non-convex but a range of algorithms for minimizing these functionals have been devised. u^* = \arg\min_{u \in\R^N} \gamma \| \nabla u \|_0 + \| u-x\|_p^p The term \| \nabla u \|_0 = \# \{ i : u_i \neq u_{i+1} \} penalizes the number of jumps and the term \| u-x\|_p^p = \sum_{i=1}^N |u_i - x_i|^p measures fidelity to data x. The parameter γ > 0 controls the tradeoff between regularity and data fidelity. Since the minimizer u^* is piecewise constant the steps are given by the non-zero locations of the gradient \nabla u^* . For p = 2 and p= 1 there are fast algorithms which give an exact solution of the Potts problem in O(N^2) . ==See also== Time-series segmentation

Text derived from https://en.wikipedia.org/w/index.php?oldid=1367014283 under CC BY-SA 4.0; modifications have been made.