---
OA_place: publisher
OA_type: hybrid
PlanS_conform: '1'
_id: '14703'
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.
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)
article_type: original
arxiv: 1
author:
- first_name: Sadashige
full_name: Ishida, Sadashige
id: 6F7C4B96-A8E9-11E9-A7CA-09ECE5697425
last_name: Ishida
orcid: 0000-0002-3121-3100
- first_name: Hugo
full_name: Lavenant, Hugo
last_name: Lavenant
citation:
ama: Ishida S, Lavenant H. Quantitative convergence of a discretization of dynamic
optimal transport using the dual formulation. Foundations of Computational
Mathematics. 2026;26:349-384. doi:10.1007/s10208-024-09686-3
apa: Ishida, S., & Lavenant, H. (2026). Quantitative convergence of a discretization
of dynamic optimal transport using the dual formulation. Foundations of Computational
Mathematics. Springer Nature. https://doi.org/10.1007/s10208-024-09686-3
chicago: Ishida, Sadashige, and Hugo Lavenant. “Quantitative Convergence of a Discretization
of Dynamic Optimal Transport Using the Dual Formulation.” Foundations of Computational
Mathematics. Springer Nature, 2026. https://doi.org/10.1007/s10208-024-09686-3.
ieee: S. Ishida and H. Lavenant, “Quantitative convergence of a discretization of
dynamic optimal transport using the dual formulation,” Foundations of Computational
Mathematics, vol. 26. Springer Nature, pp. 349–384, 2026.
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.
mla: Ishida, Sadashige, and Hugo Lavenant. “Quantitative Convergence of a Discretization
of Dynamic Optimal Transport Using the Dual Formulation.” Foundations of Computational
Mathematics, vol. 26, Springer Nature, 2026, pp. 349–84, doi:10.1007/s10208-024-09686-3.
short: S. Ishida, H. Lavenant, Foundations of Computational Mathematics 26 (2026)
349–384.
corr_author: '1'
das_tickbox: '0'
date_created: 2023-12-21T10:14:37Z
date_published: 2026-02-01T00:00:00Z
date_updated: 2026-07-23T05:39:38Z
day: '01'
ddc:
- '000'
department:
- _id: GradSch
- _id: ChWo
doi: 10.1007/s10208-024-09686-3
external_id:
arxiv:
- '2312.12213'
isi:
- '001352503300001'
file:
- access_level: open_access
checksum: 30671f88e792e8b75ae3e698ac4c131c
content_type: application/pdf
creator: dernst
date_created: 2026-07-23T05:37:52Z
date_updated: 2026-07-23T05:37:52Z
file_id: '22384'
file_name: 2026_FoundCompMath_Ishida.pdf
file_size: 1240012
relation: main_file
success: 1
file_date_updated: 2026-07-23T05:37:52Z
has_accepted_license: '1'
intvolume: ' 26'
isi: 1
keyword:
- Optimal transport
- Hamilton-Jacobi equation
- convex optimization
language:
- iso: eng
month: '02'
oa: 1
oa_version: Published Version
page: 349-384
project:
- _id: 34bc2376-11ca-11ed-8bc3-9a3b3961a088
grant_number: '101045083'
name: Computational Discovery of Numerical Algorithms for Animation and Simulation
of Natural Phenomena
publication: Foundations of Computational Mathematics
publication_identifier:
eissn:
- 1615-3383
issn:
- 1615-3375
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
researchdata_availability: no
scopus_import: '1'
status: public
supplementarymaterial: no
title: Quantitative convergence of a discretization of dynamic optimal transport using
the dual formulation
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: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 26
year: '2026'
...
---
OA_place: publisher
OA_type: hybrid
PlanS_conform: '1'
_id: '22648'
abstract:
- lang: eng
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.
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).
article_processing_charge: Yes (via OA deal)
article_type: original
arxiv: 1
author:
- first_name: Tamal K.
full_name: Dey, Tamal K.
last_name: Dey
- first_name: Michał
full_name: Lipiński, Michał
id: dfffb474-4317-11ee-8f5c-fe3fc95a425e
last_name: Lipiński
orcid: 0000-0001-9789-9750
- first_name: Manuel
full_name: Soriano Trigueros, Manuel
id: 15ebd7cf-15bf-11ee-aebd-bb4bb5121ea8
last_name: Soriano Trigueros
orcid: 0000-0003-2449-1433
citation:
ama: 'Dey TK, Lipiński M, Soriano Trigueros M. Conley-Morse persistence barcode:
A homological signature of combinatorial bifurcations. Foundations of Computational
Mathematics. 2026. doi:10.1007/s10208-026-09766-6'
apa: 'Dey, T. K., Lipiński, M., & Soriano Trigueros, M. (2026). Conley-Morse
persistence barcode: A homological signature of combinatorial bifurcations. Foundations
of Computational Mathematics. Springer. https://doi.org/10.1007/s10208-026-09766-6'
chicago: 'Dey, Tamal K., Michał Lipiński, and Manuel Soriano Trigueros. “Conley-Morse
Persistence Barcode: A Homological Signature of Combinatorial Bifurcations.” Foundations
of Computational Mathematics. Springer, 2026. https://doi.org/10.1007/s10208-026-09766-6.'
ieee: 'T. K. Dey, M. Lipiński, and M. Soriano Trigueros, “Conley-Morse persistence
barcode: A homological signature of combinatorial bifurcations,” Foundations
of Computational Mathematics. Springer, 2026.'
ista: 'Dey TK, Lipiński M, Soriano Trigueros M. 2026. Conley-Morse persistence barcode:
A homological signature of combinatorial bifurcations. Foundations of Computational
Mathematics.'
mla: 'Dey, Tamal K., et al. “Conley-Morse Persistence Barcode: A Homological Signature
of Combinatorial Bifurcations.” Foundations of Computational Mathematics,
Springer, 2026, doi:10.1007/s10208-026-09766-6.'
short: T.K. Dey, M. Lipiński, M. Soriano Trigueros, Foundations of Computational
Mathematics (2026).
corr_author: '1'
das_tickbox: '0'
date_created: 2026-08-05T06:11:30Z
date_published: 2026-08-04T00:00:00Z
date_updated: 2026-08-11T06:13:33Z
day: '04'
ddc:
- '500'
department:
- _id: HeEd
doi: 10.1007/s10208-026-09766-6
ec_funded: 1
external_id:
arxiv:
- '2504.17105'
has_accepted_license: '1'
keyword:
- Multivector field
- Conley index
- Morse decomposition
- Bifurcation
- Continuation
- Zigzag persistence
- Persistence barcode
- Gentle algebra
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.1007/s10208-026-09766-6
month: '08'
oa: 1
oa_version: Published Version
project:
- _id: fc2ed2f7-9c52-11eb-aca3-c01059dda49c
call_identifier: H2020
grant_number: '101034413'
name: 'IST-BRIDGE: International postdoctoral program'
publication: Foundations of Computational Mathematics
publication_identifier:
eissn:
- 1615-3383
issn:
- 1615-3375
publication_status: epub_ahead
publisher: Springer
quality_controlled: '1'
researchdata_availability: no
scopus_import: '1'
status: public
supplementarymaterial: yes
title: 'Conley-Morse persistence barcode: A homological signature of combinatorial
bifurcations'
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: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2026'
...
---
OA_place: publisher
OA_type: hybrid
PlanS_conform: '1'
_id: '20407'
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.
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)
article_type: original
arxiv: 1
author:
- first_name: Henrique
full_name: Ennes, Henrique
last_name: Ennes
- first_name: Raphaël
full_name: Tinarrage, Raphaël
id: 40ebcc9d-905f-11ef-bf0a-dc475da8a04e
last_name: Tinarrage
orcid: 0000-0002-1404-1095
citation:
ama: 'Ennes H, Tinarrage R. LieDetect: Detection of representation orbits of compact
Lie groups from point clouds. Foundations of Computational Mathematics.
2025. doi:10.1007/s10208-025-09728-4'
apa: 'Ennes, H., & Tinarrage, R. (2025). LieDetect: Detection of representation
orbits of compact Lie groups from point clouds. Foundations of Computational
Mathematics. Springer Nature. https://doi.org/10.1007/s10208-025-09728-4'
chicago: 'Ennes, Henrique, and Raphaël Tinarrage. “LieDetect: Detection of Representation
Orbits of Compact Lie Groups from Point Clouds.” Foundations of Computational
Mathematics. Springer Nature, 2025. https://doi.org/10.1007/s10208-025-09728-4.'
ieee: 'H. Ennes and R. Tinarrage, “LieDetect: Detection of representation orbits
of compact Lie groups from point clouds,” Foundations of Computational Mathematics.
Springer Nature, 2025.'
ista: 'Ennes H, Tinarrage R. 2025. LieDetect: Detection of representation orbits
of compact Lie groups from point clouds. Foundations of Computational Mathematics.'
mla: 'Ennes, Henrique, and Raphaël Tinarrage. “LieDetect: Detection of Representation
Orbits of Compact Lie Groups from Point Clouds.” Foundations of Computational
Mathematics, Springer Nature, 2025, doi:10.1007/s10208-025-09728-4.'
short: H. Ennes, R. Tinarrage, Foundations of Computational Mathematics (2025).
corr_author: '1'
date_created: 2025-09-28T22:01:27Z
date_published: 2025-09-15T00:00:00Z
date_updated: 2026-06-18T18:22:42Z
day: '15'
ddc:
- '500'
department:
- _id: UlWa
doi: 10.1007/s10208-025-09728-4
external_id:
arxiv:
- '2309.03086'
isi:
- '001571197200001'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.1007/s10208-025-09728-4
month: '09'
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: 'LieDetect: Detection of representation orbits of compact Lie groups from point
clouds'
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2025'
...
---
OA_place: publisher
OA_type: hybrid
_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. 2024;24:1305-1387. doi:10.1007/s10208-023-09613-y'
apa: '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. 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, 2024. 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, vol. 24. Springer Nature, pp. 1305–1387, 2024.'
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.'
mla: 'Clozeau, Nicolas, et al. “Bias in the Representative Volume Element Method:
Periodize the Ensemble Instead of Its Realizations.” Foundations of Computational
Mathematics, vol. 24, Springer Nature, 2024, pp. 1305–87, doi:10.1007/s10208-023-09613-y.'
short: N. Clozeau, M. Josien, F. Otto, Q. Xu, Foundations of Computational Mathematics
24 (2024) 1305–1387.
corr_author: '1'
date_created: 2023-06-11T22:00:40Z
date_published: 2024-08-01T00:00:00Z
date_updated: 2025-01-09T07:37:50Z
day: '01'
ddc:
- '510'
department:
- _id: JuFi
doi: 10.1007/s10208-023-09613-y
external_id:
isi:
- '000999623100001'
file:
- access_level: open_access
checksum: ec0582e2b55e2703a7da2686ae0d682e
content_type: application/pdf
creator: dernst
date_created: 2025-01-09T07:36:57Z
date_updated: 2025-01-09T07:36:57Z
file_id: '18782'
file_name: 2024_FoundCompMath_Clozeau.pdf
file_size: 1454406
relation: main_file
success: 1
file_date_updated: 2025-01-09T07:36:57Z
has_accepted_license: '1'
intvolume: ' 24'
isi: 1
language:
- iso: eng
month: '08'
oa: 1
oa_version: Published Version
page: 1305-1387
publication: Foundations of Computational Mathematics
publication_identifier:
eissn:
- 1615-3383
issn:
- 1615-3375
publication_status: published
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: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 24
year: '2024'
...
---
_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
arxiv: 1
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. 2022;22(5):1513-1566. doi:10.1007/s10208-021-09531-x
apa: Mondelli, M., Thrampoulidis, C., & Venkataramanan, R. (2022). 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, 2022. 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, vol. 22, no. 5. Springer, pp. 1513–1566, 2022.
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.
mla: Mondelli, Marco, et al. “Optimal Combination of Linear and Spectral Estimators
for Generalized Linear Models.” Foundations of Computational Mathematics,
vol. 22, no. 5, Springer, 2022, pp. 1513–66, doi:10.1007/s10208-021-09531-x.
short: M. Mondelli, C. Thrampoulidis, R. Venkataramanan, Foundations of Computational
Mathematics 22 (2022) 1513–1566.
date_created: 2021-11-03T10:59:08Z
date_published: 2022-10-01T00:00:00Z
date_updated: 2025-04-15T06:53:08Z
day: '01'
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'
intvolume: ' 22'
isi: 1
issue: '5'
keyword:
- Applied Mathematics
- Computational Theory and Mathematics
- Computational Mathematics
- Analysis
language:
- iso: eng
month: '10'
oa: 1
oa_version: Published Version
page: 1513-1566
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: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 22
year: '2022'
...
---
_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.
corr_author: '1'
date_created: 2021-07-14T06:44:53Z
date_published: 2022-01-01T00:00:00Z
date_updated: 2025-04-22T13:45:18Z
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: '01'
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: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 22
year: '2022'
...
---
_id: '6563'
abstract:
- lang: eng
text: "This paper presents two algorithms. The first decides the existence of a
pointed homotopy between given simplicial maps \U0001D453,\U0001D454:\U0001D44B→\U0001D44C,
and the second computes the group [\U0001D6F4\U0001D44B,\U0001D44C]∗ 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 \U0001D434⊆\U0001D44B."
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Marek
full_name: Filakovský, Marek
id: 3E8AF77E-F248-11E8-B48F-1D18A9856A87
last_name: Filakovský
- first_name: Lukas
full_name: Vokřínek, Lukas
last_name: Vokřínek
citation:
ama: Filakovský M, Vokřínek L. Are two given maps homotopic? An algorithmic viewpoint.
Foundations of Computational Mathematics. 2020;20:311-330. doi:10.1007/s10208-019-09419-x
apa: Filakovský, M., & Vokřínek, L. (2020). Are two given maps homotopic? An
algorithmic viewpoint. Foundations of Computational Mathematics. Springer
Nature. https://doi.org/10.1007/s10208-019-09419-x
chicago: Filakovský, Marek, and Lukas Vokřínek. “Are Two given Maps Homotopic? An
Algorithmic Viewpoint.” Foundations of Computational Mathematics. Springer
Nature, 2020. https://doi.org/10.1007/s10208-019-09419-x.
ieee: M. Filakovský and L. Vokřínek, “Are two given maps homotopic? An algorithmic
viewpoint,” Foundations of Computational Mathematics, vol. 20. Springer
Nature, pp. 311–330, 2020.
ista: Filakovský M, Vokřínek L. 2020. Are two given maps homotopic? An algorithmic
viewpoint. Foundations of Computational Mathematics. 20, 311–330.
mla: Filakovský, Marek, and Lukas Vokřínek. “Are Two given Maps Homotopic? An Algorithmic
Viewpoint.” Foundations of Computational Mathematics, vol. 20, Springer
Nature, 2020, pp. 311–30, doi:10.1007/s10208-019-09419-x.
short: M. Filakovský, L. Vokřínek, Foundations of Computational Mathematics 20 (2020)
311–330.
date_created: 2019-06-16T21:59:14Z
date_published: 2020-04-01T00:00:00Z
date_updated: 2025-07-10T11:53:32Z
day: '01'
department:
- _id: UlWa
doi: 10.1007/s10208-019-09419-x
external_id:
arxiv:
- '1312.2337'
isi:
- '000522437400004'
intvolume: ' 20'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1312.2337
month: '04'
oa: 1
oa_version: Preprint
page: 311-330
project:
- _id: 26611F5C-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: P31312
name: Algorithms for Embeddings and Homotopy Theory
publication: Foundations of Computational Mathematics
publication_identifier:
eissn:
- 1615-3383
issn:
- 1615-3375
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Are two given maps homotopic? An algorithmic viewpoint
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 20
year: '2020'
...
---
_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
arxiv: 1
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'
...