# Seminars & Events for PACM/Applied Mathematics Colloquium

##### (Deterministic) Communication Amid Uncertainty

The classical theory of communication assumes perfect coordination between sender and receiver of information, to develop a beautiful mathematical theory that ensures reliable efficient communication. Natural communication, for example, between humans, is however characterized by a lack of perfect agreement among the communicating players.

##### Living on the edge: A geometric theory of phase transitions in convex optimization

Recent empirical research indicates that many convex optimization problems with random constraints exhibit a phase transition as the number of constraints increases. For example, this phenomenon emerges in the l1 minimization method for identifying a sparse vector from random linear samples. Indeed, l1 minimization succeeds with high probability when the number of samples exceeds a threshold that depends on the sparsity level; otherwise, it fails with high probability. This talk summarizes a rigorous analysis that explains why phase transitions are ubiquitous in random convex optimization problems. It also describes tools for making reliable predictions about the quantitative aspects of the transition, including the location and the width of the transition region.

##### The cover number of a matrix and its applications

The (epsilon)-cover number of a matrix A with entries in [-1,1] is the minimum number of aligned cubes of edge-length epsilon that are needed to cover the convex hull of the columns of A. The study of this notion is motivated by algorithmic applications and leads to intriguing combinatorial, extremal and probabilistic questions regarding the connection of this notion and other complexity measures of the matrix including its rank, approximate rank, VC dimension and more. Most of the recent results are based on joint work with Lee, Shraibman and Vempala.

##### Modal Analysis with Compressive Measurements

Structural Health Monitoring (SHM) systems are critical for monitoring aging infrastructure (such as buildings or bridges) in a cost-effective manner. Such systems typically involve collections of battery-operated wireless sensors that sample vibration data over time. After the data is transmitted to a central node, modal analysis can be used to detect damage in the structure. In this talk, we propose and study three frameworks for Compressive Sensing (CS) in SHM systems; these methods are intended to minimize power consumption by allowing the data to be sampled and/or transmitted more efficiently.

##### Dissolution driven convection for carbon dioxide sequestration: The stability problem

The dissolution-driven convection in porous media is potentially a rate limiting process for sequestering carbon dioxide in underground aquifers. Super critical carbon dioxide introduced in the aquifer is lighter than the water that fills the surrounding porous rock, and hence quickly rises to the top. However, the solution of carbon dioxide in water is heavier than water. Hence, as the layer of carbon dioxide dissolves in the water,convection may ensue. The threshold criteria for convection is obscured by the continually changing background density profile as the carbon dioxide diffuses through the pores.

##### The statistical price to pay for computational efficiency

The ever increasing size of current datasets has made computation an essential aspect of the design of statistical procedures. Yet, current notions of statistical optimality rely on information theoretic considerations that completely ignore the computation question. In this work, we develop a new notion of optimality among computationally efficient methods. Building on average-case reductions from the planted clique problem, we establish optimality of various testing procedures in the context of sparse principal component analysis and quantify the statistical price to pay for computational efficiency. [Joint work with Quentin Berthet]

##### Optimizing to Optimize

Parsimony, including sparsity and low rank, has been shown to successfully model data in numerous machine learning and signal processing tasks. Traditionally, such modeling approaches rely on an iterative algorithm that minimizes an objective function with parsimony-promoting terms. PLEASE CLICK ON COLLOQUIUM TITLE FOR COMPLETE ABSTRACT.

##### Hilbert transform and image reconstruction from incomplete data in tomography

In conventional Computer Tomography (CT), reconstruction of even a small region of interest inside an object requires irradiating the entire object with x-rays. Recently a new group of algorithms has emerged that reconstructs an image from interior data, i.e. the data that is based only on x-rays intersecting the region of interest. In medical applications of CT, collecting interior data results in a reduction of the x-ray dose to the patient. In this talk we discuss some mathematical aspects of image reconstruction from interior data. Our starting point is the Gelfand-Graev formula, which establishes a relation between the ray transform of a function and its Hilbert transform along lines. Image reconstruction is reduced to the problem of inverting the finite Hilbert transform (FHT) with different types of incomplete data.

##### The evolution of social traits in network structured populations

Over many decades theoretical biologists have grappled with the question of how to measure the relative selective advantage of different behavioral strategies. The various approaches to this question have fallen into one of the following categories: fixation probability of a mutant allele in a wild type population, some measures of gene frequency and gene frequency change, and a formulation of a different type of fitness called the inclusive fitness.

PLEASE CLICK ON COLLOQUIUM TITLE FOR COMPLETE ABSTRACT.

##### Geometric methods in image processing, networks, and machine learning

Geometric methods have revolutionized the field of image processing and image analysis. I will review some of these classical methods including image snakes, total variation minimization, image segmentation methods based on curve minimization, diffuse interface methods, and state of the art fast computational algorithms that use ideas from compressive sensing. Recently some of these concepts have shown promise for problems in high dimensional data analysis and machine learning on graphs. I will briefly review the methods from imaging and then focus on the new methods for high dimensional data and network data.

##### Analysis and Algorithms for the Phase Retrieval Problem

The phase retrieval problem presents itself in many applications is physics and engineering. Recent papers on this topic present examples ranging from X-Ray crystallography to audio and image signal processing, classification with deep networks, quantum information theory, and fiber optics data transmission. The problem is to reconstruct a vector in a Hilbert space, up to a global phase factor, from magnitudes of inner products with vectors of a given frame. Two fundamental problems are: (i) analysis of frame sets when inversion is possible; and (ii) efficient algorithms to perform inversion, when possible. In this talk I will describe recent results regarding these problems including descriptions of the Cramer-Rao lower bound as well as other robustness measures for any inversion algorithm.

##### Inferring and Encoding Graph Partitions

Connections among disparate approaches to graph partitioning may be made by reinterpreting the problem as a special case of one of either of two more general and well-studied problems in machine learning: inferring

latent variables in a generative model or estimating an (information-theoretic) optimal encoding in rate distortion theory. In either approach, setting in a more general context shows how to unite and

generalize a number of approaches. As an encoding problem, we see how heuristic measures such as the normalized cut may be derived from information theoretic quantities. As an inference problem, we see how

##### Fast Direct Solvers for Elliptic PDEs

That the linear systems arising upon the discretization of elliptic PDEs can be solved very efficiently is well-known, and many successful iterative solvers with linear complexity have been constructed (multigrid, Krylov methods, etc). Interestingly, it has recently been demonstrated that it is often possible to directly compute an approximate inverse to the coefficient matrix in linear (or close to linear) time. The talk will survey some recent work in the field and will argue that direct solvers have several advantages, including improved stability and robustness, and dramatic improvements in speed in certain environments. Moreover,

the direct solvers being proposed have low communication costs, and are better suited to parallel implementations than many previously existing fast solvers.

##### New Stable Periodic Solutions to the n-Body Problem

Recently, some new surprisingly-elegant stable periodic solutions to the 4-body problem were discovered. I will review the current state-of-the-art for finding periodic solutions to the n-body problem and I will describethe interesting new ones that have been found. I will also discuss the key question of the stability of these orbits. Some are unstable (hence uninteresting), some are quasi-stable (meaning that they exhibit a ``locally'' chaotic behavior but don't blow up), while a few are amazingly stable.

##### Graph expansion, complexity, and numerical stability of algorithms

Please note special day (Tuesday). In joint work with Ballard, Demmel, and Schwartz, we showed the communication cost of algorithms (also known as I/O-complexity) to be closely related to the small-set expansion properties of the corresponding computation graphs. **CLICK ON COLLOQUIUM TITLE FOR COMPLETE ABSTRACT**

##### Matrix perturbation bounds with random noise and applications

Classical matrix perturbation bounds, such as Weyl (for eigenvalues) and David-Kahan (for eigenvectors) have been fundamental in various areas: numerical analysis, combinatorics, theoretical computer science, statistics, machine learning, etc. In this talk, I am going to discuss a popular modern setting where the perturbation is random and the original matrix (data) is low rank (or approximately low rank). In this case, we can significantly improve the classical bounds mentioned above, replacing parameters depending on the dimension of the matrix by parameters depending only on its rank. As applications, I will discuss a simple and robust approach to several matrix recovery problems, such as the hidden clique problem, the hidden coloring problem, the clustering problem, the Netflix problem, etc.

##### Distances between surfaces, with applications to biological morphology

##### Random Graphs From Less Randomness

PLEASE CLICK ON COLLOQUIUM TITLE FOR COMPLETE ABSTRACT. The study of random graphs has been dominated for over fifty years by the Erdos-Renyi (ER) model, wherein edges appear independently and with equal probability. It is by now well-understood that ER random graphs bear very little resemblance to real networks, rendering analytical results for them largely uninformative. After a quick overview of the ER model I will point out its main shortcomings and go over some of the attempts to overcome them. We will see that the main issue is the inherent tension between low-dimensionality, needed for realism, and probabilistic independence, needed for mathematical tractability. I will then describe recent work aimed at resolving this tension by defining random graphs as maximally random solutions to constrained optimization problems.

##### Differential Geometry Perspective of Shape Coherence and Curvature Evolution by Finite-Time Nonhyperbolic Splitting

PLEASE CLICK ON COLLOQUIUM TITLE FOR COMPLETE ABSTRACT. Mixing, and coherence are fundamental issues at the heart of understanding fluid dynamics and other non- autonomous dynamical systems.

##### Multiresolution Matrix Factorization

Matrices that appear in modern data analysis and machine learning problems often have complex hierarchical structures that go beyond what can be uncovered by traditional linear algebra tools, such as eigendecompositions. Inspired by ideas from multiresolution analysis, we introduce a new notion of matrix factorization that can capture structure in matrices at multiple different scales. The resulting Multiresolution Matrix Factorizations (MMFs) not only provide a wavelet basis for sparse approximation, but can also be used for matrix compression and as a prior for matrix completion. The work presented in this talk was done jointly with Nedelina Teneva and Vikas Garg.