# Program of the Conference on Phenomena in high dimensions in geometric analysis, random matrices, and computational geometry

Link to the main page of the conference.

#### Abstracts

##### Charles Bordenave, CNRS & Université de Toulouse

Title: Localization and delocalization of eigenvectors for heavy-tailed random matrices

Abstract: This is based on a joint work with Alice Guionnet. Consider an $n \times n$ Hermitian random matrix with, above the diagonal, independent entries with $\alpha$-stable symmetric distribution and $0<\alpha<2$. The spectrum of this random matrix differs significantly from the spectrum of Wigner matrices with finite variance. It can be seen as an instance of a sparse random matrix : only $O(1)$ entries in each row have a significant impact on the behavior of the matrix. We will indeed see that this model of random matrix is closely related to a random operator defined on Aldous' Poisson weighted infinite tree. When $1< \alpha<2$ and $p >2$, we will see that the $L^p$-norm of the eigenvectors normalized to have unit $L^2$-norm goes to 0. On the contrary, when $0< \alpha< 2/3$, we will see that these eigenvectors are localized. These localization/delocalization results only partially recover some predictions due to Bouchaud and Cizeau in 1994.

##### Jop Briët, Centrum Wiskunde & Informatica

Title: Grothendieck inequalities for semidefinite programs with rank constraint Joint work with Fernando de Oliveira Filho and Frank Vallentin

Abstract: Grothendieck inequalities are fundamental inequalities which are frequently used in many areas of mathematics and computer science. They can be interpreted as upper bounds for the integrality gap between two optimization problems: a difficult semidefinite program with rank-1 constraint and its easy semidefinite relaxation where the rank constrained is dropped. In this talk I will discuss Grothendieck inequalities for ranks greater than 1. The main applications of such inequalities are approximating ground states in the $n$-vector model in statistical mechanics and nonlocal games in quantum information theory.

##### Emmanuel Candes, Stanford University

Title: Solving Quadratic Equations by Convex Programming: Exact Phase Retrieval

Abstract: This talk explains how one can solve quadratic equations exactly and stably by using ideas from semidefinite programming. The motivation is phase retrieval, a problem which arises in X-ray crystallography, diffraction imaging, astronomical imaging and many other applications in which one can only observe the modulus of a diffracted wave. We demonstrate empirically that any complex-valued object can be recovered from the knowledge of the magnitude of just a few diffracted patterns by solving a simple convex optimization problem inspired by the recent literature on matrix completion. More importantly, we also demonstrate that our noise-aware algorithms are stable in the sense that the reconstruction degrades gracefully as the signal-to-noise ratio decreases. The bulk of the lecture discusses novel theory showing that our entire approach is provably surprisingly effective. In particular, we will explain the crucial role played by probability theory and ideas from geometric functional analysis.

##### Pietro Caputo, Universita Roma Tre

Title: Entropic repulsion and metastability in the solid-on-solid (SOS) model

Abstract: We discuss the relaxation to equilibrium of a random (2+1)-dimensional SOS interface pinned at the boundary of a lattice box in the low temperature phase. In the presence of a positivity (hard wall) constraint, the interface is pushed away from the wall at a height $H(L)$ proportional to $\log(L)$, where L is the side of the box. We give sharp estimates which quantify this phenomenon, known as entropic repulsion. Also, we analyze the effect of entropic repulsion on the dynamics of the interface. We show that relaxation to equilibrium occurs through a sequence of metastable transitions between successive layers until the final height $H(L)$ is achieved. In particular, this proves that the spectral gap is exponentially small in the parameter L. Equivalently, the corresponding Gibbs measure satisfies a Poincaré inequality with an exponentially large constant. This contrasts with the free case (no wall constraint), where one expects polynomial bounds to hold.

##### Ronen Eldan, Tel-Aviv University

Title: On the connection between the Thin-Shell Conjecture and the KLS Conjecture.

Abstract: We consider the isoperimetric inequality for convex bodies. We show that up to a logarithmic factor, the “worst” subsets are ellipsoids. In other words, we prove that the optimal constants related to the KLS and the thin-shell conjectures are equivalent up to a logarithmic factor. Our proof, which relies on the construction of a stochastic localization scheme, demonstrates how the isoperimetric constant of a convex body depends on the eigenvalues of a certain matrix-valued stochastic process associated with the body.

##### Nathael Gozlan, Université Paris-Est Marne-la-Vallée

Title: Displacement convexity of the entropy on the discrete hypercube

Abstract : We prove that the relative entropy functional on the discrete cube is strongly displacement convex along some paths constructed using a binomial interpolation technique. We deduce from this property a Prékopa-Leindler type inequality on the discrete hypercube. This Prekopa-Leindler inequality implies back a weak form of the discrete logarithmic-Sobolev inequality together with a discrete version of Talagrand's transport-entropy inequality. Joint work in progress with C. Roberto, P-M Samson and P. Tetali.

##### Shahar Mendelson, Technion - Israël Institute of Technology

Title: Generic Chaining and the singular values of random matrices with iid rows

Abstract: We will present a general chaining scheme for studying the supremum of the empirical process $\sup_{f \in F} |N^{-1}\sum_{i=1}^N f^2(X_i)-E f^2|$ for an arbitrary class of functions $F$ and under mild assumptions on the underlying measure. When $F$ is the Euclidean unit ball in $R^n$, whose elements are acting as linear functionals, controlling this empirical process leads to estimates on the largest and smallest singular values of the random matrix with iid rows $\Gamma=N^{-1/2}\sum_{i=1}^N <X_i,\cdot>e_i$. Using the general scheme, we will obtain sharp bounds on the largest and smallest singular values of $\Gamma$ under a “heavy tails” assumption. In particular, we will present a non-asymptotic and extended version of the Bai-Yin Theorem. Joint work with Grigoris Paouris.

##### Grigoris Paouris, Texas A&M University

Title: Small-ball probabilities for the volume of random convex sets

Abstract: We prove small-deviation estimates for the volume of random convex sets. The focus is on convex hulls and Minkowski sums of line segments generated by independent random points. The random models considered include (Lebesgue) absolutely continuous probability measures with bounded densities and the class of log-concave measures. I will also discuss some related problems. (This is a joint work with Peter Pivovarov).

##### Gilles Pisier, Université Pierre et Marie Curie and Texas A&M University

Title: Subexponential Operator Spaces and Random Matrices

Abstract: The notion of exact operator space is a certain form of joint approximation property of operators by matrices. It can be combined with properties of Gaussian random matrices to prove certain versions of Grothendieck's factorization theorem for completely bounded bilinear maps on the product of two exact operator spaces. This theme was developed in previous joint work with Junge and Shlyakhtenko and papers by Haagerup, Thorbjoernsen and Musat. We will introduce the class of subexponential operator spaces, generalizing the exact ones, and describe more recent work due to Regev and Vidick.

##### Nicole Tomczak-Jaegerman, University of Alberta

Title: Random matrices with independent rows or columns

Abstract: We will discuss a number of recent results on random matrices with independent rows or columns. The talk is based on a series of joint papers by Alain Pajor and various subsets of R. Adamczak, O. Guedon, R. Latala, A. Litvak, K. Oleszkiewicz and the speaker.

##### Roman Vershynin, University of Michigan

Title: Random hyperplane tessellations and dimension reduction

Abstract: The classical method of dimension reduction for a set $K$ in $R^N$ is to project $K$ onto a random low-dimensional subspace. Johnson-Lindenstrauss lemma gives theoretical guarantees for this method. I will describe a new geometric way of dimension reduction, which is to *cut*, rather than project, the set $K$ by random independent hyperplanes. I will describe connections of this problem with geometric functional analysis (Euclidean sections of convex sets), stochastic geometry (random tessellations), and compressed sensing (recovery of a point in $K$ from its compressed image). This is a joint work with Yaniv Plan.

program_conference2012.txt · Last modified: 2012/11/26 23:33 (external edit)