×

Change detection using an iterative algorithm with guarantees. (English) Zbl 1481.94060

Summary: Multiple domains involve systems with abruptly changing states, that result in signals with signatures that are corrupted by noise and sensor dynamics. In many applications, prior information on the magnitudes and timing distributions are unknown, compounding the difficulty of filtering such signals. Several non-linear filtering techniques are available with varying efficacies, however only a few offer theoretical guarantees. Recent research has led to a heuristic, iterative, non-linear filtering technique that is found to be effective over a range of applications. In this article, we present this iterative algorithm that learns the distribution of the event magnitude and provides an estimate of when an event has occurred. Here, every iteration involves two stages: the first one providing an estimate of the true signal that uses a prior on the distribution of event magnitudes, followed by the second stage where a distribution of the event magnitudes is computed from an estimate of the true signal. It is shown that with every iterate, the performance of the algorithm only improves and convergence of the posterior probability is established. Our comparative tests show that our algorithm provides significant performance improvements, especially for high bandwidth applications where sensor dynamics cannot be neglected. In addition, we provide a Python-based implementation of the algorithm and provide a comprehensive comparison with existing methods in practice.

MSC:

94A12 Signal theory (characterization, reconstruction, filtering, etc.)
94A13 Detection theory in information and communication theory

Software:

wbs; unbalhaar
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aggarwal, T.; Materassi, D.; Davison, R.; Hays, T.; Salapaka, M., Detection of steps in single molecule data, Cellular and Molecular Bioengineering, 5, 1, 14-31 (2012)
[2] Arlot, S.; Celisse, A.; Harchaoui, Z., A kernel multiple change-point algorithm via model selection, 56 (2019) · Zbl 1446.62120
[3] Bilmes, J. A., A gentle tutorial of the EM algorithm and its application to parameter estimation for Gaussian mixture and hidden Markov models, vol. 4, no. 510, 126 (1998), International Computer Science Institute
[4] Boyd, S. P.; Vandenberghe, L., Convex optimization (2004), Cambridge University Press: Cambridge University Press Cambridge, UK ; New York · Zbl 1058.90049
[5] Cai, H., Biomimetic nanoarchitectures for the study of T cell activation with single-molecule control (2016), Columbia University
[6] Canny, J., A computational approach to edge detection, IEEE Transactions on Pattern Analysis and Machine Intelligence, PAMI-8, 6, 679-698 (1986)
[7] Carter, N. J.; Cross, R., Mechanics of the kinesin step, Nature, 435, 7040, 308 (2005)
[8] Carter, B. C.; Vershinin, M.; Gross, S. P., A comparison of step-detection methods: how well can you do?, Biophysical Journal, 94, 1, 306-319 (2008)
[9] Ducré-Robitaille, J.-F.; Vincent, L. A.; Boulet, G., Comparison of techniques for detection of discontinuities in temperature series, International Journal of Climatology: A Journal of the Royal Meteorological Society, 23, 9, 1087-1101 (2003)
[10] Dumont, E. L.; Do, C.; Hess, H., Molecular wear of microtubules propelled by surface-adhered kinesins, Nature Nanotechnology, 10, 2, 166-169 (2015)
[11] Fryzlewicz, P., Unbalanced haar technique for nonparametric function estimation, Journal of the American Statistical Association, 102, 480, 1318-1327 (2007) · Zbl 1333.62014
[12] Fryzlewicz, P., Wild binary segmentation for multiple change-point detection, The Annals of Statistics, 42, 6 (2014) · Zbl 1302.62075
[13] Goodfellow, I.; Bengio, Y.; Courville, H., Deep learning (2016), MIT Press · Zbl 1373.68009
[14] Ha, T., Single-molecule methods leap ahead, Nature Methods, 11, 10, 1015-1018 (2014)
[15] Hares, K.; Miners, J. S.; Cook, A. J.; Rice, C.; Scolding, N.; Love, S.; Gozes, I., Overexpression of kinesin superfamily motor proteins in alzheimers disease, Journal of Alzheimer’s Disease, 60, 4, 1511-1524 (2017)
[16] Hua, W.; Young, E. C.; Fleming, M. L.; Gelles, J., Coupling of kinesin steps to ATP hydrolysis, Nature, 388, 6640, 390 (1997)
[17] Kerssemakers, J. W.; Munteanu, E. L.; Laan, L.; Noetzel, T. L.; Janson, M. E.; Dogterom, M., Assembly dynamics of microtubules at molecular resolution, Nature, 442, 7103, 709 (2006)
[18] Killick, R.; Fearnhead, P.; Eckley, I. A., Optimal detection of changepoints with a linear computational cost, Journal of the American Statistical Association, 107, 500, 1590-1598 (2012) · Zbl 1258.62091
[19] Little, M. A.; Jones, N. S., Generalized methods and solvers for noise removal from piecewise constant signals. I. background theory, Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 467, 2135, 3088-3114 (2011) · Zbl 1239.94018
[20] Lucanus, A. J.; Yip, G. W., Kinesin superfamily: roles in breast cancer, patient prognosis and therapeutics, Oncogene, 37, 7, 833-838 (2018)
[21] McConnell, M. J.; Lindberg, M. R.; Brennand, K. J.; Piper, J. C.; Voet, T.; Cowing-Zitron, C., Mosaic copy number variation in human neurons, Science, 342, 6158, 632-637 (2013)
[22] Mullner, F. E.; Syed, S.; Selvin, P. R.; Sigworth, F. J., Improved hidden Markov models for molecular motors, part 1: basic theory, Biophysical Journal, 99, 11, 3684-3695 (2010)
[23] Olshen, A. B.; Venkatraman, E. S.; Lucito, R.; Wigler, M., Circular binary segmentation for the analysis of array-based DNA copy number data, Biostatistics, 5, 4, 557-572 (2004) · Zbl 1155.62478
[24] Page, E. S., On problems in which a change in a parameter occurs at an unknown point, Biometrika, 44, 1/2, 248-252 (1957) · Zbl 0083.14705
[25] Pang, S. M.; Le, S.; Yan, J., Mechanical responses of the mechanosensitive unstructured domains in cardiac titin, Biology of the Cell, 110, 3, 65-76 (2018)
[26] Picard, D., Testing and estimating change-points in time series, Advances in Applied Probability, 17, 4, 841-867 (1985) · Zbl 0585.62151
[27] Radke, R.; Andra, S.; Al-Kofahi, O.; Roysam, B., Image change detection algorithms: a systematic survey, IEEE Transactions on Image Processing, 14, 3, 294-307 (2005)
[28] Rajaganapathy, S., Melbourne, J., Aggarwal, T., Shrivastava, R., & Salapaka, M. V. (2018). Learning and estimation of single molecule behavior. In: 2018 Annual American control conference (pp. 5125-5130). ISSN: 2378-5861.
[29] Rudin, L. I.; Osher, S.; Fatemi, E., Nonlinear total variation based noise removal algorithms, Physica D: Nonlinear Phenomena, 60, 1-4, 259-268 (1992) · Zbl 0780.49028
[30] Russell, S. J.; Norvig, P., Artificial intelligence: A modern approach (2016), Malaysia; Pearson Education Limited
[31] Sadler, B. M.; Swami, A., Analysis of multiscale products for step detection and estimation, IEEE Transactions on Information Theory, 45, 3, 1043-1051 (1999) · Zbl 0947.94007
[32] Svoboda, K.; Schmidt, C. F.; Schnapp, B. J.; Block, S. M., Direct observation of kinesin stepping by optical trapping interferometry, Nature, 365, 6448, 721-727 (1993)
[33] Sweeney, H. L.; Holzbaur, E. L., Motor proteins, Cold Spring Harbor Perspectives in Biology, 10, 5, a021931 (2018)
[34] Syed, S.; Mullner, F. E.; Selvin, P. R.; Sigworth, F. J., Improved hidden Markov models for molecular motors, part 2: extensions and application to experimental data, Biophysical Journal, 99, 11, 3696-3703 (2010)
[35] Truong, C.; Oudre, L.; Vayatis, N., Selective review of offline change point detection methods, Signal Processing, 167, Article 107299 pp. (2020)
[36] Winkler, J. R., Numerical recipes in C: The art of scientific computing, second edition, Endeavour, 17, 4, 201 (1993)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.