Sparse matrices in sparse analysis

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.