Georgia Institute of Technology College of Sciences

In modern data analysis, the datasets are often represented by large-scale matrices or tensors (the generalization of matrices to higher dimensions). To have a better understanding or extract   values effectively from these data, an important step is to construct a low-dimensional/compressed representation of the data that may be better to analyze and interpret in light of a corpus of field-specific information. To implement the goal, a primary tool is the matrix/tensor decomposition. In this talk, I will talk about novel matrix/tensor decompositions, CUR decompositions, which are memory efficient and computationally cheap. Besides, I will also discuss the applications of CUR decompositions on developing efficient algorithms or models to robust decompositions or data completion problems. Additionally, some simulation results will be provided on real and synthetic datasets. 

Let A be a subset of the integers of size n. In 1983, Erdos and Szemeredi conjectured that either A+A or A*A must have size nearly n^2. We discuss ideas towards this conjecture, such as an older connection to incidence geometry as well as somewhat newer breakthroughs in additive combinatorics. We further highlight applications of the sum-product phenomenon. 

A central goal in modern data science is to design algorithms for statistical inference tasks such as community detection, high-dimensional clustering, sparse PCA, and many others. Ideally these algorithms would be both statistically optimal and computationally efficient. However, it often seems impossible to achieve both these goals simultaneously: for many problems, the optimal statistical procedure involves a brute force search while all known polynomial-time algorithms are statistically sub-optimal (requiring more data or higher signal strength than is information-theoretically necessary). In the quest for optimal algorithms, it is therefore important to understand the fundamental statistical limitations of computationally efficient algorithms.

I will discuss an emerging theoretical framework for understanding these questions, based on studying the class of "low-degree polynomial algorithms." This is a powerful class of algorithms that captures the best known poly-time algorithms for a wide variety of statistical tasks. This perspective has led to the discovery of many new and improved algorithms, and also many matching lower bounds: we now have tools to prove failure of all low-degree algorithms, which provides concrete evidence for inherent computational hardness of statistical problems. This line of work illustrates that low-degree polynomials provide a unifying framework for understanding the computational complexity of a wide variety of statistical tasks, encompassing hypothesis testing, estimation, and optimization.