We study the categorical structure of the Grothendieck construction of an indexed category $\mathcal{L}:\mathcal{C}^{op}\to\mathbf{CAT}$ and characterise fibred limits, colimits, and monoidal structures. Next, we give sufficient conditions for the monoidal closure of the total category $\Sigma_\mathcal{C} \mathcal{L}$ of a Grothendieck construction of an indexed category $\mathcal{L}:\mathcal{C}^{op}\to\mathbf{CAT}$. Our analysis is a generalization of G\"odel's Dialectica interpretation, and it relies on a novel notion of $\Sigma$-tractible monoidal structure. As we will see, $\Sigma$-tractible coproducts simultaneously generalize cocartesian coclosed structures, biproducts and extensive coproducts. We analyse when the closed structure is fibred -- usually it is not.
Parameter inference for linear and non-Gaussian state space models is challenging because the likelihood function contains an intractable integral over the latent state variables. Exact inference using Markov chain Monte Carlo is computationally expensive, particularly for long time series data. Variational Bayes methods are useful when exact inference is infeasible. These methods approximate the posterior density of the parameters by a simple and tractable distribution found through optimisation. In this paper, we propose a novel sequential variational Bayes approach that makes use of the Whittle likelihood for computationally efficient parameter inference in this class of state space models. Our algorithm, which we call Recursive Variational Gaussian Approximation with the Whittle Likelihood (R-VGA-Whittle), updates the variational parameters by processing data in the frequency domain. At each iteration, R-VGA-Whittle requires the gradient and Hessian of the Whittle log-likelihood, which are available in closed form for a wide class of models. Through several examples using a linear Gaussian state space model and a univariate/bivariate non-Gaussian stochastic volatility model, we show that R-VGA-Whittle provides good approximations to posterior distributions of the parameters and is very computationally efficient when compared to asymptotically exact methods such as Hamiltonian Monte Carlo.
The minimization principle MIN($\prec$) studied in bounded arithmetic in [Chiari, M. and Kraj\'i\v{c}ek, J. Witnessing Functions in Bounded Arithmetic and Search Problems, Journal of Symbolic Logic, 63(3):1095-1115, 1998] says that a strict linear ordering $\prec$ on any finite interval $[0,\dots,n)$ has the minimal element. We shall prove that bounded arithmetic theory $T^1_2(\prec)$ augmented by instances of the pigeonhole principle for all $\Delta^b_1(\prec)$ formulas does not prove MIN($\prec$).
The problem of computing posterior functionals in general high-dimensional statistical models with possibly non-log-concave likelihood functions is considered. Based on the proof strategy of [49], but using only local likelihood conditions and without relying on M-estimation theory, nonasymptotic statistical and computational guarantees are provided for a gradient based MCMC algorithm. Given a suitable initialiser, these guarantees scale polynomially in key algorithmic quantities. The abstract results are applied to several concrete statistical models, including density estimation, nonparametric regression with generalised linear models and a canonical statistical non-linear inverse problem from PDEs.
In various stereological problems an $n$-dimensional convex body is intersected with an $(n-1)$-dimensional Isotropic Uniformly Random (IUR) hyperplane. In this paper the cumulative distribution function associated with the $(n-1)$-dimensional volume of such a random section is studied. This distribution is also known as chord length distribution and cross section area distribution in the planar and spatial case respectively. For various classes of convex bodies it is shown that these distribution functions are absolutely continuous with respect to Lebesgue measure. A Monte Carlo simulation scheme is proposed for approximating the corresponding probability density functions.
In $1998,$ Daemen {\it{ et al.}} introduced a circulant Maximum Distance Separable (MDS) matrix in the diffusion layer of the Rijndael block cipher, drawing significant attention to circulant MDS matrices. This block cipher is now universally acclaimed as the AES block cipher. In $2016,$ Liu and Sim introduced cyclic matrices by modifying the permutation of circulant matrices and established the existence of MDS property for orthogonal left-circulant matrices, a notable subclass within cyclic matrices. While circulant matrices have been well-studied in the literature, the properties of cyclic matrices are not. Back in $1961$, Friedman introduced $g$-circulant matrices which form a subclass of cyclic matrices. In this article, we first establish a permutation equivalence between a cyclic matrix and a circulant matrix. We explore properties of cyclic matrices similar to $g$-circulant matrices. Additionally, we determine the determinant of $g$-circulant matrices of order $2^d \times 2^d$ and prove that they cannot be simultaneously orthogonal and MDS over a finite field of characteristic $2$. Furthermore, we prove that this result holds for any cyclic matrix.
Let $G$ be a group with undecidable domino problem (such as $\mathbb{Z}^2$). We prove the undecidability of all nontrivial dynamical properties for sofic $G$-subshifts, that such a result fails for SFTs, and an undecidability result for dynamical properties of $G$-SFTs similar to the Adian-Rabin theorem. For $G$ amenable we prove that topological entropy is not computable from presentations of SFTs, and a more general result for dynamical invariants taking values in partially ordered sets.
We consider Newton's method for finding zeros of mappings from a manifold $\mathcal{X}$ into a vector bundle $\mathcal{E}$. In this setting a connection on $\mathcal{E}$ is required to render the Newton equation well defined, and a retraction on $\mathcal{X}$ is needed to compute a Newton update. We discuss local convergence in terms of suitable differentiability concepts, using a Banach space variant of a Riemannian distance. We also carry over an affine covariant damping strategy to our setting. Finally, we will discuss some applications of our approach, namely, finding fixed points of vector fields, variational problems on manifolds and finding critical points of functionals.
We show that modeling a Grassmannian as symmetric orthogonal matrices $\operatorname{Gr}(k,\mathbb{R}^n) \cong\{Q \in \mathbb{R}^{n \times n} : Q^{\scriptscriptstyle\mathsf{T}} Q = I, \; Q^{\scriptscriptstyle\mathsf{T}} = Q,\; \operatorname{tr}(Q)=2k - n\}$ yields exceedingly simple matrix formulas for various curvatures and curvature-related quantities, both intrinsic and extrinsic. These include Riemann, Ricci, Jacobi, sectional, scalar, mean, principal, and Gaussian curvatures; Schouten, Weyl, Cotton, Bach, Pleba\'nski, cocurvature, nonmetricity, and torsion tensors; first, second, and third fundamental forms; Gauss and Weingarten maps; and upper and lower delta invariants. We will derive explicit, simple expressions for the aforementioned quantities in terms of standard matrix operations that are stably computable with numerical linear algebra. Many of these aforementioned quantities have never before been presented for the Grassmannian.
We consider the two-pronged fork frame $F$ and the variety $\mathbf{Eq}(B_F)$ generated by its dual closure algebra $B_F$. We describe the finite projective algebras in $\mathbf{Eq}(B_F)$ and give a purely semantic proof that unification in $\mathbf{Eq}(B_F)$ is finitary and not unitary.
We show that it is undecidable whether a system of linear equations over the Laurent polynomial ring $\mathbb{Z}[X^{\pm}]$ admit solutions where a specified subset of variables take value in the set of monomials $\{X^z \mid z \in \mathbb{Z}\}$. In particular, we construct a finitely presented $\mathbb{Z}[X^{\pm}]$-module, where it is undecidable whether a linear equation $X^{z_1} \boldsymbol{f}_1 + \cdots + X^{z_n} \boldsymbol{f}_n = \boldsymbol{f}_0$ has solutions $z_1, \ldots, z_n \in \mathbb{Z}$. This contrasts the decidability of the case $n = 1$, which can be deduced from Noskov's Lemma. We apply this result to settle a number of problems in computational group theory. We show that it is undecidable whether a system of equations has solutions in the wreath product $\mathbb{Z} \wr \mathbb{Z}$, providing a negative answer to an open problem of Kharlampovich, L\'{o}pez and Miasnikov (2020). We show that there exists a finitely generated abelian-by-cyclic group in which the problem of solving a single quadratic equation is undecidable. We also construct a finitely generated abelian-by-cyclic group, different to that of Mishchenko and Treier (2017), in which the Knapsack Problem is undecidable. In contrast, we show that the problem of Coset Intersection is decidable in all finitely generated abelian-by-cyclic groups.