[{"has_accepted_license":"1","corr_author":"1","quality_controlled":"1","ddc":["500"],"publication":"Foundations of Computational Mathematics","OA_place":"publisher","date_published":"2026-08-04T00:00:00Z","publisher":"Springer","abstract":[{"text":"Bifurcation characterizes the qualitative changes in parameterized dynamical systems and is one of the major topics in the field. In this work, we study combinatorial bifurcations within the framework of combinatorial dynamical systems—a young but already well-established theory. We introduce the Conley–Morse persistence barcode, a compact algebraic descriptor of combinatorial bifurcations. This barcode captures structural changes in a dynamical system at the level of Morse decompositions and provides a characterization of the nature of observed transitions in terms of the Conley index. The construction of the Conley–Morse persistence barcode builds upon ideas from topological persistence. Specifically, we consider a persistence module obtained from the Conley index of invariant sets indexed over a poset. Using gentle algebras, we prove that this module decomposes into simple intervals (bars) and compute them by adapting the zigzag persistence algorithm to our purpose.","lang":"eng"}],"author":[{"last_name":"Dey","first_name":"Tamal K.","full_name":"Dey, Tamal K."},{"first_name":"Michał","full_name":"Lipiński, Michał","last_name":"Lipiński","orcid":"0000-0001-9789-9750","id":"dfffb474-4317-11ee-8f5c-fe3fc95a425e"},{"full_name":"Soriano Trigueros, Manuel","first_name":"Manuel","id":"15ebd7cf-15bf-11ee-aebd-bb4bb5121ea8","orcid":"0000-0003-2449-1433","last_name":"Soriano Trigueros"}],"date_updated":"2026-08-11T06:13:33Z","year":"2026","main_file_link":[{"url":"https://doi.org/10.1007/s10208-026-09766-6","open_access":"1"}],"department":[{"_id":"HeEd"}],"scopus_import":"1","type":"journal_article","PlanS_conform":"1","arxiv":1,"article_processing_charge":"Yes (via OA deal)","acknowledgement":"M.L. acknowledges support from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie Grant Agreement No. 101034413. T.D. acknowledges the support of NSF funds CCF-2437030 and DMS-2301360. The authors would like to thank the anonymous reviewers for their careful reading of the paper. Their feedback significantly improved the quality of the article. T.D. and M.L. would like to acknowledge many thought-provoking discussions with Marian Mrozek on combinatorial dynamical systems and their continuations. M.S.T. would like to thank Álvaro Sánchez for insightful discussions about representation theory. Open access funding provided by Institute of Science and Technology (IST Austria).","month":"08","status":"public","das_tickbox":"0","publication_identifier":{"eissn":["1615-3383"],"issn":["1615-3375"]},"date_created":"2026-08-05T06:11:30Z","supplementarymaterial":"yes","article_type":"original","doi":"10.1007/s10208-026-09766-6","language":[{"iso":"eng"}],"project":[{"grant_number":"101034413","_id":"fc2ed2f7-9c52-11eb-aca3-c01059dda49c","call_identifier":"H2020","name":"IST-BRIDGE: International postdoctoral program"}],"researchdata_availability":"no","oa":1,"external_id":{"arxiv":["2504.17105"]},"oa_version":"Published Version","tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"OA_type":"hybrid","publication_status":"epub_ahead","_id":"22648","title":"Conley-Morse persistence barcode: A homological signature of combinatorial bifurcations","fulldoi":"https://doi.org/10.1007/s10208-026-09766-6","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","keyword":["Multivector field","Conley index","Morse decomposition","Bifurcation","Continuation","Zigzag persistence","Persistence barcode","Gentle algebra"],"citation":{"ista":"Dey TK, Lipiński M, Soriano Trigueros M. 2026. Conley-Morse persistence barcode: A homological signature of combinatorial bifurcations. Foundations of Computational Mathematics.","ama":"Dey TK, Lipiński M, Soriano Trigueros M. Conley-Morse persistence barcode: A homological signature of combinatorial bifurcations. <i>Foundations of Computational Mathematics</i>. 2026. doi:<a href=\"https://doi.org/10.1007/s10208-026-09766-6\">10.1007/s10208-026-09766-6</a>","chicago":"Dey, Tamal K., Michał Lipiński, and Manuel Soriano Trigueros. “Conley-Morse Persistence Barcode: A Homological Signature of Combinatorial Bifurcations.” <i>Foundations of Computational Mathematics</i>. Springer, 2026. <a href=\"https://doi.org/10.1007/s10208-026-09766-6\">https://doi.org/10.1007/s10208-026-09766-6</a>.","ieee":"T. K. Dey, M. Lipiński, and M. Soriano Trigueros, “Conley-Morse persistence barcode: A homological signature of combinatorial bifurcations,” <i>Foundations of Computational Mathematics</i>. Springer, 2026.","apa":"Dey, T. K., Lipiński, M., &#38; Soriano Trigueros, M. (2026). Conley-Morse persistence barcode: A homological signature of combinatorial bifurcations. <i>Foundations of Computational Mathematics</i>. Springer. <a href=\"https://doi.org/10.1007/s10208-026-09766-6\">https://doi.org/10.1007/s10208-026-09766-6</a>","short":"T.K. Dey, M. Lipiński, M. Soriano Trigueros, Foundations of Computational Mathematics (2026).","mla":"Dey, Tamal K., et al. “Conley-Morse Persistence Barcode: A Homological Signature of Combinatorial Bifurcations.” <i>Foundations of Computational Mathematics</i>, Springer, 2026, doi:<a href=\"https://doi.org/10.1007/s10208-026-09766-6\">10.1007/s10208-026-09766-6</a>."},"ec_funded":1,"day":"04"},{"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"oa_version":"Published Version","publication_status":"published","OA_type":"hybrid","fulldoi":"https://doi.org/10.1007/s10208-024-09686-3","title":"Quantitative convergence of a discretization of dynamic optimal transport using the dual formulation","_id":"14703","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","keyword":["Optimal transport","Hamilton-Jacobi equation","convex optimization"],"citation":{"ama":"Ishida S, Lavenant H. Quantitative convergence of a discretization of dynamic optimal transport using the dual formulation. <i>Foundations of Computational Mathematics</i>. 2026;26:349-384. doi:<a href=\"https://doi.org/10.1007/s10208-024-09686-3\">10.1007/s10208-024-09686-3</a>","chicago":"Ishida, Sadashige, and Hugo Lavenant. “Quantitative Convergence of a Discretization of Dynamic Optimal Transport Using the Dual Formulation.” <i>Foundations of Computational Mathematics</i>. Springer Nature, 2026. <a href=\"https://doi.org/10.1007/s10208-024-09686-3\">https://doi.org/10.1007/s10208-024-09686-3</a>.","ista":"Ishida S, Lavenant H. 2026. Quantitative convergence of a discretization of dynamic optimal transport using the dual formulation. Foundations of Computational Mathematics. 26, 349–384.","apa":"Ishida, S., &#38; Lavenant, H. (2026). Quantitative convergence of a discretization of dynamic optimal transport using the dual formulation. <i>Foundations of Computational Mathematics</i>. Springer Nature. <a href=\"https://doi.org/10.1007/s10208-024-09686-3\">https://doi.org/10.1007/s10208-024-09686-3</a>","ieee":"S. Ishida and H. Lavenant, “Quantitative convergence of a discretization of dynamic optimal transport using the dual formulation,” <i>Foundations of Computational Mathematics</i>, vol. 26. Springer Nature, pp. 349–384, 2026.","short":"S. Ishida, H. Lavenant, Foundations of Computational Mathematics 26 (2026) 349–384.","mla":"Ishida, Sadashige, and Hugo Lavenant. “Quantitative Convergence of a Discretization of Dynamic Optimal Transport Using the Dual Formulation.” <i>Foundations of Computational Mathematics</i>, vol. 26, Springer Nature, 2026, pp. 349–84, doi:<a href=\"https://doi.org/10.1007/s10208-024-09686-3\">10.1007/s10208-024-09686-3</a>."},"file_date_updated":"2026-07-23T05:37:52Z","day":"01","month":"02","publication_identifier":{"issn":["1615-3375"],"eissn":["1615-3383"]},"date_created":"2023-12-21T10:14:37Z","das_tickbox":"0","status":"public","file":[{"checksum":"30671f88e792e8b75ae3e698ac4c131c","file_id":"22384","file_size":1240012,"creator":"dernst","success":1,"access_level":"open_access","file_name":"2026_FoundCompMath_Ishida.pdf","date_created":"2026-07-23T05:37:52Z","content_type":"application/pdf","relation":"main_file","date_updated":"2026-07-23T05:37:52Z"}],"supplementarymaterial":"no","doi":"10.1007/s10208-024-09686-3","language":[{"iso":"eng"}],"article_type":"original","project":[{"name":"Computational Discovery of Numerical Algorithms for Animation and Simulation of Natural Phenomena","_id":"34bc2376-11ca-11ed-8bc3-9a3b3961a088","grant_number":"101045083"}],"external_id":{"isi":["001352503300001"],"arxiv":["2312.12213"]},"page":"349-384","oa":1,"researchdata_availability":"no","year":"2026","date_updated":"2026-10-02T11:17:26Z","author":[{"id":"6F7C4B96-A8E9-11E9-A7CA-09ECE5697425","orcid":"0000-0002-3121-3100","last_name":"Ishida","first_name":"Sadashige","full_name":"Ishida, Sadashige"},{"first_name":"Hugo","full_name":"Lavenant, Hugo","last_name":"Lavenant"}],"isi":1,"volume":26,"department":[{"_id":"GradSch"},{"_id":"ChWo"}],"type":"journal_article","scopus_import":"1","PlanS_conform":"1","acknowledgement":"The authors would like to thank Chris Wojtan for his continuous support and several interesting discussions. Part of this research was performed during two visits: one of SI to the BIDSA research center at Bocconi University, and one of HL to the Institute of Science and Technology Austria. Both host institutions are warmly acknowledged for the hospitality. HL is partially supported by the MUR-Prin 2022-202244A7YL “Gradient Flows and Non-Smooth Geometric Structures with Applications to Optimization and Machine Learning”, funded by the European Union - Next Generation EU. SI is supported in part by ERC Consolidator Grant 101045083 “CoDiNA” funded by the European Research Council. Open access funding provided by Institute of Science and Technology (IST Austria).","article_processing_charge":"Yes (via OA deal)","arxiv":1,"corr_author":"1","has_accepted_license":"1","ddc":["000"],"quality_controlled":"1","date_published":"2026-02-01T00:00:00Z","OA_place":"publisher","publication":"Foundations of Computational Mathematics","publisher":"Springer Nature","intvolume":"        26","abstract":[{"lang":"eng","text":"We present a discretization of the dynamic optimal transport problem for which we can obtain the convergence rate for the value of the transport cost to its continuous value when the temporal and spatial stepsize vanish. This convergence result does not require any regularity assumption on the measures, though experiments suggest that the rate is not sharp. Via an analysis of the duality gap we also obtain the convergence rates for the gradient of the optimal potentials and the velocity field under mild regularity assumptions. To obtain such rates we discretize the dual formulation of the dynamic optimal transport problem and use the mature literature related to the error due to discretizing the Hamilton-Jacobi equation."}]},{"PlanS_conform":"1","arxiv":1,"acknowledgement":"The original work behind this article was developed for HE’s master’s thesis, supervised by RT. We are mostly in debt to César Camacho, who was HE’s co-advisor, as well as the members of the thesis jury, Clément Maria, Eduardo Mendes, and Jameson Cahill, not only for agreeing to evaluate the original work but also for many valuable inputs. Finally, we are indebted to the anonymous reviewers for their important feedback and suggestions. Open access funding provided by Institute of Science and Technology (IST Austria).","article_processing_charge":"Yes (via OA deal)","department":[{"_id":"UlWa"}],"scopus_import":"1","type":"journal_article","date_updated":"2026-06-18T18:22:42Z","author":[{"last_name":"Ennes","full_name":"Ennes, Henrique","first_name":"Henrique"},{"full_name":"Tinarrage, Raphaël","first_name":"Raphaël","id":"40ebcc9d-905f-11ef-bf0a-dc475da8a04e","orcid":"0000-0002-1404-1095","last_name":"Tinarrage"}],"year":"2025","isi":1,"main_file_link":[{"open_access":"1","url":"https://doi.org/10.1007/s10208-025-09728-4"}],"abstract":[{"lang":"eng","text":"We suggest a new algorithm to estimate representations of compact Lie groups from finite samples of their orbits. Different from other reported techniques, our method allows the retrieval of the precise representation type as a direct sum of irreducible representations. Moreover, the knowledge of the representation type permits the reconstruction of its orbit, which is useful for identifying the Lie group that generates the action, from a finite list of candidates. Our algorithm is general for any compact Lie group, but only instantiations for SO(2), T^d, SU(2), and SO(3) are considered. Theoretical guarantees of robustness in terms of Hausdorff and Wasserstein distances are derived. Our tools are drawn from geometric measure theory, computational geometry, and optimization on matrix manifolds. The algorithm is tested for synthetic data up to dimension 32, as well as real-life applications in image analysis, harmonic analysis, density estimation, equivariant neural networks, chemical conformational spaces, and classical mechanics systems, achieving very accurate results."}],"publisher":"Springer Nature","publication":"Foundations of Computational Mathematics","OA_place":"publisher","date_published":"2025-09-15T00:00:00Z","corr_author":"1","quality_controlled":"1","ddc":["500"],"day":"15","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","citation":{"mla":"Ennes, Henrique, and Raphaël Tinarrage. “LieDetect: Detection of Representation Orbits of Compact Lie Groups from Point Clouds.” <i>Foundations of Computational Mathematics</i>, Springer Nature, 2025, doi:<a href=\"https://doi.org/10.1007/s10208-025-09728-4\">10.1007/s10208-025-09728-4</a>.","short":"H. Ennes, R. Tinarrage, Foundations of Computational Mathematics (2025).","ieee":"H. Ennes and R. Tinarrage, “LieDetect: Detection of representation orbits of compact Lie groups from point clouds,” <i>Foundations of Computational Mathematics</i>. Springer Nature, 2025.","apa":"Ennes, H., &#38; Tinarrage, R. (2025). LieDetect: Detection of representation orbits of compact Lie groups from point clouds. <i>Foundations of Computational Mathematics</i>. Springer Nature. <a href=\"https://doi.org/10.1007/s10208-025-09728-4\">https://doi.org/10.1007/s10208-025-09728-4</a>","ista":"Ennes H, Tinarrage R. 2025. LieDetect: Detection of representation orbits of compact Lie groups from point clouds. Foundations of Computational Mathematics.","ama":"Ennes H, Tinarrage R. LieDetect: Detection of representation orbits of compact Lie groups from point clouds. <i>Foundations of Computational Mathematics</i>. 2025. doi:<a href=\"https://doi.org/10.1007/s10208-025-09728-4\">10.1007/s10208-025-09728-4</a>","chicago":"Ennes, Henrique, and Raphaël Tinarrage. “LieDetect: Detection of Representation Orbits of Compact Lie Groups from Point Clouds.” <i>Foundations of Computational Mathematics</i>. Springer Nature, 2025. <a href=\"https://doi.org/10.1007/s10208-025-09728-4\">https://doi.org/10.1007/s10208-025-09728-4</a>."},"_id":"20407","fulldoi":"https://doi.org/10.1007/s10208-025-09728-4","title":"LieDetect: Detection of representation orbits of compact Lie groups from point clouds","oa_version":"Published Version","publication_status":"epub_ahead","OA_type":"hybrid","oa":1,"external_id":{"arxiv":["2309.03086"],"isi":["001571197200001"]},"article_type":"original","doi":"10.1007/s10208-025-09728-4","language":[{"iso":"eng"}],"status":"public","date_created":"2025-09-28T22:01:27Z","publication_identifier":{"issn":["1615-3375"],"eissn":["1615-3383"]},"month":"09"},{"acknowledgement":"Open access funding provided by Institute of Science and Technology (IST Austria).","article_processing_charge":"Yes (via OA deal)","volume":24,"department":[{"_id":"JuFi"}],"type":"journal_article","scopus_import":"1","author":[{"full_name":"Clozeau, Nicolas","first_name":"Nicolas","id":"fea1b376-906f-11eb-847d-b2c0cf46455b","last_name":"Clozeau"},{"first_name":"Marc","full_name":"Josien, Marc","last_name":"Josien"},{"last_name":"Otto","first_name":"Felix","full_name":"Otto, Felix"},{"last_name":"Xu","first_name":"Qiang","full_name":"Xu, Qiang"}],"date_updated":"2025-01-09T07:37:50Z","year":"2024","isi":1,"abstract":[{"lang":"eng","text":"We study the representative volume element (RVE) method, which is a method to approximately infer the effective behavior ahom of a stationary random medium. The latter is described by a coefficient field a(x) generated from a given ensemble ⟨⋅⟩ and the corresponding linear elliptic operator −∇⋅a∇. In line with the theory of homogenization, the method proceeds by computing d=3 correctors (d denoting the space dimension). To be numerically tractable, this computation has to be done on a finite domain: the so-called representative volume element, i.e., a large box with, say, periodic boundary conditions. The main message of this article is: Periodize the ensemble instead of its realizations. By this, we mean that it is better to sample from a suitably periodized ensemble than to periodically extend the restriction of a realization a(x) from the whole-space ensemble ⟨⋅⟩. We make this point by investigating the bias (or systematic error), i.e., the difference between ahom and the expected value of the RVE method, in terms of its scaling w.r.t. the lateral size L of the box. In case of periodizing a(x), we heuristically argue that this error is generically O(L−1). In case of a suitable periodization of ⟨⋅⟩\r\n, we rigorously show that it is O(L−d). In fact, we give a characterization of the leading-order error term for both strategies and argue that even in the isotropic case it is generically non-degenerate. We carry out the rigorous analysis in the convenient setting of ensembles ⟨⋅⟩\r\n of Gaussian type, which allow for a straightforward periodization, passing via the (integrable) covariance function. This setting has also the advantage of making the Price theorem and the Malliavin calculus available for optimal stochastic estimates of correctors. We actually need control of second-order correctors to capture the leading-order error term. This is due to inversion symmetry when applying the two-scale expansion to the Green function. As a bonus, we present a stream-lined strategy to estimate the error in a higher-order two-scale expansion of the Green function."}],"publisher":"Springer Nature","intvolume":"        24","publication":"Foundations of Computational Mathematics","date_published":"2024-08-01T00:00:00Z","OA_place":"publisher","has_accepted_license":"1","corr_author":"1","quality_controlled":"1","ddc":["510"],"day":"01","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","file_date_updated":"2025-01-09T07:36:57Z","citation":{"ista":"Clozeau N, Josien M, Otto F, Xu Q. 2024. Bias in the representative volume element method: Periodize the ensemble instead of its realizations. Foundations of Computational Mathematics. 24, 1305–1387.","ama":"Clozeau N, Josien M, Otto F, Xu Q. Bias in the representative volume element method: Periodize the ensemble instead of its realizations. <i>Foundations of Computational Mathematics</i>. 2024;24:1305-1387. doi:<a href=\"https://doi.org/10.1007/s10208-023-09613-y\">10.1007/s10208-023-09613-y</a>","chicago":"Clozeau, Nicolas, Marc Josien, Felix Otto, and Qiang Xu. “Bias in the Representative Volume Element Method: Periodize the Ensemble Instead of Its Realizations.” <i>Foundations of Computational Mathematics</i>. Springer Nature, 2024. <a href=\"https://doi.org/10.1007/s10208-023-09613-y\">https://doi.org/10.1007/s10208-023-09613-y</a>.","ieee":"N. Clozeau, M. Josien, F. Otto, and Q. Xu, “Bias in the representative volume element method: Periodize the ensemble instead of its realizations,” <i>Foundations of Computational Mathematics</i>, vol. 24. Springer Nature, pp. 1305–1387, 2024.","apa":"Clozeau, N., Josien, M., Otto, F., &#38; Xu, Q. (2024). Bias in the representative volume element method: Periodize the ensemble instead of its realizations. <i>Foundations of Computational Mathematics</i>. Springer Nature. <a href=\"https://doi.org/10.1007/s10208-023-09613-y\">https://doi.org/10.1007/s10208-023-09613-y</a>","short":"N. Clozeau, M. Josien, F. Otto, Q. Xu, Foundations of Computational Mathematics 24 (2024) 1305–1387.","mla":"Clozeau, Nicolas, et al. “Bias in the Representative Volume Element Method: Periodize the Ensemble Instead of Its Realizations.” <i>Foundations of Computational Mathematics</i>, vol. 24, Springer Nature, 2024, pp. 1305–87, doi:<a href=\"https://doi.org/10.1007/s10208-023-09613-y\">10.1007/s10208-023-09613-y</a>."},"_id":"13129","fulldoi":"https://doi.org/10.1007/s10208-023-09613-y","title":"Bias in the representative volume element method: Periodize the ensemble instead of its realizations","tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"oa_version":"Published Version","OA_type":"hybrid","publication_status":"published","oa":1,"external_id":{"isi":["000999623100001"]},"page":"1305-1387","language":[{"iso":"eng"}],"doi":"10.1007/s10208-023-09613-y","article_type":"original","status":"public","publication_identifier":{"eissn":["1615-3383"],"issn":["1615-3375"]},"date_created":"2023-06-11T22:00:40Z","file":[{"file_id":"18782","file_size":1454406,"creator":"dernst","success":1,"checksum":"ec0582e2b55e2703a7da2686ae0d682e","content_type":"application/pdf","relation":"main_file","date_updated":"2025-01-09T07:36:57Z","file_name":"2024_FoundCompMath_Clozeau.pdf","access_level":"open_access","date_created":"2025-01-09T07:36:57Z"}],"month":"08"},{"day":"01","citation":{"short":"M. Mondelli, C. Thrampoulidis, R. Venkataramanan, Foundations of Computational Mathematics 22 (2022) 1513–1566.","mla":"Mondelli, Marco, et al. “Optimal Combination of Linear and Spectral Estimators for Generalized Linear Models.” <i>Foundations of Computational Mathematics</i>, vol. 22, no. 5, Springer, 2022, pp. 1513–66, doi:<a href=\"https://doi.org/10.1007/s10208-021-09531-x\">10.1007/s10208-021-09531-x</a>.","apa":"Mondelli, M., Thrampoulidis, C., &#38; Venkataramanan, R. (2022). Optimal combination of linear and spectral estimators for generalized linear models. <i>Foundations of Computational Mathematics</i>. Springer. <a href=\"https://doi.org/10.1007/s10208-021-09531-x\">https://doi.org/10.1007/s10208-021-09531-x</a>","ieee":"M. Mondelli, C. Thrampoulidis, and R. Venkataramanan, “Optimal combination of linear and spectral estimators for generalized linear models,” <i>Foundations of Computational Mathematics</i>, vol. 22, no. 5. Springer, pp. 1513–1566, 2022.","ama":"Mondelli M, Thrampoulidis C, Venkataramanan R. Optimal combination of linear and spectral estimators for generalized linear models. <i>Foundations of Computational Mathematics</i>. 2022;22(5):1513-1566. doi:<a href=\"https://doi.org/10.1007/s10208-021-09531-x\">10.1007/s10208-021-09531-x</a>","chicago":"Mondelli, Marco, Christos Thrampoulidis, and Ramji Venkataramanan. “Optimal Combination of Linear and Spectral Estimators for Generalized Linear Models.” <i>Foundations of Computational Mathematics</i>. Springer, 2022. <a href=\"https://doi.org/10.1007/s10208-021-09531-x\">https://doi.org/10.1007/s10208-021-09531-x</a>.","ista":"Mondelli M, Thrampoulidis C, Venkataramanan R. 2022. Optimal combination of linear and spectral estimators for generalized linear models. Foundations of Computational Mathematics. 22(5), 1513–1566."},"file_date_updated":"2021-12-13T15:47:54Z","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","keyword":["Applied Mathematics","Computational Theory and Mathematics","Computational Mathematics","Analysis"],"_id":"10211","fulldoi":"https://doi.org/10.1007/s10208-021-09531-x","title":"Optimal combination of linear and spectral estimators for generalized linear models","publication_status":"published","oa_version":"Published Version","tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"oa":1,"external_id":{"arxiv":["2008.03326"],"isi":["000685721000001"]},"page":"1513-1566","project":[{"_id":"B67AFEDC-15C9-11EA-A837-991A96BB2854","name":"IST Austria Open Access Fund"}],"article_type":"original","language":[{"iso":"eng"}],"doi":"10.1007/s10208-021-09531-x","file":[{"relation":"main_file","date_updated":"2021-12-13T15:47:54Z","content_type":"application/pdf","date_created":"2021-12-13T15:47:54Z","access_level":"open_access","file_name":"2021_Springer_Mondelli.pdf","file_size":2305731,"success":1,"creator":"alisjak","file_id":"10542","checksum":"9ea12dd8045a0678000a3a59295221cb"}],"status":"public","date_created":"2021-11-03T10:59:08Z","publication_identifier":{"eissn":["1615-3383"],"issn":["1615-3375"]},"issue":"5","month":"10","arxiv":1,"acknowledgement":"M. Mondelli would like to thank Andrea Montanari for helpful discussions. All the authors would like to thank the anonymous reviewers for their helpful comments.","article_processing_charge":"Yes (via OA deal)","type":"journal_article","scopus_import":"1","volume":22,"department":[{"_id":"MaMo"}],"isi":1,"date_updated":"2025-04-15T06:53:08Z","author":[{"first_name":"Marco","full_name":"Mondelli, Marco","orcid":"0000-0002-3242-7020","last_name":"Mondelli","id":"27EB676C-8706-11E9-9510-7717E6697425"},{"last_name":"Thrampoulidis","first_name":"Christos","full_name":"Thrampoulidis, Christos"},{"last_name":"Venkataramanan","first_name":"Ramji","full_name":"Venkataramanan, Ramji"}],"year":"2022","abstract":[{"text":"We study the problem of recovering an unknown signal 𝑥𝑥 given measurements obtained from a generalized linear model with a Gaussian sensing matrix. Two popular solutions are based on a linear estimator 𝑥𝑥^L and a spectral estimator 𝑥𝑥^s. The former is a data-dependent linear combination of the columns of the measurement matrix, and its analysis is quite simple. The latter is the principal eigenvector of a data-dependent matrix, and a recent line of work has studied its performance. In this paper, we show how to optimally combine 𝑥𝑥^L and 𝑥𝑥^s. At the heart of our analysis is the exact characterization of the empirical joint distribution of (𝑥𝑥,𝑥𝑥^L,𝑥𝑥^s) in the high-dimensional limit. This allows us to compute the Bayes-optimal combination of 𝑥𝑥^L and 𝑥𝑥^s, given the limiting distribution of the signal 𝑥𝑥. When the distribution of the signal is Gaussian, then the Bayes-optimal combination has the form 𝜃𝑥𝑥^L+𝑥𝑥^s and we derive the optimal combination coefficient. In order to establish the limiting distribution of (𝑥𝑥,𝑥𝑥^L,𝑥𝑥^s), we design and analyze an approximate message passing algorithm whose iterates give 𝑥𝑥^L and approach 𝑥𝑥^s. Numerical simulations demonstrate the improvement of the proposed combination with respect to the two methods considered separately.","lang":"eng"}],"intvolume":"        22","publisher":"Springer","publication":"Foundations of Computational Mathematics","date_published":"2022-10-01T00:00:00Z","quality_controlled":"1","ddc":["510"],"has_accepted_license":"1"},{"file":[{"checksum":"f1d372ec3c08ec22e84f8e93e1126b8c","file_id":"9650","creator":"mwintrae","file_size":1455699,"file_name":"Boissonnat-Wintraecken2021_Article_TheTopologicalCorrectnessOfPLA.pdf","access_level":"open_access","date_created":"2021-07-14T06:44:36Z","content_type":"application/pdf","relation":"main_file","date_updated":"2021-07-14T06:44:36Z"}],"status":"public","publication_identifier":{"eissn":["1615-3383"]},"date_created":"2021-07-14T06:44:53Z","month":"01","oa":1,"external_id":{"isi":["000673039600001"]},"page":"967-1012","project":[{"name":"ISTplus - Postdoctoral Fellowships","grant_number":"754411","call_identifier":"H2020","_id":"260C2330-B435-11E9-9278-68D0E5697425"}],"language":[{"iso":"eng"}],"doi":"10.1007/s10208-021-09520-0","article_type":"original","_id":"9649","fulldoi":"https://doi.org/10.1007/s10208-021-09520-0","title":"The topological correctness of PL approximations of isomanifolds","publication_status":"published","tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"oa_version":"Published Version","day":"01","citation":{"ista":"Boissonnat J-D, Wintraecken M. 2022. The topological correctness of PL approximations of isomanifolds. Foundations of Computational Mathematics . 22, 967–1012.","ama":"Boissonnat J-D, Wintraecken M. The topological correctness of PL approximations of isomanifolds. <i>Foundations of Computational Mathematics </i>. 2022;22:967-1012. doi:<a href=\"https://doi.org/10.1007/s10208-021-09520-0\">10.1007/s10208-021-09520-0</a>","chicago":"Boissonnat, Jean-Daniel, and Mathijs Wintraecken. “The Topological Correctness of PL Approximations of Isomanifolds.” <i>Foundations of Computational Mathematics </i>. Springer Nature, 2022. <a href=\"https://doi.org/10.1007/s10208-021-09520-0\">https://doi.org/10.1007/s10208-021-09520-0</a>.","mla":"Boissonnat, Jean-Daniel, and Mathijs Wintraecken. “The Topological Correctness of PL Approximations of Isomanifolds.” <i>Foundations of Computational Mathematics </i>, vol. 22, Springer Nature, 2022, pp. 967–1012, doi:<a href=\"https://doi.org/10.1007/s10208-021-09520-0\">10.1007/s10208-021-09520-0</a>.","short":"J.-D. Boissonnat, M. Wintraecken, Foundations of Computational Mathematics  22 (2022) 967–1012.","ieee":"J.-D. Boissonnat and M. Wintraecken, “The topological correctness of PL approximations of isomanifolds,” <i>Foundations of Computational Mathematics </i>, vol. 22. Springer Nature, pp. 967–1012, 2022.","apa":"Boissonnat, J.-D., &#38; Wintraecken, M. (2022). The topological correctness of PL approximations of isomanifolds. <i>Foundations of Computational Mathematics </i>. Springer Nature. <a href=\"https://doi.org/10.1007/s10208-021-09520-0\">https://doi.org/10.1007/s10208-021-09520-0</a>"},"file_date_updated":"2021-07-14T06:44:36Z","ec_funded":1,"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publication":"Foundations of Computational Mathematics ","date_published":"2022-01-01T00:00:00Z","quality_controlled":"1","ddc":["516"],"has_accepted_license":"1","corr_author":"1","abstract":[{"text":"Isomanifolds are the generalization of isosurfaces to arbitrary dimension and codimension, i.e. manifolds defined as the zero set of some multivariate vector-valued smooth function f : Rd → Rd−n. A natural (and efficient) way to approximate an isomanifold is to consider its Piecewise-Linear (PL) approximation based on a triangulation T of the ambient space Rd. In this paper, we give conditions under which the PL-approximation of an isomanifold is topologically equivalent to the isomanifold. The conditions are easy to satisfy in the sense that they can always be met by taking a sufficiently\r\nfine triangulation T . This contrasts with previous results on the triangulation of manifolds where, in arbitrary dimensions, delicate perturbations are needed to guarantee topological correctness, which leads to strong limitations in practice. We further give a bound on the Fréchet distance between the original isomanifold and its PL-approximation. Finally we show analogous results for the PL-approximation of an isomanifold with boundary.","lang":"eng"}],"intvolume":"        22","publisher":"Springer Nature","type":"journal_article","scopus_import":"1","department":[{"_id":"HeEd"}],"volume":22,"related_material":{"record":[{"relation":"earlier_version","status":"public","id":"7952"}]},"isi":1,"author":[{"first_name":"Jean-Daniel","full_name":"Boissonnat, Jean-Daniel","last_name":"Boissonnat"},{"full_name":"Wintraecken, Mathijs","first_name":"Mathijs","last_name":"Wintraecken","orcid":"0000-0002-7472-2220","id":"307CFBC8-F248-11E8-B48F-1D18A9856A87"}],"date_updated":"2025-04-22T13:45:18Z","year":"2022","acknowledgement":"First and foremost, we acknowledge Siargey Kachanovich for discussions. We thank Herbert Edelsbrunner and all members of his group, all former and current members of the Datashape team (formerly known as Geometrica), and André Lieutier for encouragement. We further thank the reviewers of Foundations of Computational Mathematics and the reviewers and program committee of the Symposium on Computational Geometry for their feedback, which improved the exposition.\r\nThis work was funded by the European Research Council under the European Union’s ERC Grant Agreement number 339025 GUDHI (Algorithmic Foundations of Geometric Understanding in Higher Dimensions). This work was also supported by the French government, through the 3IA Côte d’Azur Investments in the Future project managed by the National Research Agency (ANR) with the reference number ANR-19-P3IA-0002. Mathijs Wintraecken also received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement no. 754411.","article_processing_charge":"Yes (via OA deal)"},{"date_created":"2019-06-16T21:59:14Z","publication_identifier":{"issn":["1615-3375"],"eissn":["1615-3383"]},"status":"public","month":"04","project":[{"grant_number":"P31312","call_identifier":"FWF","_id":"26611F5C-B435-11E9-9278-68D0E5697425","name":"Algorithms for Embeddings and Homotopy Theory"}],"external_id":{"isi":["000522437400004"],"arxiv":["1312.2337"]},"page":"311-330","oa":1,"language":[{"iso":"eng"}],"doi":"10.1007/s10208-019-09419-x","article_type":"original","title":"Are two given maps homotopic? An algorithmic viewpoint","fulldoi":"https://doi.org/10.1007/s10208-019-09419-x","_id":"6563","oa_version":"Preprint","publication_status":"published","day":"01","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","citation":{"ama":"Filakovský M, Vokřínek L. Are two given maps homotopic? An algorithmic viewpoint. <i>Foundations of Computational Mathematics</i>. 2020;20:311-330. doi:<a href=\"https://doi.org/10.1007/s10208-019-09419-x\">10.1007/s10208-019-09419-x</a>","chicago":"Filakovský, Marek, and Lukas Vokřínek. “Are Two given Maps Homotopic? An Algorithmic Viewpoint.” <i>Foundations of Computational Mathematics</i>. Springer Nature, 2020. <a href=\"https://doi.org/10.1007/s10208-019-09419-x\">https://doi.org/10.1007/s10208-019-09419-x</a>.","ista":"Filakovský M, Vokřínek L. 2020. Are two given maps homotopic? An algorithmic viewpoint. Foundations of Computational Mathematics. 20, 311–330.","apa":"Filakovský, M., &#38; Vokřínek, L. (2020). Are two given maps homotopic? An algorithmic viewpoint. <i>Foundations of Computational Mathematics</i>. Springer Nature. <a href=\"https://doi.org/10.1007/s10208-019-09419-x\">https://doi.org/10.1007/s10208-019-09419-x</a>","ieee":"M. Filakovský and L. Vokřínek, “Are two given maps homotopic? An algorithmic viewpoint,” <i>Foundations of Computational Mathematics</i>, vol. 20. Springer Nature, pp. 311–330, 2020.","mla":"Filakovský, Marek, and Lukas Vokřínek. “Are Two given Maps Homotopic? An Algorithmic Viewpoint.” <i>Foundations of Computational Mathematics</i>, vol. 20, Springer Nature, 2020, pp. 311–30, doi:<a href=\"https://doi.org/10.1007/s10208-019-09419-x\">10.1007/s10208-019-09419-x</a>.","short":"M. Filakovský, L. Vokřínek, Foundations of Computational Mathematics 20 (2020) 311–330."},"date_published":"2020-04-01T00:00:00Z","publication":"Foundations of Computational Mathematics","quality_controlled":"1","abstract":[{"lang":"eng","text":"This paper presents two algorithms. The first decides the existence of a pointed homotopy between given simplicial maps 𝑓,𝑔:𝑋→𝑌, and the second computes the group [𝛴𝑋,𝑌]∗ of pointed homotopy classes of maps from a suspension; in both cases, the target Y is assumed simply connected. More generally, these algorithms work relative to 𝐴⊆𝑋."}],"publisher":"Springer Nature","intvolume":"        20","volume":20,"department":[{"_id":"UlWa"}],"scopus_import":"1","type":"journal_article","year":"2020","date_updated":"2025-07-10T11:53:32Z","author":[{"last_name":"Filakovský","id":"3E8AF77E-F248-11E8-B48F-1D18A9856A87","full_name":"Filakovský, Marek","first_name":"Marek"},{"last_name":"Vokřínek","full_name":"Vokřínek, Lukas","first_name":"Lukas"}],"main_file_link":[{"url":"https://arxiv.org/abs/1312.2337","open_access":"1"}],"isi":1,"article_processing_charge":"No","arxiv":1},{"volume":19,"type":"journal_article","date_updated":"2021-01-12T08:08:28Z","author":[{"full_name":"Mondelli, Marco","first_name":"Marco","id":"27EB676C-8706-11E9-9510-7717E6697425","orcid":"0000-0002-3242-7020","last_name":"Mondelli"},{"last_name":"Montanari","first_name":"Andrea","full_name":"Montanari, Andrea"}],"year":"2019","main_file_link":[{"url":"https://arxiv.org/abs/1708.05932","open_access":"1"}],"arxiv":1,"extern":"1","publication":"Foundations of Computational Mathematics","date_published":"2019-06-01T00:00:00Z","quality_controlled":"1","abstract":[{"lang":"eng","text":"In phase retrieval, we want to recover an unknown signal 𝑥∈ℂ𝑑 from n quadratic measurements of the form 𝑦𝑖=|⟨𝑎𝑖,𝑥⟩|2+𝑤𝑖, where 𝑎𝑖∈ℂ𝑑 are known sensing vectors and 𝑤𝑖 is measurement noise. We ask the following weak recovery question: What is the minimum number of measurements n needed to produce an estimator 𝑥^(𝑦) that is positively correlated with the signal 𝑥? We consider the case of Gaussian vectors 𝑎𝑎𝑖. We prove that—in the high-dimensional limit—a sharp phase transition takes place, and we locate the threshold in the regime of vanishingly small noise. For 𝑛≤𝑑−𝑜(𝑑), no estimator can do significantly better than random and achieve a strictly positive correlation. For 𝑛≥𝑑+𝑜(𝑑), a simple spectral estimator achieves a positive correlation. Surprisingly, numerical simulations with the same spectral estimator demonstrate promising performance with realistic sensing matrices. Spectral methods are used to initialize non-convex optimization algorithms in phase retrieval, and our approach can boost the performance in this setting as well. Our impossibility result is based on classical information-theoretic arguments. The spectral algorithm computes the leading eigenvector of a weighted empirical covariance matrix. We obtain a sharp characterization of the spectral properties of this random matrix using tools from free probability and generalizing a recent result by Lu and Li. Both the upper bound and lower bound generalize beyond phase retrieval to measurements 𝑦𝑖 produced according to a generalized linear model. As a by-product of our analysis, we compare the threshold of the proposed spectral method with that of a message passing algorithm."}],"publisher":"Springer","intvolume":"        19","_id":"6662","title":"Fundamental limits of weak recovery with applications to phase retrieval","fulldoi":"https://doi.org/10.1007/s10208-018-9395-y","oa_version":"Preprint","publication_status":"published","day":"01","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","citation":{"ieee":"M. Mondelli and A. Montanari, “Fundamental limits of weak recovery with applications to phase retrieval,” <i>Foundations of Computational Mathematics</i>, vol. 19, no. 3. Springer, pp. 703–773, 2019.","apa":"Mondelli, M., &#38; Montanari, A. (2019). Fundamental limits of weak recovery with applications to phase retrieval. <i>Foundations of Computational Mathematics</i>. Springer. <a href=\"https://doi.org/10.1007/s10208-018-9395-y\">https://doi.org/10.1007/s10208-018-9395-y</a>","mla":"Mondelli, Marco, and Andrea Montanari. “Fundamental Limits of Weak Recovery with Applications to Phase Retrieval.” <i>Foundations of Computational Mathematics</i>, vol. 19, no. 3, Springer, 2019, pp. 703–73, doi:<a href=\"https://doi.org/10.1007/s10208-018-9395-y\">10.1007/s10208-018-9395-y</a>.","short":"M. Mondelli, A. Montanari, Foundations of Computational Mathematics 19 (2019) 703–773.","ista":"Mondelli M, Montanari A. 2019. Fundamental limits of weak recovery with applications to phase retrieval. Foundations of Computational Mathematics. 19(3), 703–773.","ama":"Mondelli M, Montanari A. Fundamental limits of weak recovery with applications to phase retrieval. <i>Foundations of Computational Mathematics</i>. 2019;19(3):703-773. doi:<a href=\"https://doi.org/10.1007/s10208-018-9395-y\">10.1007/s10208-018-9395-y</a>","chicago":"Mondelli, Marco, and Andrea Montanari. “Fundamental Limits of Weak Recovery with Applications to Phase Retrieval.” <i>Foundations of Computational Mathematics</i>. Springer, 2019. <a href=\"https://doi.org/10.1007/s10208-018-9395-y\">https://doi.org/10.1007/s10208-018-9395-y</a>."},"status":"public","date_created":"2019-07-22T13:23:48Z","publication_identifier":{"eissn":["1615-3383"]},"month":"06","issue":"3","oa":1,"page":"703-773","external_id":{"arxiv":["1708.05932"]},"doi":"10.1007/s10208-018-9395-y","language":[{"iso":"eng"}],"article_type":"original"}]