In this thesis, we focus on the estimation of two structured graphical models with constraints: (1) total positivity and (2) Laplacian constraints. The two structured graphical models have received increasing attention in recent years, primarily due to their interesting properties. Estimating precision matrices is a central problem in the study of graphical models, which presents the probabilistic relationships between random variables. We study the estimation of precision matrices under the two structured graphical models, including theory, algorithms, and applications.

We first consider the problem of learning graphical models under total positivity. In this model, the distributions are Gaussian and satisfy the constraint of total positivity, a particular form of positive dependence....[ Read more ]

In this thesis, we focus on the estimation of two structured graphical models with constraints: (1) total positivity and (2) Laplacian constraints. The two structured graphical models have received increasing attention in recent years, primarily due to their interesting properties. Estimating precision matrices is a central problem in the study of graphical models, which presents the probabilistic relationships between random variables. We study the estimation of precision matrices under the two structured graphical models, including theory, algorithms, and applications.

We first consider the problem of learning graphical models under total positivity. In this model, the distributions are Gaussian and satisfy the constraint of total positivity, a particular form of positive dependence. Such models arise in a variety of applications such as actuarial sciences, taxonomic reasoning, and financial markets. The total positivity constraint is relevant for example for portfolio selection, since instruments in equity markets are often positively dependent as a result of the market factor. The state-of-the-art methods for learning graphical models under total positivity are first-order algorithms based on the block coordinate descent. Such algorithms are efficient for low-dimensional problems, while they become time-consuming in high-dimensional cases, because they need to solve a large number of nonnegative quadratic programs. We propose a fast and scalable algorithm based on projected Newton-like method for solving this problem with the theoretical convergence guaranteed, and establish the support recovery consistency.

We then consider the problem of learning graphical models under Laplacian constraints, where the precision matrix is a Laplacian matrix. In this model, the elements of the precision matrix can quantify the similarity between nodes. Such property is desired in modelling smooth graphs where a large graph weight between two nodes represents a significant similarity between their signal values. The estimated precision matrix is useful in graph signal processing, because it enjoys the spectral property that its eigenvalues and eigenvectors can be interpreted as spectral frequencies and Fourier bases. However, how to learn a sparse graph under this model remains to be further explored. Recent works used the ℓ₁-norm with the goal of estimating sparse precision matrices under Laplacian constraints. Both theoretically and experimentally, we show that the widely used ℓ₁-norm is not effective in imposing a sparse solution in this problem. To overcome the issue of the ℓ₁ norm, we propose a new estimator by introducing the nonconvex sparsity penalty. We establish the non-asymptotic optimization performance guarantees on both optimization error and statistical error, and prove that the algorithm will converge to the oracle estimator.

Finally, we study the minimax rate of convergence for the estimation of sparse precision matrices under Laplacian constrained Gaussian graphical models. The minimax rate of convergence characterizes the fundamental difficulty of an estimation problem, and a desired estimator is expected to achieve this rate. We establish the minimax rate of convergenc through the derivation of the minimax lower and upper bounds, which provides a benchmark for evaluating rate optimality of the estimators. We also prove an interesting result that the maximum likelihood estimator under the Laplacian constraints exists almost surely with as few as one observation regardless of the underlying dimension, in contrast to the general Gaussian graphical models, where the maximum likelihood estimator does not exists if the number of observations is smaller than the dimension.