HSE University Student Finds Optimum Algorithm for Finding Wasserstein Barycentre

In August, Control, Information, and Optimisation school was held by Sirius education centre. At the school Daniil Tyapkin, fourth-year student of Applied Mathematics and Computer Science bachelor’s programme has found an optimum algorithm of finding Wasserstein barycentre, which he was solving throughout 2020. Here Daniil talks about the history of the problem and its practical applications.

 

About myself and mathematics

Now I study in the fourth year of Applied Mathematics and Computer Science bachelor’s programme. I specialise on theoretical computer science. Until recently, I was researching topological data analysis at the International Laboratory of Algebraic Topology and Its Applications. However, now I am more interested in probability theory, as well as random graphs, concentration of measure, and stochastic optimisation.

It’s not a piece of pie to study at the Faculty of Computer Science because I have many extracurricular courses. I enjoy my programme except for the scarcity of mathematical courses. Thankfully, I was able to compensate it with extracurricular courses.

 

History of the solution

I first heard about Wasserstein barycentres this winter at the seminar of G2PS-group, headed by Quentin Paris. I encountered this problem again while working on the continuous optimisation project under Dr Alexander Gasnikov. I asked him to give me a task on optimal transport; he gave me a variation of the barycentre problem and demonstrated the plausible approach to the solution. Solving this problem during May and June, I found some uncommon results, which we wanted to present at NeurIPS conference. However, the hurry made our work look worse, so it was rejected.

Yet again I confronted this problem at the Sirius school. I wanted to present my earlier result at the poster session. Dr Gasnikov instead offered to elaborate on it. During the lecture, he told us about the current approach by Darina Dvinskikh, doctoral student at Weierstrass Institute (Berlin). He also noted that this solution can be elaborated. That night, I found the optimum solution.

 

History of the problem

Wasserstein barycentre is not the most famous problem, albeit with an interesting history. 18th-century French mathematician Gaspard Monge was the first one to try solving the optimal transport problem. As far as I know, he was solving the task of moving the cannonballs into a pit with the minimal effort. The problem, as he formulated it, was too complex. It was Leonid Kantorovich who optimised the problem in the 20th century so that it could be solved.

Optimal transport theory helps us, for example, to find the distance between pictures. We want to “move” the intensity of every pixel in some other place. If we are moving it too far, we’ll be fined more than if we moving it less far or not at all.

Apart from estimating distance, we want to calculate a certain weighted centre of mass (barycentre) of multiple pictures. We are, in a way, looking for a middle picture. For example, we can write the number “3” many times. If we calculate a middle picture, we will have a generalised “3”.

The solution was found soon after the Kantorovich statement of the problem; however, the optimum solution question is still open – and I was solving it. In my case, I looked at an approximate solution for a great number of pictures with 1000 by 1000 resolution, to be exact. Previous solution was only good for ten pictures.

 

Applications?

This problem can be used in neuroscience research. MRI records are often used to find anomalies in brain activity. In a long record, it is complicated to find them. That’s when the algorithm comes into play. To track the changes, we can compare two adjacent images. However, this comparison is hampered by noises and the fact that changes occur during several consecutive images. So we want to average several images and then compare these “barycentres”.

It is hard to tell now about what will happen with this solution. Now Darina Dvinskikh and me work on a preprint of the article. Later – we’ll see.