TBA by Sumit Mukherjee
- Series
- Stochastics Seminar
- Time
- Thursday, November 30, 2023 - 15:30 for 1 hour (actually 50 minutes)
- Location
- Skiles 006
- Speaker
- Sumit Mukherjee – Columbia University – sm3949@columbia.edu
We study the problem of estimating the left and right singular subspaces for a collection of heterogeneous random graphs with a shared common structure. We analyze an algorithm that first estimates the orthogonal projection matrices corresponding to these subspaces for each individual graph, then computes the average of the projection matrices, and finally finds the matrices whose columns are the eigenvectors corresponding to the d largest eigenvalues of the sample averages. We show that the algorithm yields an estimate of the left and right singular vectors whose row-wise fluctuations are normally distributed around the rows of the true singular vectors. We then consider a two-sample hypothesis test for the null hypothesis that two graphs have the same edge probabilities matrices against the alternative hypothesis that their edge probabilities matrices are different. Using the limiting distributions for the singular subspaces, we present a test statistic whose limiting distribution converges to a central chi-square (resp. non-central chi-square) under the null (resp. alternative) hypothesis. Finally, we adapt the theoretical analysis for multiple networks to the setting of distributed PCA; in particular, we derive normal approximations for the rows of the estimated eigenvectors using distributed PCA when the data exhibit a spiked covariance matrix structure.
This talk will present an overview of the behavior of the eigenvalues of the fractional Brownian matrix motion and other related matrix processes. We will do so by emphasizing the dynamics of the eigenvalues processes, the non-colliding property, the limit of the associated empirical process, as well as the free Brownian motion and the non commutative fractional Brownian motion.
We consider the Ising Curie-Weiss model on the complete graph constrained under a given $\ell_{p}$ norm. For $p=\infty$, it reduces to the classical Ising Curie-Weiss model. We prove that for all $p\ge 2$, there exists a critical inverse temperature $\beta_{c}(p)$ such that for $\beta<\beta_{c}(p)$, the magnetization is concentrated at zero and satisfies an appropriate Gaussian CLT. On the other hand, for $\beta>\beta_{c}(p)$, the magnetization is not concentrated at zero similar to the classical case. We further generalize the model for general symmetric spin distributions and prove similar phase transition. In this talk, we discuss a brief overview of classical Curie-Weiss model, a generalized Hubbard-Stratonovich transforms, and how we apply the transform to Curie-Weiss model under $\ell^p$ constraint. This is based on joint work with Partha Dey.
Gaussian mixture block models are distributions over graphs that strive to model modern networks: to generate a graph from such a model, we associate each vertex with a latent feature vector sampled from a mixture of Gaussians, and we add edge if and only if the feature vectors are sufficiently similar. The different components of the Gaussian mixture represent the fact that there may be different types of nodes with different distributions over features---for example, in a social network each component represents the different attributes of a distinct community. Natural algorithmic tasks associated with these networks are embedding (recovering the latent feature vectors) and clustering (grouping nodes by their mixture component).
In this talk, we focus on clustering and embedding graphs sampled from high-dimensional Gaussian mixture block models, where the dimension of the latent feature vectors goes to infinity as the size of the network goes to infinity. This high-dimensional setting is most appropriate in the context of modern networks, in which we think of the latent feature space as being high-dimensional. We analyze the performance of canonical spectral clustering and embedding algorithms for such graphs in the case of 2-component spherical Gaussian mixtures and begin to sketch out the information-computation landscape for clustering and embedding in these models.
This is based on joint work with Tselil Schramm.
In this talk, we present recent results on the geometry of centrally-symmetric random polytopes generated by N independent copies of a random vector X. We show that under minimal assumptions on X, for N>Cn, and with high probability, the polytope contains a deterministic set that is naturally associated with the random vector - namely, the polar of a certain floating body. This solves the long-standing question on whether such a random polytope contains a canonical body. Moreover, by identifying the floating bodies associated with various random vectors we recover the estimates that have been obtained previously, and thanks to the minimal assumptions on X we derive estimates in cases that had been out of reach, involving random polytopes generated by heavy-tailed random vectors (e.g., when X is q-stable or when X has an unconditional structure). Finally, the structural results are used for the study of a fundamental question in compressive sensing - noise blind sparse recovery. This is joint work with Olivier Guédon (University of Paris-Est Marne La Vallée), Christian Kümmerle (UNC Charlotte), Shahar Mendelson (Sorbonne University Paris), and Holger Rauhut (LMU Munich).
Bio: Felix Krahmer received his PhD in Mathematics in 2009 from New York University under the supervision of Percy Deift and Sinan Güntürk. He was a Hausdorff postdoctoral fellow in the group of Holger Rauhut at the University of Bonn, Germany from 2009-2012. In 2012 he joined the University of Göttingen as an assistant professor for mathematical data analysis, where he has been awarded an Emmy Noether Junior Research Group. From 2015-2021 he was assistant professor for optimization and data analysis in the department of mathematics at the Technical University of Munich, before he was tenured and promoted to associate professor in 2021. His research interests span various areas at the interface of probability, analysis, machine learning, and signal processing including randomized sensing and reconstruction, fast random embeddings, quantization, and the computational sensing paradigm.