Large data limit of the MBO scheme for data clustering: Γ-convergence of the thresholding energies
In this work we present the first rigorous analysis of the MBO scheme for data clustering in the large data limit. Each iteration of the scheme corresponds to one step of implicit gradient descent for the thresholding energy on the similarity graph of some dataset. For a subset of the nodes of the g...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article (Journal) |
| Language: | English |
| Published: |
October 2025
|
| In: |
Applied and computational harmonic analysis
Year: 2025, Volume: 79, Pages: 1-34 |
| ISSN: | 1096-603X |
| DOI: | 10.1016/j.acha.2025.101800 |
| Online Access: | Resolving-System, lizenzpflichtig, Volltext: https://doi.org/10.1016/j.acha.2025.101800 Verlag, lizenzpflichtig, Volltext: https://www.sciencedirect.com/science/article/pii/S1063520325000545 
|
| Author Notes: | Tim Laux, Jona Lelmi |
| Summary: | In this work we present the first rigorous analysis of the MBO scheme for data clustering in the large data limit. Each iteration of the scheme corresponds to one step of implicit gradient descent for the thresholding energy on the similarity graph of some dataset. For a subset of the nodes of the graph, the thresholding energy at time h measures the amount of heat transferred from the subset to its complement at time h, rescaled by a factor h. It is then natural to think that outcomes of the MBO scheme are (local) minimizers of this energy. We prove that the algorithm is consistent, in the sense that these (local) minimizers converge to (local) minimizers of a suitably weighted optimal partition problem. |
|---|---|
| Item Description: | Online veröffentlicht: 14. August 2025 Gesehen am 17.02.2026 |
| Physical Description: | Online Resource |
| ISSN: | 1096-603X |
| DOI: | 10.1016/j.acha.2025.101800 |