Source author record

Ioana Dumitriu

Ioana Dumitriu appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

math.PR math.CO math-ph math.MP Distributed, Parallel, and Cluster Computing math.NA Numerical Analysis Computational Complexity Data Structures and Algorithms Machine Learning Mathematical Software

Catalog footprint

What is connected

12works

11topics

4close collaborators

Actions

Connect this record

Open graph Browse works

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

preprint2022arXiv

Spectra of Overlapping Wishart Matrices and the Gaussian Free Field

Consider a doubly-infinite array of iid centered variables with moment conditions, from which one can extract a finite number of rectangular, overlapping submatrices, and form the corresponding Wishart matrices. We show that under basic smoothness assumptions, centered linear eigenstatistics of such matrices converge jointly to a Gaussian vector with an interesting covariance structure. This structure, which is similar to those appearing in work of Borodin, Borodin and Gorin, and Johnson and Pal can be described in terms of the height function, and leads to a connection with the Gaussian Free Field on the upper half-plane. Finally, we generalize our results from univariate polynomials to a special class of planar functions.

preprint2020arXiv

Recovery and Rigidity in a Regular Stochastic Block Model

The stochastic block model is a natural model for studying community detection in random networks. Its clustering properties have been extensively studied in the statistics, physics and computer science literature. Recently this area has experienced major mathematical breakthroughs, particularly for the binary (two-community) version, see Mossel, Neeman, Sly (2012, 2013) and Massoulie (2013). In this paper, we introduce a variant of the binary model which we call the regular stochastic block model (RSBM). We prove rigidity by showing that with high probability an exact recovery of the community structure is possible. Spectral methods exhibit a regime where this can be done efficiently. Moreover we also prove that, in this setting, any suitably good partial recovery can be bootstrapped to obtain a full recovery of the communities.

preprint2015arXiv

On expansion of $G_{n, d}$ with respect to $G_{m, d}$

In several works, Mendel and Naor have introduced and developed theory surrounding a nonlinear expansion constant similar to the spectral gap for sequences of graphs, in which one considers embeddings of a graph $G$ into a metric space $X$ \cite{mendel2010towards, mendel2013nonlinear, mendel2014expanders}. Here, we investigate the open question of whether the random regular graph $G_{n, d}$ is an expander when embedded into the metric space of a random regular graph $G_{m, d}$ a.a.s., where $m\leq n$. We show that if $m$ is fixed, the answer is affirmative. In addition, when $m\to \infty$, we provide partial solutions to the problem in the case that $d$ is fixed or that $d\to \infty$ under the constraint $d=o(m^{1/2})$.

preprint2015arXiv

Relative Density and Exact Recovery in Heterogeneous Stochastic Block Models

The Stochastic Block Model (SBM) is a widely used random graph model for networks with communities. Despite the recent burst of interest in recovering communities in the SBM from statistical and computational points of view, there are still gaps in understanding the fundamental information theoretic and computational limits of recovery. In this paper, we consider the SBM in its full generality, where there is no restriction on the number and sizes of communities or how they grow with the number of nodes, as well as on the connection probabilities inside or across communities. This generality allows us to move past the artifacts of homogenous SBM, and understand the right parameters (such as the relative densities of communities) that define the various recovery thresholds. We outline the implications of our generalizations via a set of illustrative examples. For instance, $\log n$ is considered to be the standard lower bound on the cluster size for exact recovery via convex methods, for homogenous SBM. We show that it is possible, in the right circumstances (when sizes are spread and the smaller the cluster, the denser), to recover very small clusters (up to $\sqrt{\log n}$ size), if there are just a few of them (at most polylogarithmic in $n$).

preprint2014arXiv

The Marčenko-Pastur law for sparse random bipartite biregular graphs

We prove that the empirical spectral distribution of a (d_L, d_R)-biregular, bipartite random graph, under certain conditions, converges to a symmetrization of the Marčenko-Pastur distribution of random matrix theory. This convergence is not only global (on fixed-length intervals) but also local (on intervals of increasingly smaller length). Our method parallels the one used previously by Dumitriu and Pal (2012).

preprint2012arXiv

Global Fluctuations for Linear Statistics of β-Jacobi Ensembles

We study the global fluctuations for linear statistics of the form $\sum_{i=1}^n f(λ_i)$ as $n \rightarrow \infty$, for $C^1$ functions $f$, and $λ_1, ..., λ_n$ being the eigenvalues of a (general) $β$-Jacobi ensemble, for which tridiagonal models were given by Killip and Nenciu as well as Edelman and Sutton. The fluctuation from the mean ($\sum_{i=1}^n f(λ_i) - \Exp \sum_{i=1}^n f(λ_i)$) is given asymptotically by a Gaussian process. We compute the covariance matrix for the process and show that it is diagonalized by a shifted Chebyshev polynomial basis; in addition, we analyze the deviation from the predicted mean for polynomial test functions, and we obtain a law of large numbers.

preprint2012arXiv

Sparse regular random graphs: Spectral density and eigenvectors

We examine the empirical distribution of the eigenvalues and the eigenvectors of adjacency matrices of sparse regular random graphs. We find that when the degree sequence of the graph slowly increases to infinity with the number of vertices, the empirical spectral distribution converges to the semicircle law. Moreover, we prove concentration estimates on the number of eigenvalues over progressively smaller intervals. We also show that, with high probability, all the eigenvectors are delocalized.

preprint2011arXiv

Smallest eigenvalue distributions for two classes of $β$-Jacobi ensembles

We compute the exact and limiting smallest eigenvalue distributions for two classes of $β$-Jacobi ensembles not covered by previous studies. In the general $β$ case, these distributions are given by multivariate hypergeometric ${}_2F_{1}^{2/β}$ functions, whose behavior can be analyzed asymptotically for special values of $β$ which include $β\in 2\mathbb{N}_{+}$ as well as for $β= 1$. Interest in these objects stems from their connections (in the $β= 1,2$ cases) to principal submatrices of Haar-distributed (orthogonal, unitary) matrices appearing in randomized, communication-optimal, fast, and stable algorithms for eigenvalue computations \cite{DDH07}, \cite{BDD10}.

preprint2010arXiv

Minimizing Communication for Eigenproblems and the Singular Value Decomposition

Algorithms have two costs: arithmetic and communication. The latter represents the cost of moving data, either between levels of a memory hierarchy, or between processors over a network. Communication often dominates arithmetic and represents a rapidly increasing proportion of the total cost, so we seek algorithms that minimize communication. In \cite{BDHS10} lower bounds were presented on the amount of communication required for essentially all $O(n^3)$-like algorithms for linear algebra, including eigenvalue problems and the SVD. Conventional algorithms, including those currently implemented in (Sca)LAPACK, perform asymptotically more communication than these lower bounds require. In this paper we present parallel and sequential eigenvalue algorithms (for pencils, nonsymmetric matrices, and symmetric matrices) and SVD algorithms that do attain these lower bounds, and analyze their convergence and communication costs.

preprint2009arXiv

Tridiagonal realization of the anti-symmetric Gaussian $β$-ensemble

The Householder reduction of a member of the anti-symmetric Gaussian unitary ensemble gives an anti-symmetric tridiagonal matrix with all independent elements. The random variables permit the introduction of a positive parameter $β$, and the eigenvalue probability density function of the corresponding random matrices can be computed explicitly, as can the distribution of $\{q_i\}$, the first components of the eigenvectors. Three proofs are given. One involves an inductive construction based on bordering of a family of random matrices which are shown to have the same distributions as the anti-symmetric tridiagonal matrices. This proof uses the Dixon-Anderson integral from Selberg integral theory. A second proof involves the explicit computation of the Jacobian for the change of variables between real anti-symmetric tridiagonal matrices, its eigenvalues and $\{q_i\}$. The third proof maps matrices from the anti-symmetric Gaussian $β$-ensemble to those realizing particular examples of the Laguerre $β$-ensemble. In addition to these proofs, we note some simple properties of the shooting eigenvector and associated Prüfer phases of the random matrices.

preprint2007arXiv

Fast linear algebra is stable

In an earlier paper, we showed that a large class of fast recursive matrix multiplication algorithms is stable in a normwise sense, and that in fact if multiplication of $n$-by-$n$ matrices can be done by any algorithm in $O(n^{ω+ η})$ operations for any $η> 0$, then it can be done stably in $O(n^{ω+ η})$ operations for any $η> 0$. Here we extend this result to show that essentially all standard linear algebra operations, including LU decomposition, QR decomposition, linear equation solving, matrix inversion, solving least squares problems, (generalized) eigenvalue problems and the singular value decomposition can also be done stably (in a normwise sense) in $O(n^{ω+ η})$ operations.

preprint2004arXiv

Eigenvalues of Hermite and Laguerre ensembles: Large Beta Asymptotics

In this paper we examine the zero and first order eigenvalue fluctuations for the $β$-Hermite and $β$-Laguerre ensembles, using the matrix models we described in \cite{dumitriu02}, in the limit as $β\to \infty$. We find that the fluctuations are described by Gaussians of variance $O(1/β)$, centered at the roots of a corresponding Hermite (Laguerre) polynomial. We also show that the approximation is very good, even for small values of $β$, by plotting exact level densities versus sum of Gaussians approximations.