AF: Medium: Collaborative Research: Beyond Sparsity: Refined Measures of Complexity for Linear Algebra

Modern data science applications exploit structure in real life data using machine learning (including deep learning) algorithms. At the core of most of these systems are algorithms for a branch of mathematics called linear algebra. In particular, a large portion of these algorithms utilize the fact that real life data has properties that can be captured using certain parsimonious linear algebraic structures. This project studies new, more powerful linear algebraic structures and algorithms that exploit these new structures. Given the fundamental importance of these algorithms, ideas generated from this project are expected to be implemented in widely deployed machine learning systems. The outreach component of this project involves (1) a technical workshop for researchers from diverse areas and (2) outreach events for K-12 students. A variety of problems in modern data science have been successfully characterized using a width. For example, one of the most common widths, the rank of a matrix, has a near-ubiquitous use across many applications. This project significantly expands the understanding of several recently proposed widths and extracts their full potential for positive practical outcomes. Furthermore, it contributes to the recently growing work on beyond worst-case analysis in linear algebra, machine learning and coding theory. 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.