You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
"\n# Semi-discrete OT: a toy 2D problem\n\nThis example shows the :mod:`ot.semidiscrete` solver on a small 2D problem:\na uniform source on $[0, 1]^2$ and 15 random target atoms with uniform\nweights. With so few atoms the Laguerre cells can be drawn by brute force on\na grid.\n\nWe call :func:`ot.semidiscrete.solve_semidiscrete` with its default\narguments: the underlying algorithm is **Projected Averaged SGD**, and the\ndefault ``decreasing_reg=True`` adds the **DRAG** entropic-regularization\nschedule of [90]_, which improves convergence.\n\nFor the returned potential $g$ we report:\n\n- the empirical Laguerre-cell masses (mean and max absolute deviation from\n $1/15$);\n- the semi-dual objective\n $\\langle g, b\\rangle + \\mathbb{E}_X[\\varphi_g(X)]$ estimated by\n Monte Carlo, where the c-transform\n $\\varphi_g(x) = \\min_j\\big(c(x, y_j) - g_j\\big)$ is computed by\n :func:`ot.semidiscrete.semidiscrete_c_transform`. The solver **maximises** this\n objective.\n\n.. [90] Genans, F., Godichon-Baggioni, A., Vialard, F.-X., Wintenberger, O.\n (2025). *Decreasing Entropic Regularization Averaged Gradient for\n Semi-Discrete Optimal Transport.* NeurIPS 2025.\n"
8
+
]
9
+
},
10
+
{
11
+
"cell_type": "code",
12
+
"execution_count": null,
13
+
"metadata": {
14
+
"collapsed": false
15
+
},
16
+
"outputs": [],
17
+
"source": [
18
+
"# Author: Ferdinand Genans <genans.ferdinand@gmail.com>\n#\n# License: MIT License\n\n# sphinx_gallery_thumbnail_number = 1\n\nimport numpy as np\nimport matplotlib.pyplot as plt\n\nfrom ot.semidiscrete import (\n solve_semidiscrete,\n semidiscrete_atom_weights,\n semidiscrete_c_transform,\n semidiscrete_ot_map,\n)"
"## Solve and visualise\n\nA single call to :func:`solve_semidiscrete` runs DRAG with the default\narguments (``decreasing_reg=True``). We show the initial Voronoi cells\n($g = 0$) next to the Laguerre cells at the optimum.\nWith the squared-Euclidean cost (default ``metric='sqeuclidean'``), the cost\nbetween a source point in $[0, 1]^2$ and an atom is\n$\\|x - y\\|^2 \\le 2$. We clip the potential to\n``[-max_cost, max_cost] = [-2, 2]``, the localizing set where an optimal\npotential lies ([90]_, Lemma 1), which speeds up convergence.\n\n"
"## Transport map over the Laguerre cells\n\n:func:`semidiscrete_ot_map` with ``reg=0`` is the hard Monge map: every\nsource point is sent to the atom of its Laguerre cell. Overlaying the map\n(arrows on a source grid) on the *faded* cells shows each cell's mass\ncollapsing onto its atom -- a direct illustration of the mapping function.\n\n"
62
+
]
63
+
},
64
+
{
65
+
"cell_type": "code",
66
+
"execution_count": null,
67
+
"metadata": {
68
+
"collapsed": false
69
+
},
70
+
"outputs": [],
71
+
"source": [
72
+
"gx = np.linspace(0.04, 0.96, 14)\ngrid = np.stack([a.ravel() for a in np.meshgrid(gx, gx)], axis=1)\nmapped = semidiscrete_ot_map(target_positions, grid, g_drag, reg=0.0)\nlabels = semidiscrete_atom_weights(target_positions, grid, g_drag, reg=0.0).argmax(\n axis=1\n)\n\ncmap = plt.get_cmap(\"tab20\", n_atoms)\nfig, ax = plt.subplots(figsize=(6.5, 6.5))\nplot_laguerre_cells(\n target_positions, g_drag, ax, \"Approximated OT map over Laguerre cells\", alpha=0.22\n)\nax.quiver(\n grid[:, 0],\n grid[:, 1],\n mapped[:, 0] - grid[:, 0],\n mapped[:, 1] - grid[:, 1],\n angles=\"xy\",\n scale_units=\"xy\",\n scale=1,\n width=0.005,\n headwidth=4,\n headlength=5,\n color=[cmap(i) for i in labels],\n zorder=2,\n)\nplt.tight_layout()\nplt.show()"
73
+
]
74
+
},
75
+
{
76
+
"cell_type": "markdown",
77
+
"metadata": {},
78
+
"source": [
79
+
"## Cell masses and Monte Carlo cost\n\nAt the optimum each Laguerre cell should carry mass $1/15$. We report\nthe empirical mass error and the semi-dual objective\n\n\\begin{align}\\mathcal{S}(g) = \\langle g, b\\rangle + \\mathbb{E}_X[\\varphi_g(X)]\\end{align}\n\nestimated by Monte Carlo. The solver maximises $\\mathcal{S}$.\n\n"
"## Laguerre-cell masses\n\nAt the optimum every cell carries the same mass $1/15$. The bar plot\nshows the empirical mass per cell against this ground truth (dashed line):\nevery cell sits close to the theoretical value.\n\n"
98
+
]
99
+
},
100
+
{
101
+
"cell_type": "code",
102
+
"execution_count": null,
103
+
"metadata": {
104
+
"collapsed": false
105
+
},
106
+
"outputs": [],
107
+
"source": [
108
+
"cmap = plt.get_cmap(\"tab20\", n_atoms)\nfig, ax = plt.subplots(figsize=(7.5, 4))\nax.bar(\n np.arange(n_atoms),\n m_drag,\n color=[cmap(i) for i in range(n_atoms)],\n edgecolor=\"black\",\n linewidth=0.6,\n)\nax.axhline(\n target_mass,\n ls=\"--\",\n color=\"black\",\n lw=1.5,\n label=\"theoretical mass per cell at the optimum\",\n)\nax.set_ylim(0, 1.6 * target_mass)\nax.set_xticks(np.arange(n_atoms))\nax.set_xlabel(\"atom index\")\nax.set_ylabel(\"Laguerre-cell mass\")\nax.set_title(\"Approximated OT: Laguerre-cell masses\")\nax.legend()\nplt.tight_layout()\nplt.show()"
0 commit comments