CRII: CIF: Approximate Message Passing Algorithms for High-Dimensional Estimation

Due a remarkable increase in computational power over the last few decades, the amount of data collected in fields such as biology, astronomy, and finance has expanded considerably. Because of this explosion of new data, many modern scientific and engineering applications require analysis of and learning on larger datasets and more complex problems than the field has ever considered before. A major challenge for researchers is to understand how much data, or information, is necessary to solve such complex statistical problems, and given that data, how to most effectively use it to gain insight about the real-world application at hand. This project explores these questions by developing and analyzing the performance of computationally-efficient algorithms and statistical procedures for these settings. The research will bring together tools and ideas from information theory, statistical physics, and applied probability to use as a framework for understanding modern, high-dimensional statistics problems and complex machine learning tasks that are core challenges in engineering and data science. Just as the research in this project is interdisciplinary, so are the educational activities pursued, which focus on making research outcomes accessible to non-experts, increasing opportunities for students from underrepresented communities in computing and data science, and training a new generation of data scientists with multi-disciplinary skillsets and research interests.

This project studies a class of computationally-efficient algorithms, referred to as approximate message passing or AMP, that are used for high-dimensional statistical inference and estimation tasks that underlie many practical applications such as imaging in healthcare and security or building autonomous vehicles using artificial intelligence. Moreover, because AMP allows for exact characterization of its asymptotic performance, such algorithms have been used to establish theory for estimation problems in machine learning and statistics. In many of these applications, AMP outperforms the best competing algorithms in both accuracy and runtime. Drawing on techniques from information theory, signal processing, machine learning, probability, and statistical physics, the goal of the project is to significantly expand and improve the theoretical foundations of AMP algorithms in order to (i) greatly extend the algorithm's capabilities in high-dimensional estimation, (ii) characterize the theoretical properties of the existing AMP algorithms for more general problem settings, and (iii) create new application areas for AMP algorithms and their supporting theory. The work will lead to the introduction or greater use of AMP in burgeoning fields like machine learning and artificial intelligence.

This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.