pythonot.github.io/master/gen_modules/ot.bsp.html at master · PythonOT/pythonot.github.io

Repository navigation

History

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

224

225

226

227

228

229

230

231

232

233

234

235

236

237

238

239

240

241

242

243

244

245

246

247

248

249

250

251

252

253

254

255

256

257

258

259

260

261

262

263

264

265

266

267

268

269

270

271

272

273

274

275

276

277

278

<!DOCTYPE html>

<head>

<title>ot.bsp — POT Python Optimal Transport 0.9.8.dev documentation</title>

</head>

POT Python Optimal Transport

</a>

</form>

</div>

</div><div class="wy-menu wy-menu-vertical" data-spy="affix" role="navigation" aria-label="Navigation menu">

<li class="toctree-l1"><a class="reference internal" href="../index.html">POT: Python Optimal Transport</a></li>

<li class="toctree-l1"><a class="reference internal" href="../auto_examples/plot_quickstart_guide.html">Quickstart Guide</a></li>

<li class="toctree-l1"><a class="reference internal" href="../auto_examples/index.html">Examples gallery</a></li>

<li class="toctree-l1"><a class="reference internal" href="../user_guide.html">User guide</a></li>

<li class="toctree-l1 current"><a class="reference internal" href="../all.html">API and modules</a><ul class="current">

<li class="toctree-l2"><a class="reference internal" href="ot.backend.html">ot.backend</a></li>

<li class="toctree-l2"><a class="reference internal" href="ot.batch.html">ot.batch</a></li>

<li class="toctree-l2"><a class="reference internal" href="ot.bregman.html">ot.bregman</a></li>

<li class="toctree-l3"><a class="reference internal" href="#ot.bsp.compute_bspot_bijection"><code class="docutils literal notranslate">compute_bspot_bijection()</code></a></li>

<li class="toctree-l3"><a class="reference internal" href="#ot.bsp.merge_bijections"><code class="docutils literal notranslate">merge_bijections()</code></a></li>

</ul>

</li>

<li class="toctree-l2"><a class="reference internal" href="ot.datasets.html">ot.datasets</a></li>

<li class="toctree-l2"><a class="reference internal" href="ot.factored.html">ot.factored</a></li>

<li class="toctree-l2"><a class="reference internal" href="ot.gaussian.html">ot.gaussian</a></li>

<li class="toctree-l2"><a class="reference internal" href="ot.gromov.html">ot.gromov</a></li>

<li class="toctree-l2"><a class="reference internal" href="ot.lowrank.html">ot.lowrank</a></li>

<li class="toctree-l2"><a class="reference internal" href="ot.mapping.html">ot.mapping</a></li>

<li class="toctree-l2"><a class="reference internal" href="ot.optim.html">ot.optim</a></li>

<li class="toctree-l2"><a class="reference internal" href="ot.partial.html">ot.partial</a></li>

<li class="toctree-l2"><a class="reference internal" href="ot.regpath.html">ot.regpath</a></li>

<li class="toctree-l2"><a class="reference internal" href="ot.sliced.html">ot.sliced</a></li>

<li class="toctree-l2"><a class="reference internal" href="ot.smooth.html">ot.smooth</a></li>

<li class="toctree-l2"><a class="reference internal" href="ot.stochastic.html">ot.stochastic</a></li>

<li class="toctree-l2"><a class="reference internal" href="ot.unbalanced.html">ot.unbalanced</a></li>

<li class="toctree-l2"><a class="reference internal" href="ot.utils.html">ot.utils</a></li>

<li class="toctree-l2"><a class="reference internal" href="../all.html#module-ot">Main <code class="xref py py-mod docutils literal notranslate">ot</code> functions</a></li>

</ul>

</li>

<li class="toctree-l1"><a class="reference internal" href="../releases.html">Releases</a></li>

<li class="toctree-l1"><a class="reference internal" href="../contributors.html">Contributors</a></li>

<li class="toctree-l1"><a class="reference internal" href="../contributing.html">Contributing to POT</a></li>

<li class="toctree-l1"><a class="reference internal" href="../code_of_conduct.html">Code of conduct</a></li>

</ul>

</div>

</nav>

<a href="../index.html">POT Python Optimal Transport</a>

</nav>

<li class="breadcrumb-item"><a href="../all.html">API and modules</a></li>

<a href="../_sources/gen_modules/ot.bsp.rst.txt" rel="nofollow"> View page source</a>

</li>

</ul>

<hr/>

</div>

Efficient combinatorial optimization for low transport cost bijections based on Binary Space Partitioning trees (BSP-OT).

ot.bsp.compute_bspot_bijection(X, Y, n_plans=64, p=2, initial_perm=None, gaussian_slicing='auto', seed=0)<a class="reference internal" href="../_modules/ot/bsp/bsp_ot.html#compute_bspot_bijection">[source]</a><a class="headerlink" href="#ot.bsp.compute_bspot_bijection" title="Link to this definition"></a></dt>

<dd>This solver provides a good and fast approximation of the combinatorial problem of finding

a bijection between two point clouds that minimizes the transport cost:

\[\min_{\sigma \in S_n} \sum_{i=1}^n \|X_i - Y_{\sigma(i)}\|_p^p\]</div>

To do so, it generates \(n_{plans}\) random bijective BSP matchings, merges them together to obtain a bijection of low transport cost.

Log-linear complexity in the number of points. Algorithm 2 & 3 from [84].

Note

There is no guarantee on the quality of the returned bijection, but the method is highly scalable on the CPU.

Worst cases are obtained between point clouds that are very similar (e.g. two samples from the same distribution),

where the solver can get stuck in local minima, but works well when the point clouds are very different.

The method also works best for the standard squared euclidean cost (p=2), as this cost enables

efficient BSP construction heuristic (with a cubic dependence on the dimension, this feature is disabled

for dimensions larger than 64).

</div>

<dt class="field-odd">Parameters:</dt>

<li>X (array-like, shape (n_samples, dimension))</li>

<li>Y (array-like, shape (n_samples, dimension))</li>

<li>n_plans (<a class="reference external" href="https://docs.python.org/3/builtins/functions.html#int" title="(in Python v3.15)">int</a>) – The number of BSP Matchings used to compute the final bijection.</li>

<li>p (<a class="reference external" href="https://docs.python.org/3/builtins/functions.html#int" title="(in Python v3.15)">int</a>, optional) – The power of the ground metric (default 2 for squared euclidean, -1 for infinity norm).</li>

<li>initial_perm (array-like, shape (n_samples,), optional) – Bijection to use for initializing merging (optional).</li>

<li>gaussian_slicing ("auto" or <a class="reference external" href="https://docs.python.org/3/builtins/functions.html#bool" title="(in Python v3.15)">bool</a>, optional) – If true then uses the Gaussian slicing heuristic to improve matching quality.

Comes with a cubic complexity with dimension.

If ‘auto’, then the heuristic is used for dimensions smaller than 64, and disabled for larger dimensions.</li>

<li>seed (<a class="reference external" href="https://docs.python.org/3/builtins/functions.html#int" title="(in Python v3.15)">int</a>, optional) – Random seed for reproducibility (default 0).</li>

</ul>

</dd>

<dt class="field-even">Returns:</dt>

<li>cost (float) – The transport cost of the final bijection.</li>

<li>perm (array-like, shape (n_samples,)) – The final bijection, stored as a permutation (e.g. a list of numbers) such that X[i] is assigned to Y[perm[i]].</li>

<li>perms (array-like, shape (n_plans,n_samples)) – The intermediary bijections used to compute the final one.</li>

</ul>

</dd>

</dl>

</dd></dl>

ot.bsp.merge_bijections(X, Y, perms, p=2)<a class="reference internal" href="../_modules/ot/bsp/bsp_ot.html#merge_bijections">[source]</a><a class="headerlink" href="#ot.bsp.merge_bijections" title="Link to this definition"></a></dt>

<dd>Merge several bijections between two point clouds to obtain a new one with low transport cost.

The new bijection is guaranteed to have a transport cost no greater than the cost of any of the input bijections.

Based on simple local/global swapping strategy, with a linear complexity in the number of points.

Algorithm 3 from [84].

<dt class="field-odd">Parameters:</dt>

<li>X (array-like, shape (n_samples, dimension))</li>

<li>Y (array-like, shape (n_samples, dimension))</li>

<li>perms (array-like, shape (n_plans,n_samples)) – The bijections to merge, stored as permutations (e.g. a list of numbers)</li>

If p is -1, the infinity norm is used.</li>

</ul>

</dd>

<dt class="field-even">Returns:</dt>

<li>cost (float) – The transport cost of the merged bijection.</li>

<li>perm (array-like, shape (n_samples,)) – The merged bijection, stored as a permutation (e.g. a list of numbers) such that X[i] is assigned to Y[perm[i]].</li>

</ul>

</dd>

</dl>

</dd></dl>

</section>

</div>

<a href="ot.bregman.html" class="btn btn-neutral float-left" title="ot.bregman" accesskey="p" rel="prev"> Previous</a>

</div>

<hr/>

</div>

Built with <a href="https://www.sphinx-doc.org/">Sphinx</a> using a

<a href="https://github.com/readthedocs/sphinx_rtd_theme">theme</a>

provided by <a href="https://readthedocs.org">Read the Docs</a>.

</footer>

</div>

</section>

</div>

<div class="rst-versions" data-toggle="rst-versions" role="note"

aria-label="versions">

<!-- add shift_up to the class for force viewing ,

data-toggle="rst-current-version" -->

Python Optimal Transport 0.9.8.dev

<!-- versions

-->

<span class="rst-current-version" style="display: inline-block;padding:

0px;color:#fcfcfcab;float:left;font-size: 100%;">

Versions:

<a href="https://pythonot.github.io/"

style="padding: 3px;color:#fcfcfc;font-size: 100%;">Release</a>

<a href="https://pythonot.github.io/master"

style="padding: 3px;color:#fcfcfc;font-size: 100%;">Development</a>

<a href="https://github.com/PythonOT/POT"

style="padding: 3px;color:#fcfcfc;font-size: 100%;">Code</a>

<!--

<dl>

<dt>Versions</dt>

<dd><a href="https://pythonot.github.io/">Release</a></dd>

<dd><a href="https://pythonot.github.io/master">Development</a></dd>

<dt><a href="https://github.com/PythonOT/POT">Code on Github</a></dt>

</dl>

<hr>

</div>

</div>-->

</div><script>

jQuery(function () {

SphinxRtdTheme.Navigation.enable(true);

});

</script>

</body>

</html>

FilesExpand file tree

ot.bsp.html

Latest commit

History

ot.bsp.html

File metadata and controls