diff options
author | Rémi Flamary <remi.flamary@gmail.com> | 2019-06-25 08:34:59 +0200 |
---|---|---|
committer | Rémi Flamary <remi.flamary@gmail.com> | 2019-06-25 08:34:59 +0200 |
commit | 1e0977fd346d91c837ef90dff8c75a65b182d021 (patch) | |
tree | c037198a8b90223114d05c072146b4f18b099696 /docs/source/quickstart.rst | |
parent | 7f0739f73fa6a8c7fa22269c727b48d3640627be (diff) |
cleaunup gromov + stat guide
Diffstat (limited to 'docs/source/quickstart.rst')
-rw-r--r-- | docs/source/quickstart.rst | 156 |
1 files changed, 141 insertions, 15 deletions
diff --git a/docs/source/quickstart.rst b/docs/source/quickstart.rst index ac96f26..d8d4838 100644 --- a/docs/source/quickstart.rst +++ b/docs/source/quickstart.rst @@ -1,8 +1,6 @@ -Quick start -=========== - - +Quick start guide +================= In the following we provide some pointers about which functions and classes to use for different problems related to optimal transport (OT). @@ -11,6 +9,11 @@ to use for different problems related to optimal transport (OT). Optimal transport and Wasserstein distance ------------------------------------------ +.. note:: + In POT, most functions that solve OT or regularized OT problems have two + versions that return the OT matrix or the value of the optimal solution. For + instance :any:`ot.emd` return the OT matrix and :any:`ot.emd2` return the + Wassertsein distance. Solving optimal transport ^^^^^^^^^^^^^^^^^^^^^^^^^ @@ -36,6 +39,10 @@ that will return the optimal transport matrix :math:`\gamma^*`: # M is the ground cost matrix T=ot.emd(a,b,M) # exact linear program +The method used for solving the OT problem is the network simplex, it is +implemented in C from [1]_. It has a complexity of :math:`O(n^3)` but the +solver is quite efficient and uses sparsity of the solution. + .. hint:: Examples of use for :any:`ot.emd` are available in the following examples: @@ -73,16 +80,19 @@ properties. It can computed from an already estimated OT matrix with - :any:`auto_examples/plot_compute_emd` -.. note:: - In POT, most functions that solve OT or regularized OT problems have two - versions that return the OT matrix or the value of the optimal solution. Fir - instance :any:`ot.emd` return the OT matrix and :any:`ot.emd2` return the - Wassertsein distance. - - Regularized Optimal Transport ----------------------------- +Entropic regularized OT +^^^^^^^^^^^^^^^^^^^^^^^ + + +Other regularization +^^^^^^^^^^^^^^^^^^^^ + +Stochastic gradient decsent +^^^^^^^^^^^^^^^^^^^^^^^^^^^ + Wasserstein Barycenters ----------------------- @@ -99,8 +109,8 @@ GPU acceleration -How to? -------- +FAQ +--- @@ -128,5 +138,121 @@ How to? 2. **Compute a Wasserstein distance** - - +References +---------- + +.. [1] Bonneel, N., Van De Panne, M., Paris, S., & Heidrich, W. (2011, + December). `Displacement nterpolation using Lagrangian mass transport + <https://people.csail.mit.edu/sparis/publi/2011/sigasia/Bonneel_11_Displacement_Interpolation.pdf>`__. + In ACM Transactions on Graphics (TOG) (Vol. 30, No. 6, p. 158). ACM. + +.. [2] Cuturi, M. (2013). `Sinkhorn distances: Lightspeed computation of + optimal transport <https://arxiv.org/pdf/1306.0895.pdf>`__. In Advances + in Neural Information Processing Systems (pp. 2292-2300). + +.. [3] Benamou, J. D., Carlier, G., Cuturi, M., Nenna, L., & Peyré, G. + (2015). `Iterative Bregman projections for regularized transportation + problems <https://arxiv.org/pdf/1412.5154.pdf>`__. SIAM Journal on + Scientific Computing, 37(2), A1111-A1138. + +.. [4] S. Nakhostin, N. Courty, R. Flamary, D. Tuia, T. Corpetti, + `Supervised planetary unmixing with optimal + transport <https://hal.archives-ouvertes.fr/hal-01377236/document>`__, + Whorkshop on Hyperspectral Image and Signal Processing : Evolution in + Remote Sensing (WHISPERS), 2016. + +.. [5] N. Courty; R. Flamary; D. Tuia; A. Rakotomamonjy, `Optimal Transport + for Domain Adaptation <https://arxiv.org/pdf/1507.00504.pdf>`__, in IEEE + Transactions on Pattern Analysis and Machine Intelligence , vol.PP, + no.99, pp.1-1 + +.. [6] Ferradans, S., Papadakis, N., Peyré, G., & Aujol, J. F. (2014). + `Regularized discrete optimal + transport <https://arxiv.org/pdf/1307.5551.pdf>`__. SIAM Journal on + Imaging Sciences, 7(3), 1853-1882. + +.. [7] Rakotomamonjy, A., Flamary, R., & Courty, N. (2015). `Generalized + conditional gradient: analysis of convergence and + applications <https://arxiv.org/pdf/1510.06567.pdf>`__. arXiv preprint + arXiv:1510.06567. + +.. [8] M. Perrot, N. Courty, R. Flamary, A. Habrard (2016), `Mapping + estimation for discrete optimal + transport <http://remi.flamary.com/biblio/perrot2016mapping.pdf>`__, + Neural Information Processing Systems (NIPS). + +.. [9] Schmitzer, B. (2016). `Stabilized Sparse Scaling Algorithms for + Entropy Regularized Transport + Problems <https://arxiv.org/pdf/1610.06519.pdf>`__. arXiv preprint + arXiv:1610.06519. + +.. [10] Chizat, L., Peyré, G., Schmitzer, B., & Vialard, F. X. (2016). + `Scaling algorithms for unbalanced transport + problems <https://arxiv.org/pdf/1607.05816.pdf>`__. arXiv preprint + arXiv:1607.05816. + +.. [11] Flamary, R., Cuturi, M., Courty, N., & Rakotomamonjy, A. (2016). + `Wasserstein Discriminant + Analysis <https://arxiv.org/pdf/1608.08063.pdf>`__. arXiv preprint + arXiv:1608.08063. + +.. [12] Gabriel Peyré, Marco Cuturi, and Justin Solomon (2016), + `Gromov-Wasserstein averaging of kernel and distance + matrices <http://proceedings.mlr.press/v48/peyre16.html>`__ + International Conference on Machine Learning (ICML). + +.. [13] Mémoli, Facundo (2011). `Gromov–Wasserstein distances and the + metric approach to object + matching <https://media.adelaide.edu.au/acvt/Publications/2011/2011-Gromov%E2%80%93Wasserstein%20Distances%20and%20the%20Metric%20Approach%20to%20Object%20Matching.pdf>`__. + Foundations of computational mathematics 11.4 : 417-487. + +.. [14] Knott, M. and Smith, C. S. (1984).`On the optimal mapping of + distributions <https://link.springer.com/article/10.1007/BF00934745>`__, + Journal of Optimization Theory and Applications Vol 43. + +.. [15] Peyré, G., & Cuturi, M. (2018). `Computational Optimal + Transport <https://arxiv.org/pdf/1803.00567.pdf>`__ . + +.. [16] Agueh, M., & Carlier, G. (2011). `Barycenters in the Wasserstein + space <https://hal.archives-ouvertes.fr/hal-00637399/document>`__. SIAM + Journal on Mathematical Analysis, 43(2), 904-924. + +.. [17] Blondel, M., Seguy, V., & Rolet, A. (2018). `Smooth and Sparse + Optimal Transport <https://arxiv.org/abs/1710.06276>`__. Proceedings of + the Twenty-First International Conference on Artificial Intelligence and + Statistics (AISTATS). + +.. [18] Genevay, A., Cuturi, M., Peyré, G. & Bach, F. (2016) `Stochastic + Optimization for Large-scale Optimal + Transport <https://arxiv.org/abs/1605.08527>`__. Advances in Neural + Information Processing Systems (2016). + +.. [19] Seguy, V., Bhushan Damodaran, B., Flamary, R., Courty, N., Rolet, + A.& Blondel, M. `Large-scale Optimal Transport and Mapping + Estimation <https://arxiv.org/pdf/1711.02283.pdf>`__. International + Conference on Learning Representation (2018) + +.. [20] Cuturi, M. and Doucet, A. (2014) `Fast Computation of Wasserstein + Barycenters <http://proceedings.mlr.press/v32/cuturi14.html>`__. + International Conference in Machine Learning + +.. [21] Solomon, J., De Goes, F., Peyré, G., Cuturi, M., Butscher, A., + Nguyen, A. & Guibas, L. (2015). `Convolutional wasserstein distances: + Efficient optimal transportation on geometric + domains <https://dl.acm.org/citation.cfm?id=2766963>`__. ACM + Transactions on Graphics (TOG), 34(4), 66. + +.. [22] J. Altschuler, J.Weed, P. Rigollet, (2017) `Near-linear time + approximation algorithms for optimal transport via Sinkhorn + iteration <https://papers.nips.cc/paper/6792-near-linear-time-approximation-algorithms-for-optimal-transport-via-sinkhorn-iteration.pdf>`__, + Advances in Neural Information Processing Systems (NIPS) 31 + +.. [23] Aude, G., Peyré, G., Cuturi, M., `Learning Generative Models with + Sinkhorn Divergences <https://arxiv.org/abs/1706.00292>`__, Proceedings + of the Twenty-First International Conference on Artficial Intelligence + and Statistics, (AISTATS) 21, 2018 + +.. [24] Vayer, T., Chapel, L., Flamary, R., Tavenard, R. and Courty, N. + (2019). `Optimal Transport for structured data with application on + graphs <http://proceedings.mlr.press/v97/titouan19a.html>`__ Proceedings + of the 36th International Conference on Machine Learning (ICML).
\ No newline at end of file |