John Urschel

Nodal Decompositions of Graphs, to appear in Linear Algebra and its Applications PDF

ABSTRACT: A nodal domain of a function is a maximally connected subset of the domain for which the function does not change sign. Courant's nodal domain theorem gives a bound on the number of nodal domains of eigenfunctions of elliptic operators. In particular, the k^{th} eigenfunction contains no more than k nodal domains. We prove a generalization of Courant's theorem to discrete graphs. Namely, we show that for the k^{th} eigenvalue of a generalized Laplacian of a discrete graph, there exists a set of corresponding eigenvectors such that each eigenvector can be decomposed into at most k nodal domains. In addition, we show this set to be of co-dimension zero with respect to the entire eigenspace.

On the Characterization and Uniqueness of Centroidal Voronoi Tessellations, SIAM Journal on Numerical Analysis, 55(3), 1525–1547. PDF

ABSTRACT: Vector quantization is a classical signal-processing technique with significant applications in data compression, pattern recognition, clustering, and data stream mining. It is well known that for critical points of the quantization energy, the tessellation of the domain is a centroidal Voronoi tessellation. However, for dimensions greater than one, rigorously verifying a given centroidal Voronoi tessellation is a local minimum can prove difficult. Using variational techniques, we give a full characterization of the second variation of a centroidal Voronoi tessellation and give sufficient conditions for a centroidal Voronoi tessellation to be a local minimum. In addition, the conditions under which a centroidal Voronoi tessellation for a given density and domain is unique have been elusive for dimensions greater than one. We prove that there does not exist a unique two generator centroidal Voronoi tessellation for dimensions greater than one.

Learning Determinantal Point Processes with Moments and Cycles (with V. Brunel, A. Moitra, P. Rigollet), International Conference on Machine Learning (ICML) 2017 PDF

ABSTRACT: Determinantal Point Processes (DPPs) are a family of probabilistic models that have a repulsive behavior, and lend themselves naturally to many tasks in machine learning where returning a diverse set of objects is important. While there are fast algorithms for sampling, marginalization and conditioning, much less is known about learning the parameters of a DPP. Our contribution is twofold: (i) we establish the optimal sample complexity achievable in this problem and show that it is governed by a natural parameter, which we call the cycle sparsity; (ii) we propose a provably fast combinatorial algorithm that implements the method of moments efficiently and achieves optimal sample complexity. Finally, we give experimental results that confirm our theoretical findings.

Maximum Likelihood Estimation of Determinantal Point Processes (with V. Brunel, A. Moitra, P. Rigollet), preprint PDF

ABSTRACT: Determinantal point processes (DPPs) have wide-ranging applications in machine learning, where they are used to enforce the notion of diversity in subset selection problems. Many estimators have been proposed, but surprisingly the basic properties of the maximum likelihood estimator (MLE) have received little attention. The difficulty is that it is a non-concave maximization problem, and such functions are notoriously difficult to understand in high dimensions, despite their importance in modern machine learning. Here we study both the local and global geometry of the expected log-likelihood function. We prove several rates of convergence for the MLE and give a complete characterization of the case where these are parametric. We also exhibit a potential curse of dimensionality where the asymptotic variance of the MLE scales exponentially with the dimension of the problem. Moreover, we exhibit an exponential number of saddle points, and give evidence that these may be the only critical points.

On the Approximation of Laplacian Eigenvalues in Graph Disaggregation (with X. Hu, L. Zikatanov), Linear and Multilinear Algebra, 65(9): 1805-1822, 2017 PDF

ABSTRACT: Graph disaggregation is a technique used to address the high cost of computation for power law graphs on parallel processors. The few high-degree vertices are broken into multiple small-degree vertices, in order to allow for more efficient computation in parallel. In particular, we consider computations involving the graph Laplacian, which has significant applications, including diffusion mapping and graph partitioning, among others. We prove results regarding the spectral approximation of the Laplacian of the original graph by the Laplacian of the disaggregated graph. In addition, we construct an alternate disaggregation operator whose eigenvalues interlace those of the original Laplacian. Using this alternate operator, we construct a uniform preconditioner for the original graph Laplacian.

On the Maximal Error of Spectral Approximation of Graph Bisection (with L. Zikatanov), Linear and Multilinear Algebra, 64(10): 1972-1979, 2016 PDF

ABSTRACT: Spectral graph bisections are a popular heuristic aimed at approximating the solution of the NP-complete graph bisection problem. This technique, however, does not always provide a robust tool for graph partitioning. Using a special class of graphs, we prove that the standard spectral graph bisection can produce bisections that are far from optimal. In particular, we show that the maximum error in the spectral approximation of the optimal bisection (partition sizes exactly equal) cut for such graphs is bounded below by a constant multiple of the order of the graph squared.

A Cascadic Multigrid Algorithm for Computing the Fiedler Vector of Graph Laplacians (with X. Hu, J. Xu, L. Zikatanov), Journal of Computational Mathematics, Vol. 33 No. 2, 2015, 209-226 PDF

ABSTRACT: In this paper, we develop a cascadic multigrid algorithm for fast computation of the Fiedler vector of a graph Laplacian, namely, the eigenvector corresponding to the second smallest eigenvalue. This vector has been found to have applications in fields such as graph partitioning and graph drawing. The algorithm is a purely algebraic approach based on a heavy edge coarsening scheme and pointwise smoothing for refinement. To gain theoretical insight, we also consider the related cascadic multigrid method in the geometric setting for elliptic eigenvalue problems and show its uniform convergence under certain assumptions. Numerical tests are presented for computing the Fiedler vector of several practical graphs, and numerical results show the efficiency and optimality of our proposed cascadic multigrid algorithm.

Spectral Bisection of Graphs and Connectedness (with L. Zikatanov), Linear Algebra and its Applications, Volume 449, 15 May 2014, Pages 1-16 PDF

ABSTRACT: We present a refinement of the work of Miroslav Fiedler regarding bisections of irreducible matrices. We consider graph bisections as defined by the cut set consisting of characteristic edges of the eigenvector corresponding to the smallest non-zero eigenvalue of the graph Laplacian (the so-called Fiedler vector). We provide a simple and transparent analysis, including the cases when there exist components with value zero. Namely, we extend the class of graphs for which the Fiedler vector is guaranteed to produce connected subgraphs in the bisection. Furthermore, we show that for all connected graphs there exist Fiedler vectors such that connectedness is preserved by the bisection, and estimate the measure of the set of connectedness preserving Fiedler vectors with respect to the set of all Fiedler vectors.

A Space-Time Multigrid Method for the Numerical Valuation of Barrier Options, Communications in Mathematical Finance, vol. 2, no. 3, 2013, 1-20 PDF

ABSTRACT: We introduce an adaptive space-time multigrid method for the pricing of barrier options. In particular, we consider the numerical valuation of up-and-out options by the method of lines. We treat both the implicit Euler and Crank-Nicolson methods. We implement a space-time multigrid method in which the domain in space and time are treated simultaneously. We consider an adaptive coarsening technique in which the choice of restriction operator is dependent on the grid’s degree of anisotropy at each level. We perform local Fourier analysis to find a suitable choice of our anisotropy constant. We detail the advantages and disadvantages of our technique. In particular, we stress that our algorithm is extremely well suited for parallel computing and, with a suitable smoother, has parallel complexity O(log M + log N), allowing for fast computation of extremely large scale problems.

Instabilities in the Sun-Jupiter-Asteroid Three Body Problem (with J. Galante), Celestial Mechanics and Dynamical Astronomy, March 2013, Volume 115, Issue 3, pp 233-259 PDF

ABSTRACT: We consider dynamics of a Sun–Jupiter–Asteroid system, and, under some simplifying assumptions, show the existence of instabilities in the motions of an asteroid. In particular, we show that an asteroid whose initial orbit is far from the orbit of Mars can be gradually perturbed into one that crosses Mars’ orbit. Properly formulated, the motion of the asteroid can be described as a Hamiltonian system with two degrees of freedom, with the dynamics restricted to a “large” open region of the phase space reduced to an exact area preserving map. Instabilities arise in regions where the map has no invariant curves. The method of MacKay and Percival is used to explicitly rule out the existence of these curves, and results of Mather abstractly guarantee the existence of diffusing orbits. We emphasize that finding such diffusing orbits numerically is quite difficult, and is outside the scope of this paper.