ILAS 2017 Meeting: Invited Mini-Symposium on
Linear Algebra and Positivity with Applications to Data Science
("Positivity with Applications")

Abstract. The Hadamard product of two matrices is formed by multiplying corresponding entries, and the Schur product theorem states that this operation preserves positive semidefiniteness.

It follows immediately that every analytic function with non-negative Maclaurin coefficients, when applied entrywise, preserves positive semidefiniteness for matrices of any order. The converse is due to Schoenberg: a function which preserves positive semidefiniteness for matrices of arbitrary order is necessarily analytic and has non-negative Maclaurin coefficients.

For matrices of fixed order, the situation is more interesting. This talk will present recent work which shows the existence of polynomials with negative leading term which preserve positive semidefiniteness, and characterises precisely how large this term may be.

This is joint work with D. Guillot (Delaware), A. Khare (Stanford) and M. Putinar (UC Santa Barbara and Newcastle). This work was supported by the American Institute of Mathematics and the International Centre for Mathematical Sciences, Edinburgh.

Abstract. The theory of dense graph limits shows how to embed arbitrary sized matrices of the form $M \in [0,1]_{m \times m}$ in a common graphon space consisting of symmetric measurable functions of the form $W : [0,1]^2 \to [0,1]$. The space of such functions is equipped with a norm called the cut-norm, which is canonical for dense matrices. In our paper, we prove the continuity of top eigenvectors of the Laplacian associated to such matrices with respect to the cut norm. As a consequence, we derive distribution-free consistency results for spectral clustering. In this talk, we will discuss the cut-norm, the novel framework we have developed for the analysis of graph clustering, and the technical results required to derive our results.

This is joint work with Apoorva Khare, Dominique Guillot, and Bala Rajaratnam.

Abstract. An $m \times n$ matrix $A$ is called totally nonnegative, TN (resp. totally positive, TP) of every minor of $A$ is nonnegative (resp. positive). For an entry-wise nonnegative matrix $B=[b_{ij}]$ and $t \gt 0$, $B^{\circ t}$ is defined to be the matrix with entries $b_{ij}^t$ ($t$th Hadamard power of $B$). It is known that $A^{\circ t}$ need not be TN nor TP whenever $A$ is TN or TP. However, if $A$ is TP, then $A^{\circ t}$ is eventually TP.

On the other hand, if $B$ is a $n \times n$ positive semidefinite and entry-wise nonnegative matrix, then $B^{\circ t}$ is positive semidefinite for all $t \geq n-2$. The number $n-2$ is referred to as a Hadamard critical exponent. In this talk we will show that for $n \geq 5$, there is no Hadamard critical exponent in the TP setting. We will also explore similarities between the positive semidefinite case and the class of TP Hankel matrices.

This work is joint with Profs. A. Sokal and C.R. Johnson.

Abstract. Many real-life networks can be modelled by stochastic processes with a spatial embedding. The spatial reality can be used to represent attributes of the vertices which are inaccessible or unknown, but which are assumed to inform link formation. For example, in a social network, vertices may be considered as members of a social space, where the coordinates represent the interests and background of the users. The graph formation is modelled as a stochastic process, where the probability of a link occurring between two vertices decreases as their metric distance increases. A fundamental question is to determine whether a given network is compatible with a spatial model. That is, given a graph how can we judge whether the graph is likely generated by a spatial model, and if so whether the model is uniform in nature?

Using the theory of graph limits, we show how to recognize graph sequences produced by random graph processes with a linear embedding (a natural embedding into real line). We then discuss whether a linear embedding is uniform in nature, that is whether it is possible to "transform" the linear embedding into one in which the probability of a link between two vertices depends only on the distance between them. We give necessary and sufficient conditions for the existence of a uniform linear embedding for random graphs with finite number of probability values. Our findings show that for a general linear embedding the answer is negative in most cases.

This talk is based on joint articles with H. Chuangpishit, M. Hurshman, J. Janssen, and N. Kalyaniwalia.

Abstract. Many applications involve computing shortest paths over the nodes of a graph relative to a measure of pairwise node dissimilarity. When the node attributes are real valued random vectors and the dissimilarity is an increasing function of Euclidean distance these shortest paths can have continuum limits as the number of nodes approaches infinity. Such continuum limits can lead to low complexity continuous diffusion approximations to the combinatorial shortest path problem. This work is joint with Sung Jin Hwang and Steven Damelin and was supported in part by NSF Grant CCF-1217880 and ARO grant W911NF-15-1-0479.

Abstract. We present randomized algorithms for estimating the trace and determinant of Hermitian positive semi-definite matrices. The algorithms are based on subspace iteration, and access the matrix only through matrix vector products. We analyse the error due to randomization, for starting guesses whose elements are Gaussian or Rademacher random variables. The analysis is cleanly separated into a structural (deterministic) part followed by a probabilistic part. Our absolute bounds for the expectation and concentration of the estimators are non-asymptotic and informative even for matrices of low dimension. For the trace estimators, we also present asymptotic bounds on the number of samples (columns of the starting guess) required to achieve a user-specified relative error.

This is joint work with Alen Alexanderian and Arvind Saibaba. The work is supported in part by the XDATA Program of the Defense Advanced Research Projects Agency.

Abstract. It is known that $n-2$ is the least number for which the $r$th Hadamard power of an $n\times n$ doubly nonnegative matrix is doubly nonnegative for all $r\ge n-2.$ An analogous result holds for positive semidefinite matrices with real (not necessarily nonnegative) entries. We shall discuss two interesting classes of positive semidefinite matrices whose $r$th Hadamard powers need not be positive semidefinite for $r \lt n-2$. In particular we shall focus on the $n\times n$ matrices, $\left[(1+x_ix_j)^r\right]$ and $\left[|\cos((i-j)\pi/n)|^r\right]$ where $r$ is a positive number and $x_1,\ldots,x_n$ are distinct positive real numbers.

Abstract. We consider graphical Gaussian models with edge and vertex symmetries on the precision matrix, as introduced by Hojsgaard and Lauritzen (2008).

First, we identify the Diaconis-Ylvisaker conjugate prior for these models and develop a scheme to sample from the prior and posterior distributions. We thus obtain estimates of the posterior mean of the precision and covariance matrices. We verify the accuracy of our estimates on simulated data for graphs with up to thirty vertices and various symmetries.

Second, for larger graph, we develop a distributed estimation method for the precision matrix and give the asymptotic distribution of the estimate thus obtained.

This is joint work with Qiong Li and Xin Gao, York University. This work was supported by NSERC grant 14094.

Abstract. We study the set of minimal upper bounds of finitely many symmetric matrices, in the Loewner order. In the case of two matrices, we provide a parametrization of this set in terms of the quotient of the indefinite orthogonal group $O(p,q)$ by the maximal compact subgroup $O(p) \times O(q)$. Moreover, we show that a matrix is a minimal upper bound of $A_1, \dots A_p$ if and only if it is positively exposed, meaning that it is the unique upper bound that minimizes a function of the form $X \mapsto \text{trace}(CX)$ where $C$ is a positive definite matrix. Finally, when only two matrices are involved, we show that most usual selections of minimal upper bounds can be computed analytically.

Abstract. We study maximum likelihood estimation for exponential families that are multivariate totally positive of order two (MTP2). Such distributions appear in the context of ferromagnetism in the Ising model and various latent models, as for example Brownian motion tree models used in phylogenetics. We show that maximum likelihood estimation for MTP2 exponential families is a convex optimization problem. For quadratic exponential families such as Ising models and Gaussian graphical models, we show that MTP2 implies sparsity of the underlying graph without the need of a tuning parameter. Moreover, we show that the MLE always exists even in the high-dimensional setting. These properties make MTP2 constraints an intriguing alternative to methods for learning sparse graphical models such as the graphical lasso.

Abstract. A reciprocal linear space is the image of a linear space under coordinate-wise inversion. This nice algebraic variety appears in many contexts and its structure is governed by the combinatorics of an underlying hyperplane arrangement. A reciprocal linear space is also an example of a hyperbolic variety, meaning that there is a family of linear spaces all of whose intersections with it are real. This special real structure is witnessed by a determinantal representation of its Chow form in the Grassmannian. For generic linear spaces, these determinantal formulas are closely related to the Laplacian of the complete graph and generalizations to simplicial matroids. In this talk, I will introduce reciprocal linear spaces and discuss the relation of their algebraic properties to their combinatorial and real structure.