Rigidity theory in statistical inference

Daniel Irving Bernstein · 2026

Read Rigidity theory in statistical inference by Daniel Irving Bernstein (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-10864.txt.

Introduction

Daniel Irving Bernstein writes an expository survey on rigidity theory in statistical inference. A statistical model is a family of probability distributions. Fitting picks the member that best matches data. For Gaussian models, the maximum likelihood threshold says how many samples are needed before a best fit is sure to exist.

Bernstein sums up what is known about these thresholds. He stresses their links with rigidity theory, the study of when frameworks of bars and joints hold firm. The tie is a surprise bridge between statistics and geometry. Survey papers like this one let newcomers enter a field through its results and its open problems in one read.

Catalog record

CREATORDaniel Irving Bernstein
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE23 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2601-10864

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Rigidity theory in statistical inference Daniel Irving Bernstein Abstract . In this expository article, we summarize what is known about maximum likelihood thresholds of Gaussian models, paying special attention to connections with rigidity theory. 1. Introduction A statistical model is a collection of probability distributions, and model fitting is the process of choosing the probability distribution within a statistical model that best describes a particular dataset, according to some criteria. One of the most fundamental families of statistical models are the unconstrained n -variate Gaussian models , which are the families of probability distributions whose density functions can be expressed as follows for some symmetric positive definite n\times n matrix \Sigma , called the covariance matrix and some \mu\in\mathbb{R}^{n} , called the mean vector f_{\mu,\Sigma}({\bf x}):=\frac{\exp\left(-\frac{1}{2}({\bf x}-\mu)^{T}\Sigma^{-1}({\bf x}-\mu)\right)}{\sqrt{(2\pi)^{d}\det(\Sigma)}}. In many applications, one has a dataset {\bf x}_{1},\dots,{\bf x}_{d} consisting of elements of \mathbb{R}^{n} which are believed to have been independently generated according to some fixed multivariate Gaussian and the goal is to estimate the parameters \mu and \Sigma which define that distribution. By treating this dataset as fixed and viewing the entries of \mu and \Sigma as variables, one can proceed by solving the following optimization problem (1) \displaystyle\mathmakebox[\widthof{$\underset{\displaystyle\mu,\Sigma}{\mathrm{subject~to}}$}][l]{\underset{\displaystyle\mu,\Sigma}{\mathrm{maximize}}}\quad\prod_{i=1}^{d}f_{\mu,\Sigma}({\bf x}_{i})\hfil\hfil\displaystyle\displaystyle\hfil\hfil\displaystyle\displaystyle \displaystyle\mathmakebox[\widthof{$\underset{\displaystyle\phantom{\mu,\Sigma}}{\mathrm{subject~to}}$}][c]{{\mathrm{subject~to}}}\quad \displaystyle\mu\in\mathbb{R}^{n}{\rm\ and\ }\Sigma{\rm\ positive\ definite}. When ( 1 ) has a solution, the optimal values \hat{\mu} and \hat{\Sigma} for the parameters \mu and \Sigma are the sample mean and covariance, i.e. \hat{\mu}=\frac{1}{d}\sum_{i=1}^{d}{\bf x}_{i}\qquad\qquad\hat{\Sigma}=\sum_{i=1}^{d}({\bf x}_{i}-\hat{\mu})({\bf x}_{i}-\hat{\mu})^{T}. This solves ( 1 ) precisely when \hat{\Sigma} is invertible. Many statistical models that are used in practice come from adding constraints to an unconstrained Gaussian model. In particular, for every set \mathcal{N} of n\times n symmetric positive definite matrices, one has the statistical model whose density functions are the following \{f_{\mu,\Sigma}:\mu\in\mathbb{R}^{n}{\rm\ and\ }\Sigma\in\mathcal{N}\}. Fitting such a model to a dataset {\bf x}_{1},\dots,{\bf x}_{d} can be done by solving the natural generalization of ( 1 ), namely the following (2) \displaystyle\mathmakebox[\widthof{$\underset{\displaystyle\mu,\Sigma}{\mathrm{subject~to}}$}][l]{\underset{\displaystyle\mu,\Sigma}{\mathrm{maximize}}}\quad\prod_{i=1}^{d}f_{\mu,\Sigma}({\bf x}_{i})\hfil\hfil\displaystyle\displaystyle\hfil\hfil\displaystyle\displaystyle \displaystyle\mathmakebox[\widthof{$\underset{\displaystyle\phantom{\mu,\Sigma}}{\mathrm{subject~to}}$}][c]{{\mathrm{subject~to}}}\quad \displaystyle\mu\in\mathbb{R}^{n}{\rm\ and\ }\Sigma\in\mathcal{N}. The mean vector \mu plays no meaningful role in the theoretical questions we are interested in. By replacing every dataset {\bf x}_{1},\dots,{\bf x}_{d} with its centering around the sample mean \hat{\mu} , i.e. with {\bf x}_{1}-\hat{\mu},\dots,{\bf x}_{d}-\hat{\mu} , we can without loss of generality assume that \mu=0 . By doing this and applying several operations to the objective function in ( 2 ) that preserve optimality (taking logarithms, dropping constant terms, etc.), we can transform ( 2 ) into the following equivalent optimization problem where X denotes the n\times d matrix whose columns are the datapoints {\bf x}_{1},\dots,{\bf x}_{d} (3) \displaystyle\mathmakebox[\widthof{$\underset{\displaystyle\Sigma}{\mathrm{subject~to}}$}][l]{\underset{\displaystyle\Sigma}{\mathrm{minimize}}}\quad\tr(X^{T}X\Sigma^{-1})-\log\det(\Sigma^{-1})\hfil\hfil\displaystyle\displaystyle\hfil\hfil\displaystyle\displaystyle \displaystyle\mathmakebox[\widthof{$\underset{\displaystyle\phantom{\Sigma}}{\mathrm{subject~to}}$}][c]{{\mathrm{subject~to}}}\quad \displaystyle\Sigma\in\mathcal{N} We can also shift perspective and view the entries of the inverse covariance matrix as our variables. In particular, we can set K:=\Sigma^{-1}\qquad{\rm and}\qquad\mathcal{M}:=\{A^{-1}:A\in\mathcal{N}\}. Also notice that X only enters the picture as X^{T}X . Putting this all together we have an optimization problem of the following form, where S is an arbitrary n\times n symmetric positive semidefinite matrix of rank at most d and \mathcal{M} is an arbitrary set of n\times n symmetric positive definite matrices (4) \displaystyle\mathmakebox[\widthof{$\underset{\displaystyle K}{\mathrm{subject~to}}$}][l]{\underset{\displaystyle K}{\mathrm{minimize}}}\quad\tr(SK)-\log\det(K)\hfil\hfil\displaystyle\displaystyle\hfil\hfil\displaystyle\displaystyle \displaystyle\mathmakebox[\widthof{$\underset{\displaystyle\phantom{K}}{\mathrm{subject~to}}$}][c]{{\mathrm{subject~to}}}\quad \displaystyle K\in\mathcal{M}. This motivates the following definition. Definition 1 . Let \mathcal{M} be a set of n\times n symmetric positive definite matrices. The smallest d such that the optimization problem ( 4 ) has a solution for almost all n\times n symmetric positive semidefinite S of rank d is called the maximum likelihood threshold (MLT) of \mathcal{M} . In this article, we will discuss what is known about maximum likelihood thresholds of various families of statistical models \mathcal{M} and how rigidity theory is relevant. 1.1. Notation We use the notation \mathcal{S}^{n},\mathcal{S}^{n}_{+},\mathcal{S}^{n}_{+}(d),\mathcal{S}^{n}_{++} to respectively denote the sets of n\times n the sets of symmetric matrices, positive semidefinite matrices, positive semidefinite matrices of rank d , and positive definite matrices. The set \{1,\dots,n\} will be denoted [n] . Given a graph G , the set of edges of G will be denoted E(G) . 2. Gaussian graphical models Let G be a graph on vertex set [n] and define \mathcal{M}_{G}:=\{A\in\mathcal{S}^{n}_{++}:A_{ij}=0{\rm\ if\ }i\neq j{\rm\ and\ }ij\notin E(G)\}. Given a graph G , the corresponding Gaussian graphical model is the family of multivariate Gaussian distributions whose inverse covariance lies in \mathcal{M}_{G} . See Figure 1 for an example. These models were originally introduced and studied by Dempster in 1972 in [ 6 ] . A simple consequence of Dempster’s result is the following alternative characterization of the MLT of a model \mathcal{M}_{G} . Theorem 2 ( [ 6 ] ) . Let G be a graph on vertex set [n] . Then the MLT of \mathcal{M}_{G} is the minimum d such that for almost every S\in\mathcal{S}^{n}_{+}(d) , there exists T\in\mathcal{S}^{n}_{++} such that T_{ii}=S_{ii} for all i\in[n] and T_{ij}=S_{ij} for all ij\in E . 1 2 3 4 G= L_{G}=\left\{\left.\begin{pmatrix}x_{11}&x_{12}&0&x_{14}\\ x_{12}&x_{22}&x_{23}&0\\ 0&x_{23}&x_{33}&x_{34}\\ x_{14}&0&x_{34}&x_{44}\end{pmatrix}\right|x_{11},\dots x_{44},\in\mathbb{R}\right\} \mathcal{M}_{G}=L_{G}\cap\mathcal{S}^{n}_{++} Figure 1. A graph and its corresponding Gaussian graphical model Computing or bounding the maximum likelihood threshold of \mathcal{M}_{G} in terms of the combinatorics of G is surprisingly difficult. The first result in this direction was proven in 1993 by Buhl in [ 5 ] , which we state below after recalling the necessary graph theoretic definitions. Recall that a graph is chordal if it has no induced cycles of length four or greater, and that a chordal cover of a graph G is a chordal graph containing G as a subgraph. The treewidth of a graph G is one less than the minimum clique number of a chordal cover of G . The clique number of a chordal graph is therefore one plus its treewidth, and thus a corollary of the following result is that the MLT of a chordal graph is its clique number. Theorem 3 ( [ 5 ] ) . Let G be a graph with clique number \omega and treewidth \tau . Then the MLT of G lies between \omega and \tau+1 . In 2012, Uhler showed [ 13 ] how one can use Gröbner bases to bound the MLT of \mathcal{M}_{G} from above. Gross and Sullivant later showed [ 9 ] how this upper bound can be understood in terms of rigidity properties of G . We now describe this after introducing the necessary rigidity-theoretic language. A d -dimensional framework consists of a graph G on vertex set [n] and a function p:[n]\rightarrow\mathbb{R}^{d} . A d -dimensional framework (G,p) should be conceptualized as a physical construction of the graph G in d -dimensional space by placing vertex i at point p(i) . Two frameworks (G,p) and (G,q) on the same graph are equivalent if \|p(i)-p(j)\|=\|q(i)-q(j)\| for every edge ij of G and moreover congruent if \|p(i)-p(j)\|=\|q(i)-q(j)\| holds for every pair i,j\in[n] . The left two frameworks in Figure 2 are equivalent but not congruent. A d -dimensional framework (G,p) is locally rigid if there exists \varepsilon>0 such that whenever q:[n]\rightarrow\mathbb{R}^{d} satisfies \|p(i)-q(i)\|\leq\varepsilon for all i\in[n] , (G,p) and (G,q) are equivalent. The frameworks on the left in Figure 2 are both locally rigid. The framework on the right is not, and this can be seen by noting that the framework can shear as shown. For each graph G and each positive integer d , there exists a subset S of functions p:[n]\rightarrow\mathbb{R}^{d} of Lebesge measure zero such

Read the complete text