June  2022, 4(2): 243-269. doi: 10.3934/fods.2022005

ANAPT: Additive noise analysis for persistence thresholding

1. 

Michigan State University, College of Engineering, East Lansing, MI 48824-1226, USA

2. 

Montana State University, School of Computing & Dept. of Mathematical Sciences, Bozeman, MT 59717, USA

* Corresponding author: Audun D. Myers

Received  September 2021 Revised  December 2021 Published  June 2022 Early access  March 2022

Fund Project: The first author is supported by NSF grants CMMI-1759823 and DMS-1759824

We introduce a novel method for Additive Noise Analysis for Persistence Thresholding (ANAPT) which separates significant features in the sublevel set persistence diagram of a time series based on a statistics analysis of the persistence of a noise distribution. Specifically, we consider an additive noise model and leverage the statistical analysis to provide a noise cutoff or confidence interval in the persistence diagram for the observed time series. This analysis is done for several common noise models including Gaussian, uniform, exponential, and Rayleigh distributions. ANAPT is computationally efficient, does not require any signal pre-filtering, is widely applicable, and has open-source software available. We demonstrate the functionality of ANAPT with both numerically simulated examples and an experimental data set. Additionally, we provide an efficient $ \Theta(n\log(n)) $ algorithm for calculating the zero-dimensional sublevel set persistence homology.

Citation: Audun D. Myers, Firas A. Khasawneh, Brittany T. Fasy. ANAPT: Additive noise analysis for persistence thresholding. Foundations of Data Science, 2022, 4 (2) : 243-269. doi: 10.3934/fods.2022005
References:
[1]

N. AtienzaR. Gonzalez-Diaz and M. Rucco, Persistent entropy for separating topological features from noise in vietoris-rips complexes, Journal of Intelligent Information Systems, 52 (2017), 637-655.  doi: 10.1007/s10844-017-0473-4.

[2]

G. E. P. Box, G. M. Jenkins, G. C. Reinsel and G. M. Ljung, Time Series Analysis: Forecasting and Control, John Wiley & Sons, 2016.

[3]

P. Bubenik, Statistical topological data analysis using persistence landscapes, Journal of Machine Learning Research, 16 (2015), 77-102. 

[4]

P. Bühlmann and P. Buhlmann, Sieve bootstrap for time series, Bernoulli, 3 (1997), 123-148.  doi: 10.2307/3318584.

[5]

G. Carlsson, J. Gorham, M. Kahle and J. Mason, Computational topology for configuration spaces of hard disks,, Physical Review E, 85 (2012), 011303. doi: 10.1103/PhysRevE. 85.011303.

[6]

F. Chazal, V. De Silva, M. Glisse and S. Oudot, The Structure and Stability of Persistence Modules, SpringerBriefs in Mathematics. Springer, [Cham], 2016. doi: 10.1007/978-3-319-42545-0.

[7]

F. Chazal, B. T. Fasy, F. Lecci, B. Michel, A. Rinaldo and L. Wasserman, Robust topological inference: Distance to a measure and kernel distance, J. Mach. Learn. Res., 18 (2018), Paper No. 159, 40 pp.

[8]

F. Chazal, B. T. Fasy, F. Lecci, A. Rinaldo, A. Singh and L. Wasserman, On the bootstrap for persistence diagrams and landscapes, arXiv preprint, arXiv: 1311.0376, 2013.

[9]

S. Chowdhury and F. Mémoli, Convergence of hierarchical clustering and persistent homology methods on directed networks, Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 1152–1169, SIAM, Philadelphia, PA, 2018. doi: 10.1137/1.9781611975031.75.

[10]

D. Cohen-SteinerH. Edelsbrunner and J. Harer, Stability of persistence diagrams, Discrete & Computational Geometry, 37 (2006), 103-120.  doi: 10.1007/s00454-006-1276-5.

[11]

S. Czesla, T. Molle and J. H. M. M. Schmitt, A posteriori noise estimation in variable data sets, Astronomy & Astrophysics, 609 (2018), A39. doi: 10.1051/0004-6361/201730618.

[12]

C. J. A. Delfinado and H. Edelsbrunner, An incremental algorithm for Betti numbers of simplicial complexes on the 3-sphere, Computer Aided Geometric Design, 12 (1995), 771-784.  doi: 10.1016/0167-8396(95)00016-Y.

[13]

M. Dindin, Y. Umeda and F. Chazal, Topological data analysis for arrhythmia detection through modular neural networks, In Advances in Artificial Intelligence, 2020, 177–188. doi: 10.1007/978-3-030-47358-7_17.

[14]

H. Edelsbrunner and J. Harer, Computational Topology - an Introduction, American Mathematical Society, Providence, RI, 2010. doi: 10.1090/mbk/069.

[15]

H. Edelsbrunner and J. Harer, Persistent homology-a survey, Contemporary Mathematics, 453 (2008), 257-282.  doi: 10.1090/conm/453/08802.

[16]

H. EdelsbrunnerD. Letscher and A. Zomorodian, Topological persistence and simplification, Discrete & Computational Geometry, 28 (2002), 511-533.  doi: 10.1007/s00454-002-2885-2.

[17]

B. T. FasyF. LecciA. RinaldoL. WassermanS. BalakrishnanA. Singh and et al., Confidence sets for persistence diagrams, The Annals of Statistics, 42 (2014), 2301-2339.  doi: 10.1214/14-AOS1252.

[18]

S. Gholizadeh and W. Zadrozny, A short survey of topological data analysis in time series and systems analysis, arXiv preprint, arXiv: 1809.10745, 2018.

[19]

J. HuJ. B. Gao and K. D. White, Estimating measurement noise in a time series by exploiting nonstationarity, Chaos, Solitons & Fractals, 22 (2004), 807-819.  doi: 10.1016/j.chaos.2004.02.061.

[20]

F. A. Khasawneh and E. Munch, Utilizing topological data analysis for studying signals of time-delay systems, Time Delay Systems, Adv. Delays Dyn., Springer, Cham, 7 (2017), 93–106.

[21]

F. A. Khasawneh and E. Munch, Topological data analysis for true step detection in periodic piecewise constant signals, Proceedings of the Royal Society A: Mathematical, Physical and Engineering Science, 474 (2018), 20180027, 24pp. doi: 10.1098/rspa. 2018.0027.

[22]

F. A. Khasawneh, E. Munch and J. A. Perea, Chatter classification in turning using machine learning and topological data analysis, IFAC-PapersOnLine, 51 (2018), 195–200. doi: 10.1016/j. ifacol. 2018.07.222.

[23]

P. Lawson, A. B. Sholl, J. Quincy Brown, B. Terese Fasy and C. Wenk, Persistent homology for the quantitative evaluation of architectural features in prostate cancer histology, Scientific Reports, 9 (2019), Article number: 1139. doi: 10.1038/s41598-018-36798-y.

[24]

H. Lee, H. Kang, M. K. Chung, B. -N. Kim and D. S. Lee, Persistent brain network homology from the perspective of dendrogram, IEEE Transactions on Medical Imaging, 31 (2012), 2267–2277. doi: 10.1109/TMI. 2012.2219590.

[25]

E. Munch, A user's guide to topological data analysis, Journal of Learning Analytics, 4, 2017. doi: 10.18608/jla. 2017.42.6.

[26]

A. Myers and F. A. Khasawneh, On the automatic parameter selection for permutation entropy, Chaos: An Interdisciplinary Journal of Nonlinear Science, 30 (2020), 033130, 17 pp. doi: 10.1063/1.5111719.

[27]

A. Myers, E. Munch and F. A Khasawneh, Persistent homology of complex networks for dynamic state detection, Phys. Rev. E, 100 (2019), 022314, 14 pp. doi: 10.1103/physreve. 100.022314.

[28]

A. Otto, M. C. Yesilli and F. A. Khasawneh, Topological feature vectors for chatter detection in turning processes, The International Journal of Advanced Manufacturing Technology, 2022. arXiv: 1905.08671. doi: 10.1007/s00170-021-08242-5.

[29]

J. A. Perea, A brief history of persistence.,

[30]

J. A. Perea and J. Harer, Sliding windows and persistence: An application of topological methods to signal analysis, Foundations of Computational Mathematics, 15 (2015), 799-838.  doi: 10.1007/s10208-014-9206-z.

[31]

D. Petrushenko and F. A. Khasawneh, Uncertainty propagation of system parameters to the dynamic response: An application to a benchtop pendulum, ASME 2017 International Mechanical Engineering Congress and Exposition, 2018, 10 pages. doi: 10.1115/IMECE2017-71105.

[32]

D. N. Politis and J. P. Romano, The stationary bootstrap, Journal of the American Statistical Association, 89 (1994), 1303-1313.  doi: 10.1080/01621459.1994.10476870.

[33]

M. Rucco, F. Castiglione, E. Merelli and M. Pettini, Characterisation of the idiotypic immune network through persistent entropy, In Proceedings of ECCS 2014, Springer International Publishing, 2016, 117–128. doi: 10.1007/978-3-319-29228-1_11.

[34]

F. Takens, Detecting strange attractors in turbulence, Dynamical Systems and Turbulence, Warwick 1980 (Coventry, 1979/1980), 366–381, Lecture Notes in Math., 898, Springer, Berlin-New York, 1981.

[35]

C. J. Tralie and J. A. Perea, (Quasi)periodicity quantification in video data, using topology, SIAM Journal on Imaging Sciences, 11 (2018), 1049–1077. doi: 10.1137/17M1150736.

[36]

K. Urbanowicz and J. A. Hołyst, Noise-level estimation of time series using coarse-grained entropy, Physical Review E, 67 (2003), 046218.  doi: 10.1103/PhysRevE.67.046218.

[37]

X. Wan, W. Wang, J. Liu and T. Tong, Estimating the sample mean and standard deviation from the sample size, median, range and/or interquartile range, BMC Medical Research Methodology, 14 (2014), Article number: 135. doi: 10.1186/1471-2288-14-135.

[38]

G. R. Wood and B. P. Zhang, Estimation of the lipschitz constant of a function, Journal of Global Optimization, 8 (1996), 91-103.  doi: 10.1007/BF00229304.

show all references

References:
[1]

N. AtienzaR. Gonzalez-Diaz and M. Rucco, Persistent entropy for separating topological features from noise in vietoris-rips complexes, Journal of Intelligent Information Systems, 52 (2017), 637-655.  doi: 10.1007/s10844-017-0473-4.

[2]

G. E. P. Box, G. M. Jenkins, G. C. Reinsel and G. M. Ljung, Time Series Analysis: Forecasting and Control, John Wiley & Sons, 2016.

[3]

P. Bubenik, Statistical topological data analysis using persistence landscapes, Journal of Machine Learning Research, 16 (2015), 77-102. 

[4]

P. Bühlmann and P. Buhlmann, Sieve bootstrap for time series, Bernoulli, 3 (1997), 123-148.  doi: 10.2307/3318584.

[5]

G. Carlsson, J. Gorham, M. Kahle and J. Mason, Computational topology for configuration spaces of hard disks,, Physical Review E, 85 (2012), 011303. doi: 10.1103/PhysRevE. 85.011303.

[6]

F. Chazal, V. De Silva, M. Glisse and S. Oudot, The Structure and Stability of Persistence Modules, SpringerBriefs in Mathematics. Springer, [Cham], 2016. doi: 10.1007/978-3-319-42545-0.

[7]

F. Chazal, B. T. Fasy, F. Lecci, B. Michel, A. Rinaldo and L. Wasserman, Robust topological inference: Distance to a measure and kernel distance, J. Mach. Learn. Res., 18 (2018), Paper No. 159, 40 pp.

[8]

F. Chazal, B. T. Fasy, F. Lecci, A. Rinaldo, A. Singh and L. Wasserman, On the bootstrap for persistence diagrams and landscapes, arXiv preprint, arXiv: 1311.0376, 2013.

[9]

S. Chowdhury and F. Mémoli, Convergence of hierarchical clustering and persistent homology methods on directed networks, Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 1152–1169, SIAM, Philadelphia, PA, 2018. doi: 10.1137/1.9781611975031.75.

[10]

D. Cohen-SteinerH. Edelsbrunner and J. Harer, Stability of persistence diagrams, Discrete & Computational Geometry, 37 (2006), 103-120.  doi: 10.1007/s00454-006-1276-5.

[11]

S. Czesla, T. Molle and J. H. M. M. Schmitt, A posteriori noise estimation in variable data sets, Astronomy & Astrophysics, 609 (2018), A39. doi: 10.1051/0004-6361/201730618.

[12]

C. J. A. Delfinado and H. Edelsbrunner, An incremental algorithm for Betti numbers of simplicial complexes on the 3-sphere, Computer Aided Geometric Design, 12 (1995), 771-784.  doi: 10.1016/0167-8396(95)00016-Y.

[13]

M. Dindin, Y. Umeda and F. Chazal, Topological data analysis for arrhythmia detection through modular neural networks, In Advances in Artificial Intelligence, 2020, 177–188. doi: 10.1007/978-3-030-47358-7_17.

[14]

H. Edelsbrunner and J. Harer, Computational Topology - an Introduction, American Mathematical Society, Providence, RI, 2010. doi: 10.1090/mbk/069.

[15]

H. Edelsbrunner and J. Harer, Persistent homology-a survey, Contemporary Mathematics, 453 (2008), 257-282.  doi: 10.1090/conm/453/08802.

[16]

H. EdelsbrunnerD. Letscher and A. Zomorodian, Topological persistence and simplification, Discrete & Computational Geometry, 28 (2002), 511-533.  doi: 10.1007/s00454-002-2885-2.

[17]

B. T. FasyF. LecciA. RinaldoL. WassermanS. BalakrishnanA. Singh and et al., Confidence sets for persistence diagrams, The Annals of Statistics, 42 (2014), 2301-2339.  doi: 10.1214/14-AOS1252.

[18]

S. Gholizadeh and W. Zadrozny, A short survey of topological data analysis in time series and systems analysis, arXiv preprint, arXiv: 1809.10745, 2018.

[19]

J. HuJ. B. Gao and K. D. White, Estimating measurement noise in a time series by exploiting nonstationarity, Chaos, Solitons & Fractals, 22 (2004), 807-819.  doi: 10.1016/j.chaos.2004.02.061.

[20]

F. A. Khasawneh and E. Munch, Utilizing topological data analysis for studying signals of time-delay systems, Time Delay Systems, Adv. Delays Dyn., Springer, Cham, 7 (2017), 93–106.

[21]

F. A. Khasawneh and E. Munch, Topological data analysis for true step detection in periodic piecewise constant signals, Proceedings of the Royal Society A: Mathematical, Physical and Engineering Science, 474 (2018), 20180027, 24pp. doi: 10.1098/rspa. 2018.0027.

[22]

F. A. Khasawneh, E. Munch and J. A. Perea, Chatter classification in turning using machine learning and topological data analysis, IFAC-PapersOnLine, 51 (2018), 195–200. doi: 10.1016/j. ifacol. 2018.07.222.

[23]

P. Lawson, A. B. Sholl, J. Quincy Brown, B. Terese Fasy and C. Wenk, Persistent homology for the quantitative evaluation of architectural features in prostate cancer histology, Scientific Reports, 9 (2019), Article number: 1139. doi: 10.1038/s41598-018-36798-y.

[24]

H. Lee, H. Kang, M. K. Chung, B. -N. Kim and D. S. Lee, Persistent brain network homology from the perspective of dendrogram, IEEE Transactions on Medical Imaging, 31 (2012), 2267–2277. doi: 10.1109/TMI. 2012.2219590.

[25]

E. Munch, A user's guide to topological data analysis, Journal of Learning Analytics, 4, 2017. doi: 10.18608/jla. 2017.42.6.

[26]

A. Myers and F. A. Khasawneh, On the automatic parameter selection for permutation entropy, Chaos: An Interdisciplinary Journal of Nonlinear Science, 30 (2020), 033130, 17 pp. doi: 10.1063/1.5111719.

[27]

A. Myers, E. Munch and F. A Khasawneh, Persistent homology of complex networks for dynamic state detection, Phys. Rev. E, 100 (2019), 022314, 14 pp. doi: 10.1103/physreve. 100.022314.

[28]

A. Otto, M. C. Yesilli and F. A. Khasawneh, Topological feature vectors for chatter detection in turning processes, The International Journal of Advanced Manufacturing Technology, 2022. arXiv: 1905.08671. doi: 10.1007/s00170-021-08242-5.

[29]

J. A. Perea, A brief history of persistence.,

[30]

J. A. Perea and J. Harer, Sliding windows and persistence: An application of topological methods to signal analysis, Foundations of Computational Mathematics, 15 (2015), 799-838.  doi: 10.1007/s10208-014-9206-z.

[31]

D. Petrushenko and F. A. Khasawneh, Uncertainty propagation of system parameters to the dynamic response: An application to a benchtop pendulum, ASME 2017 International Mechanical Engineering Congress and Exposition, 2018, 10 pages. doi: 10.1115/IMECE2017-71105.

[32]

D. N. Politis and J. P. Romano, The stationary bootstrap, Journal of the American Statistical Association, 89 (1994), 1303-1313.  doi: 10.1080/01621459.1994.10476870.

[33]

M. Rucco, F. Castiglione, E. Merelli and M. Pettini, Characterisation of the idiotypic immune network through persistent entropy, In Proceedings of ECCS 2014, Springer International Publishing, 2016, 117–128. doi: 10.1007/978-3-319-29228-1_11.

[34]

F. Takens, Detecting strange attractors in turbulence, Dynamical Systems and Turbulence, Warwick 1980 (Coventry, 1979/1980), 366–381, Lecture Notes in Math., 898, Springer, Berlin-New York, 1981.

[35]

C. J. Tralie and J. A. Perea, (Quasi)periodicity quantification in video data, using topology, SIAM Journal on Imaging Sciences, 11 (2018), 1049–1077. doi: 10.1137/17M1150736.

[36]

K. Urbanowicz and J. A. Hołyst, Noise-level estimation of time series using coarse-grained entropy, Physical Review E, 67 (2003), 046218.  doi: 10.1103/PhysRevE.67.046218.

[37]

X. Wan, W. Wang, J. Liu and T. Tong, Estimating the sample mean and standard deviation from the sample size, median, range and/or interquartile range, BMC Medical Research Methodology, 14 (2014), Article number: 135. doi: 10.1186/1471-2288-14-135.

[38]

G. R. Wood and B. P. Zhang, Estimation of the lipschitz constant of a function, Journal of Global Optimization, 8 (1996), 91-103.  doi: 10.1007/BF00229304.

Figure 1.  Persistence diagram summarizing the sublevel sets of a function $ f(t) $ over finite domain $ t \in[t_a, t_b] $. This function has two local minima (blue squares) and two local maxima (red circles
Figure 2.  Sublevel set persistence applied to $ x(t) $ of a single variable function or time series with and without additive noise $ \epsilon $ from $ \mathcal{N} $, shown in red and blue, respectively. This demonstrates the stability of persistent homology with the time series (left) with and without additive noise and the small effect on the resulting persistence diagrams (right). In addition, the light red region separates the significant features from those associated to additive noise
Figure 3.  Histograms $ h(*) $ of the zero mean normal distriubtion $ \mathcal{N}(0,\sigma^2 =1) $ and the resulting birth times $ B $ and death times $ D $, which are compared to the density distributions from Equation(5)
Figure 4.  Additive noise probability distributions $ f(z) $ for the four models realized in this work: uniform, Gaussian, Rayleigh, and exponential
Figure 5.  Example time series showing sample $ \delta_i $
Figure 6.  Numeric function fitting of Equationk__ge (52) to the mean of the median lifetime $ \tilde{L} $ of $ f_i(t) $ for $ i \in [1,3] $ where $ \mathcal{N} $ is unit variance Gaussian additive noise with $ \delta \in [0,2] $ being incremented to understand the effects of signal on the median lifetime
Figure 7.  Demonstration of distribution parameter $ \sigma $ estimation of Gaussian additive noise in $ x(t) = A\sin(\pi t) + \mathcal{N} $ using the median lifetime with and without signal compensation as $ \sigma $ and $ \sigma^* $, respectively
Figure 8.  Comparison between the persistent homology, bootstrap resampling, and ANAPT methods for separating noise from topological signal in the sublevel set persistence diagram. The example signal is generated from a chaotic Lorenz system
Figure 9.  Comparison of distribution parameter estimation techniques (low-Pass filter residuals, cubic spline residuals, and sublevel set persistence) for estimating $ \sigma $ of the additive Gaussian noise contaminating the $ x(t) $ solution of the Lorenz system in Eq.55
Figure 10.  Numerical simulations with $ 10^5 $ data points for each of the four investigated noise models with probability densities on the top row and lifetime probability densities on the bottom row with their associated cutoff $ C_\alpha $. The distribution parameters were set as $ \sigma = \Delta = \lambda = \sigma = 1 $ and were estimated as $ \sigma \approx 0.996 $, $ \Delta \approx 1.013 $, $ \lambda \approx 1.009 $, and $ \sigma \approx 0.998 $ for the Gaussian, uniform, Rayleigh, and exponential distributions, respectively
Figure 11.  Example cutoff calculation for time series $ x(t) = A(\sin(\pi t) + \sin(t)) + \epsilon $, where $ \epsilon $ is additive noise from a Gaussian distribution with zero mean and four different standard deviations as $ \sigma \in [0.2, 1, 2, 4] $. The resulting sublevel set persistence diagrams with cutoff $ C_\alpha^* $ are shown to the right
Figure 12.  Experimental time series from free drop response of single pendulum with corresponding cutoffs in the persistence diagram and time-order lifetimes plot
Figure 13.  Histogram of the highlighted section of signal in Fig. 12 with fitted Rayleigh distribution
Table 1.  Ratios $ \rho = \bar{L} / \tilde{L} $ for estimating sample mean from the sample median with uncertainty as three standard deviations
Distribution Gussian Uniform Rayleigh Exponential
$ \rho = \bar{L}/\tilde{L} $ $ 1.154 \pm 0.012 $ $ 1.000 \pm 0.010 $ $ 1.136 \pm 0.013 $ $ 1.265 \pm 0.016 $
Distribution Gussian Uniform Rayleigh Exponential
$ \rho = \bar{L}/\tilde{L} $ $ 1.154 \pm 0.012 $ $ 1.000 \pm 0.010 $ $ 1.136 \pm 0.013 $ $ 1.265 \pm 0.016 $
Table 2.  Constants of Equation (52) for each distribution type investigated in this work with associated uncertainty from ten trials
Distribution Gussian Uniform Rayleigh Exponential
$ c_1 $ $ 0.845 \pm 0.029 $ $ 0.880 \pm 0.017 $ $ 0.726 \pm 0.026 $ $ 0.436 \pm 0.036 $
$ c_2 $ $ 0.809 \pm 0.061 $ $ 0.639 \pm 0.026 $ $ 0.605 \pm 0.054 $ $ 0.393 \pm 0.075 $
Distribution Gussian Uniform Rayleigh Exponential
$ c_1 $ $ 0.845 \pm 0.029 $ $ 0.880 \pm 0.017 $ $ 0.726 \pm 0.026 $ $ 0.436 \pm 0.036 $
$ c_2 $ $ 0.809 \pm 0.061 $ $ 0.639 \pm 0.026 $ $ 0.605 \pm 0.054 $ $ 0.393 \pm 0.075 $
Algorithm 1.  Zero-Dimensional Persistence Algorithm
Data: Array A of n Real Numbers
Result: Persistence Diagram
$\begin{array}{l} {\bf{begin}}\\ \;\;\left| \begin{array}{l} \;\;\;\;M = {\rm{list}}\;{\rm{of}}\;{\rm{local}}\;{\rm{extrema}}\;{\rm{in}}\;A\left( {{\rm{non - endpoint}}\;{\rm{maxima}}\;{\rm{and}}\;{\rm{minima}}} \right);\\ \;\;\;\;Q = {\rm{priority}}\;{\rm{queue}}\;{\rm{of}}\;{\rm{pointers}}\;{\rm{to}}\;{\rm{elements}}\;{\rm{of}}\;M;\\ \;\;\;\;{\bf{while}}\;\left| M \right| > 3\;{\bf{do}}\\ \;\;\;\;\;\;\left| \begin{array}{l} m \leftarrow Q.pop;\\ b \leftarrow {\rm{min}}\left\{ {m.height,m.next.height} \right\};\\ d \leftarrow {\rm{max}}\left\{ {m.height,m.next.height} \right\};\\ {\rm{Add}}\;(b,d){\rm{ to}}\;pairs;\\ {\rm{Update}}\;Q\;{\rm{and}}\;M; \end{array} \right.\\ \;\;\;\;{\bf{end}}\\ \;\;\;\;{\bf{return}}\;pairs \end{array} \right.\\ {\bf{end}} \end{array}$
Data: Array A of n Real Numbers
Result: Persistence Diagram
$\begin{array}{l} {\bf{begin}}\\ \;\;\left| \begin{array}{l} \;\;\;\;M = {\rm{list}}\;{\rm{of}}\;{\rm{local}}\;{\rm{extrema}}\;{\rm{in}}\;A\left( {{\rm{non - endpoint}}\;{\rm{maxima}}\;{\rm{and}}\;{\rm{minima}}} \right);\\ \;\;\;\;Q = {\rm{priority}}\;{\rm{queue}}\;{\rm{of}}\;{\rm{pointers}}\;{\rm{to}}\;{\rm{elements}}\;{\rm{of}}\;M;\\ \;\;\;\;{\bf{while}}\;\left| M \right| > 3\;{\bf{do}}\\ \;\;\;\;\;\;\left| \begin{array}{l} m \leftarrow Q.pop;\\ b \leftarrow {\rm{min}}\left\{ {m.height,m.next.height} \right\};\\ d \leftarrow {\rm{max}}\left\{ {m.height,m.next.height} \right\};\\ {\rm{Add}}\;(b,d){\rm{ to}}\;pairs;\\ {\rm{Update}}\;Q\;{\rm{and}}\;M; \end{array} \right.\\ \;\;\;\;{\bf{end}}\\ \;\;\;\;{\bf{return}}\;pairs \end{array} \right.\\ {\bf{end}} \end{array}$
[1]

Christopher Oballe, Alan Cherne, Dave Boothe, Scott Kerick, Piotr J. Franaszczuk, Vasileios Maroulas. Bayesian topological signal processing. Discrete and Continuous Dynamical Systems - S, 2022, 15 (4) : 797-817. doi: 10.3934/dcdss.2021084

[2]

Hassan Abdallah, Adam Regalski, Mohammad Behzad Kang, Maria Berishaj, Nkechi Nnadi, Asadur Chowdury, Vaibhav A. Diwadkar, Andrew Salch. Statistical inference for persistent homology applied to simulated fMRI time series data. Foundations of Data Science, 2022  doi: 10.3934/fods.2022014

[3]

Annalisa Pascarella, Alberto Sorrentino, Cristina Campi, Michele Piana. Particle filtering, beamforming and multiple signal classification for the analysis of magnetoencephalography time series: a comparison of algorithms. Inverse Problems and Imaging, 2010, 4 (1) : 169-190. doi: 10.3934/ipi.2010.4.169

[4]

Yuanjia Ma. The optimization algorithm for blind processing of high frequency signal of capacitive sensor. Discrete and Continuous Dynamical Systems - S, 2019, 12 (4&5) : 1399-1412. doi: 10.3934/dcdss.2019096

[5]

George Siopsis. Quantum topological data analysis with continuous variables. Foundations of Data Science, 2019, 1 (4) : 419-431. doi: 10.3934/fods.2019017

[6]

Tyrus Berry, Timothy Sauer. Consistent manifold representation for topological data analysis. Foundations of Data Science, 2019, 1 (1) : 1-38. doi: 10.3934/fods.2019001

[7]

Erik Carlsson, John Gunnar Carlsson, Shannon Sweitzer. Applying topological data analysis to local search problems. Foundations of Data Science, 2022  doi: 10.3934/fods.2022006

[8]

Ji-Bo Wang, Bo Zhang, Hongyu He. A unified analysis for scheduling problems with variable processing times. Journal of Industrial and Management Optimization, 2022, 18 (2) : 1063-1077. doi: 10.3934/jimo.2021008

[9]

Aymen Alian, Yu-Lun Lo, Kirk Shelley, Hau-Tieng Wu. Reconsider phase reconstruction in signals with dynamic periodicity from the modern signal processing perspective. Foundations of Data Science, 2022, 4 (3) : 355-393. doi: 10.3934/fods.2022010

[10]

Akram Aldroubi, Rocio Diaz Martin, Ivan Medri, Gustavo K. Rohde, Sumati Thareja. The Signed Cumulative Distribution Transform for 1-D signal analysis and classification. Foundations of Data Science, 2022, 4 (1) : 137-163. doi: 10.3934/fods.2022001

[11]

Li Gang. An optimization detection algorithm for complex intrusion interference signal in mobile wireless network. Discrete and Continuous Dynamical Systems - S, 2019, 12 (4&5) : 1371-1384. doi: 10.3934/dcdss.2019094

[12]

Jason R. Scott, Stephen Campbell. Auxiliary signal design for failure detection in differential-algebraic equations. Numerical Algebra, Control and Optimization, 2014, 4 (2) : 151-179. doi: 10.3934/naco.2014.4.151

[13]

Tsuguhito Hirai, Hiroyuki Masuyama, Shoji Kasahara, Yutaka Takahashi. Performance analysis of large-scale parallel-distributed processing with backup tasks for cloud computing. Journal of Industrial and Management Optimization, 2014, 10 (1) : 113-129. doi: 10.3934/jimo.2014.10.113

[14]

Jiping Tao, Zhijun Chao, Yugeng Xi. A semi-online algorithm and its competitive analysis for a single machine scheduling problem with bounded processing times. Journal of Industrial and Management Optimization, 2010, 6 (2) : 269-282. doi: 10.3934/jimo.2010.6.269

[15]

Yu-Ting Lin, John Malik, Hau-Tieng Wu. Wave-shape oscillatory model for nonstationary periodic time series analysis. Foundations of Data Science, 2021, 3 (2) : 99-131. doi: 10.3934/fods.2021009

[16]

Jelena Grbić, Jie Wu, Kelin Xia, Guo-Wei Wei. Aspects of topological approaches for data science. Foundations of Data Science, 2022, 4 (2) : 165-216. doi: 10.3934/fods.2022002

[17]

Domenica Borra, Tommaso Lorenzi. Asymptotic analysis of continuous opinion dynamics models under bounded confidence. Communications on Pure and Applied Analysis, 2013, 12 (3) : 1487-1499. doi: 10.3934/cpaa.2013.12.1487

[18]

Weidong Bao, Wenhua Xiao, Haoran Ji, Chao Chen, Xiaomin Zhu, Jianhong Wu. Towards big data processing in clouds: An online cost-minimization approach. Big Data & Information Analytics, 2016, 1 (1) : 15-29. doi: 10.3934/bdia.2016.1.15

[19]

Min-Fan He, Li-Ning Xing, Wen Li, Shang Xiang, Xu Tan. Double layer programming model to the scheduling of remote sensing data processing tasks. Discrete and Continuous Dynamical Systems - S, 2019, 12 (4&5) : 1515-1526. doi: 10.3934/dcdss.2019104

[20]

Roger Metzger, Carlos Arnoldo Morales Rojas, Phillipe Thieullen. Topological stability in set-valued dynamics. Discrete and Continuous Dynamical Systems - B, 2017, 22 (5) : 1965-1975. doi: 10.3934/dcdsb.2017115

 Impact Factor: 

Metrics

  • PDF downloads (230)
  • HTML views (243)
  • Cited by (0)

[Back to Top]