What Do We Know About Matrix Estimation?

2018 ISIT Tutorial
What Do We Know About Matrix Estimation?
Christina Lee Yu and Devavrat Shah


The task of estimating matrix based on its noisy, partial observation has emerged as the canonical challenge across a variety of fields spanning Inference, Machine Learning and Statistics
over the past decade or so.

Popularized examples abound, including Recommendation systems, Asymptotic Graph Theory (e.g. Graphons), Network Science (e.g. Community Detection), Social Data Processing (e.g. Ranking and Crowd Sourcing), Causal Inference (e.g. Synthetic Control), Panel Data Analysis, Bio-informatics (e.g. DNA sequencing) and more.

The purpose of this tutorial is to provide a comprehensive survey of various algorithmic and analytic approaches developed over the past decade across fields of information sciences, broadly defined. The goal is to ground these developments in the context of a “universal” model through connections with the theory of exchangeability (i.e. De Finetti (1937), Aldous and Hoover (1980s)). A particular attention will be paid to statistical and computational trade-off that arise in this class of problems. Open questions pertaining to conjectured fundamental limits and mysterious empirical algorithmic successes will be discussed.

Christina Fragouli is a Professor in the Department of Electrical Engineering at the University of California, Los Angeles.  She received the B.S. degree in Electrical Engineering from the National Technical University of Athens, Greece, and the M.Sc. and Ph.D. degrees in Electrical Engineering from the University of California at Los Angeles. Before joining UCLA,  she has worked as an Assistant and Associate Professor in the School of Computer and Communication Sciences, EPFL, Switzerland, and at the Information Sciences Center, AT&T Labs, Florham Park New Jersey. She served as  an Associate Editor for  IEEE Communications Letters , for  Elsevier Computer Communication , for  IEEE Transactions on Communications , for  IEEE Transactions on Information Theory , and for  IEEE Transactions on Mobile Communications . Her research interests are in algorithms for network information flow, network security and privacy.