PERCEPT: A New Online Change-Point Detection Method using Topological Data Analysis

References

• Aurenhammer, F. (1991), “Voronoi Diagrams — A Survey of a Fundamental Geometric Data Structure,” ACM Computing Surveys, 23, 345–405. DOI: 10.1145/116873.116880.
   Web of Science ®Google Scholar
• Basseville, M., and Nikiforov, I. V. (1993), “Detection of Abrupt Changes: Theory and Application, Upper Saddle River, NJ: Prentice Hall.
   Google Scholar
• Beksi, W. J., and Papanikolopoulos, N. (2016), “3D Eegion Segmentation using Topological Persistence,” in 2016 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pp. 1079–1084.
   Google Scholar
• Bendich, P., Edelsbrunner, H., and Kerber, M. (2011), “Computing Robustness and Persistence for Images,” IEEE Transactions on Visualization and Computer Graphics, 6, 1251–1260.
   Google Scholar
• Bernhard, S., Smola, A. J., and Bach, F. (2018), Learning with Kernels: Support Vector Machines, Regularization, Optimization, and Beyond, Cambridge, MA: MIT Press.
   Google Scholar
• Cang, Z., Mu, L., Wu, K., Opron, K., Xia, K., and Wei, G.-W. (2015), “A Topological Approach for Protein Classification,” Molecular Based Mathematical Biology, 3, 140–162.
   Google Scholar
• Chazal, F. (2016), “High-Dimensional Topological Data Analysis,” in Handbook of Discrete and Computational Geometry, eds. C. D. Toth, J. O’Rourke, J. E. Goodman, (3rd ed.), pp. 663–683, Boca Raton, FL: CRC Press.
   Google Scholar
• Cohen-Steiner, D., Edelsbrunner, H., and Harer, J. (2007), “Stability of Persistence Diagrams,” Discrete & Computational Geometry, 37, 103–120.
   Web of Science ®Google Scholar
• Edelsbrunner, H., and Harer, J. (2008), “Persistent Homology – A Survey,” Contemporary Mathematics, 453, 257–282.
   Google Scholar
• Ester, M., Kriegel, H.-P., Sander, J., and Xu, X. (1996), “A Density-based Algorithm for Discovering Clusters in Large Spatial Databases with Noise,” in Proceedings of the Second International Conference on Knowledge Discovery and Data Mining, pp. 226–231. AAAI Press.
   Google Scholar
• Fothergill, S., Mentis, H., Kohli, P., and Nowozin, S. (2012), “Instructing People for Training Gestural Interactive Systems,” Proceedings of the 2012 ACM annual conference on Human Factors in Computing Systems - CHI ’12, pp. 1737–1746.
   Google Scholar
• Freudenthal, H. (1942), “Simplizialzerlegungen von beschrankter flachheit,” Annals of Mathematics, 43, 580–582. DOI: 10.2307/1968813.
   Google Scholar
• Ghrist, R. (2008), “Barcodes: The Persistent Topology of Data,” Bulletin of the American Mathematical Society, 45, 61–75. DOI: 10.1090/S0273-0979-07-01191-3.
   Web of Science ®Google Scholar
• Gidea, M., and Katz, Y. A. (2017), “Topological Data Analysis of Financial Time Series: Landscapes of Crashes,” Physica A: Statistical Mechanics and its Applications, 491, 820–834. DOI: 10.1016/j.physa.2017.09.028.
   Web of Science ®Google Scholar
• Gretton, A., Borgwardt, K. M., Rasch, M. J., Schölkopf, B., and Smola, A. (2012), “A Kernel Two-Sample Test,” Journal of Machine Learning Research, 13, 723–773.
   Web of Science ®Google Scholar
• Han, S., Okonek, T., Yadav, N., and Zheng, X. (2018), “Distributions of Matching Distances in Topological Data Analysis,” SIAM Undergraduate Research Online 13, 57–76.
   Google Scholar
• Hotelling, H. (1947), Multivariate Quality Control Illustrated by Air Testing of Sample Bombsights, pp. 111–184, New York: McGraw-Hill.
   Google Scholar
• Islambekov, U., Yuvaraj, M., and Gel, Y. (2019), “Harnessing the Power of Topological Data Analysis to Detect Change Points,” Environmetrics, 31, e2612. DOI: 10.1002/env.2612.
   Web of Science ®Google Scholar
• Jiao, Y., Chen, Y., and Gu, Y. (2018), “Subspace Change-Point Detection: A New Model and Solution,” IEEE Journal of Selected Topics in Signal Processing, 12, 1224–1239. DOI: 10.1109/JSTSP.2018.2873147.
   Web of Science ®Google Scholar
• Ketchen, D. J., and Shook, C. L. (1996), “The Application of Cluster Analysis in Strategic Management Research: An Analysis and Critique,” Strategic Management Journal, 17, 441–458. DOI: 10.1002/(SICI)1097-0266(199606)17:6<441::AID-SMJ819>3.0.CO;2-G.
   Web of Science ®Google Scholar
• Krishna, A., Mak, S., and Joseph, R. (2019), “Distributional Clustering: A Distribution-Preserving Clustering Method,” arXiv preprint arXiv:1911.05940.
   Google Scholar
• Lai, T. L. (1998), “Information Bounds and Quick Detection of Parameter Changes in Stochastic Systems,” IEEE Transactions on Information Theory, 44, 2917–2929.
   Web of Science ®Google Scholar
• Lau, T. S., Tay, W. P., and Veeravalli, V. V. (2018), “A Binning Approach to Quickest Change Detection with Unknown Post-Change Distribution,” IEEE Transactions on Signal Processing, 67, 609–621. DOI: 10.1109/TSP.2018.2881666.
   Web of Science ®Google Scholar
• Li, S., Xie, Y., Dai, H., and Song, L. (2015), “M-statistic for Kernel Change-Point Detection,” in Proceedings of the Advances in Neural Information Processing Systems, pp. 3366–3374.
   Google Scholar
• Lloyd, S. (1982), “Least Squares Quantization in PCM,” IEEE Transactions on Information Theory, 28, 129–137. DOI: 10.1109/TIT.1982.1056489.
   Web of Science ®Google Scholar
• Lorden, G. (1971), “Procedures for Reacting to a Change in Distribution,” Annals of Mathematical Statistics, 42, 1897–1908. DOI: 10.1214/aoms/1177693055.
   Google Scholar
• Mak, S., Sung, C.-L., Wang, X., Yeh, S.-T., Chang, Y.-H., Joseph, V. R., Yang, V., and Wu, C. F. J. (2018), “An Efficient Surrogate Model for Emulation and Physics Extraction of Large Eddy Simulations,” Journal of the American Statistical Association, 113, 1443–1456. DOI: 10.1080/01621459.2017.1409123.
   Web of Science ®Google Scholar
• Molloy, T. L., and Ford, J. J. (2017), “Misspecified and Asymptotically Minimax Robust Quickest Change Detection,” IEEE Transactions on Signal Processing, 65, 5730–5742. DOI: 10.1109/TSP.2017.2740202.
   Web of Science ®Google Scholar
• Moustakides, G. V. (1986), “Optimal Stopping Times for Detecting Changes in Distributions,” Annals of Statistics, 14, 1379–1387.
   Web of Science ®Google Scholar
• Ofori-Boateng, D., Dominguez, I. S., Akcora, C., Kantarcioglu, M., and Gel, Y. R. (2021), “Topological Anomaly Detection in Dynamic Multilayer Blockchain Networks,” in Machine Learning and Knowledge Discovery in Databases. Research Track, eds. M. Ceci, J. Hollmén, L. Todorovski, C. Vens, and S. Džeroskipp, pp. 788–804, Cham: Springer.
   Google Scholar
• Oh, S., Hoogs, A., Perera, A., Cuntoor, N., Chen, C.-C., Lee, J. T., Mukherjee, S., Aggarwal, J. K., Lee, H., Davis, L., Swears, E., Wang, X., Ji, Q., Reddy, K., Shah, M., Vondrick, C., Pirsiavash, H., Ramanan, D., Yuen, J., Torralba, A., Song, B., Fong, A., Roy-Chowdhury, A., and Desai, M. (2011), “A Large-Scale Benchmark Dataset for Event Recognition in Surveillance Video,” IEEE Xplore, pp. 3153–3160.
   Google Scholar
• Page, E. S. (1954), “Continuous Inspection Schemes,” Biometrika, 41, 100–115.
   Web of Science ®Google Scholar
• Perea, J. A., and Harer, J. (2015), “Sliding Windows and Persistence: An Application of Topological Methods to Signal Analysis,” Foundations of Computational Mathematics, 15, 799–838. DOI: 10.1007/s10208-014-9206-z.
   Web of Science ®Google Scholar
• Poor, H. V., and Hadjiliadis, O. (2008), Quickest Detection, Cambridge: Cambridge University Press.
   Google Scholar
• Roberts, S. W. (1959), “Control chart Tests based on Geometric Moving Averages,” Technometrics, 1, 239–250. DOI: 10.1080/00401706.1959.10489860.
   Google Scholar
• Seversky, L. M., Davis, S., and Berger, M. (2016), “On Time-Series Topological Data Analysis: New Data and Opportunities,” in 2016 IEEE Conference on Computer Vision and Pattern Recognition Workshops (CVPRW), pp. 1014–1022. DOI: 10.1109/CVPRW.2016.131.
   Google Scholar
• Shewhart, W. A. (1925), “The Application of Statistics as an Aid in maintaining Quality of a Manufactured Product,” Journal of the American Statistical Association, 20, 546–548. DOI: 10.1080/01621459.1925.10502930.
   Google Scholar
• Shi, J., and Malik, J. (2000), “Normalized Cuts and Image Segmentation,” IEEE Transactions on Pattern Analysis and Machine Intelligence, 22, 888–905. DOI: 10.1109/34.868688.
   Web of Science ®Google Scholar
• Siegmund, D. O. (1985), Sequential Analysis: Tests and Confidence Intervals. Springer Series in Statistics, New York: Springer.
   Google Scholar
• Sizemore, A. E., Phillips-Cremins, J. E., Ghrist, R., and Bassett, D. S. (2019), “The Importance of the Whole: Topological Data Analysis for the Network Neuroscientist,” Network Neuroscience, 3, 656–673. DOI: 10.1162/netn_a_00073.
   PubMed Web of Science ®Google Scholar
• Tartakovsky, A., Nikiforov, I., and Basseville, M. (2015), Sequential Analysis: Hypothesis Testing and Changepoint Detection. Ser. Monographs on Statistics and Applied Probability 136. Boca Raton, FL: Chapman & Hall/CRC Press.
   Google Scholar
• Tralie, C., Saul, N., and Bar-On, R. (2018), “Ripser.py: A Lean Persistent Homology Library for Python,” The Journal of Open Source Software, 3, 925. DOI: 10.21105/joss.00925.
   Google Scholar
• Turaga, P., Chellappa, R., Subrahmanian, V. S., and Udrea, O. (2008), “Machine Recognition of Human Activities: A Survey,” IEEE Transactions on Circuits and Systems for Video Technology, 18, 1473–1488. DOI: 10.1109/TCSVT.2008.2005594.
   Web of Science ®Google Scholar
• Wang, H., Xie, L., Cuozzo, A., Mak, S., and Xie, Y. (2020), “Uncertainty Quantification for Inferring Hawkes Networks,” in Advances in Neural Information Processing Systems.
   Google Scholar
• Wang, H., Xie, L., Xie, Y., Cuozzo, A., and Mak, S. (2022), “Sequential Change-Point Detection for Mutually Exciting Point Processes over Networks,” Technometrics (accepted), DOI: 10.1080/00401706.2022.2054862..
   Web of Science ®Google Scholar
• Wright, M., and Zheng, X. (2020), “Topological Data Analysis on Simple English Wikipedia Articles,” The PUMP Journal of Undergraduate Research, 3, 308–328.
   Google Scholar
• Xie, L., and Xie, Y. (2021), “Sequential Change Detection by Optimal Weighted l2 Divergence,” IEEE Journal on Selected Areas in Information Theory, 2, 747–761.
   Google Scholar
• Xie, L., Xie, Y., and Moustakides, G. V. (2020), “Sequential Subspace Change Point Detection,” Sequential Analysis, 39, 307–335. DOI: 10.1080/07474946.2020.1823191.
   Web of Science ®Google Scholar
• Xie, Y., Huang, J., and Willett, R. (2012), “Change-Point Detection for High-Dimensional Time Series with Missing Data,” IEEE Journal of Selected Topics in Signal Processing, 7, 12–27. DOI: 10.1109/JSTSP.2012.2234082.
   Web of Science ®Google Scholar
• Zhang, T., Ramakrishnan, R., and Livny, M. (1996), “Birch: An Efficient Data Clustering Method for Very Large Databases,” SIGMOD Record, 25, 103–114. DOI: 10.1145/235968.233324.
   Google Scholar