ILAS 2017

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

July 24–27, 2017, Iowa State University

Last modified on May 19, 2017

This is a local page for the invited Minisymposium on "Linear Algebra and Positivity with Applications to Data Science", at the 2017 meeting of the International Linear Algebra Society (ILAS). The Minisymposium takes place on July 24, 25, and 27. The organizers are: Dominique Guillot, Apoorva Khare, and Bala Rajaratnam.

For information on hotels, and registration, click on the ILAS 2017 logo at the top of this page.

Making sense of vast amounts of data has become one of the great challenges of the 21st century. This mini-symposium will highlight how recent advances in analysis (in particular positivity and related topics), linear algebra, algebraic geometry, and statistics provide new tools to analyze data in areas such as covariance estimation and the theory of graphical models.

Click on the name of a speaker to go to their abstract below.

Monday, July 24 Room 202, Carver Hall
14:45–15:10     Mahya Ghandehari Geometric graphs and uniform embeddings
15:15–15:40     Alfred Hero Continuum limits for shortest paths
15:45–16:10     Peter Diao Distribution-Free Consistency of Graph Clustering
Tuesday, July 25 Room 305, Carver Hall
10:10–10:35     Nikolas Stott Minimal upper bounds in the Loewner order: characterizations and parametrization
10:40–11:05     Tanvi Jain Hadamard powers of two classes of positive matrices
11:10–11:35     Shaun Fallat Hadamard Powers, Critical Exponents, and Total Positivity
11:40–12:05     Alexander Belton A quantitative form of Schoenberg's theorem in fixed dimension
Thursday, July 27 Room 232, Carver Hall
10:10–10:35     Ilse Ipsen Randomized matrix-free trace and log-determinant estimators
10:40–11:05     Helene Massam Precision matrix estimation and sampling in coloured graphical Gaussian models
11:10–11:35     Caroline Uhler Your dreams may come true with MTP2
11:40–12:05     Cynthia Vinzant Hyperbolicity and reciprocal linear spaces
Alexander Belton (Lancaster University, UK) July 25 (Tue), 11:40 AM
A quantitative form of Schoenberg's theorem in fixed dimension Carver 305

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.

Peter Diao (SAMSI and UNC Chapel Hill) July 24 (Mon), 3:45 PM
Distribution-Free Consistency of Graph Clustering Carver 202

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.

Shaun Fallat (University of Regina, Canada) July 25 (Tue), 11:10 AM
Hadamard Powers, Critical Exponents, and Total Positivity Carver 305

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.

Mahya Ghandehari (University of Delaware) July 24 (Mon), 2:45 PM
Geometric graphs and uniform embeddings Carver 202

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.

Alfred Hero (University of Michigan) July 24 (Mon), 3:15 PM
Continuum limits for shortest paths Carver 202

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.

Ilse Ipsen (NC State University) July 27 (Thu), 10:10 AM
Randomized matrix-free trace and log-determinant estimators Carver 232

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.

Tanvi Jain (Indian Statistical Institute at Delhi, India) July 25 (Tue), 10:40 AM
Hadamard powers of two classes of positive matrices Carver 305

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.

Helene Massam (York University, Canada) July 27 (Thu), 10:40 AM
Precision matrix estimation and sampling in coloured graphical Gaussian models Carver 232

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.

Nikolas Stott (INRIA & CMAP, Ecole polytechnique, Université Paris-Saclay, France) July 25 (Tue), 10:10 AM
Minimal upper bounds in the Loewner order: characterizations and parametrization Carver 305

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.

Caroline Uhler (MIT) July 27 (Thu), 11:10 AM
Your dreams may come true with MTP2 Carver 232

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.

Cynthia Vinzant (NC State University) July 27 (Thu), 11:40 AM
Hyperbolicity and reciprocal linear spaces Carver 232

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.