ott.geometry.geometry.Geometry.to_LRCGeometry#

Geometry.to_LRCGeometry(rank, tol=0.01, seed=0)[source]#

Factorize the cost matrix in sublinear time [Indyk et al., 2019].

Uses the implementation of [Scetbon et al., 2021], algorithm 4.

It holds that with probability 0.99, \(||A - UV||_F^2 \leq || A - A_k ||_F^2 + tol \cdot ||A||_F^2\), where \(A\) is n x m cost matrix, \(UV\) the factorization computed in sublinear time and \(A_k\) the best rank-k approximation.

Parameters
  • rank (int) – Target rank of the cost_matrix.

  • tol (float) – Tolerance of the error. The total number of sampled points is \(min(n, m,\frac{rank}{tol})\).

  • seed (int) – Random seed.

Return type

LRCGeometry

Returns

Low-rank geometry.