In the golden autumn of New York, the sea water is clear and the sky is blue. The afternoon sun shines goldenly, and after the autumn wind blows, fallen leaves begin to fall. Although the autumn air is crisp and the mood is uplifting, the chill is gradually setting in and the inexplicable sadness is always lingering. At the beginning of the semester, many freshmen entered school, full of energy and youth. Looking at them, Lao Gu couldn't help but miss the time when he was in school.
Scarborough Fair
At that time, Tsinghua Garden had a very strong literary and artistic atmosphere, and there were often various concerts and solo concerts. Every night there are people practicing guitar playing and singing on the playground of Dongda University. Every afternoon, bursts of piano sounds can be heard from the rehearsal rooms of the Youth League Committee and literary and art societies. Clarinets, oboes, flutes and other musical instruments are mixed into a thick texture, occasionally torn apart by the high notes of trombones and trumpets. One evening, Jin Dezhe and Li Xuesong held a concert in the back hall of the main building. They sang a touching "Scarborough Fair" by Simon and Garfunkel. The melody of the song is beautiful, the lyrics are sad and graceful, the guitar instrumentation is elegant and distant, and the harmonies of Simon and Garfunkel are seamless and touching. It can be called a classic among folk songs. Later, Lao Gu and his band friends Hao Jialiang and Chen Hao played this piece of music countless times. Hao Jialiang used his exciting and loud trumpet to create a mellow and soft feeling, and Chen Hao's clarinet tone was even more pure and sentimental. During his PhD, Lao Gu often rehearsed at MIT with friends from the Tsinghua band. He once played "Scarborough Fair" on soprano saxophone, but he always felt that the gorgeous sound of the Soprano Saxophone could not express the melancholy and sadness contained in this piece of music. Later, Lao Gu worked in New York and often visited Central Park. Simon and Garfunkel had parted ways, but reunited in 1981 for a free concert in Central Park. As the sun set and the bright moon rose, the pair sang this old song again and it became eternal.
"Scarborough Fair" is sung with three sighs. After each line of lyrics, a sigh is added, "Parsley, Sage, Rosemary and Thyme", which translates to "parsley, sage, rosemary and thyme", the names of the four spices, which puzzled Lao Gu. Later, Lao Gu visited Yorkshire, England, where Scarborough fair is located. Compared with New York, Old York, which has a history of two thousand years, is ancient and gloomy, with extremely rich history and culture. Whitby Abbey here is the birthplace of vampires; York Minster is the largest Gothic church in Northern Europe with a multi-layered foundation. In history, the Romans, Normans, Vikings, and Anglo-Saxons conquered this land many times. They destroyed the churches of the conquered people and rebuilt their own churches on the original sites. Scarborough Fair was once a stronghold for the Vikings to collect and sell their stolen goods. Troubadours improvised at the fair, and their popular ballads were passed down, inspiring Paul Simon and Garfunkel. Lao Gu asked a local professor friend the meaning of "parsley, sage, rosemary and thyme". The professor friend explained a painful historical anecdote to Lao Gu. In 1347, war broke out between the Muslims and the Christian colonists of Genoa. During the war, the Black Death broke out in the Muslim army. The Muslim army loaded the sick into catapults and launched them into the city of Genoa. The terrified Genoese fled back to Italy, triggering a plague across Europe. The Black Death killed almost half of Europe's population, leaving people disillusioned with the church and faith. During the plague, a group of thieves walked through the streets filled with death and stole wantonly. When they were arrested, they revealed a secret recipe to ward off the plague, the main ingredients of which were parsley, sage, rosemary and thyme. As a result, the names of the "Four Thieves" were left in history: Parsley, Sage, Rosemary and Thyme. Due to the horror of the plague, people spread this secret recipe widely and evolved into a spell in folk songs. The lyrics of "Scarborough Fair" actually have such a tragic cultural background, such as national wars, religious wars, the Black Death, and the Reformation. No wonder it has an indescribable sadness and poignancy. Hundreds of years later, these historical scars have been healed by time, and the painful memories have been transformed into beautiful melodies and elegant lyrics. Although human civilization has advanced to a level unimaginable by the ancients, medical treatment has become increasingly developed, and science has become increasingly prosperous, the shadows of religious wars and global plagues still linger.
optimal transmission
Among the cultural traditions of old Europe, the most pure and profound one is mathematics. Humans appreciate music almost instinctively. The appreciation of mathematics requires long-term professional training. But in terms of the aesthetic value and spiritual shock it brings to people, mathematics is more sublime, intense and lasting. Since the French mathematician Monge started research on optimal transmission theory in the early 18th century, countless pure mathematicians, applied mathematicians, computer scientists, and engineers have been fascinated by this theory for hundreds of years and have contributed to the development of this theory from all angles. Pure mathematicians prove the existence, uniqueness and regularity of understanding; applied mathematicians design iteration formats, prove convergence order, error estimation, numerical stability; computer scientists design data structures and parallel algorithms to improve algorithm robustness and efficiency; engineers use them to perform image enhancement, pathological analysis, statistical inference, generative models, design optical devices, etc. Due to social division of labor and vocational training, few people can thoroughly understand this theoretical downstream panorama, and can only focus on a relatively limited part of the theory or algorithm. For example, the various a priori estimation techniques developed with painstaking efforts by pure mathematicians cannot be directly applied by the vast majority of computer scientists. Therefore, they lack the motivation to study them, and thus miss the opportunity to appreciate the deep beauty. Recently, as optimal transmission theory has increasingly become one of the theoretical foundations of deep learning, the entire society has become increasingly enthusiastic about learning optimal transmission theory. It is believed that optimal transmission theory and the Monge-Ampere equation theory will gradually become popular among the people and be carried forward in the field of engineering and medical care.
Optimal transport mapping still exists on metric space, especially on Riemannian manifolds, but its regularity analysis is relatively difficult. The optimal transmission theory on the sphere is relatively mature, but it is currently not widely used in the engineering field. I believe that as 3D printing technology matures, the theory of spherical optimal transmission will eventually shine. Here, we discuss a classic application of spherical optimal transmission theory: constructing surfaces from curvature, namely the Weyl problem, Minkowski problem and Alexandroff problem in convex geometry.
Classic problems in convex geometry
According to the classical theory of differential geometry, the surface in three-dimensional space is determined by the first fundamental form (Riemannian metric) and the second fundamental form. The Riemannian metric determines the intrinsic geometry of the surface. It can measure the length of the curves on the surface, the angle between the curves, and the area of the region. It also determines the Gaussian curvature of the surface. The second fundamental form determines the principal curvature and mean curvature of the surface. But for convex surfaces, the Riemannian metric alone determines the embedding of the surface in three-dimensional space.
Figure 1: Source sphere, Gaussian sphere, convex surface.
We write the convex surface as , and use polar coordinates to represent the convex surface, that is, use a positive function defined on the unit sphere to express the radial length. Let be a point on the unit sphere at which the ray along the direction intersects with the convex surface. Assuming that the unit normal vector of the surface at a point is, Gaussian mapping maps the surface to the unit sphere:,. We denote the Riemannian metric of the surface as , the Gaussian curvature of the surface as , the surface element on the unit sphere as , and the surface element on the surface as . The mapping from the parametric unit sphere (source domain) to the Gaussian unit sphere (target domain) is a composite mapping: , . We explain several classic questions below.
Ricci flow: Given a surface with a Riemannian metric, given a target Gaussian curvature, and satisfying the Gauss-Boner condition, there is a conformal factor function that satisfies, where is the initial metric of the surface, and the Riemannian metric-induced curvature is equal to. The unknown conformal factor function here can be obtained by the classic Ricci flow method. The theory and algorithm of discrete surface Ricci flow are also very mature. Therefore, the computational problem of finding metrics from curvature should have been completely solved. However, we only get the Riemannian metric, and sometimes we need to further obtain the isometric embedding or immersion of the surface in the Euclidean space.
Minkowski problem
Minkowski problem: We give Gaussian curvature on the target domain Gaussian sphere, that is, given any point on the Gaussian sphere, the corresponding positive Gaussian curvature is, satisfying the conditions
Find the polar coordinate representation of the surface. Equivalently, Gaussian mapping pushes the surface elements onto the Gaussian sphere and obtains a measure on the Gaussian sphere.
The convex surface is found from this forward measure.
From a computational perspective, this problem can be solved as follows. First we discretize the Minkowski problem. We decompose the Gaussian sphere into cells and calculate the integral
Let the normal vector be and the area be , satisfying the constraints
We want a convex polyhedron, the normal vector of the corresponding face is, and the area is.
Figure 2: Discrete Minkowski problem.
Here the equation of the supporting plane of the convex polyhedron is, where the height of the plane is unknown. The convex polyhedron formed by these supporting planes is denoted as , here. We construct the energy function as the volume of the convex polyhedron: maximizing the volume of the convex polyhedron satisfies the restriction. The partial derivative of the volume of a polyhedron with respect to the height of the supporting plane is equal to the area of the corresponding face:
This proves the existence of solutions to the discrete Minkowski problem. Then the Brunn-Minkowski inequality proves the uniqueness of the solution.
We then gradually refine the dissection of the Gaussian sphere to obtain a series of convex polyhedrons, from which we select subsequences to converge to a smooth solution.
Alexandrov problem Alexandrov problem
We find the extreme path
get point set
A convex polyhedron is the convex hull of these points.
Adjust the polar diameter so that the discrete Gaussian curvature satisfies
The so-called Gaussian curvature is the spherical area of the set of normal vectors of all support planes passing through the vertex.
For any vertex, we construct a plane
The inner envelope of these planes is
The inner envelope is projected onto the unit sphere to obtain the cell decomposition of the sphere:
Here the area of the cell cavity depends monotonically on. By adjusting all, the normalization condition is satisfied
Let the area of the cell be equal to, which is equivalent to satisfying the discrete Gaussian curvature condition. From the optimal transmission mapping theory, we can get the unique solution.
Get the power diagram of the sphere:
By adjusting all power weights to meet the normalization conditions, such that
The area of the cell cavity is equal to.
Furthermore, we can use the variational method to solve and optimize the following convex energy
Optimization can be performed using Newton's method. After obtaining the power diagram that meets the conditions, the discrete optimal transmission map maps each cell to the corresponding sample point: . For specific calculation details, please refer to [1].
Figure 3: Stanford Rabbit.
Figure 4. Stanford rabbit conformal mapping onto the unit sphere.
Figure 5. Spherical optimal transmission of Stanford Rabbit.
Figure 6. Gargoyle model.
Figure 7. Conformal mapping of monsters.
Figure 8. Optimal transmission mapping for the sphere.
We conducted the same experiment using a monster model (Figure 6-8).
For the continuous Alexandrov problem, we can use a series of solutions to the discrete Alexandrov problem to approximate the continuous solution.
Figure 9. Max Planck’s head, convex surface obtained by solving Alexandrov problem.
Figure 10. Image of conformal mapping and image of optimal transmission mapping.
The left frame of Figure 9 shows the head of Max Planck. We conformally map the avatar surface onto the unit sphere (left frame in Figure 10), calculate the optimal transmission mapping between the push-forward surface element and the spherical surface element (right frame in Figure 10), and obtain the convex surface determined by the push-forward surface element (right frame in Figure 9).
Weyl problem
Summary
【1】L. Cui, X. Qi, C. Wen, N. Lei, X. Li，M. Zhang and X. Gu, "Spherical Optimal Transport", CAD Volume 115, Pages 181-193.
Machine-translated from the Chinese original 球面上的最优传输和微分几何 (published 2020-05-03). WeChat original ↗