Performance of Quantum-Inspired Matrix Completion: The Impact of Sampling Strategies

Overview

Low-rank matrix completion has attracted significant attention because this technique can be applied to solve many inference problems. Recently, Tang et al. (2018) proposed a quantum-inspired algorithm and they proved theoretically that the algorithm can achieve better performance. However, there is still a lack of numerical studies to understand the actual performance of the new algorithm. The objective of this project was to address this issue by comparing the performance of two sampling strategies on real datasets to evaluate which one was more effective in improving the accuracy of inference of data using traditional matrix completion. The two strategies include the traditional uniform random sampling, and the weighted random sampling suggested in the quantum-inspired algorithm. In the experiments, real world data sets were used and the computation program was developed in Python, where the sampling rate represented the percent of random data that was picked out. There were a total of nine different sampling rates, ranging from 0.1 to 0.9, all of which increased at a constant step of 0.1. For each sampling rate, ten trials were done for each of the two strategies and the average recovery errors were calculated for both strategies. The results show that the weighted random sampling did help to achieve a smaller error percentile than the traditional uniform random sampling. In our future work, we will continue trying to implement and evaluate the matrix completion part in the quantum-inspired algorithm, which can improve recommendations and network-management systems for people.

Competition history

• ISEF 2019 Mathematics · Entry MATH022

Resources

• ISEF abstract page ↗

Related projects

Closest projects by meaning, across every fair and year in the corpus.