Georgia Institute of Technology College of Sciences

In first-passage percolation, we place i.i.d. nonnegative weights (t_e) on the edges of a graph and consider the induced weighted graph metric T(x,y). When the underlying graph is the two-dimensional square lattice, there is a phase transition in the model depending on the probability p that an edge weight equals zero: for p<1/2, the metric T(0,x) grows linearly in x, whereas for p>1/2, it remains stochastically bounded. The critical case occurs for p=1/2, where there are large but finite clusters of zero-weight edges. In this talk, I will review work with Wai-Kit Lam and Xuan Wang in which we determine the rate of growth for T(0,x) up to a constant factor for all critical distributions. Then I will explain recent work with Jack Hanson and Wai-Kit Lam in which we determine the "time constant" (leading order constant in the rate of growth) in the special case where the graph is the triangular lattice, and the weights are placed on the vertices. This is the only class of distributions known where this time constant is computable: we find that it is an explicit function of the infimum of the support of t_e intersected with (0,\infty).

I will talk about the structure of large square random matrices with centered i.i.d. heavy-tailed entries (only two finite moments are assumed). In our previous work with R. Vershynin we have shown that the operator norm of such matrix A can be reduced to the optimal sqrt(n)-order with high probability by zeroing out a small submatrix of A, but did not describe the structure of this "bad" submatrix, nor provide a constructive way to find it. Now we can give a very simple description of this small "bad" subset: it is enough to zero out a small fraction of the rows and columns of A with largest L2 norms to bring its operator norm to the almost optimal sqrt(loglog(n)*n)-order, under additional assumption that the entries of A are symmetrically distributed. As a corollary, one can also obtain a constructive procedure to find a small submatrix of A that one can zero out to achieve the same regularization.

I am planning to discuss some details of the proof, the main component of which is the development of techniques that extend constructive regularization approaches known for the Bernoulli matrices (from the works of Feige and Ofek, and Le, Levina and Vershynin) to the considerably broader class of heavy-tailed random matrices.

Neural networks have led to new and state of the art approaches for image recovery. They provide a contrast to standard image processing methods based on the ideas of sparsity and wavelets. In this talk, we will study two different random neural networks. One acts as a model for a learned neural network that is trained to sample from the distribution of natural images. Another acts as an unlearned model which can be used to process natural images without any training data. In both cases we will use high dimensional concentration estimates to establish theory for the performance of random neural networks in imaging problems.

One of the most famous methods for solving large-scale over-determined linear systems is Kaczmarz algorithm, which iteratively projects the previous approximation x_k onto the solution spaces of the next equation in the system. An elegant proof of the exponential convergence of this method using correct randomization of the process is due to Strohmer and Vershynin (2009). Many extensions and generalizations of the method were proposed since then, including the works of Needell, Tropp, Ward, Srebro, Tan and many others. An interesting unifying view on a number of iterative solvers (including several versions of the Kaczmarz algorithm) was proposed by Gower and Richtarik in 2016. The main idea of their sketch-and-project framework is the following: one can observe that the random selection of a row (or a row block) can be represented as a sketch, that is, left multiplication by a random vector (or a matrix), thereby pre-processing every iteration of the method, which is represented by a projection onto the image of the sketch.

I will give an overview of some of these methods, and talk about the role that random matrix theory plays in the showing their convergence. I will also discuss our new results with Deanna Needell on the block Gaussian sketch and project method.