{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,13]],"date-time":"2025-10-13T09:19:32Z","timestamp":1760347172733,"version":"3.37.3"},"reference-count":50,"publisher":"Springer Science and Business Media LLC","issue":"8","license":[{"start":{"date-parts":[[2024,9,30]],"date-time":"2024-09-30T00:00:00Z","timestamp":1727654400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,9,30]],"date-time":"2024-09-30T00:00:00Z","timestamp":1727654400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001711","name":"Schweizerischer Nationalfonds zur F\u00f6rderung der Wissenschaftlichen Forschung","doi-asserted-by":"publisher","award":["00021-172636"],"award-info":[{"award-number":["00021-172636"]}],"id":[{"id":"10.13039\/501100001711","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100010665","name":"H2020 Marie Sk\u0142odowska-Curie Actions","doi-asserted-by":"publisher","award":["85986","NCCR Synapsy","NCCR Synapsy"],"award-info":[{"award-number":["85986","NCCR Synapsy","NCCR Synapsy"]}],"id":[{"id":"10.13039\/100010665","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Appl. and Comput. Topology"],"published-print":{"date-parts":[[2024,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>At the intersection of Topological Data Analysis (TDA) and machine learning, the field of cellular signal processing has advanced rapidly in recent years. In this context, each signal on the cells of a complex is processed using the combinatorial Laplacian, and the resultant Hodge decomposition. Meanwhile, discrete Morse theory has been widely used to speed up computations by reducing the size of complexes while preserving their global topological properties. In this paper, we provide an approach to signal compression and reconstruction on chain complexes that leverages the tools of algebraic discrete Morse theory. The main goal is to reduce and reconstruct a based chain complex together with a set of signals on its cells via deformation retracts, preserving as much as possible the global topological structure of both the complex and the signals. We first prove that any deformation retract of real degree-wise finite-dimensional based chain complexes is equivalent to a Morse matching. We will then study how the signal changes under particular types of Morse matchings, showing its reconstruction error is trivial on specific components of the Hodge decomposition. Furthermore, we provide an algorithm to compute Morse matchings with minimal reconstruction error.<\/jats:p>","DOI":"10.1007\/s41468-024-00191-8","type":"journal-article","created":{"date-parts":[[2024,9,30]],"date-time":"2024-09-30T21:01:59Z","timestamp":1727730119000},"page":"2285-2326","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Morse theoretic signal compression and reconstruction on chain complexes"],"prefix":"10.1007","volume":"8","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9136-8924","authenticated-orcid":false,"given":"Stefania","family":"Ebli","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Celia","family":"Hacker","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kelly","family":"Maggs","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,9,30]]},"reference":[{"key":"191_CR1","doi-asserted-by":"publisher","first-page":"2992","DOI":"10.1109\/TSP.2020.2981920","volume":"68","author":"S Barbarossa","year":"2020","unstructured":"Barbarossa, S., Sardellitti, S.: Topological signal processing over simplicial complexes. IEEE Trans. Signal Process. 68, 2992\u20133007 (2020)","journal-title":"IEEE Trans. Signal Process."},{"key":"191_CR2","doi-asserted-by":"crossref","unstructured":"Barbarossa, S., Sardellitti, S., Ceci, E.: Learning from signals defined over simplicial complexes. In: IEEE 2018 IEEE Data Science Workshop (DSW), 51\u2013 55 (2018)","DOI":"10.1109\/DSW.2018.8439885"},{"issue":"6","key":"191_CR3","doi-asserted-by":"publisher","first-page":"1373","DOI":"10.1162\/089976603321780317","volume":"15","author":"M Belkin","year":"2003","unstructured":"Belkin, M., Niyogi, P.: Laplacian eigenmaps for dimensionality reduction and data representation. Neural Comput. 15(6), 1373\u20131396 (2003)","journal-title":"Neural Comput."},{"key":"191_CR4","unstructured":"Bodnar, Cristian, Frasca, Fabrizio, Wang, Yu\u00a0Guang, Otter, Nina, Mont\u00fafar, Guido, Li\u00f2, P., Bronstein, M.: Weisfeiler and Lehman go topological: Message passing simplicial networks. Proceedings of the 38th International Conference on Machine Learning PMLR 139, 1026\u20131037 (2021)"},{"issue":"4","key":"191_CR5","doi-asserted-by":"publisher","first-page":"18","DOI":"10.1109\/MSP.2017.2693418","volume":"34","author":"MM Bronstein","year":"2017","unstructured":"Bronstein, M.M., Bruna, J., LeCun, Y., Szlam, A., Vandergheynst, P.: Geometric deep learning: going beyond euclidean data. IEEE Signal Process. Mag. 34(4), 18\u201342 (2017)","journal-title":"IEEE Signal Process. Mag."},{"key":"191_CR6","unstructured":"Brown, R.: The twisted Eilenberg-Zilber theorem. In: Simposio di Topologia (Messina, 1964). Edizioni Oderisi, Gubbio (1965)"},{"key":"191_CR7","unstructured":"Carri\u00e8re, M., Chazal, F., Glisse, M., Ike, Y., Kannan, H.: A note on stochastic subgradient descent for persistence-based functionals: convergence and practical aspects, CoRR (2020) available at arXiv:2010.08356"},{"key":"191_CR8","doi-asserted-by":"crossref","unstructured":"Chen, S., Sandryhaila, A., Moura, J.M.F., Kovacevic, J.: Signal denoising on graphs via graph filtering. In: IEEE 2014 IEEE Global Conference on Signal and Information Processing (GlobalSIP), pp. 872\u2013 876 (2014)","DOI":"10.1109\/GlobalSIP.2014.7032244"},{"issue":"1","key":"191_CR9","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1016\/j.acha.2006.04.006","volume":"21","author":"RR Coifman","year":"2006","unstructured":"Coifman, R.R.: Lafon, St\u00e9phane: diffusion maps. Appl. Comput. Harmonic Anal. 21(1), 5\u201330 (2006)","journal-title":"Appl. Comput. Harmonic Anal."},{"key":"191_CR10","unstructured":"Contreras, I., Tawfeek, A.\u00a0R.: On discrete gradient vector fields and laplacians of simplicial complexes (2021), available at arXiv:2105.05388"},{"issue":"2","key":"191_CR11","doi-asserted-by":"publisher","first-page":"331","DOI":"10.2140\/pjm.2019.300.331","volume":"300","author":"I Contreras","year":"2019","unstructured":"Contreras, I., Xu, B.: The graph Laplacian and Morse inequalities. Pac. J. Math. 300(2), 331\u2013345 (2019)","journal-title":"Pac. J. Math."},{"issue":"4","key":"191_CR12","doi-asserted-by":"publisher","first-page":"957","DOI":"10.1007\/s10208-015-9266-8","volume":"16","author":"J Curry","year":"2016","unstructured":"Curry, J., Ghrist, R., Nanda, V.: Discrete Morse theory for computing cellular sheaf cohomology. Found. Comput. Math. 16(4), 957\u201397 (2016)","journal-title":"Found. Comput. Math."},{"key":"191_CR13","first-page":"3844","volume":"29","author":"M Defferrard","year":"2016","unstructured":"Defferrard, M., Bresson, X., Vandergheynst, P.: Convolutional neural networks on graphs with fast localized spectral filtering. Adv. Neural. Inf. Process. Syst. 29, 3844\u20133852 (2016)","journal-title":"Adv. Neural. Inf. Process. Syst."},{"key":"191_CR14","doi-asserted-by":"publisher","first-page":"654","DOI":"10.1109\/TPAMI.2014.2346172","volume":"37","author":"O Delgado-Friedrichs","year":"2015","unstructured":"Delgado-Friedrichs, O., Robins, V., Sheppard, A.: Skeletonization and partitioning of digital images using discrete Morse theory. IEEE Trans. Pattern Anal. Mach. Intell. 37, 654\u2013666 (2015)","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"issue":"1","key":"191_CR15","doi-asserted-by":"publisher","first-page":"79","DOI":"10.2307\/2373615","volume":"98","author":"J Dodziuk","year":"1976","unstructured":"Dodziuk, J.: Finite-difference approach to the Hodge theory of harmonic forms. Am. J. Math. 98(1), 79\u2013104 (1976)","journal-title":"Am. J. Math."},{"key":"191_CR16","unstructured":"Du, C., Szul, C., Manawa, A., Rasekh, N., Guzman, R., Davidson, R.: RGB image-based data analysis via discrete morse theory and persistent homology, CoRR, abs\/1801.09530 (2018). available at arXiv:1801.09530"},{"key":"191_CR17","unstructured":"Ebli, S., Defferrard, M., Spreemann, G.: Simplicial neural networks. Topological Data Analysis and Beyond workshop at NeurIPS (2020)"},{"issue":"1","key":"191_CR18","doi-asserted-by":"publisher","first-page":"240","DOI":"10.1007\/BF02566245","volume":"17","author":"B Eckmann","year":"1944","unstructured":"Eckmann, B.: Harmonische Funktionen und Randwertaufgaben in einem Komplex. Commentarii Mathematici Helvetici 17(1), 240\u2013255 (1944)","journal-title":"Commentarii Mathematici Helvetici"},{"issue":"1","key":"191_CR19","doi-asserted-by":"publisher","first-page":"90","DOI":"10.1006\/aima.1997.1650","volume":"134","author":"R Forman","year":"1998","unstructured":"Forman, R.: Morse theory for cell complexes. Adv. Math. 134(1), 90\u2013145 (1998)","journal-title":"Adv. Math."},{"issue":"12","key":"191_CR20","doi-asserted-by":"publisher","first-page":"5063","DOI":"10.1090\/S0002-9947-02-03041-6","volume":"354","author":"R Forman","year":"2002","unstructured":"Forman, R.: Discrete Morse Theory and the Cohomology Ring. Trans. Am. Math. Soc. 354(12), 5063\u20135085 (2002)","journal-title":"Trans. Am. Math. Soc."},{"key":"191_CR21","unstructured":"Gabrielsson, R.B., Nelson, B.\u00a0J., Dwaraknath, A., Skraba, P.: A Topology Layer for Machine Learning. In: Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, 202026 pp. 1553\u2013 1563"},{"key":"191_CR22","first-page":"398","volume":"16","author":"VKAM Gugenheim","year":"1972","unstructured":"Gugenheim, V.K.A.M.: On the chain-complex of a fibration. Ill. J. Math. 16, 398\u2013414 (1972)","journal-title":"Ill. J. Math."},{"key":"191_CR23","unstructured":"Hansen, J., Gebhart, T.: Sheaf neural networks (2019). available at arXiv:2012.06333"},{"issue":"4","key":"191_CR24","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1007\/s41468-019-00038-7","volume":"3","author":"J Hansen","year":"2019","unstructured":"Hansen, J., Ghrist, R.: Toward a spectral theory of cellular sheaves. J. Appl. Comput. Topol. 3(4), 315\u2013358 (2019)","journal-title":"J. Appl. Comput. Topol."},{"key":"191_CR25","volume-title":"Algebraic topology","author":"A Hatcher","year":"2002","unstructured":"Hatcher, A.: Algebraic topology. Cambridge University Press (2002)"},{"key":"191_CR26","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1017\/S0962492902000041","volume":"11","author":"R Hiptmair","year":"2002","unstructured":"Hiptmair, R.: Finite elements in computational electromagnetism. Acta Numer 11, 237\u2013339 (2002)","journal-title":"Acta Numer"},{"key":"191_CR27","volume-title":"Discrete exterior calculus","author":"AN Hirani","year":"2003","unstructured":"Hirani, A.N.: Discrete exterior calculus. California Institute of Technology (2003)"},{"key":"191_CR28","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1016\/j.aim.2013.05.007","volume":"244","author":"D Horak","year":"2013","unstructured":"Horak, D., Jost, J.: Spectra of combinatorial Laplace operators on simplicial complexes. Adv. Math. 244, 303\u2013336 (2013)","journal-title":"Adv. Math."},{"key":"191_CR29","unstructured":"Hu, X., Wang, Y., Fuxin, L., Samaras, D., Chen, C.: Topology-aware segmentation using discrete Morse theory. in: International conference on learning representations (2021)"},{"key":"191_CR30","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1137\/S0895480104445885","volume":"20","author":"M Joswig","year":"2006","unstructured":"Joswig, M., Pfetsch, M.E.: Computing optimal Morse matchings. SIAM J. Discret. Math. 20, 11\u201325 (2006)","journal-title":"SIAM J. Discret. Math."},{"key":"191_CR31","volume-title":"Computational homology","author":"T Kaczynski","year":"2006","unstructured":"Kaczynski, T., Mischaikow, K., Mrozek, M.: Computational homology. Springer, Berlin (2006)"},{"issue":"4","key":"191_CR32","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1016\/S0898-1221(97)00289-7","volume":"35","author":"T Kaczy\u0144ski","year":"1998","unstructured":"Kaczy\u0144ski, T., Mrozek, M., \u015alusarek, M.: Homology computation by reduction of chain complexes. Comput. Math. Appl. 35(4), 59\u201370 (1998)","journal-title":"Comput. Math. Appl."},{"key":"191_CR33","first-page":"15965","volume":"33","author":"K Kim","year":"2020","unstructured":"Kim, K., Kim, J., Zaheer, M., Kim, J., Chazal, F., Wasserman, L.: Pllay: Efficient topological layer based on persistent landscapes. Adv. Neural Inf. Process. Syst. 33, 15965\u201377 (2020)","journal-title":"Adv. Neural Inf. Process. Syst."},{"key":"191_CR34","doi-asserted-by":"crossref","unstructured":"Li, P., Shlezinger, N., Zhang, H. , Wang, B., Eldar, Y.C.: Graph signal compression via task-based quantization, Icassp 2021 - 2021 In: IEEE international conference on acoustics, speech and signal processing (ICASSP), 5514\u2013 5518 (2021)","DOI":"10.1109\/ICASSP39728.2021.9414657"},{"key":"191_CR35","unstructured":"Martinez-Figueroa, F.: Optimal Discrete Morse Theory Simplification (Expository Survey), (2021), available at arXiv:2111.05774"},{"issue":"2","key":"191_CR36","doi-asserted-by":"publisher","first-page":"858","DOI":"10.1137\/21M1435471","volume":"4","author":"F M\u00e9moli","year":"2022","unstructured":"M\u00e9moli, F., Wan, Z., Wang, Y.: Persistent Laplacians: properties, algorithms and implications. SIAM J. Math. Data Sci. 4(2), 858\u2013884 (2022)","journal-title":"SIAM J. Math. Data Sci."},{"key":"191_CR37","volume-title":"Morse theory","author":"J Milnor","year":"1969","unstructured":"Milnor, J.: Morse theory. Princeton University Press (1969)"},{"issue":"2","key":"191_CR38","doi-asserted-by":"publisher","first-page":"330","DOI":"10.1007\/s00454-013-9529-6","volume":"50","author":"K Mischaikow","year":"2013","unstructured":"Mischaikow, K., Nanda, V.: Morse theory for filtrations and efficient computation of persistent homology. Discrete & Computational Geometry 50(2), 330\u2013353 (2013)","journal-title":"Discrete & Computational Geometry"},{"key":"191_CR39","unstructured":"Moor, M., Horn, M., Rieck, B., Borgwardt, K.: Topological autoencoders. In: Proceedings of the 37th international conference on machine learning, pp. 7045\u20137054 (2020)"},{"issue":"5","key":"191_CR40","doi-asserted-by":"publisher","first-page":"808","DOI":"10.1109\/JPROC.2018.2820126","volume":"106","author":"A Ortega","year":"2018","unstructured":"Ortega, A., Frossard, P., Kova\u010devi\u0107, J., Moura, J.M.F., Vandergheynst, P.: Graph signal processing: Overview, challenges, and applications. Proc. IEEE 106(5), 808\u2013828 (2018)","journal-title":"Proc. IEEE"},{"key":"191_CR41","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-36104-3","volume-title":"Topological signal processing","author":"M Robinson","year":"2014","unstructured":"Robinson, M.: Topological signal processing, vol. 81. Springer (2014)"},{"key":"191_CR42","doi-asserted-by":"crossref","unstructured":"Roddenberry, T.M., Schaub, M.T., Hajij, M.: Signal processing on cell complexes. In: IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 8852\u2013 8856 (2022)","DOI":"10.1109\/ICASSP43922.2022.9747233"},{"key":"191_CR43","doi-asserted-by":"publisher","DOI":"10.1016\/j.sigpro.2021.108149","volume":"187","author":"MT Schaub","year":"2021","unstructured":"Schaub, M.T., Zhu, Yu., Seby, J.-B., Roddenberry, TMitchell, Segarra, S.: Signal processing on higher-order networks: Livin\u2019 on the edge... and beyond. Signal Process. 187, 108149 (2021)","journal-title":"Signal Process."},{"key":"191_CR44","unstructured":"Singh, G., Memoli, F., Carlsson, G.: Topological Methods for the Analysis of High Dimensional Data Sets and 3D Object Recognition. In: Eurographics symposium on point-based graphics (2007)"},{"key":"191_CR45","first-page":"124","volume":"26","author":"E Sk\u00f6ldberg","year":"2018","unstructured":"Sk\u00f6ldberg, E.: Algebraic Morse theory and homological perturbation theory. Algebra Discrete Math. 26, 124\u2013129 (2018)","journal-title":"Algebra Discrete Math."},{"issue":"01","key":"191_CR46","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1090\/S0002-9947-05-04079-1","volume":"358","author":"E Sk\u00f6ldberg","year":"2006","unstructured":"Sk\u00f6ldberg, E.: Morse theory from an algebraic viewpoint. Trans. Am. Math. Soc. 358(01), 115\u2013129 (2006)","journal-title":"Trans. Am. Math. Soc."},{"key":"191_CR47","unstructured":"Stefania, E., Celia, H., Kelly, M.: Morse theoretic signal compression and reconstruction on chain complexes, GitHub (2022), note Availabe at https:\/\/github.com\/stefaniaebli\/dmt-signal-processing"},{"issue":"4","key":"191_CR48","doi-asserted-by":"publisher","first-page":"395","DOI":"10.1007\/s11222-007-9033-z","volume":"17","author":"L Von UlrikeL","year":"2007","unstructured":"Von UlrikeL, L.: A tutorial on spectral clustering. Stat. Comput. 17(4), 395\u2013416 (2007)","journal-title":"Stat. Comput."},{"issue":"08","key":"191_CR49","doi-asserted-by":"publisher","first-page":"1646","DOI":"10.1109\/TPAMI.2011.95","volume":"33","author":"P Wood","year":"2011","unstructured":"Wood, P., Sheppard, A.P., Robins, V.: Theory and algorithms for constructing discrete Morse complexes from grayscale digital images. IEEE Trans. Pattern Anal. Mach. Intell. 33(08), 1646\u20131658 (2011)","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"191_CR50","unstructured":"Zhou, D., Sch\u00f6lkopf, B.: A regularization framework for learning from graph data. In: ICML 2004 workshop on statistical relational learning and its connections to other fields (SRL 2004), pp. 132\u2013137 (2004)"}],"container-title":["Journal of Applied and Computational Topology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s41468-024-00191-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s41468-024-00191-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s41468-024-00191-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,11,6]],"date-time":"2024-11-06T21:22:42Z","timestamp":1730928162000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s41468-024-00191-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,9,30]]},"references-count":50,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2024,12]]}},"alternative-id":["191"],"URL":"https:\/\/doi.org\/10.1007\/s41468-024-00191-8","relation":{},"ISSN":["2367-1726","2367-1734"],"issn-type":[{"type":"print","value":"2367-1726"},{"type":"electronic","value":"2367-1734"}],"subject":[],"published":{"date-parts":[[2024,9,30]]},"assertion":[{"value":"23 March 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 April 2023","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 July 2024","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 September 2024","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"On behalf of all authors, the corresponding author states that there is no Conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}