Collaborative Research: Scalable Methods for Incomplete Tensors: To Complete or Not to Complete?

This project develops a theoretical and computational toolkit to enable the practical use of incomplete tensors, broadening the reach of data-driven methods across science and engineering. It's undeniable that the scale at which data is readily available has led to numerous innovations: algorithms use driver data to learn how to maneuver cars autonomously, large language models use text data to train themselves to generate text automatically, and models such as AlphaFold have accelerated scientific discovery. Yet these breakthroughs also reveal a fundamental limitation: many real-world datasets are incomplete, noisy, or only partially observable, constraining the performance and reliability of data-driven systems. Understanding how to reason and compute effectively with such imperfect data has become a central challenge that this project addresses. By improving how incomplete data are modeled and recovered, this research could advance economic competitiveness, empowering US companies to build more accurate, efficient, and trustworthy AI and data analytics products. The project offers opportunities for rigorous training of graduate students in these theoretical and algorithmic techniques. This project focuses on the study of incomplete tensors, bridging theory and practice by (1) analyzing the sample complexity, or number of entries needed, to recover a low-rank tensor, (2) developing and analyzing numerical methods for tensor completion when missingness is structured, and (3) developing and analyzing alternative completion-free methods when completion, in general, is not feasible. More specifically, this project develops a new randomized sampling paradigm for low-rank tensor completion, demonstrating that carefully designed sampling schemes enable polynomial-time recovery with nearly linear sample complexity. This sampling framework opens the door to numerical methods that accurately recover low-rank tensors from substantially fewer observations than previously required. Building on these sampling techniques, the PIs develop and analyze efficient algorithms for tensor completion, addressing both completion under structured missingness and completion-free optimization. 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.