Robust crossings detection in noisy signals using topological signal processing. (English) Zbl 07927540
Summary: This article explores a novel method of bracketing zero-crossings for both 1-D functions and discretely sampled time series by the application of 0-D persistent homology from algebraic topology. We introduce an algorithm and demonstrate its capability of detecting crossing in noisy signals across various sampling frequencies. Compared to other software-based methods for crossing-detection in signals, our approach is typically faster, shows a higher accuracy, and has the unique ability to identify all roots within the provided interval instead of detecting only one out of all. We also discuss different options for mathematically estimating the persistence threshold – a parameter which impacts and controls the correct bracketing of roots. Finally, we explore the potential of extending our algorithm to higher dimensions.
MSC:
| 55N31 | Persistent homology and applications, topological data analysis |
| 55-04 | Software, source code, etc. for problems pertaining to algebraic topology |
| 65H04 | Numerical computation of roots of polynomial equations |
Keywords:
zero-crossings; signal processing; persistent homology; time series analysis; topological data analysisReferences:
| [1] | H. M. Antia,, Numerical Methods for Scientists and Engineers, Birkhäuser, 2002. · Zbl 1014.65001 |
| [2] | E. Badr, H. Attiya and A. E. Ghamry, Novel hybrid algorithms for root determining using advantages of open methods and bracketing methods, Alexandria Engineering Journal, 61 (2022), 11579-11588. doi: 10.1016/j.aej.2022.05.007. · doi:10.1016/j.aej.2022.05.007 |
| [3] | E. Bayat, N. Divani-Vais, M. M. Firoozabadi and N. Ghal-Eh, A comparative study on neutron-gamma discrimination with ne213 and ugltt scintillators using zero-crossing method, Radiation Physics and Chemistry, 81 (2012), 217-220. doi: 10.1016/j.radphyschem.2011.10.016. · doi:10.1016/j.radphyschem.2011.10.016 |
| [4] | P. Daponte, D. Grimaldi, A. Molinaro and Y. D. Sergeyev, An algorithm for finding the zero crossing of time signals with lipschitzean derivatives, Measurement, 16 (1995), 37-49. doi: 10.1016/0263-2241(95)00016-e. · doi:10.1016/0263-2241(95)00016-e |
| [5] | P. Daponte, D. Grimaldi, A. Molinaro and Y. D. Sergeyev, Fast detection of the first zero-crossing in a measurement signal set, Measurement, 19 (1996), 29-39. doi: 10.1016/S0263-2241(96)00059-0. · doi:10.1016/S0263-2241(96)00059-0 |
| [6] | T. K. Dey and Y. Wang, Computational Topology for Data Analysis, Cambridge University Press, 2021. doi: 10.1017/9781009099950. · Zbl 1498.57001 · doi:10.1017/9781009099950 |
| [7] | M. B. Djuric and Z. R. Djurisic, Frequency measurement of distorted signals using fourier and zero crossing techniques, Electric Power Systems Research, 78 (2008), 1407-1415. doi: 10.1016/j.epsr.2008.01.008. · doi:10.1016/j.epsr.2008.01.008 |
| [8] | I. Fried, High-order iterative bracketing methods, International Journal for Numerical Methods in Engineering, 94 (2013), 708-714. doi: 10.1002/nme.4467. · Zbl 1352.65140 · doi:10.1002/nme.4467 |
| [9] | V. Friedman, A zero crossing algorithm for the estimation of the frequency of a single sinusoid in white noise, IEEE Transactions on Signal Processing, 42 (1994), 1565-1569. doi: 10.1109/78.286978. · doi:10.1109/78.286978 |
| [10] | D. J. Kavvadias, F. S. Makri and M. N. Vrahatis, Efficiently computing many roots of a function, Journal on Scientific Computing, 27 (2005), 93-107. doi: 10.1137/S1064827502406531. · Zbl 1113.65049 · doi:10.1137/S1064827502406531 |
| [11] | S. Kim, M. Kojima and K.-C. Toh, A newton-bracketing method for a simple conic optimization problem, Optimization Methods and Software, 36 (2020) 371-388. doi: 10.1080/10556788.2020.1782906. · Zbl 1470.90063 · doi:10.1080/10556788.2020.1782906 |
| [12] | V. Kodnyanko, Improved bracketing parabolic method for numerical solution of nonlinear equations, Applied Mathematics and Computation, 400 (2021), Paper No. 125995, 6 pp. doi: 10.1016/j.amc.2021.125995. · Zbl 1508.65050 · doi:10.1016/j.amc.2021.125995 |
| [13] | Z. Li, J. Jiang, L. Hong and J. Q. Sun, A subspace expanding technique for global zero finding of multi-degree-of-freedom nonlinear systems, Applied Mathematics and Mechanics (English Edition), 41 (2020), 769-784. doi: 10.1007/s10483-020-2604-6. · Zbl 1457.74073 · doi:10.1007/s10483-020-2604-6 |
| [14] | R. A. Maronna, R. D. Martin, V. J. Yohai and M. Salibian-Barrera, Robust Statistics, Wiley Series in Probability and Statistics, 2 ed., John Wiley & Sons, Nashville, TN, (2018). |
| [15] | T. Masuda, H. Miyano and T. Sadoyama, The measurement of muscle fiber conduction velocity using a gradient threshold zero-crossing method, IEEE Transactions on Biomedical Engineering, BME-29 (1982), 673-678. doi: 10.1109/TBME.1982.324859. · doi:10.1109/TBME.1982.324859 |
| [16] | MathWorks, dsp.zerocrossingdetector, (2012), https://www.mathworks.com/help/dsp/ref/dsp.zerocrossingdetector-system-object.html. |
| [17] | P. Misans and M. Terauds, Cw doppler radar based land vehicle speed measurement algorithm using zero crossing and least squares method, Proceedings of the Biennial Baltic Electronics Conference, BEC, (2012). doi: 10.1109/BEC.2012.6376841. · doi:10.1109/BEC.2012.6376841 |
| [18] | A. Molinaro and Y. D. Sergeyev, An efficient algorithm for the zero crossing detection in digitized measurement signal, Measurement, 30 (2001), 187-196. doi: 10.1016/s0263-2241(01)00002-1. · doi:10.1016/s0263-2241(01)00002-1 |
| [19] | E. Munch, A user’s guide to topological data analysis, Journal of Learning Analytics, 4 (2017). doi: 10.18608/jla.2017.42.6. · doi:10.18608/jla.2017.42.6 |
| [20] | A. Myers, F. Khasawneh, J. Tempelman and D. Petrushenko, Low-cost double pendulum for high-quality data collection with open-source video tracking and analysis, (2020). doi: 10.17632/7YD2NTBH3W.1. · doi:10.17632/7YD2NTBH3W.1 |
| [21] | A. D. Myers, J. R. Tempelman, D. Petrushenko and F. A. Khasawneh, Low-cost double pendulum for high-quality data collection with open-source video tracking and analysis, HardwareX, 8 (2020), e00138. doi: 10.1016/j.ohx.2020.e00138. · doi:10.1016/j.ohx.2020.e00138 |
| [22] | A. D. Myers, M. Yesilli, S. Tymochko, F. Khasawneh and E. Munch, Teaspoon: A comprehensive python package for topological signal processing, in: TDA & Beyond, (2020). URL: https://openreview.net/forum?id = qUoVqrIcy2P. |
| [23] | S. Y. Oudot, Persistence Theory: From Quiver Representations to Data Analysis, Mathematical Surveys and Monographs, American Mathematical Society, (2017). doi: 10.1090/surv/209. · doi:10.1090/surv/209 |
| [24] | F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot and E. Duchesnay, Scikit-learn: Machine learning in Python, Journal of Machine Learning Research, 12 (2011), 2825-2830. · Zbl 1280.68189 |
| [25] | R. M. Pindoriya, A. K. Mishra, B. S. Rajpurohit and R. Kumar, Analysis of position and speed control of sensorless bldc motor using zero crossing back-emf technique, 1st IEEE International Conference on Power Electronics, Intelligent Control and Energy Systems, ICPEICES 2016, (2017). doi: 10.1109/ICPEICES.2016.7853072. · doi:10.1109/ICPEICES.2016.7853072 |
| [26] | W. H. Press, S. A. Teukolsky, W. T. Vetterling and B. P. Flannery, Numerical recipes: The art of scientific computing, 3rd edition ed., Cambridge University Press, chapter chapter9, (2007), p. 459. |
| [27] | S. K. Rahman, D. A. Mohammed, B. M. Hussein, B. A. Salam and K. R. Mohammed, An improved bracketing method for numerical solution of nonlinear equations based on ridders method, Matrix Science Mathematic, 6 (2022), 30-33. doi: 10.26480/msmk.02.2022.30.33. · doi:10.26480/msmk.02.2022.30.33 |
| [28] | G. Raju, Recognition of unconstrained handwritten malayalam characters using zero-crossing of wavelet coefficients, Proceedings - 2006 14th International Conference on Advanced Computing and Communications, ADCOM 2006. doi: 10.1109/ADCOM.2006.4289886. · doi:10.1109/ADCOM.2006.4289886 |
| [29] | N. N. R. Ranga Suri, N. Murty and G. Athithan, Outlier Detection: Techniques and Applications, Intelligent Systems Reference Library. 1 ed., Springer International Publishing, Basel, Switzerland, (2019). doi: 10.1007/978-3-030-05127-3. · doi:10.1007/978-3-030-05127-3 |
| [30] | M. A. Razbani, Global root bracketing method with adaptive mesh refinement, Applied Mathematics and Computation, 268 (2015), 628-635. doi: 10.1016/j.amc.2015.06.121. · Zbl 1410.65170 · doi:10.1016/j.amc.2015.06.121 |
| [31] | A. Sadrpour, L. G. Crespo and S. P. Kenny, Analysis of nonlinear systems via bernstein expansions, AIAA Guidance, Navigation, and Control (GNC) Conference, (2013). doi: 10.2514/6.2013-4557. · doi:10.2514/6.2013-4557 |
| [32] | C. E. Shannon, A mathematical theory of communication, Bell System Technical Journal, 27 (1948), 379-423. doi: 10.1002/j.1538-7305.1948.tb01338.x. · Zbl 1154.94303 · doi:10.1002/j.1538-7305.1948.tb01338.x |
| [33] | G. Smecher and B. Champagne, Optimum crossing-point estimation of a sampled analog signal with a periodic carrier, Signal Processing, 91 (2011), 1951-1962. doi: 10.1016/j.sigpro.2011.02.018. · Zbl 1217.94064 · doi:10.1016/j.sigpro.2011.02.018 |
| [34] | K. R. Sreenivasan, A. Prabhu and R. Narasimha, Zero-crossings in turbulent signals, J. Fluid Mech, 137 (1983), 251-272. doi: 10.1017/S0022112083002396. · doi:10.1017/S0022112083002396 |
| [35] | S. Srinivasan and J. Ophir, A zero-crossing strain estimator for elastography, Ultrasound in Medicine & Biology, 29 (2003), 227-238. URL: https://www.sciencedirect.com/science/article/pii/S030156290200697X. doi: 10.1016/S0301-5629(02)00697-X. · doi:10.1016/S0301-5629(02)00697-X |
| [36] | A. Suhadolnik, Combined bracketing methods for solving nonlinear equations, Applied Mathematics Letters, 25 (2012), 1755-1760. doi: 10.1016/j.aml.2012.02.006. · Zbl 1253.65074 · doi:10.1016/j.aml.2012.02.006 |
| [37] | A. Suhadolnik, Superlinear bracketing method for solving nonlinear equations, Applied Mathematics and Computation, 219 (2013), 7369-7376. doi: 10.1016/j.amc.2012.12.064. · Zbl 1288.65067 · doi:10.1016/j.amc.2012.12.064 |
| [38] | S. Tanweer, GitHub - stanweer1/zeros-using-tsp, (2024), https://github.com/stanweer1/Zeros-using-TSP. |
| [39] | A. Ukil, S. Chen and A. Andenna, Detection of stator short circuit faults in three-phase induction motors using motor current zero-crossing instants, Electric Power Systems Research, 81 (2011), 1036-1044. doi: 10.1016/j.epsr.2010.12.003. · doi:10.1016/j.epsr.2010.12.003 |
| [40] | M. Vetterli, P. Marziliano and T. Blu, Sampling signals with finite rate of innovation, IEEE Transactions on Signal Processing, 50 (2002), 1417-1428. doi: 10.1109/TSP.2002.1003065. · Zbl 1369.94309 · doi:10.1109/TSP.2002.1003065 |
| [41] | R. W. Wall, Simple methods for detecting zero crossing, IECON Proceedings (Industrial Electronics Conference), 3 (2003), 2477-2481. doi: 10.1109/IECON.2003.1280634. · doi:10.1109/IECON.2003.1280634 |
| [42] | W. Zijlstra and A. L. Hof, Assessment of spatio-temporal gait parameters from trunk accelerations during human walking, Gait & Posture, 18 (2003), 1-10. doi: 10.1016/S0966-6362(02)00190-X. · doi:10.1016/S0966-6362(02)00190-X |
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.
