summer notes

wy Lv3
  2024-07-12 14:22:21 2024-07-12 14:22:21 Created   2024-07-12 15:28:54 2024-07-12 15:28:54 Updated  337 Words  2 Mins  

Learning Notes on Optimal Transport

1. Introduction

OT allows to definemeaningful distancesbetween point clouds (ordatasets), hence isapplicable in most ML settings.

2. Mathematical Formulation

2.1 Monge’s Problem

Monge’s formulation of the OT problem seeks a mapping

$$[math]$$

that transports a mass distributed according to a density

$$[math]$$

to another mass distributed according to a density

$$[math]$$

, minimizing the cost function:

$$[math]$$

2.2 Kantorovich’s Relaxation

Leonid Kantorovich introduced a relaxed version of Monge’s problem, which is easier to solve with modern computational tools. It transforms the problem into finding a joint distribution

$$[math]$$

over the product space of the sources and the destinations that minimizes:

$$[math]$$

where ( c(x, y) ) is the cost of transporting mass from ( x ) to ( y ).

Useful Video Screenshot

WechatIMG3644.jpeg
WechatIMG3645.jpeg
WechatIMG3639.jpeg
WechatIMG3643.jpeg
WechatIMG3638.jpeg
WechatIMG3640.jpeg
WechatIMG3637.jpeg
WechatIMG3636.jpeg
WechatIMG3646.jpeg

coupling

coupling.jpeg

3. Computational Methods

3.1 Linear Programming

For discrete distributions, the OT problem can be formulated as a linear program where the objective is to minimize the total transportation cost subject to constraints ensuring that the mass is properly moved from sources to destinations.

  • Title: summer notes

  • Author: wy

  • Created at
    :     2024-07-12 22:22:21 

  •           **Updated at
              :** 2024-07-12 23:28:54
      
  
  

  •       **Link:** https://yuuee-www.github.io/blog/2024/07/12/summer-notes/
  
  

  •       **
          License:
      **
      

      
          This work is licensed under [CC BY-NC-SA 4.0](https://creativecommons.org/licenses/by-nc-sa/4.0).
      
  


      
  

  

  

  
      
          
              
                  [summer notes2
                          Prev posts](/2024/07/13/summer-notes2/)
              
          
          
              
                  [musings
                          Next posts](/2024/07/12/musings/)
              
          
      
  

  
      
          


  Comments



  
      



  


      
  



  
      

  On this page
  summer notes

  1. Learning Notes on Optimal Transport

  2. 1. Introduction

  3. 2. Mathematical Formulation

1. [2.1 Monge’s Problem](#2-1-Monge%E2%80%99s-Problem)
2. [2.2 Kantorovich’s Relaxation](#2-2-Kantorovich%E2%80%99s-Relaxation)
3. [Useful Video Screenshot](#Useful-Video-Screenshot)
4. [coupling](#coupling)
  1. 3. Computational Methods
1. [3.1 Linear Programming](#3-1-Linear-Programming)



    


            

        

        

    

    
        

    
    
        ©
        
          2022
          -
        
        2024    [wy](/)
        
            
            

                
                    24 posts in total
                
                
            

        
    
    
        
        
            
                
                    VISITOR COUNT
                    
                
            
            
                
                    TOTAL PAGE VIEWS
                    
                
            
        
    
    
        POWERED BY [Hexo](https://hexo.io)
        THEME [Redefine v2.6.4](https://github.com/EvanNotFound/hexo-theme-redefine)
    
    
    
        
            Blog up for  days  hrs  Min  Sec

-

-

-

-

-

-

-

  • Title: summer notes
  • Author: wy
  • Created at : 2024-07-12 14:22:21
  • Updated at : 2024-07-12 15:28:54
  • Link: https://yue-ruby-w.site/2024/07/12/2024-07-12-summer-notes/
  • License: This work is licensed under CC BY-NC-SA 4.0.
On this page
summer notes
  1. Learning Notes on Optimal Transport
    1. 1. Introduction
    2. 2. Mathematical Formulation
      1. 2.1 Monge’s Problem
      2. 2.2 Kantorovich’s Relaxation
      3. Useful Video Screenshot
      4. coupling
    3. 3. Computational Methods
      1. 3.1 Linear Programming