- You are here:
- GT Home
- Home
- News & Events

Series: Stochastics Seminar

We consider the problem of recovering a set
of locations given observations of the direction between pairs of these
locations. This recovery task arises from the Structure from Motion
problem, in which a three-dimensional structure is sought from a
collection of two-dimensional images. In this context, the locations of
cameras and structure points are to be found from epipolar geometry and
point correspondences among images. These correspondences are often
incorrect because of lighting, shadows, and the effects of perspective.
Hence, the resulting observations of relative directions contain
significant corruptions. To solve the location recovery problem in the
presence of corrupted relative directions, we introduce a tractable
convex program called ShapeFit. Empirically, ShapeFit can succeed on
synthetic data with over 40% corruption. Rigorously, we prove that
ShapeFit can recover a set of locations exactly when a fraction of the
measurements are adversarially corrupted and when the data model is
random. This and subsequent work was done in collaboration with
Choongbum Lee, Vladislav Voroninski, and Tom Goldstein.

Series: Stochastics Seminar

Consider a sample of a centered random vector with unit covariance matrix.
We show that under certain regularity assumptions, and up to a natural
scaling, the smallest and the largest eigenvalues of the empirical
covariance matrix converge, when the dimension and the sample size both
tend to infinity, to the left and right edges of the Marchenko-Pastur
distribution. The assumptions are related to tails of norms of orthogonal
projections. They cover isotropic log-concave random vectors as well as
random vectors with i.i.d. coordinates with almost optimal moment
conditions. The method is a refinement of the rank one update approach used
by Srivastava and Vershynin to produce non-asymptotic quantitative
estimates. In other words we provide a new proof of the Bai and Yin theorem
using basic tools from probability theory and linear algebra, together with
a new extension of this theorem to random matrices with dependent entries.
Based on joint work with Djalil Chafai.

Series: Stochastics Seminar

Low-rank structure commonly arises in many applications including genomics, signal processing, and portfolio allocation. It is also used in many statistical inference methodologies such as principal component analysis. In this talk, I will present some recent results on recovery of a high-dimensional low-rank matrix with rank-one measurements and related problems including phase retrieval and optimal estimation of a spiked covariance matrix based on one-dimensional projections. I will also discuss structured matrix completion which aims to recover a low rank matrix based on incomplete, but structured observations.

Series: Stochastics Seminar

We prove that the log-Brunn-Minkowski inequality (log-BMI) for the
Lebesgue measure in dimension n
would imply the log-BMI and, therefore, the B-conjecture for any even
log-concave measure in dimension n. As a consequence,
we prove the log-BMI and the B-conjecture for any even log-concave
measure,
in the plane. Moreover, we prove that the log-BMI
reduces to the following: For each dimension n, there is a density
f_n,
which satisfies an integrability assumption, so that the
log-BMI holds for parallelepipeds with parallel facets, for the density
f_n. As byproduct of our methods, we study possible
log-concavity of the function t -> |(K+_p\cdot e^tL)^{\circ}|,
where
p\geq 1 and K, L are symmetric convex bodies,
which we are able to prove in some instances and as a further
application,
we confirm the variance conjecture in a special class of convex bodies.
Finally, we establish
a non-trivial dual form of the log-BMI.

Series: Stochastics Seminar

Recently, new general bounds for the distance to the normal of a non-linear
functional have been obtained, both with Poisson input and with IID points
input. In the Poisson case, the results have been obtained by combining
Stein's method with Malliavin calculus and a 'second-order Poincare
inequality', itself obtained through a coupling involving Glauber's
dynamics. In the case where the input consists in IID points, Stein's
method is again involved, and combined with a particular inequality
obtained by Chatterjee in 2008, similar to the second-order Poincar?
inequality. Many new results and optimal speeds have been obtained for some
Euclidean geometric functionals, such as the minimal spanning tree, the
Boolean model, or the Voronoi approximation of sets.

Series: Stochastics Seminar

This is survey talk where, both for random words and random permutations, I
will present a panoramic view of the subject ranging from classical results to recent
breakthroughs. Throughout, equivalencies with some directed last passage percolation
models with dependent weights will be pointed out.

Series: Stochastics Seminar

Many problems can be formulated as recovering a low-rank tensor. Although an increasingly
common task, tensor recovery remains a challenging problem because of the delicacy
associated with the decomposition of higher order tensors. We introduce a general
framework of convex regularization for low rank tensor estimation.

Series: Stochastics Seminar

Series: Stochastics Seminar

In the 1970s, Girko made the striking observation that, after centering,
traces of functions of large random matrices have approximately Gaussian
distribution. This convergence is true without any further normalization
provided f is smooth enough, even though the trace involves a number of
terms equal to the dimension of the matrix. This is particularly
interesting, because for some rougher, but still natural observables,
like the number of eigenvalues in an interval, the fluctuations diverge.
I will explain how such results can be obtained, focusing in particular
on controlling the fluctuations when the function is not very regular.

Series: Stochastics Seminar

The Abelian sandpile was invented as a "self-organized critical" model
whose stationary behavior is similar to that of a classical statistical
mechanical system at a critical point. On the d-dimensional lattice,
many variables measuring correlations in the sandpile are expected to
exhibit power-law decay. Among these are various measures of the size of
an avalanche when a grain is added at stationarity: the probability that
a particular site topples in an avalanche, the diameter of an avalanche,
and the number of sites toppled in an avalanche. Various predictions
about these exist in the physics literature, but relatively little is
known rigorously. We provide some power-law upper and lower bounds for
these avalanche size variables and a new approach to the question of
stabilizability in two dimensions.