Presburger arithmetic is the first-order theory of the integers with addition and ordering, but without multiplication. This theory is decidable and the sets it defines admit several different representations, including formulas, generators, and finite automata, the latter being the focus of this thesis. Finite-automata representations of Presburger sets work by encoding numbers as words and sets by automata-defined languages. With this representation, set operations are easily computable as automata operations, and minimized deterministic automata are a canonical representation of Presburger sets. However, automata-based representations are somewhat opaque and do not allow all operations to be performed efficiently. An ideal situation would be to be able to move easily between formula-based and automata-based representations but, while building an automaton from a formula is a well understood process, moving the other way is a much more difcult problem that has only attracted attention fairly recently. The main results of this thesis are new algorithms for extracting information about Presburger-definable sets represented by finite automata. More precisely, we present algorithms that take as input a finite-automaton representing a Presburger definable set S and compute in polynomial time the affine hull over Q or over Z of the set S, i.e., the smallest set defined by a conjunction of linear equations (and congruence relations in Z) which includes S. Also, we present an algorithm that takes as input a deterministic finite-automaton representing the integer elements of a polyhedron P and computes a quantifier-free formula corresponding to this set. The algorithms rely on a very detailed analysis of the scheme used for encoding integer vectors and this analysis sheds light on some structural properties of finite-automata representing Presburger definable sets. The algorithms presented have been implemented and the results are encouraging : automata with more than 100000 states are handled in seconds.

This thesis is about extended affine Lie algebras and extended affine Weyl groups. In Chapter I, we provide the basic knowledge necessary for the study of extended affine Lie algebras and related objects. In Chapter II, we show that the well-known twisting phenomena which appears in the realization of the twisted affine Lie algebras can be extended to the class of extended affine Lie algebras, in the sense that some extended affine Lie algebras (in particular nonsimply laced extended affine Lie algebras) can be realized as fixed point subalgebras of some other extended affine Lie algebras (in particular simply laced extended affine Lie algebras) relative to some finite order automorphism. We show that extended affine Lie algebras of type A₁, B, C and BC can be realized as twisted subalgebras of types A_§¤(l ¡Ã 2) and D algebras. Also we show that extended affine Lie algebras of type BC can be realized as twisted subalgebras of type C algebras. In Chapter III, the last chapter, we study the Weyl groups of reduced extended affine root systems. We start by describing the extended affine Weyl group as a semidirect product of a finite Weyl group and a Heisenberg-like normal subgroup. This provides a unique expression for the Weyl group elements which in turn leads to a presentation of the Weyl group, called a presentation by conjugation. Using a new notion, called the index, which is an invariant of the extended affine root systems, we show that one of the important features of finite and affine root systems (related to Weyl group) holds for the class of extended affine root systems. We also show that extended affine Weyl groups (of index zero) are homomorphic images of some indefinite Weyl groups where the homomorphism and its kernel are given explicitly.

[Truncated abstract] One common task in Computer Vision is the estimation of three-dimensional surface shape from two-dimensional images. This task is important as a precursor to higher level tasks such as object recognition - since shape of an object gives clues to what the object is - and object modelling for graphics. Many visual cues have been suggested in the literature to provide shape information, including the shading of an object, its occluding contours (the outline of the object that slants away from the viewer) and its appearance from two or more views. If the image exhibits a significant amount of texture, then this too may be used as a shape cue. Here, ‘texture’ is taken to mean the pattern on the surface of the object, such as the dots on a pear, or the tartan pattern on a tablecloth. This problem of estimating the shape of an object based on its texture is referred to as shape-form-texture and it is the subject of this thesis . . . The work in this thesis is likely to impact in a number of ways. The second shape-form-texture algorithm provides one of the most general solutions to the problem. On the other hand, if the assumptions of the first shape-form-texture algorithm are met, this algorithm provides an extremely usable method, in that users should be able to input images of textured objects and click on the frontal texture to quickly reconstruct a fairly good estimation of the surface. And lastly, the algorithm for estimating the transformation between textures can be used as a part of many shape-form-texture algorithms, as well as being useful in other areas of Computer Vision. This thesis gives two examples of other applications for the method: re-texturing an object and placing objects in a scene.

This dissertation aims at theoretically studying a block of layers that is common in al- most all deep learning models. The block of layers of interest is the composition of an affine layer followed by a nonlinear activation that is followed by another affine layer. We study this block from three perspectives. (i) An Optimization Perspective. Is it possible that the output of the forward pass through this block is an optimal solution to a certain convex optimization problem? We show an equivalency between the forward pass through this block and a single iteration of deterministic and stochastic algorithms solving a ten- sor formulated convex optimization problem. As consequence, we derive for the first time a formula for computing the singular values of convolutional layers surpassing the need for the prohibitive construction of the underlying linear operator. Thereafter, we show that several deep networks can have this block replaced with the corresponding optimiza- tion algorithm predicted by our theory resulting in networks with improved generalization performance. (ii) A Probabilistic Perspective. Is it possible to analytically analyze the output of a deep network upon subjecting the input to Gaussian noise? To that regard, we derive analytical formulas for the first and second moments of this block under Gaussian input noise. We demonstrate that the derived expressions can be used to efficiently analyze the output of an arbitrary deep network in addition to constructing Gaussian adversarial attacks surpassing any need for prohibitive data augmentation procedures. (iii) A Tropi- cal Geometry Perspective. Is it possible to characterize the decision boundaries of this block as a geometric structure representing a solution set to a certain class of polynomials (tropical polynomials)? If so, then, is it possible to utilize this geometric representation of the decision boundaries for novel reformulations to classical computer vision and machine learning tasks on arbitrary deep networks? We show that the decision boundaries of this block are a subset of a tropical hypersurface, which is intimately related to a the polytope that is the convex hull of two zonotopes. We utilize this geometric characterization to shed lights on new perspectives of network pruning.

Cette thèse présente plusieurs extensions relatives aux modèles affines positifs de taux d'intérêt. Un premier chapitre introduit les concepts reliés aux modélisations employées dans les chapitres suivants. Il détaille la définition de processus dits affines, et la construction de modèles de prix d'actifs obtenus par non-arbitrage. Le chapitre 2 propose une nouvelle méthode d’estimation et de filtrage pour les modèles espace-état linéaire-quadratiques. Le chapitre suivant applique cette méthode d’estimation à la modélisation d’écarts de taux interbancaires de la zone Euro, afin d’en décomposer les fluctuations liées au risque de défaut et de liquidité. Le chapitre 4 développe une nouvelle technique de création de processus affines multivariés à partir leurs contreparties univariées, sans imposer l’indépendance conditionnelle entre leurs composantes. Le dernier chapitre applique cette méthode et dérive un processus affine multivarié dont certaines composantes peuvent rester à zéro pendant des périodes prolongées. Incorporé dans un modèle de taux d’intérêt, ce processus permet de rendre compte efficacement des taux plancher à zéro. / This thesis presents new developments in the literature of non-negative affine interest rate models. The first chapter is devoted to the introduction of the main mathematical tools used in the following chapters. In particular, it presents the so-called affine processes which are extensively employed in no-arbitrage interest rate models. Chapter 2 provides a new filtering and estimation method for linear-quadratic state-space models. This technique is exploited in the 3rd chapter to estimate a positive asset pricing model on the term structure of Euro area interbank spreads. This allows us to decompose the interbank risk into a default risk and a liquidity risk components. Chapter 4 proposes a new recursive method for building general multivariate affine processes from their univariate counterparts. In particular, our method does not impose the conditional independence between the different vector elements. We apply this technique in Chapter 5 to produce multivariate non-negative affine processes where some components can stay at zero for several periods. This process is exploited to build a term structure model consistent with the zero lower bound features.

Algebraic geometry is the study of systems of polynomial equations in one or more variables. Thinking of polynomials as functions reveals a close connection between affine varieties, which are geometric structures, and ideals, which are algebraic objects. An affine variety is a collection of tuples that represents the solutions to a system of equations. An ideal is a special subset of a ring and is what provides the tools to prove geometric theorems algebraically. In this thesis, we establish that a variety depends on the ideal generated by its defining equations. The ability to change the basis of an ideal without changing the variety is a powerful tool in determining a variety. In general, the quotient and remainder on division of polynomials in more than one variable are not unique. One property of a Groebner basis is that it yields a unique remainder on division. To prove geometric theorems algebraically, we first express the hypotheses and conclusions as polynomials. Then, with the aid of a computer, apply the Groebner Basis Algorithm to determine if the conclusion polynomial(s) vanish on the same variety as the hypotheses.

We provide the definition and a complete characterization of regular affine processes. This type of process unifies the concepts of continuous-state branching processes with immigration and Ornstein-Uhlenbeck type processes. We show, and provide foundations for, a wide range of financial applications for regular affine processes. (author's abstract) / Series: Working Papers SFB "Adaptive Information Systems and Modelling in Economics and Management Science"

Thesis (M. Phil.)--University of Hong Kong, 2002. / Includes bibliographical references (leaves 123-125).

published_or_final_version / abstract / Electrical and Electronic Engineering / Master / Master of Philosophy

published_or_final_version / Electrical and Electronic Engineering / Master / Master of Philosophy