--- _id: '13129' 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." acknowledgement: Open access funding provided by Institute of Science and Technology (IST Austria). article_processing_charge: Yes (via OA deal) article_type: original author: - first_name: Nicolas full_name: Clozeau, Nicolas id: fea1b376-906f-11eb-847d-b2c0cf46455b last_name: Clozeau - first_name: Marc full_name: Josien, Marc last_name: Josien - first_name: Felix full_name: Otto, Felix last_name: Otto - first_name: Qiang full_name: Xu, Qiang last_name: Xu citation: ama: 'Clozeau N, Josien M, Otto F, Xu Q. Bias in the representative volume element method: Periodize the ensemble instead of its realizations. Foundations of Computational Mathematics. 2023. doi:10.1007/s10208-023-09613-y' apa: 'Clozeau, N., Josien, M., Otto, F., & Xu, Q. (2023). Bias in the representative volume element method: Periodize the ensemble instead of its realizations. Foundations of Computational Mathematics. Springer Nature. https://doi.org/10.1007/s10208-023-09613-y' chicago: 'Clozeau, Nicolas, Marc Josien, Felix Otto, and Qiang Xu. “Bias in the Representative Volume Element Method: Periodize the Ensemble Instead of Its Realizations.” Foundations of Computational Mathematics. Springer Nature, 2023. https://doi.org/10.1007/s10208-023-09613-y.' ieee: 'N. Clozeau, M. Josien, F. Otto, and Q. Xu, “Bias in the representative volume element method: Periodize the ensemble instead of its realizations,” Foundations of Computational Mathematics. Springer Nature, 2023.' ista: 'Clozeau N, Josien M, Otto F, Xu Q. 2023. Bias in the representative volume element method: Periodize the ensemble instead of its realizations. Foundations of Computational Mathematics.' mla: 'Clozeau, Nicolas, et al. “Bias in the Representative Volume Element Method: Periodize the Ensemble Instead of Its Realizations.” Foundations of Computational Mathematics, Springer Nature, 2023, doi:10.1007/s10208-023-09613-y.' short: N. Clozeau, M. Josien, F. Otto, Q. Xu, Foundations of Computational Mathematics (2023). date_created: 2023-06-11T22:00:40Z date_published: 2023-05-30T00:00:00Z date_updated: 2023-08-02T06:12:39Z day: '30' ddc: - '510' department: - _id: JuFi doi: 10.1007/s10208-023-09613-y external_id: isi: - '000999623100001' has_accepted_license: '1' isi: 1 language: - iso: eng main_file_link: - open_access: '1' url: https://doi.org/10.1007/s10208-023-09613-y month: '05' oa: 1 oa_version: Published Version publication: Foundations of Computational Mathematics publication_identifier: eissn: - 1615-3383 issn: - 1615-3375 publication_status: epub_ahead publisher: Springer Nature quality_controlled: '1' scopus_import: '1' status: public title: 'Bias in the representative volume element method: Periodize the ensemble instead of its realizations' tmp: image: /images/cc_by.png legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0) short: CC BY (4.0) type: journal_article user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8 year: '2023' ... --- _id: '9649' abstract: - lang: eng 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." 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) article_type: original author: - first_name: Jean-Daniel full_name: Boissonnat, Jean-Daniel last_name: Boissonnat - first_name: Mathijs full_name: Wintraecken, Mathijs id: 307CFBC8-F248-11E8-B48F-1D18A9856A87 last_name: Wintraecken orcid: 0000-0002-7472-2220 citation: ama: Boissonnat J-D, Wintraecken M. The topological correctness of PL approximations of isomanifolds. Foundations of Computational Mathematics . 2022;22:967-1012. doi:10.1007/s10208-021-09520-0 apa: Boissonnat, J.-D., & Wintraecken, M. (2022). The topological correctness of PL approximations of isomanifolds. Foundations of Computational Mathematics . Springer Nature. https://doi.org/10.1007/s10208-021-09520-0 chicago: Boissonnat, Jean-Daniel, and Mathijs Wintraecken. “The Topological Correctness of PL Approximations of Isomanifolds.” Foundations of Computational Mathematics . Springer Nature, 2022. https://doi.org/10.1007/s10208-021-09520-0. ieee: J.-D. Boissonnat and M. Wintraecken, “The topological correctness of PL approximations of isomanifolds,” Foundations of Computational Mathematics , vol. 22. Springer Nature, pp. 967–1012, 2022. ista: Boissonnat J-D, Wintraecken M. 2022. The topological correctness of PL approximations of isomanifolds. Foundations of Computational Mathematics . 22, 967–1012. mla: Boissonnat, Jean-Daniel, and Mathijs Wintraecken. “The Topological Correctness of PL Approximations of Isomanifolds.” Foundations of Computational Mathematics , vol. 22, Springer Nature, 2022, pp. 967–1012, doi:10.1007/s10208-021-09520-0. short: J.-D. Boissonnat, M. Wintraecken, Foundations of Computational Mathematics 22 (2022) 967–1012. date_created: 2021-07-14T06:44:53Z date_published: 2022-01-01T00:00:00Z date_updated: 2023-08-02T06:49:17Z day: '01' ddc: - '516' department: - _id: HeEd doi: 10.1007/s10208-021-09520-0 ec_funded: 1 external_id: isi: - '000673039600001' file: - access_level: open_access checksum: f1d372ec3c08ec22e84f8e93e1126b8c content_type: application/pdf creator: mwintrae date_created: 2021-07-14T06:44:36Z date_updated: 2021-07-14T06:44:36Z file_id: '9650' file_name: Boissonnat-Wintraecken2021_Article_TheTopologicalCorrectnessOfPLA.pdf file_size: 1455699 relation: main_file file_date_updated: 2021-07-14T06:44:36Z has_accepted_license: '1' intvolume: ' 22' isi: 1 language: - iso: eng month: '0' oa: 1 oa_version: Published Version page: 967-1012 project: - _id: 260C2330-B435-11E9-9278-68D0E5697425 call_identifier: H2020 grant_number: '754411' name: ISTplus - Postdoctoral Fellowships publication: 'Foundations of Computational Mathematics ' publication_identifier: eissn: - 1615-3383 publication_status: published publisher: Springer Nature quality_controlled: '1' related_material: record: - id: '7952' relation: earlier_version status: public scopus_import: '1' status: public title: The topological correctness of PL approximations of isomanifolds tmp: image: /images/cc_by.png legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0) short: CC BY (4.0) type: journal_article user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8 volume: 22 year: '2022' ... --- _id: '10211' abstract: - lang: eng text: "We study the problem of recovering an unknown signal \U0001D465\U0001D465 given measurements obtained from a generalized linear model with a Gaussian sensing matrix. Two popular solutions are based on a linear estimator \U0001D465\U0001D465^L and a spectral estimator \U0001D465\U0001D465^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 \U0001D465\U0001D465^L and \U0001D465\U0001D465^s. At the heart of our analysis is the exact characterization of the empirical joint distribution of (\U0001D465\U0001D465,\U0001D465\U0001D465^L,\U0001D465\U0001D465^s) in the high-dimensional limit. This allows us to compute the Bayes-optimal combination of \U0001D465\U0001D465^L and \U0001D465\U0001D465^s, given the limiting distribution of the signal \U0001D465\U0001D465. When the distribution of the signal is Gaussian, then the Bayes-optimal combination has the form \U0001D703\U0001D465\U0001D465^L+\U0001D465\U0001D465^s and we derive the optimal combination coefficient. In order to establish the limiting distribution of (\U0001D465\U0001D465,\U0001D465\U0001D465^L,\U0001D465\U0001D465^s), we design and analyze an approximate message passing algorithm whose iterates give \U0001D465\U0001D465^L and approach \U0001D465\U0001D465^s. Numerical simulations demonstrate the improvement of the proposed combination with respect to the two methods considered separately." 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) article_type: original author: - first_name: Marco full_name: Mondelli, Marco id: 27EB676C-8706-11E9-9510-7717E6697425 last_name: Mondelli orcid: 0000-0002-3242-7020 - first_name: Christos full_name: Thrampoulidis, Christos last_name: Thrampoulidis - first_name: Ramji full_name: Venkataramanan, Ramji last_name: Venkataramanan citation: ama: Mondelli M, Thrampoulidis C, Venkataramanan R. Optimal combination of linear and spectral estimators for generalized linear models. Foundations of Computational Mathematics. 2021. doi:10.1007/s10208-021-09531-x apa: Mondelli, M., Thrampoulidis, C., & Venkataramanan, R. (2021). Optimal combination of linear and spectral estimators for generalized linear models. Foundations of Computational Mathematics. Springer. https://doi.org/10.1007/s10208-021-09531-x chicago: Mondelli, Marco, Christos Thrampoulidis, and Ramji Venkataramanan. “Optimal Combination of Linear and Spectral Estimators for Generalized Linear Models.” Foundations of Computational Mathematics. Springer, 2021. https://doi.org/10.1007/s10208-021-09531-x. ieee: M. Mondelli, C. Thrampoulidis, and R. Venkataramanan, “Optimal combination of linear and spectral estimators for generalized linear models,” Foundations of Computational Mathematics. Springer, 2021. ista: Mondelli M, Thrampoulidis C, Venkataramanan R. 2021. Optimal combination of linear and spectral estimators for generalized linear models. Foundations of Computational Mathematics. mla: Mondelli, Marco, et al. “Optimal Combination of Linear and Spectral Estimators for Generalized Linear Models.” Foundations of Computational Mathematics, Springer, 2021, doi:10.1007/s10208-021-09531-x. short: M. Mondelli, C. Thrampoulidis, R. Venkataramanan, Foundations of Computational Mathematics (2021). date_created: 2021-11-03T10:59:08Z date_published: 2021-08-17T00:00:00Z date_updated: 2023-09-05T14:13:57Z day: '17' ddc: - '510' department: - _id: MaMo doi: 10.1007/s10208-021-09531-x external_id: arxiv: - '2008.03326' isi: - '000685721000001' file: - access_level: open_access checksum: 9ea12dd8045a0678000a3a59295221cb content_type: application/pdf creator: alisjak date_created: 2021-12-13T15:47:54Z date_updated: 2021-12-13T15:47:54Z file_id: '10542' file_name: 2021_Springer_Mondelli.pdf file_size: 2305731 relation: main_file success: 1 file_date_updated: 2021-12-13T15:47:54Z has_accepted_license: '1' isi: 1 keyword: - Applied Mathematics - Computational Theory and Mathematics - Computational Mathematics - Analysis language: - iso: eng month: '08' oa: 1 oa_version: Published Version project: - _id: B67AFEDC-15C9-11EA-A837-991A96BB2854 name: IST Austria Open Access Fund publication: Foundations of Computational Mathematics publication_identifier: eissn: - 1615-3383 issn: - 1615-3375 publication_status: published publisher: Springer quality_controlled: '1' scopus_import: '1' status: public title: Optimal combination of linear and spectral estimators for generalized linear models tmp: image: /images/cc_by.png legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0) short: CC BY (4.0) type: journal_article user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1 year: '2021' ... --- _id: '6662' abstract: - lang: eng text: "In phase retrieval, we want to recover an unknown signal \U0001D465∈ℂ\U0001D451 from n quadratic measurements of the form \U0001D466\U0001D456=|⟨\U0001D44E\U0001D456,\U0001D465⟩|2+\U0001D464\U0001D456, where \U0001D44E\U0001D456∈ℂ\U0001D451 are known sensing vectors and \U0001D464\U0001D456 is measurement noise. We ask the following weak recovery question: What is the minimum number of measurements n needed to produce an estimator \U0001D465^(\U0001D466) that is positively correlated with the signal \U0001D465? We consider the case of Gaussian vectors \U0001D44E\U0001D44E\U0001D456. 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 \U0001D45B≤\U0001D451−\U0001D45C(\U0001D451), no estimator can do significantly better than random and achieve a strictly positive correlation. For \U0001D45B≥\U0001D451+\U0001D45C(\U0001D451), 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 \U0001D466\U0001D456 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." article_type: original author: - first_name: Marco full_name: Mondelli, Marco id: 27EB676C-8706-11E9-9510-7717E6697425 last_name: Mondelli orcid: 0000-0002-3242-7020 - first_name: Andrea full_name: Montanari, Andrea last_name: Montanari citation: ama: Mondelli M, Montanari A. Fundamental limits of weak recovery with applications to phase retrieval. Foundations of Computational Mathematics. 2019;19(3):703-773. doi:10.1007/s10208-018-9395-y apa: Mondelli, M., & Montanari, A. (2019). Fundamental limits of weak recovery with applications to phase retrieval. Foundations of Computational Mathematics. Springer. https://doi.org/10.1007/s10208-018-9395-y chicago: Mondelli, Marco, and Andrea Montanari. “Fundamental Limits of Weak Recovery with Applications to Phase Retrieval.” Foundations of Computational Mathematics. Springer, 2019. https://doi.org/10.1007/s10208-018-9395-y. ieee: M. Mondelli and A. Montanari, “Fundamental limits of weak recovery with applications to phase retrieval,” Foundations of Computational Mathematics, vol. 19, no. 3. Springer, pp. 703–773, 2019. ista: Mondelli M, Montanari A. 2019. Fundamental limits of weak recovery with applications to phase retrieval. Foundations of Computational Mathematics. 19(3), 703–773. mla: Mondelli, Marco, and Andrea Montanari. “Fundamental Limits of Weak Recovery with Applications to Phase Retrieval.” Foundations of Computational Mathematics, vol. 19, no. 3, Springer, 2019, pp. 703–73, doi:10.1007/s10208-018-9395-y. short: M. Mondelli, A. Montanari, Foundations of Computational Mathematics 19 (2019) 703–773. date_created: 2019-07-22T13:23:48Z date_published: 2019-06-01T00:00:00Z date_updated: 2021-01-12T08:08:28Z day: '01' doi: 10.1007/s10208-018-9395-y extern: '1' external_id: arxiv: - '1708.05932' intvolume: ' 19' issue: '3' language: - iso: eng main_file_link: - open_access: '1' url: https://arxiv.org/abs/1708.05932 month: '06' oa: 1 oa_version: Preprint page: 703-773 publication: Foundations of Computational Mathematics publication_identifier: eissn: - 1615-3383 publication_status: published publisher: Springer quality_controlled: '1' status: public title: Fundamental limits of weak recovery with applications to phase retrieval type: journal_article user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 19 year: '2019' ...