The invertibility of random matrices with iid entries has been the object of intense study over the past decade, due in part to its role in proving the circular law, as well as its importance in numerical analysis (smoothed analysis). In this talk we review recent progress in our understanding of invertibility for some non-iid models: adjacency matrices of sparse random regular digraphs, and random matrices with inhomogeneous variance profile. We will also discuss estimates for the number of singular values in short intervals. Graph regularity properties play a key role in both problems. Based in part on joint works with Walid Hachem, Jamal Najim, David Renfrew, Anirban Basak and Ofer Zeitouni.

Many problems of contemporary interest in signal processing and machine learning involve highly non-convex optimization problems. While nonconvex problems are known to be intractable in general, simple local search heuristics such as (stochastic) gradient descent are often surprisingly effective at finding global optima on real or randomly generated data. In this talk I will discuss some results explaining the success of these heuristics by connecting convergence of nonconvex optimization algorithms to supremum of certain stochastic processes. I will focus on two problems.

The first problem, concerns the recovery of a structured signal from under-sampled random quadratic measurements. I will show that projected gradient descent on a natural nonconvex formulation finds globally optimal solutions with a near minimal number of samples, breaking through local sample complexity barriers that have emerged in recent literature. I will also discuss how these new mathematical developments pave the way for a new generation of data-driven phaseless imaging systems that can utilize prior information to significantly reduce acquisition time and enhance image reconstruction, enabling nano-scale imaging at unprecedented speeds and resolutions. The second problem is about learning the optimal weights of the shallowest of neural networks consisting of a single Rectified Linear Unit (ReLU). I will discuss this problem in the high-dimensional regime where the number of observations are fewer than the ReLU weights. I will show that projected gradient descent on a natural least-squares objective, when initialization at 0, converges at a linear rate to globally optimal weights with a number of samples that is optimal up to numerical constants.

We will discuss recent developments relating Poissonian soups of random walks à la Lawler-Werner, Le Jan and Sznitman, with Gaussian free fields. We will show how the underlying correspondence, which can be traced back to early work of Symanzik in constructive field theory, can be used to effectively study phase transitions in such systems.

Previous works have shown that arctic circle phenomenons and limiting behaviors of some integrable discrete systems can be explained by a variational principle. In this talk we will present the first results of the same type for a non-integrable discrete system: graph homomorphisms form Z^d to a regular tree. We will also explain how the technique used could be applied to other non-integrable models.

Normal approximation for recovery of structured unknowns in high dimension: Steining the Steiner formula Larry Goldstein, University of Southern California Abstract Intrinsic volumes of convex sets are natural geometric quantities that also play important roles in applications. In particular, the discrete probability distribution L(VC) given by the sequence v0,...,vd of conic intrinsic volumes of a closed convex cone C in Rd summarizes key information about the success of convex programs used to solve for sparse vectors, and other structured unknowns such as low rank matrices, in high dimensional regularized inverse problems. The concentration of VC implies the existence of phase transitions for the probability of recovery of the unknown in the number of observations. Additional information about the probability of recovery success is provided by a normal approximation for VC. Such central limit theorems can be shown by first considering the squared length GC of the projection of a Gaussian vector on the cone C. Applying a second order Poincar´e inequality, proved using Stein’s method, then produces a non-asymptotic total variation bound to the normal for L(GC). A conic version of the classical Steiner formula in convex geometry translates finite sample bounds and a normal limit for GC to that for VC. Joint with Ivan Nourdin and Giovanni Peccati. http://arxiv.org/abs/1411.6265