Ph.D Thesis

Ph.D StudentKozdoba Mark
SubjectHow Much is Typical Better than Worse in High Dimensions
DepartmentDepartment of Mathematics
Supervisor PROF. Shahar Mendelson
Full Thesis textFull thesis text - English Version


This work contains three main groups of results.

The first group of results concerns the study of the approximation of the covariance operator of a measure on a Hilbert space by the empirical covariance matrix. While the isotropic case of this problem is well understood, the approach is not particularly well suited for the non-isotropic case and in particular for some infinite dimensional situations that arise in the context of the Machine Learning Theory.  We propose a new notion of approximation, which is in some situations significantly more meaningful and, by a slight modification of the traditional approach we derive bounds on the number of samples that guarantees good approximation with high probability, with respect to the new notion. In addition, we provide estimates on the distance between the eigenspaces of the empirical covariance matrix  and the appropriate eigenspaces of the covariance operator.

Our second group of results is related to the concentration of measure phenomenon. We define the notion of the decomposition of measure of a metric measure spaces and show how certain well behaved decompositions imply sub-Gaussian concentration of measure. Our arguments generalize the classical martingale approach and the classical martingale proofs of concentration give rise to certain constructions of decompositions of measure. We show how random walks on the space can be used to construct a different kind of decompositions. An analysis of this type of decompositions leads to a natural generalization of a notion of a bound on the Ricci curvature from Riemannian manifolds to general metric measure spaces and in particular to graphs. This provides a new perspective even on the most familiar examples, such as the combinatorial cube and the symmetric group.  Similar results were obtained recently by other authors.

The third group of results deals with the covariance structure of measures in Rn which are 1-Lipschitz images of metric measure spaces. We are interested in the connection between the geometry of the space and the decay of the eigenvalues of the covariance. We derive estimates for the decay for the class of metric measure spaces of finite length. Our results here are based on the decompositions of measure.