Krylov subspace methods for approximating functions of symmetric positive definite matrices with applications to applied statistics and anomalous diffusion

Matrix function approximation is a current focus of worldwide interest and finds application in a variety of areas of applied mathematics and statistics. In this thesis we focus on the approximation of A^(-α/2)b, where A ∈ ℝ^(n×n) is a large, sparse symmetric positive definite matrix and b ∈ ℝ^n is a vector. In particular, we will focus on matrix function techniques for sampling from Gaussian Markov random fields in applied statistics and the solution of fractional-in-space partial differential equations. Gaussian Markov random fields (GMRFs) are multivariate normal random variables characterised by a sparse precision (inverse covariance) matrix. GMRFs are popular models in computational spatial statistics as the sparse structure can be exploited, typically through the use of the sparse Cholesky decomposition, to construct fast sampling methods. It is well known, however, that for sufficiently large problems, iterative methods for solving linear systems outperform direct methods. Fractional-in-space partial differential equations arise in models of processes undergoing anomalous diffusion. Unfortunately, as the fractional Laplacian is a non-local operator, numerical methods based on the direct discretisation of these equations typically requires the solution of dense linear systems, which is impractical for fine discretisations. In this thesis, novel applications of Krylov subspace approximations to matrix functions for both of these problems are investigated. Matrix functions arise when sampling from a GMRF by noting that the Cholesky decomposition A = LL^T is, essentially, a `square root' of the precision matrix A. Therefore, we can replace the usual sampling method, which forms x = L^(-T)z, with x = A^(-1/2)z, where z is a vector of independent and identically distributed standard normal random variables. Similarly, the matrix transfer technique can be used to build solutions to the fractional Poisson equation of the form ϕn = A^(-α/2)b, where A is the finite difference approximation to the Laplacian. Hence both applications require the approximation of f(A)b, where f(t) = t^(-α/2) and A is sparse. In this thesis we will compare the Lanczos approximation, the shift-and-invert Lanczos approximation, the extended Krylov subspace method, rational approximations and the restarted Lanczos approximation for approximating matrix functions of this form. A number of new and novel results are presented in this thesis. Firstly, we prove the convergence of the matrix transfer technique for the solution of the fractional Poisson equation and we give conditions by which the finite difference discretisation can be replaced by other methods for discretising the Laplacian. We then investigate a number of methods for approximating matrix functions of the form A^(-α/2)b and investigate stopping criteria for these methods. In particular, we derive a new method for restarting the Lanczos approximation to f(A)b. We then apply these techniques to the problem of sampling from a GMRF and construct a full suite of methods for sampling conditioned on linear constraints and approximating the likelihood. Finally, we consider the problem of sampling from a generalised Matern random field, which combines our techniques for solving fractional-in-space partial differential equations with our method for sampling from GMRFs.

Learning the Kernel Matrix with Semi-Definite Programming

Kernel-based learning algorithms work by embedding the data into a Euclidean space, and then searching for linear relations among the embedded data points. The embedding is performed implicitly, by specifying the inner products between each pair of points in the embedding space. This information is contained in the so-called kernel matrix, a symmetric and positive definite matrix that encodes the relative positions of all points. Specifying this matrix amounts to specifying the geometry of the embedding space and inducing a notion of similarity in the input space -- classical model selection problems in machine learning. In this paper we show how the kernel matrix can be learned from data via semi-definite programming (SDP) techniques. When applied to a kernel matrix associated with both training and test data this gives a powerful transductive algorithm -- using the labelled part of the data one can learn an embedding also for the unlabelled part. The similarity between test points is inferred from training points and their labels. Importantly, these learning problems are convex, so we obtain a method for learning both the model class and the function without local minima. Furthermore, this approach leads directly to a convex method to learn the 2-norm soft margin parameter in support vector machines, solving another important open problem. Finally, the novel approach presented in the paper is supported by positive empirical results.

Random projections on manifolds of symmetric positive definite matrices for image classification

Recent advances suggest that encoding images through Symmetric Positive Definite (SPD) matrices and then interpreting such matrices as points on Riemannian manifolds can lead to increased classification performance. Taking into account manifold geometry is typically done via (1) embedding the manifolds in tangent spaces, or (2) embedding into Reproducing Kernel Hilbert Spaces (RKHS). While embedding into tangent spaces allows the use of existing Euclidean-based learning algorithms, manifold shape is only approximated which can cause loss of discriminatory information. The RKHS approach retains more of the manifold structure, but may require non-trivial effort to kernelise Euclidean-based learning algorithms. In contrast to the above approaches, in this paper we offer a novel solution that allows SPD matrices to be used with unmodified Euclidean-based learning algorithms, with the true manifold shape well-preserved. Specifically, we propose to project SPD matrices using a set of random projection hyperplanes over RKHS into a random projection space, which leads to representing each matrix as a vector of projection coefficients. Experiments on face recognition, person re-identification and texture classification show that the proposed approach outperforms several recent methods, such as Tensor Sparse Coding, Histogram Plus Epitome, Riemannian Locality Preserving Projection and Relational Divergence Classification.

Right-Definite Multiparameter Sturm–Liouville Problems With Eigenparameter-Dependent Boundary Conditions

We study a system of ordinary differential equations linked by parameters and subject to boundary conditions depending on parameters. We assume certain definiteness conditions on the coefficient functions and on the boundary conditions that yield, in the corresponding abstract setting, a right-definite case. We give results on location of the eigenvalues and oscillation of the eigenfunctions.

On the issues of resolving a low melting combination as a definite eutectic or an elusive cocrystal: A critical evaluation

Cocrystals and eutectics are different yet related crystalline multi-component adducts with diverse applications in pharmaceutical and materials fields. Recently, they were shown to be alternate products of cocrystallization experiments. Whereas a cocrystal shows distinct diffraction, spectroscopic and thermal signatures as compared to parent components, the hallmark of a eutectic is its low melting nature. However, in certain cases, there can be a problem when one resorts to design a cocrystal and assess its formation vis-A -vis a eutectic. In the absence of a gold standard method to make a cocrystal, it is often difficult to judge how exhaustive should the cocrystallization trials be to ensure the accomplishment of a desired/putative cocrystal. Further, a cocrystal can manifest with intermolecular interactions and/or crystal structure similar to that of its parent compounds such that the conventional diffraction and spectroscopic techniques will be of little help to conclusively infer the formation of cocrystal in the lack of single crystals. Such situations combined with low melting behavior of a combination brings the complication of resolving the combination as a cocrystal or eutectic since now both the adducts share common features. Based on the curious case of Caffeine-Benzoic acid combination, this study aims to unfold the intricate issues related to the design, formation and characterization of cocrystals and eutectics for a way forward. The utility of heteronuclear seeding methodology in establishing a given combination as a cocrystal-forming one or a eutectic-forming one in four known systems is appraised.

Matrices whose hermitian part is positive definite

We are concerned with the class ∏_n of nxn complex matrices A for which the Hermitian part H(A) = A+A*/2 is positive definite.

Various connections are established with other classes such as the stable, D-stable and dominant diagonal matrices. For instance it is proved that if there exist positive diagonal matrices D, E such that DAE is either row dominant or column dominant and has positive diagonal entries, then there is a positive diagonal F such that FA ϵ ∏_n.

Powers are investigated and it is found that the only matrices A for which A^m ϵ ∏_n for all integers m are the Hermitian elements of ∏_n. Products and sums are considered and criteria are developed for AB to be in ∏_n.

Since ∏_n n is closed under inversion, relations between H(A)^-1 and H(A^-1) are studied and a dichotomy observed between the real and complex cases. In the real case more can be said and the initial result is that for A ϵ ∏_n, the difference H(adjA) - adjH(A) ≥ 0 always and is ˃ 0 if and only if S(A) = A-A*/2 has more than one pair of conjugate non-zero characteristic roots. This is refined to characterize real c for which cH(A^-1) - H(A)^-1 is positive definite.

The cramped (characteristic roots on an arc of less than 180°) unitary matrices are linked to ∏_n and characterized in several ways via products of the form A ^-1A*.

Classical inequalities for Hermitian positive definite matrices are studied in ∏_n and for Hadamard's inequality two types of generalizations are given. In the first a large subclass of ∏_n in which the precise statement of Hadamardis inequality holds is isolated while in another large subclass its reverse is shown to hold. In the second Hadamard's inequality is weakened in such a way that it holds throughout ∏_n. Both approaches contain the original Hadamard inequality as a special case.

Rank-preserving geometric means of positive semi-definite matrices

The generalization of the geometric mean of positive scalars to positive definite matrices has attracted considerable attention since the seminal work of Ando. The paper generalizes this framework of matrix means by proposing the definition of a rank-preserving mean for two or an arbitrary number of positive semi-definite matrices of fixed rank. The proposed mean is shown to be geometric in that it satisfies all the expected properties of a rank-preserving geometric mean. The work is motivated by operations on low-rank approximations of positive definite matrices in high-dimensional spaces.© 2012 Elsevier Inc. All rights reserved.

Towards a Computational Theory of Definite Anaphora Comprehension in English Discourse

This report investigates the process of focussing as a description and explanation of the comprehension of certain anaphoric expressions in English discourse. The investigation centers on the interpretation of definite anaphora, that is, on the personal pronouns, and noun phrases used with a definite article the, this or that. Focussing is formalized as a process in which a speaker centers attention on a particular aspect of the discourse. An algorithmic description specifies what the speaker can focus on and how the speaker may change the focus of the discourse as the discourse unfolds. The algorithm allows for a simple focussing mechanism to be constructed: and element in focus, an ordered collection of alternate foci, and a stack of old foci. The data structure for the element in focus is a representation which encodes a limted set of associations between it and other elements from teh discourse as well as from general knowledge.

Behavioral Measures and their Correlation with IPM Iteration Counts on Semi-Definite Programming Problems

We study four measures of problem instance behavior that might account for the observed differences in interior-point method (IPM) iterations when these methods are used to solve semidefinite programming (SDP) problem instances: (i) an aggregate geometry measure related to the primal and dual feasible regions (aspect ratios) and norms of the optimal solutions, (ii) the (Renegar-) condition measure C(d) of the data instance, (iii) a measure of the near-absence of strict complementarity of the optimal solution, and (iv) the level of degeneracy of the optimal solution. We compute these measures for the SDPLIB suite problem instances and measure the correlation between these measures and IPM iteration counts (solved using the software SDPT3) when the measures have finite values. Our conclusions are roughly as follows: the aggregate geometry measure is highly correlated with IPM iterations (CORR = 0.896), and is a very good predictor of IPM iterations, particularly for problem instances with solutions of small norm and aspect ratio. The condition measure C(d) is also correlated with IPM iterations, but less so than the aggregate geometry measure (CORR = 0.630). The near-absence of strict complementarity is weakly correlated with IPM iterations (CORR = 0.423). The level of degeneracy of the optimal solution is essentially uncorrelated with IPM iterations.

‘That’s definite discrimination’: practice under the umbrella of inclusion

Inclusive practice is well embedded across society and has developed over time. However, although policy and public view have moved forward, the way organisations address the agenda for inclusion often represents a superficial interpretation of this concept. Qualitative data were gathered using new ethnography to explore the experiences of a library-based reading group for visually impaired readers. The voices of the individuals shed light on the individual and collective experience of reading. These insights challenge the traditional views of distinct provision that are designed to address targets for inclusion of individuals with disabilities. We argue for a clearer focus on the unintentional consequences of practice in the name of inclusion that leave individuals feeling marginalised. This paper suggests the alternative focus on social justice as offering a discourse that focuses on society and away from the individual.

The syntax-semantics of bare and definite plural subjects in the L2 Spanish of English natives

This study investigates the extent to which advanced native-English L2 learners of Spanish come to acquire restrictions on bare plural preverbal subjects in L2 Spanish (e.g. gatos “cats” vs. definite plurals such as los gatos “the cats”). It tests L2 knowledge of available semantic readings of bare plurals and definite plurals in Spanish, where [+specific] and [+generic] interpretations are syntactically represented differently from English. Assuming L1 transfer, and in view of a potential subset/superset relationship of the two grammars, the learning task in this domain is not a straightforward one. Target acquisition requires both grammatical expansion and retraction; Spanish definite plural subjects require the addition of an L1-unavailable [+generic] reading, while a loss of an L1-available [+generic] reading for preverbal subject bare plurals is required. The results and analysis show that advanced L2 learners of Spanish (English L1) can circumvent a superficial subset/superset learnability problem by means of feature resetting in line with the Nominal Mapping Parameter.

Production and on-line comprehension of definite articles and clitic pronouns by Greek sequential bilingual children and monolingual children with specific language impairment

The present study compared production and on-line comprehension of definite articles and third person direct object clitic pronouns in Greek-speaking typically developing, sequential bilingual (L2-TD) children and monolingual children with specific language impairment (L1-SLI). Twenty Turkish Greek L2-TD children, 16 Greek L1-SLI children, and 31 L1-TD Greek children participated in a production task examining definite articles and clitic pronouns and, in an on-line comprehension task, involving grammatical sentences with definite articles and clitics and sentences with grammatical violations induced by omitted articles and clitics. The results showed that the L2-TD children were sensitive to the grammatical violations despite low production. In contrast, the children with SLI were not sensitive to clitic omission in the on-line task, despite high production. These results support a dissociation between production and on-line comprehension in L2 children and for impaired grammatical representations and lack of automaticity in children with SLI. They also suggest that on-line comprehension tasks may complement production tasks by differentiating between the language profiles of L2-TD children and children with SLI.

Production of definite and indefinite articles in typically developing English-speaking children and children with SLI

The present paper examines the production of definite and indefinite articles in English-speaking typically developing (TD) children and children with Specific Language Impairment (SLI). Twenty four English-speaking children with SLI (mean age: 7;5), twenty nine TD age-matched (TD-AM) children (mean age: 7;5) and eleven younger (mean age: 5;5) TD vocabulary-matched (TD-VM) children participated in a production task involving short stories without picture props based on Schafer and de Villiers (2000). Article production was examined in two different semantic contexts for the definite article, namely in the anaphoric and the bridging context. In the anaphoric condition, definiteness is established via linguistic means, whereas in the bridging condition via shared world knowledge. Indefinite article production was examined in the referential specific, non-referential predicational, and non-referential instrumental contexts. The referential specific context involves [+speaker, −hearer] knowledge and the non-referential predicational and instrumental [−speaker, −hearer] knowledge. Results showed that in the definite article contexts, all three groups performed better on the bridging compared with the anaphoric condition; in the indefinite article contexts, they had better performance on the non-referential predicational vs. the referential specific and the non-referential instrumental conditions. In terms of errors, the TD-VM children and the children with SLI produced significantly more substitutions than the TD-AM children in the definite article contexts. In the indefinite article contexts, the three groups did not differ in terms of accuracy or error patterns. The present results point towards problems in the discourse integration of entities that are part of the speaker's and hearer's knowledge in children with SLI and TD-VM controls, especially in definite articles. These problems are accentuated in the children with SLI due to their grammatical impairment and suggest that children with SLI exhibit a delayed acquisition profile.