Development of technology that computes similarity and correspondence between large-scale data at high speed and accuracy
Fast and accurate analysis of data relationships for more efficient generative AI and media processing

Tokyo - April 5, 2024 - NTT Corporation (NTT) has proposed a new fast algorithm for the optimal transport¹, which seeks similarity and correspondence between input data, that obtains the optimal solution by utilizing cyclic symmetry² latent in real-world data and has demonstrated its effectiveness theoretically and experimentally for the first time.
　The proposed algorithm reduces the optimal transport problem to a small optimization problem with significantly fewer variables by utilizing cyclic symmetry and various optimization techniques and then solves the small optimization problem instead of the original problem. As a result, this algorithm obtains the optimal solution faster than solving the original optimal transport problem directly.
　This will promote R&D to help people improve and transmit their visual cognitive abilities through comparison, quantification, and visualization of physical movements between experts and beginners, and advance toward the realization of service infrastructure to expand the abilities of a diverse range of people, including sports.
　The results were presented at the 38th Annual AAAI Conference on Artificial Intelligence³ (AAAI-24, adoption rate 23.8%), the premier international conference in the field of AI, held in Vancouver, Canada, from February 20 to 27, 2024.

1. Background and overview of the study

As part of NTT's efforts to expand natural human abilities through ICT, we are conducting research to bring about innovative improvements in people's visual cognitive abilities by passing down superior visual perception (visual umwelt) by skilled people and AI who can identify essential changes and differences in the real world. Specifically, we aim to build a system for improving visual perception that detects only essential changes and differences accurately and visualizes them clearly through visual exaggeration. For example, we believe that it can help athletes learn motor skills by improving the visual perception of the top athlete's movements, help residents perform difficult surgery by improving the visual perception of the microtremor, and create an experience in which the intention of the athlete and performer is conveyed through visual exaggeration.
　To realize the above system, basic technologies that detect changes and differences between large-scale data in the real world with high accuracy and high speed are required. In recent years, the optimal transportation problem has attracted attention as one of such technologies. However, solving the optimal transportation problem requires a huge computational cost. We have developed a technique to compute the similarity and correspondence between large-scale data based on the optimal transportation problem with high speed and accuracy by utilizing cyclic symmetry latent in real-world data, thereby reducing the computational cost.

Figure 1 Real-World Images with Cyclic Symmetry (* Including Mirror Symmetry)

2. Technical points

Figure 2 Overview of the Proposed Method

Figure 3 Experimental results when solving an optimal transport problem between 1000-dimensional data with (n=50)-order cyclic symmetry.

3. Outlook

We will continue to promote research and development for the improvement and transmission of people's visual and cognitive abilities through the comparison, quantification, and visualization of physical movements between experts and beginners using these results.
　As one of the technological foundations of IOWN, which aims to connect diverse people around the world, and to build a service platform for expanding and demonstrating the capabilities of diverse people, including sports.

¹Optimal transport
Refers to the problem of finding the optimal transportation plan between data that minimizes the total transportation cost. It was proposed by Monge in 1781 and formulated with linear programming by Kantorovich in 1942. Intuitively, as shown in Figure 4, this problem can be interpreted as a problem of finding a moving method (optimal transportation plan) that minimizes the total cost of moving sandpile 𝑝(𝑥) to sandpile 𝑞(𝑦).

Figure 4 Examples of Intuitive Interpretations of Optimal Transportation Problems

²Cyclic symmetry
A property in which the structure does not change after applying a transformation such as rotation or inversion (e.g., gears and snow crystals have cyclic symmetry).

³AAAI
Premier international conference on artificial intelligence
URL: https://aaai.org/aaai-conference/

About NTT

NTT contributes to a sustainable society through the power of innovation. We are a leading global technology company providing services to consumers and businesses as a mobile operator, infrastructure, networks, applications, and consulting provider. Our offerings include digital business consulting, managed application services, workplace and cloud solutions, data center and edge computing, all supported by our deep global industry expertise. We are over $97B in revenue and 330,000 employees, with $3.6B in annual R&D investments. Our operations span across 80+ countries and regions, allowing us to serve clients in over 190 of them. We serve over 75% of Fortune Global 100 companies, thousands of other enterprise and government clients and millions of consumers.