A Parallel Method for Earth Mover’s Distance
| Autor: | Wotao Yin, Wuchen Li, Ernest K. Ryu, Stanley Osher, Wilfrid Gangbo |
|---|---|
| Rok vydání: | 2017 |
| Předmět: |
Numerical Analysis
Mathematical optimization Applied Mathematics General Engineering Image processing 02 engineering and technology Type (model theory) 01 natural sciences Regularization (mathematics) Theoretical Computer Science 010101 applied mathematics Computational Mathematics Compressed sensing Computational Theory and Mathematics Simple (abstract algebra) 0202 electrical engineering electronic engineering information engineering 020201 artificial intelligence & image processing Minification 0101 mathematics Fast methods Algorithm Software Mathematics Earth mover's distance |
| Zdroj: | Journal of Scientific Computing. 75:182-197 |
| ISSN: | 1573-7691 0885-7474 |
| DOI: | 10.1007/s10915-017-0529-1 |
| Popis: | We propose a new algorithm to approximate the Earth Mover’s distance (EMD). Our main idea is motivated by the theory of optimal transport, in which EMD can be reformulated as a familiar $$L_1$$ type minimization. We use a regularization which gives us a unique solution for this $$L_1$$ type problem. The new regularized minimization is very similar to problems which have been solved in the fields of compressed sensing and image processing, where several fast methods are available. In this paper, we adopt a primal-dual algorithm designed there, which uses very simple updates at each iteration and is shown to converge very rapidly. Several numerical examples are provided. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full text from SpringerLink