MIMS EPrints
Not a member yet
2151 research outputs found
Sort by
The Theory of Spectrum Exchangeability
Get PDFSpectrum Exchangeability, Sx, is an irrelevance principle of Pure Inductive Logic, and arguably the most natural (but not the only) extension of Atom Exchangeability to polyadic languages. It has been shown that all probability functions which satisfy Sx are comprised of a mixture of two essential types of probability functions; heterogeneous and homogeneous functions. We determine the theory of Spectrum Exchangeability, which for a fixed language L is the set of sentences of L which must be assigned probability 1 by every probability function satisfying Sx, by examining separately the theories of heterogeneity and homogeneity. We find that the theory of Sx is equal to the theory of finite structures, i.e. those sentences true in all finite structures for L, and it emerges that Sx is inconsistent with the principle of Super-Regularity (Universal Certainty). As a further consequence we are able to characterize those probability functions which satisfy Sx and the Finite Values Property
Local Fusion Graphs and Sporadic Simple Groups
Get PDFFor a group G with G-conjugacy class of involutions X, the local fusion graph F(G,X) has X as its vertex set, with distinct vertices x and y joined by an edge if, and only if, the product xy has odd order. Here we show that, with only three possible exceptions, for all pairs (G,X) with G a sporadic simple group or the automorphism group of a sporadic simple group, F(G,X) has diameter 2
Squish scaling
No full textWe present a new technique for computing similarity scalings for max-plus matrices. These �¢����squish scalings�¢���� can be chosen to optimise certain quantities allowing one to, for instance, minimise the difference between the largest and smallest entry in a matrix or emphasize certain subsets of entries in the matrix such as the tridiagonal or some permutation
An explicit reconstruction algorithm for the transverse ray transform of a second rank tensor field from three axis data
Get PDFWe give an explicit plane-by-plane filtered back-projection reconstruction algorithm for the transverse ray transform of symmetric second rank tensor fields on Euclidean 3-space, using data from rotation about three orthogonal axes. We show that in the general case two axis data is insufficient but give an explicit reconstruction procedure for the potential case with two axis data
Computing Fundamental matrix decompositions accurately via the matrix sign function in two iterations: The power of Zolotarev's functions
Get PDFThe symmetric eigenvalue decomposition and the singular value decomposition (SVD) are fundamental matrix decompositions with many applications. Conventional algorithms for computing these decompositions are suboptimal in view of recent trends in computer architectures, which require minimizing communication together with arithmetic costs. Spectral divide-and-conquer algorithms, which recursively decouple the problem into two smaller subproblems, can achieve both requirements. Such algorithms can be constructed with the polar decomposition playing two key roles: it forms a bridge between the symmetric eigendecomposition and the SVD, and its connection to the matrix sign function naturally leads to spectral-decoupling. For computing the polar decomposition, the
scaled Newton and QDWH iterations are two of the most popular algorithms, as they are backward stable and converge in at most nine and six iterations, respectively. Following this framework, we develop a higher-order variant of the QDWH iteration for the polar decomposition. The key idea of this algorithm comes from approximation theory: we use the best rational approximant for the scalar sign function due to Zolotarev in 1877. The algorithm exploits the extraordinary property enjoyed by the sign function
that a high-degree Zolotarev function (best rational approximant) can be obtained by appropriately composing low-degree Zolotarev functions. This lets the algorithm converge in just \emph{two} iterations in double-precision arithmetic, with the whopping rate of convergence \emph{seventeen}. The resulting algorithms for the
symmetric eigendecompositions and the SVD have higher arithmetic costs than the QDWH-based algorithms, but are better-suited for parallel computing and exhibit excellent numerical backward stability
Taylor's Theorem for Matrix Functions with Applications to Condition Number Estimation
Get PDFWe derive an explicit formula for the remainder term of a
Taylor polynomial of a matrix function.
This formula generalizes a known result for the remainder of the
Taylor series for an analytic function of a complex scalar.
We investigate some consequences of this result,
which culminate in new upper bounds for the level-1 and level-2
condition numbers of a matrix function in terms of the
pseudospectrum of the matrix.
Numerical experiments show that,
although the bounds can be pessimistic,
they can be computed almost three orders of magnitude faster than the
standard methods for the -norm condition number of .
This makes the upper bounds ideal for a quick estimation of the
condition number whilst a more accurate (and expensive) method
can be used if further accuracy is required
The RKFIT algorithm for nonlinear rational approximation
Get PDFThe RKFIT algorithm outlined in [M. Berljafa and S. Güttel, Generalized rational Krylov decompositions with an application to rational approximation, SIAM J. Matrix Anal. Appl., 2015] is a Krylov-based approach for solving nonlinear rational least squares problems. This paper puts RKFIT into a general framework, allowing for its extension to nondiagonal rational approximants and a family of approximants sharing a common denominator. Furthermore, we derive a strategy for the degree reduction of the approximants, as well as methods for their conversion to partial fraction form, for the efficient evaluation, and root-finding. We also discuss commons and differences of RKFIT and the popular vector fitting algorithm. A MATLAB implementation of RKFIT is provided and numerical experiments, including the fitting of a MIMO dynamical system and an optimization problem related to exponential integration, demonstrate its applicability
Anderson Acceleration of the Alternating Projections Method for Computing the Nearest Correlation Matrix
No full textIn a wide range of applications it is required to compute the nearest correlation matrix in the Frobenius norm to a given symmetric but indefinite matrix. Of the available methods with guaranteed convergence to the unique solution of this problem the easiest to implement, and perhaps the most widely used, is the alternating projections method. However, the rate of convergence of this method is at best linear, and it can require a large number of iterations to converge to within a given tolerance. We show that Anderson acceleration, a technique for accelerating the convergence of fixed-point iterations, can be applied to the alternating projections method and that in practice it brings a significant reduction in both the number of iterations and the computation time. We also show that Anderson acceleration remains effective, and indeed can provide even greater improvements, when it is applied to the variants of the nearest correlation matrix problem in which specified elements are fixed or a lower bound is imposed on the smallest eigenvalue. Alternating projections is a general method for finding a point in the intersection of several sets and ours appears to be the first demonstration that this class of methods can benefit from Anderson acceleration
An examination of the SEP Candidate Analogical Inference Rule within Pure Inductive Logic
Get PDFWithin the framework of (Unary) Pure Inductive Logic we investigate four possible formulations of a probabilistic principle of analogy based on a template considered by Paul Bartha in the Stanford Encyclopedia of Philosophy and give some characterizations of the probability functions which satisfy them. In addition we investigate an alternative interpretation of analogical support, also considered by Bartha, based not on the enhancement of probability but on the creation of possibility
The Principle of Signature Exchangeability
Get PDFWe investigate the notion of a signature in Polyadic Inductive Logic and study the probability functions satisfying the Principle of Signature Exchangeability. In the binary case, we prove a representation theorem for such functions and show that they satisfy a binary version of the Principle of Instantial Relevance. We discuss polyadic versions of the Principle of Instantial Relevance and Johnson�s Sufficientness Postulate