See SPOT Efficiently Solve the Optimal Transport Problem

Contact

Kristen Perez

Communications Officer

Sidebar Content
No sidebar content submitted.
Summaries

Summary Sentence:

CSE Ph.D. Studen Yujia Xie is presenting a paper that has found a computationally inexpensive method to solve for the optimal transport problem.

Full Summary:

No summary paragraph submitted.

Media
  • SPOT Diagram SPOT Diagram
    (image/png)

Optimal transport (OT) is a kind of problem that tries to find the best way to transport resources in a given shape to another given shape. Despite the deceptively simple definition, the process by which OT is solved for in computational problems is usually too costly a process for many needs.

A new algorithm, dubbed SPOT, is able to solve OT problems in a scalable, computationally inexpensive manner. SPOT is also the first algorithm that is able to effectively solve the OT problem in a continuous case, which was once labeled as prohibitive.

“In many cases, OT problems are considered computationally prohibitive,” said School of Computational Science and Engineering (CSE) Ph.D. Student Yujia Xie, the primary investigator of the study.

“One such example is in high-dimensional continuous cases. For continuous cases, people used to discretize the space first, then treat the problem as a discrete optimization problem. However, the computation is very expensive. This makes the high-dimensional problem prohibitive. SPOT is able to solve such problems efficiently, which is a greatly liberating move towards more effective transport for computational needs.”

The optimal transport problem has a long history that dates back to 1781. It has wide applications, including applied mathematics, economy and geography. One of its important uses is to compare how close two probability distributions are. 

“Our algorithm not only gives an elegant solution to optimal transport problems seen in computational applications, but also provides an example of how to apply recently developed implicit generative tools to challenges with a long history. Hopefully, people can become inspired by the idea in solving other challenges.”

Xie will present the findings of this paper on Thursday June 13, 2019 at the Thirty-sixth International Conference on Machine Learning.

Additional Information

Groups

OMS, School of Computational Science and Engineering

Categories
No categories were selected.
Related Core Research Areas
No core research areas were selected.
Newsroom Topics
No newsroom topics were selected.
Keywords
optimal transport, CSE computational science engineering
Status
  • Created By: Kristen Perez
  • Workflow Status: Published
  • Created On: Jun 12, 2019 - 10:21pm
  • Last Updated: Jun 12, 2019 - 10:24pm