Princeton University

School of Engineering & Applied Science

Sparse matrices in sparse analysis

Anna Gilbert, University of Michigan
B205 Engineering Quadrangle
Wednesday, February 13, 2019 - 4:30pm


In this talk, I will give two vignettes on the theme of sparse matrices in sparse analysis. The first vignette covers work from compressive sensing in which we want to design sparse matrices (i.e., matrices with few non-zero entries) that we use to (linearly) sense or measure compressible signals. We also design algorithms such that, from these measurements and these matrices, we can efficiently recover a compressed, or sparse, representation of the sensed data. I will discuss the role of expander graphs and error correcting codes in these designs and applications to high throughput biological screens.

The second vignette flips the theme; suppose we are given a distance or similarity matrix for a data set that is corrupted in some fashion, find a sparse correction or repair to the distance matrix so as to ensure the corrected distances come from a metric; i.e., repair as few entries as possible in the matrix so that we have a metric. I will discuss generalizations to graph metrics, applications to (and from) metric embeddings, and algorithms for variations of this problem. I will also touch upon applications in machine learning and bio-informatics.



I received an S.B. degree from the University of Chicago and a Ph.D. from Princeton University, both in Mathematics. In 1997, I was a postdoctoral fellow at Yale University and AT&T Labs-Research. From 1998 to 2004, I was a member of technical staff at AT&T Labs-Research in Florham Park, NJ. Since then, I have been with the Department of Mathematics at the University of Michigan, where I am now the Herman H. Goldstine Collegiate Professor. I also have a joint appointment in Electrical and Computer Engineering. I have received several awards, including a Sloan Research Fellowship (2006), an NSF CAREER award (2006), the National Academy of Sciences Award for Initiatives in Research (2008), the Association of Computing Machinery (ACM) Douglas Engelbart Best Paper award (2008), the EURASIP Signal Processing Best Paper award (2010), and the SIAM Ralph E. Kleinman Prize (2013).

My research interests include analysis, probability, discrete mathematics, and algorithms. I am especially interested in randomized algorithms with applications to harmonic analysis, signal and image processing, and massive datasets.