如图9所示,假设是一个凸函数,亦即其图为一凸曲线。则的图,是其所有切线的包络(envelope)。斜率为的切线记为,方程表示为 , 这里截距定义为: 就是的勒让德变换,它们互为勒让德共轭,换言之,。几何上,的勒让德变换给出了的所有切线,这些切线的包络给出了。每一个对应着唯一的,这里。 图10. c-变换。 我们可以将勒让德变换进行推广,如图10所示,假设是单参数曲线族,以变元为参数,曲线族的包络为。这里,曲线由传输代价函数所决定,其方程表示为: 这里,我们称为的c-变换(c-transform), 。 如果,则我们说为c-凸函数(c-convex)。 对偶问题(DP)可以进一步表示成如下形式: 。 扭曲条件 根据以上的讨论,我们看到对于最优传输方案,其质量主要集中于集合 , 换言之。如果是n维流形,对于任意,由唯一决定,则最优传输方案成为最优传输映射。 根据包络的几何特征,假设在处,和相切,我们得到必要条件: , 图11. 扭曲条件。 我们得到映射 ,如果这一映射对任意都是单射,则我们说代价函数满足扭曲条件(twist condition)。可以看出,如果代价函数满足扭曲条件,则对于任意的,满足相切条件的唯一,因此映射就是最优传输映射。 图11展示了一个不满足扭曲条件的例子,在处,存在同时满足相切条件。 假如,代价函数,这里是一个严格的凸函数,那么它满足扭曲条件,,则传输映射有表达式: 这里,我们再一次用到了勒让德变换。 作为这套理论的应用,我们给出两个在日常生活中最为常见的例子。 蒙日-安培方程 考察代价函数为距离, 则h为严格凸的函数,最优传输映射存在。如果我们考虑距离情形,,则其勒让德变换为恒同变换,最优传输映射公式为: 我们令,则得到所谓的Brenier定理:距离的最优传输映射由一个函数的梯度给出。 我们再考虑保持测度的性质:,我们就会得到著名的蒙日-安培方程。梯度映射的雅克比行列式为海森矩阵, 因此,最优传输映射和蒙日-安培方程具有非常亲密的血缘关系,而后者也和传统的闵科夫斯基问题(Minkowski Problem)有很深的渊源[5]。 加权Voronoi图 从计算角度讲,最优传输映射和计算几何中的加权Voronoi图(Power Voronoi Diagram)是彼此等价的。我们在这里进行一番推导。 我们设是欧式空间中的紧凸集,为离散点集, , 配备狄拉克测度:
。 考察对偶问题,则为离散函数,定义在离散点集上,设,则
, 我们在考察的c-变换,得到 , 固定,函数关于为凹函数。由此,我们得到Power Voronoi图, 我们得到
这里是相应的Voronoi胞腔的-体积。 由此,我们得到对偶问题为:最大化如下能量
这一能量为凹函数,其梯度为 (责任编辑:本港台直播) |