Recently, optimal transfer theory has received more and more attention in the field of deep learning. It is generally believed that the purpose of deep learning is to learn probability distributions on low-dimensional data manifolds embedded in high-dimensional background space, so the main tasks are divided into manifold structure learning and probability distribution learning. Probability distribution learning boils down to optimization in the space composed of all possible distributions, and its variational method is based on optimal transmission theory. Mode collapse in generative models can be explained by the regularity of optimal transport maps. According to Brenier's theorem, the optimal transmission map at the cost of the square of the Euclidean distance is given by the gradient map of the convex function (Brenier potential energy), and the Brenier potential energy function satisfies the classic Monge-Ampere equation. The Monge-Ampere equation is closely related to the classic Minkowski-Alexandrov theory in differential geometry.
In differential geometry, the full system invariants of a surface are the first fundamental form (Riemannian metric) and the second fundamental form, and the Gaussian curvature of the surface is determined by the metric. For convex surfaces, the Riemannian metric alone determines the shape of the surface. Obtaining the shape of a convex surface from Gaussian curvature is called the Minkowski problem. Mr. Qiu Chengtong and Professor Zheng Shaoyuan once extended the Minkowski theorem to high-dimensional situations. Solving the Minkowski problem is equivalent to solving the spherical Monge-Ampere equation, which is further equivalent to spherical optimal transmission mapping.
Mr. Yau Shing-tung proposed 100 open problems in differential geometry in 1993 [1]. In the past few decades, it has guided the development of the world's geometry field. The 19th problem is to find an efficient numerical solution to the Minkowski problem and how to generalize this problem to non-convex surfaces:
“The Minkowski problem is a problem of determining a closed convex surface in terms of the curvature function defined on the unit sphere via the Gauss map. It would be interesting to find an efficient algorithm to solve the problem numerically. It would be very interesting also to find a suitable generalization of the Minkowski problem to nonconvex surfaces. Presumably one needs to understand a multivalued support function and multivalued curvature functions. Can these functions determine the closed surface uniquely? If it is unique, will the result be stable under small perturbations of the data? How does one compute the lines of curvature, the asymptotic lines and the umbilical points in terms of Minkowski data? ”
Over the past two decades, we have been trying to answer Qiu’s question 19. In 2016, under the leadership of Mr. Qiu, we used the geometric variation method to solve the optimal transmission mapping in Euclidean geometry, which laid the foundation for the answer to this problem [2]. In 2019, we extended this method from Euclidean geometry to spherical geometry, thus answering the first part of Mr. Qiu’s question 19, which is to find a numerical solution to the Minkowski problem with an efficient algorithm. Unexpectedly, the Monge-Ampere equation theory actually shines in the field of deep learning. History once again proves Mr. Qiu's far-sightedness and the profound impact of geometric analysis methods on engineering applications.
Our online course last year explained this theory and algorithm in detail. Here we review it as follows.
|
|
|
Minkowski problem
The Minkowski problem is to determine the shape of a convex surface from Gauss curvature. There have been many formulations in history. Here we only consider the first type. Other types of Minkowski problems also have solutions based on the variational method. Let us first examine this problem locally. Let is a function defined on a plane area, then its graph is a curved surface. The Gauss curvature formula of the subsurface is:
this is classicMonge-Ampere equation. We know Brenier theory in optimal transport: the optimal transport mapping between given measures is the gradient map of the Brenier potential energy function, which satisfies the Monge-Ampere equation. Therefore, by Brenier's theorem (or equivalent), we can get the convex surface shape from Gauss curvature. If we consider the overall closed surface, we naturally get the Minkowski problem.
Figure 2. Minkowski problem.
Assume that is a closed convex surface embedded in the three-dimensional Euclidean space, and the unit origin is inside the surface. We can regard the surface as a graph of a radial function defined on the unit sphere: let represent the unit sphere in three-dimensional space, be any point on the sphere, represent a direction in three-dimensional space, be a positive function defined on the sphere, and the graph of this function is recorded as
The surface is the graph of a certain radial function , we also call it the polar coordinate of the surface. Assuming that the surface is smooth, then there is a unique tangent plane and normal vector at any point on the surface. Mapping the point into its normal vector is called normal vector mapping. If the surface is not smooth, then we generalize the tangent plane to a support plane and the normal vector to a subnormal vector: for any point , a support plane passing through the point will be divided into two. The original surface is included in the lower side (negative side) of the support plane. The normal vector of the support plane is called a subnormal vector of the surface at the point. The set of all subnormal vectors is:
次法向量映射 将点 映射到其次法向量集合 。这里次法向量映射是广义多值映射，一点 的像是一个集合 。 From this we define Gaussian map,,
Given a Borel set on a sphere, is a region on the surface, is a region on the Gaussian sphere, and is the total Gaussian curvature of . This defines the Gaussian curvature measure of the sphere:
Here is the Hausdorff measure on the sphere.
Minkowski problem: Given a Borel measure on the sphere , find a convex surface such that ?
Let a subset of the sphere, we say, be convex if the set of cones
It's convex. The polar set of is defined as
The classic Minkowski theorem gives the necessary and sufficient conditions for the existence and uniqueness of the solution to the Minkowski problem:
Minkowski theoremLet be a Borel measure on, then there exists a convex surface such that, if and only if and for all compact convex sets, , and if it exists, then the difference between different solutions is a dilation.
Spherical optimal transmission problem
Given the sum of two Borel measures on the unit sphere, the conditions in the condition and theorem are satisfied. The geodesic distance between any two points is recorded as, that is, the length of the great arc connecting the two points is
We define the transmission cost as,
A spherical automorphism is said to be measure-preserving if for any Borel set,
was recorded as.
Spherical optimal transmission problemUnder all measure-preserving spherical automorphisms, find the one with the smallest total transmission cost:
According to the dual formulation of optimal transmission theory, problem (2) is equivalent to the following Kantorovich dual problem,
Here is the Gauss curvature measure. It is the c-transform, or the generalized Legendre transform,
Symmetrically, we have
From optimal transport theory we know the existence and uniqueness of the optimal solution (in the sense of differing by a constant). Then it is the solution to Minkowski's problem.
The existence and uniqueness of the solution to the classic Minkowski problem can be proved using the Alexandrov mapping lemma method. This method is essentially based on algebraic topology and cannot directly provide a constructive method. Mr. Qiu Chengtong and Professor Zheng Shaoyuan used the continuity method to prove the existence of the solution to the arbitrary-dimensional Minkowski problem based on the Monge-Ampere equation theory. This method linearizes the Monge-Ampere differential operator and uses an iterative method to solve it. Each step is equivalent to solving a linear elliptic partial differential equation. To date, this approach has not used the numerical solution of the spherical Monge-Ampere equations. The theory given here based on the optimal transmission theory provides a structural proof, which is equivalent to the geometric variation method that Mr. Qiu led us to develop [2].
Generalized Legendre transformation
Starting from the c-transformation, it is easier to understand the equivalence between the Minkowski geometric point of view and the optimal transmission point of view. The c-transformation in optimal transmission is equivalent to the generalized Legendre transformation in convex geometry, and the latter is very natural and intuitive. In common language, the so-called generalized Legendre transformation is: a convex surface is the inner envelope of all its supporting planes. Given the polar coordinate representation of a convex surface , we examine the supporting surfaces (cut planes). Let be the polar coordinate representation of a plane in , not passing through the origin. If the distance from the origin to is , the normal vector of is , then the polar coordinates of are expressed as
This represents the distance from the origin to the plane, which we call the normal intercept. For all the support planes examined, the normal intercept of the support plane with the normal vector is , and the spherical function is obtained in this way. Fixing a direction, the ray along the direction starting from the origin intersects all support planes, and its nearest intersection point from the origin is on the surface, which means that the inner envelope of is:
Taking the logarithm of both sides at the same time, we get
Equation (5) is equivalent to
Geometrically, this means that we take all the points on the surface, project them in the direction, and take the largest one as the normal intercept of the support plane where the normal vector is considered. Fixed, assuming that the extreme value is obtained at a point, then the normal vector at the point is, which means that the mapping is a Gauss map of the surface. Comparing equation (4) with equation (6), we have
At this time, the optimal transmission mapping is the Gauss mapping.
Figure 3. Generalized Legendre transformation on the sphere.
From this, we see that the generalized Legendre transformation of the convex surface is the c-transformation, the optimal transmission map is the Gauss map, and the optimal transmission theory and the convex differential geometry theory are naturally equivalent.
Spherical Power Diagram
From a computational perspective, the Minkowski problem, the optimal transmission of the sphere and the Voronoi Diagram/Delaunay Triangulation theory in computational geometry are consistent, but here it is the Power Diagram and Weighted Delaunay triangulation of the sphere.
Figure 4. Spherical Power Diagram
Given a spherical geodesic triangle, three sides are geodesics, three interior angles are , and the length of its opposite side is . The cosine law of the sphere gives the relationship between the sides and angles.
Given a geodesic circle on a sphere with center and radius), is a point outside the circle, and is a tangent to the geodesic circle. The tangent point is , and the geodesic distance between and is called the power distance to the geodesic circle, which is recorded as
Given a family of geodesics on the sphere,
The corresponding spherical Power Diagram is a cell decomposition of the sphere,
The dual triangulation of Power Diagram is called Weighted Delaunay Triangulation. We see that it is equivalent to
This means that the spherical Power Diagram is enclosed by the in-plane
The projection is obtained. Comparing formula (5) and formula (7), we see the similarity.
On a computer, we discretize as a sum of Dirac measures,
Here. The corresponding Kantorovich potential energy function is recorded as, Kantorovich dual energy (3) can be rewritten as
The gradient of the Kantorovich energy is equal to the target area of each Power cell minus the current area,
Here is the current area. Suppose it is an edge on the Weighted Delaunay triangulation, and its dual Power Diagram edge is . The intersection point of the two edges is . It will be divided into two segments with lengths of and . It will be divided into two segments with directional lengths of and . Each term of the Hessian matrix of energy is
The diagonal elements are
The Hessian matrix is strictly positive definite on the linear subspace, so the energy is strongly convex, and the extreme value exists and is unique. We use Newton's method to perform convex optimization to obtain the updated direction.
Figure 5. The cerebral cortex is conformally mapped onto a sphere, and the forward surface elements define the target measure on the sphere.
The key to this algorithm is that the temporary solution at each step in the optimization process is within the admissible solution space. Once it crosses the boundary, it must be returned to the admissible solution space and the search direction must be readjusted. The admissible solution space is defined as the Kantorovich potential energy function such that all power cells are non-empty,
We show that the column admissible solution space is convex. At the beginning of the algorithm, it will be initialized to calculate the update direction using Newton's method, update the potential energy function, calculate the convex hull, and then calculate the inner envelope of the convex hull dual, and the support plane family is. The convex hull is projected to the center of the unit sphere to obtain the Weighted Delaunay triangulation of the sphere, and the inner envelope is projected to the center of the sphere to obtain the Power Diagram of the sphere. Calculate the spherical area of each cell to obtain the energy gradient, calculate the triangulation and all side lengths of the power diagram, and obtain the Hessian matrix of the energy. If some cells disappear, we return to the admissible solution space and reduce the step size and try again. Iterate like this until the gradient approaches zero. The initial target measure is the Gaussian curvature measure, and the final convex hull is the solution to the Minkowski problem. The image mapped by the subnormal vector of each vertex is the corresponding Power cell.
Figure 6. Spherical Power Diagram (left frame) and Weighted Delaunay triangulation (right frame).
Figure 7. Potential energy function.
Figure 8. Solution to Minkowski problem, convex surface reconstructed from Gaussian curvature.
Figures 5 to 8 show a calculation example: the surface of the cerebral cortex is conformally mapped onto the unit sphere, and the surface elements of the surface are pushed forward to the sphere, and the target measure is defined. Then there is a convex surface, and this measure is the Gaussian curvature measure. Figure 6 shows the final calculated spherical Power Diagram and the dual Weighted Delaunay triangulation. Figure 7 is the corresponding potential energy function. Figure 8 is the generalized Legendre dual of the potential energy function, which is the solution to the Minkowski problem.
Figure 9. Global parameterization of sphere area preservation.
As a direct application, we can use this algorithm to obtain the area-preserving parameterization of zero-genus surfaces. Assuming that the total area of the surface is equal to the area of the spherical surface, through calculation, each vertex of the final surface is mapped to the center of gravity of the cell of the spherical Power Diagram. The homeomorphic mapping obtained in this way maintains the surface elements. Even if it is any area on the surface, the mapping will be mapped to, and the area will be equal to.
Summary
The Minkowski problem is a classic problem in convex differential geometry. Mr. Qiu Chengtong and Professor Zheng Shaoyuan extended the Minkowski theorem to high dimensions. Mr. Qiu proposed the numerical solution algorithm for the Minkowski problem as an open problem in 1993. Our team gave the answer to the first half of this problem in 2019. Its back half remains open.
The Minkowski problem boils down to the spherical Monge-Ampere problem, which can be characterized by optimal transmission theory. Based on the geometric variation method, we summarize it as the power diagram and weighted Delaunay triangulation algorithm in computational geometry, and extend it to spherical geometry to use Newton's method to iteratively optimize convex energy.
In the field of deep learning, more and more scholars believe that optimal transmission theory is one of the main theoretical foundations of explainable AI. More and more related papers have begun to emerge, and it has gradually become an independent sub-field. Recently, more and more friends have realized the importance of this method, and many colleagues and classmates have contacted Lao Gu to apply this algorithm to fields such as medical images, pattern recognition, and integrated circuit chip design. Recently, I have also discussed relevant theoretical algorithm details with Professor Luo Feng, Academician Wang Xujia, Professor Liu Kefeng, and Professor Chen Shikui.
summer courses
Optimal transmission on the sphere, geometric variation method and the solution to the Minkowski problem were taught in last year's course. We are planning to offer the "Computational Conformal Geometry" course online again this year, specifically explaining these modern geometric theories and calculations, with bilingual teaching. Our online courses are scheduled to start in July 2022, 4 times a week, 8:30-10:00pm each time. The specific course link will be released soon, so stay tuned. You can join the 2022 course WeChat group by scanning the QR code below.
Machine-translated from the Chinese original 由曲率决定形状：Minkowski问题的解 (published 2023-09-22). WeChat original ↗