US2015293884A1PendingUtilityA1
Method to compute the barycenter of a set of histograms
Est. expiryApr 14, 2034(~7.7 yrs left)· nominal 20-yr term from priority
Inventors:Marco Cuturi Cameto
G06V 10/761G06F 18/23G06F 18/22G06F 17/16G06F 17/18
35
PatentIndex Score
0
Cited by
0
References
0
Claims
Abstract
The object of the present invention is to provide novel methods to carry out clustering in huge datasets using generalized formulations. We propose (1) an efficient and novel method to compute the barycenter (or mean) of a set of histograms under the optimal transport distance; (2) as an extension of the first method, an efficient and novel method to cluster data sets of vectors R d with constraints on the clusters' size.
Claims
exact text as granted — not AI-modified1 . A method that relies on approximating the solution of any optimization problem that involves optimal transport distances, using, instead of each of these distances, a numerical approximation of the optimal transport distance that incorporates an entropic smoothing term of weight 1/λ, λ being a positive number.
2 . A method to compute approximate dual and primal optimal variables, comprising:
a step of storing the dataset {c 1 , c 2 , . . . , c N } of N histograms in the simple Σ n of n variables into a matrix C with n lines and N columns, and setting a convergence tolerance TOL; a step of computing the matrices K and Q with d lines and d columns, whose elements (i,j) are equal to k ij =exp(−λ m ij ); q ij =m ij exp(−λ m ij ); a step of initializing a matrix U with d lines and N columns, where each element of U is equal to 1/d; a step of computing the matrix L=diag(L/r) K. Set z=infinity; a step of repeating a) and b) until z<TOL is met:
a) U=L/(L (C/(K′U)))
b) every predetermined number of iterations,
i. forming V=C/(K′ U); U=L/(LV)
ii. updating the exit condition z=∥V.*(K′U)−C)∥; and
a step of computing the aggregated approximate objective, aggregating dual optimum ρ* λ and aggregating primal optimum T* λ
d
M
λ
(
r
,
c
)
=
maximize
∑
i
=
1
n
ρ
i
r
i
+
∑
j
=
1
m
γ
j
c
j
-
1
λ
∑
i
=
1
,
j
=
1
n
,
m
-
λ
(
m
ij
-
ρ
i
-
γ
j
)
subject
to
ρ
∈
ℝ
n
,
γ
∈
ℝ
m
ρ
*
λ
=
1
λ
[
∑
j
=
1
N
(
log
(
u
1
j
)
-
log
(
u
ij
)
)
⋮
⋮
]
i
T
*
λ
=
[
w
ij
K
ij
]
ij
where
W
=
U
V
T
3 . A method to compute Wasserstein barycenters of N histograms, comprising:
a step of gathering a dataset {c 1 , c 2 , . . . , c N } of N histograms in the simplex Σ n of n variables, and a matrix M with n columns and rows; a step of defining a relevant subset Θ of Σ n along with a projector P Θ onto that subset where a projector is a function which returns, given any vector y, the closest point in Θ; a step of initializing r to the vector [1/n, . . . , 1/n]; and a step of repeating c) to f) until desired convergence;
c) solving N dual problems {d λ M (r,c 1 ), d λ M (r,c 2 ), . . . , d λ M (r,c N )} to recover N distances d i and N dual optimal variables ρ i * λ using the subroutine described below,
d) forming the approximate objective and approximate gradient using the method of claim 1 ,
objective
=
∑
i
=
1
N
d
i
,
ρ
=
1
N
∑
i
=
1
ρ
i
-
λ
e) updating the current variable r←P Θ (r−ερ), and
f) stopping if the absolute difference in objective between two successive iterations is below a predefined tolerance.
4 . A method to compute Wasserstein barycenters of empirical measures in R d with weights constrained to be in a subset Θ of Σ k , comprising:
gathering a weighted cloud of points {x 1 , x 2 , . . . , x n } of n points in R d with a weight vector b in the simplex Σ n of n variables, where the points can be represented as a matrix X of d lines and n columns:
defining a relevant subset Θ of Σ k along with a projector P Θ onto that subset, where the projector is a function which returns, given any vector α, the closest point in Θ of that point;
initializing Y to a d lines and k columns matrix, where each column might be sampled randomly among the columns of X;
setting α to the vector [1/k, 1/k, . . . , 1k]; and
repeating g) to j) until desired convergence;
g) forming the distance matrix
M YX =|∥y i −x j ∥ 2 2 | ij
h) computing the optimal weights α using Algorithm 1 using M as a distance matrix parameter and b as the input histogram (N=1).
i) computing the approximate optimal transport T* λ using the method of claim 1 , and
j) updating Y←X T* 1 diag(b −1 ).Join the waitlist — get patent alerts
Track US2015293884A1 — get alerts on status changes and closely related new filings.
We store only your email — no account needed. See our privacy policy.