Abstract We discuss the invertibility of severval figures arising from iterated function systems (IFS). We shall prove the attractor of a totally disconnected IFS is invertible. More generally, we introduce a concept of branch point condition and prove that the attractor of an IFS is invertible if it satisfies the branch point condition.

Un morphisme d’espaces de probabilité vers l’espace de Wiener, qui est de plus adapté, peut être associé canoniquement à certaines lois d’équations différentielles stchastiques, une de ses propriétés essentielles étant qu’il est un isomorphisme d’espaces de probabilité si et seulement si l’équation différentielle stochastique associée admet une unique solution forte. Puisqu’on peut le voir comme un mouvement Brownien canoniquement associé à une loi, on lui donnera le nom de transformée Brownienne de la loi, et il s’agira de s’intéresser à son inversibilité. Comme on le verra en la présentant, cette notion, qui s’enracine autour de résultats déjà employés par Fölmer il y a fort longtemps, prolonge naturellement la notion d’inversibilité des dérives adaptées qui a été développée ces dernières années dans les travaux d’Üstünel et de Zakai où elle se trouve déjà en germes, et ouvre naturellement à un large éventail d’applications très concrètes. On sera naturellement amené à envisager des problèmes issus de la théorie du filtrage, de la physique statistique, du contrôle stochastique, du transport optimal, ainsi que la théorie de l’information. En particulier, on donnera un résultat d’unicité trajectorielle très général pour la représentation stochastique de la mécanique quantique en temps Euclidien, et on étendra l’inégalité de Shannon aux espaces de Wiener absraits, cette dernière recevant au passage une jolie interprétation en termes de perte d’information dans un canal Gaussien. On transportera ensuite cette notion d’inversibilité dans des cadres plus géométriques tels que l’espace des chemins à valeurs dans un groupe de Lie. / I this work we investigate a notion of stochastic invertibility on Wiener space. Rougghly speaking a morphism of probability spaces with values on the Wiener space, which is further adapted, can be canonically associated to the laws of the solutions to some stochastic differential equations. One of the main properties of this morphism is to be invertible (i.e. to be an isomorphism of probability spaces) if and only if the underlying stochastic differential equation has a unique strong solution. Since it may be seen as a Brownian motion, we cal it the Brownian transform of the associated law, and we will study the invertibility of this Brownan transform. We will see that this notion, whose origins may be found in earlier results related to stochastic mechanics, extends and enlightens the notion of invertibility of adapted shifts on Wiener space which was investigated by Üstünel and Zakai in their recent papers, where this notion already appears clearly between the lines. Moreover, from the origin many problems arising in various fields are deeply related to this notion. This opens to a wide spectrum of applications, some of them being very concrete. We will investigate problems of various origins such as statistical physics, information theory, filtering, but also stochastic control and optimal transport. For instance, we will prove a very general result of pathwise uniqueness for the stochastic picture of euclidean quantum mechanics, and we will extend Shannon’s inequality to any abstract Wiener spaces. We also show how this notion of invertivility fits naturally in stochastic differencial geometry.

This thesis contains three articles. The first two concern inversion andlocal injectivity of the weighted Radon transform in the plane. The thirdpaper concerns two of the key results from compressive sensing.In Paper A we prove an identity involving three singular double integrals.This is then used to prove an inversion formula for the weighted Radon transform,allowing all weight functions that have been considered previously.Paper B is devoted to stability estimates of the standard and weightedlocal Radon transform. The estimates will hold for functions that satisfy an apriori bound. When weights are involved they must solve a certain differentialequation and fulfill some regularity assumptions.In Paper C we present some new constant bounds. Firstly we presenta version of the theorem of uniform recovery of random sampling matrices,where explicit constants have not been presented before. Secondly we improvethe condition when the so-called restricted isometry property implies the nullspace property. / <p>QC 20140228</p>

Whilst results from Structural Proof Theory can be couched in many formalisms, it is the sequent calculus which is the most amenable of the formalisms to metamathematical treatment. Constructive syntactic proofs are filled with bureaucratic details; rarely are all cases of a proof completed in the literature. Two intermediate results can be used to drastically reduce the amount of effort needed in proofs of Cut admissibility: Weakening and Invertibility. Indeed, whereas there are proofs of Cut admissibility which do not use Invertibility, Weakening is almost always necessary. Use of these results simply shifts the bureaucracy, however; Weakening and Invertibility, whilst more easy to prove, are still not trivial. We give a framework under which sequent calculi can be codified and analysed, which then allows us to prove various results: for a calculus to admit Weakening and for a rule to be invertible in a calculus. For the latter, even though many calculi are investigated, the general condition is simple and easily verified. The results have been applied to G3ip, G3cp, G3s, G3-LC and G4ip. Invertibility is important in another respect; that of proof-search. Should all rules in a calculus be invertible, then terminating root-first proof search gives a decision procedure for formulae without the need for back-tracking. To this end, we present some results about the manipulation of rule sets. It is shown that the transformations do not affect the expressiveness of the calculus, yet may render more rules invertible. These results can guide the design of efficient calculi. When using interactive proof assistants, every case of a proof, however complex, must be addressed and proved before one can declare the result formalised. To do this in a human readable way adds a further layer of complexity; most proof assistants give output which is only legible to a skilled user of that proof assistant. We give human-readable formalisations of Cut admissibility for G3cp and G3ip, Contraction admissibility for G4ip and Craig's Interpolation Theorem for G3i using the Isar vernacular of Isabelle. We also formalise the new invertibility results, in part using the package for reasoning about first-order languages, Nominal Isabelle. Examples are given showing the effectiveness of the formalisation. The formal proof of invertibility using the new methods is drastically shorter than the traditional, direct method.

Let K be any field and Q be the rationals. Define K^1[X] = {f(X) e K[X]| the coefficient of X in f(X) is zero} and Q^1β[X] = {f(X) e Q[X]| the coefficent of β1(X) in the binomial expansion of f(X) is zero}, where {β1(X)}^∞ i=0 are the well-known binomial polynomials. In this work, I establish the following results: K^1[X] and Q^1β[X] are one-dimensional, Noetherian, non-Prüfer domains with the two-generator property on ideals. Using the unique factorization structure of the overrings K[X] and Q[X], the nonprincipal ideal structures of both rings are characterized, and from this characterization, necessary and sufficient conditions are found for a nonprincipal ideal to be invertible. The nonprincipal invertible ideals are then characterized in terms of the coefficients of the generators, and an explicit formula for the inverse of any proper invertible ideal is found. Finally, the class groups of both rings are shown to be torsion free abelian groups. Let n be any nonnegative integer. Results similar to the above are found in the generalizations of these two rings, K^n[X] and q^nβ[X], where the coefficients on the first n nonconstant basis elements are zero. For the domains K^1[X] and Q^1β[X], the property of strong two-generation is explored in detail and the following results are established: 1. K^1[X] and Q^1β[X] are not strongly two-generated, 2. In either ring, any polynomial with a constant term, or of degree two or three is a strong two-generator. 3. In K^1[X] any polynomial divisible by X^4 is not a strong two-generator, 4. An ideal I in K^1[X] or Q^1β[X] is strongly two-generated if and only if it is invertible.

Let P and Q be two idempotents, we review the results about the equivalence between the invertibility of a linear combination aP +bQ and that of P +Q, where a and b are any nonzero complex numbers with a + b eq 0. It is possible to extend the results to the case P and Q are square-zero elements. However, we will show that these extensions are impossible in general for P and Q being partial isometries or n-potents with n geq 3. We will show in case P and Q are square-zero elements, the invertibility of P +Q is equivalent to that of aP +bQ for nonzero a, b.

Dans cette thèse, on aborde trois thèmes : problème de sélection de colonnes dans une matrice, distance de Banach-Mazur au cube et estimation de la covariance de matrices aléatoires. Bien que les trois thèmes paraissent éloignés, les techniques utilisées se ressemblent tout au long de la thèse. Dans un premier lieu, nous généralisons le principe d'invertibilité restreinte de Bourgain-Tzafriri. Ce résultat permet d'extraire un "grand" bloc de colonnes linéairement indépendantes dans une matrice et d'estimer la plus petite valeur singulière de la matrice extraite. Nous proposons ensuite un algorithme déterministe pour extraire d'une matrice un bloc presque isométrique c’est à dire une sous-matrice dont les valeurs singulières sont proches de 1. Ce résultat nous permet de retrouver le meilleur résultat connu sur la célèbre conjecture de Kadison-Singer. Des applications à la théorie locale des espaces de Banach ainsi qu'à l'analyse harmonique sont déduites. Nous donnons une estimation de la distance de Banach-Mazur d'un corps convexe de Rn au cube de dimension n. Nous proposons une démarche plus élémentaire, basée sur le principe d'invertibilité restreinte, pour améliorer et simplifier les résultats précédents concernant ce problème. Plusieurs travaux ont été consacrés pour approcher la matrice de covariance d'un vecteur aléatoire par la matrice de covariance empirique. Nous étendons ce problème à un cadre matriciel et on répond à la question. Notre résultat peut être interprété comme une quantification de la loi des grands nombres pour des matrices aléatoires symétriques semi-définies positives. L'estimation obtenue s'applique à une large classe de matrices aléatoires / In this thesis, we address three themes : columns subset selection in a matrix, the Banach-Mazur distance to the cube and the estimation of the covariance of random matrices. Although the three themes seem distant, the techniques used are similar throughout the thesis. In the first place, we generalize the restricted invertibility principle of Bougain-Tzafriri. This result allows us to extract a "large" block of linearly independent columns inside a matrix and estimate the smallest singular value of the restricted matrix. We also propose a deterministic algorithm in order to extract an almost isometric block inside a matrix i.e a submatrix whose singular values are close to 1. This result allows us to recover the best known result on the Kadison-Singer conjecture. Applications to the local theory of Banach spaces as well as to harmonic analysis are deduced. We give an estimate of the Banach-Mazur distance between a symmetric convex body in Rn and the cube of dimension n. We propose an elementary approach, based on the restricted invertibility principle, in order to improve and simplify the previous results dealing with this problem. Several studies have been devoted to approximate the covariance matrix of a random vector by its sample covariance matrix. We extend this problem to a matrix setting and we answer the question. Our result can be interpreted as a quantified law of large numbers for positive semidefinite random matrices. The estimate we obtain, applies to a large class of random matrices

No description available.

Programming languages traditionally describe computations going one way: a program might compute a hash value from a string, or an encrypted message from a plaintext. However, sometimes it is also of interest to go the other way around: for encryption, we not only want to encrypt messages but also to decrypt them, and to be sure that the decryption correctly reproduces the original message. In an invertible programming language, a single program specifies two directions of a transformation, and the language guarantees that the two correspond as inverses. Invertible languages often require programs to be composed from atomic invertible fragments, a property known as local invertibility. This requirement has connections to applications such as low-energy and quantum computing. However, many invertible algorithms are more naturally expressed as depending unidirectionally on some inputs, e.g., the encryption key—this property is known as partial invertibility. Existing work largely lacks a systematic treatment of partial invertibility, and the connection to the locally invertible paradigm is not yet well-understood. In this thesis, we show that with the right design tradeoff, partial invertibility can be expressed within a locally invertible setting. We present KALPIS, a new functional language supporting expressive partial invertibility, yet maintaining a straightforward locally invertible semantics. This is made formal by a novel arrow combinator language RRARR, with primitives embodying functions, parameterized bijections, and interactions between the two. The formulation is based on recent work on effects in invertible computation, namely the irreversibility effect and the reversible reader. We substantiate the work with a prototype implementation of KALPIS, and demonstrate its utility through a number of nontrivial examples. Further, we give a complete formalization of the two systems, including the operational semantics and type system of KALPIS and a locally invertible interpretation and equational characterization of RRARR. Finally, we give a compositional translation from KALPIS into RRARR, motivating us to call it an arrow metalanguage. Most of the formalization is mechanized using the proof assistant Agda. / Programmeringsspråk beskriver traditionellt beräkningar som går åt ett håll: ett program kan till exempel beräkna ett hash-värde från en sträng eller ett krypterat meddelande från en klartext. Ibland är det dock även av intresse att gå åt andra hållet: vid kryptering vill vi inte bara kryptera meddelanden utan också avkryptera dem, och vara säkra på att avkrypteringen korrekt återskapar det ursprungliga meddelandet. I ett inverterbart programmeringsspråk beskriver ett enskilt program två riktningar av en transformation, och språket garanterar att de två motsvarar varandra som inverser. Inverterbara språk kräver ofta att program konstrueras från enskilt inverterbara komponenter, en egenskap som kallas lokal inverterbarhet. Denna egenskap har kopplingar till tillämpningar som lågenergioch kvantdatorer. Å andra sidan är det ofta naturligt att inverterbara algoritmer beror enkelriktat på vissa indata, till exempel krypteringsnyckeln—något som kallas partiell inverbarhet. Tidigare forskning saknar i stor utsträckning en systematisk behandling av partiell inverterbarhet, och kopplingen till lokal inverterbarhet är ännu inte välförstådd. I denna avhandling visar vi att med rätt designavvägning kan partiell inverterbarhet uttryckas ovanpå en lokalt inverterbar grund. Vi presenterar KALPIS, ett nytt funktionellt språk som stöder uttrycksfull partiell inverterbarhet, samtidigt som det bibehåller en enkel lokalt inverterbar semantik. Detta formaliseras genom ett nytt Arrow-kombinatorspråk RRARR, vars primitiver representerar funktioner, parameteriserade bijektioner och interaktioner mellan de två. Formuleringen baseras på ny forskning om sidoeffekter i inverterbar beräkning, nämligen irreversibilitetseffekten och reversible reader. Vi substantierar arbetet med en prototypimplementation av KALPIS och visar dess användbarhet genom ett antal icketriviala exempel. Dessutom ger vi en komplett formalisering av de två systemen, inklusive operativ semantik och typsystem för KALPIS och en lokalt inverterbar tolkning och ekvationskaraktärisering av RRARR. Slutligen ger vi en kompositionell översättning från KALPIS till RRARR, vilket motiverar oss att kalla det ett Arrow-metaspråk. Det mesta av formaliseringen är mekaniserad med hjälp av bevisassistenten Agda.

En esta tesis doctoral se deriva un procedimiento de contraste localmente óptimo para la hipótesis nula de cointegración en modelos ARIMA multivariantes. Si existen combinaciones lineales estacionarias entre las variables integradas que componen el sistema objeto de análisis, la diferenciación simultánea de las mismas introduce una estructura MA(1) adicional no invertible en el modelo VARIMA que sigue el vector de series. El procedimiento de análisis que se propone en esta tesis, por tanto, consiste en ajustar un modelo VARIMA al vector de series y detectar la presencia de cointegración contrastando la no invertibilidad del polinomio media móvil. Para ello se deriva la extensión multivariante de los contrastes de no invertibilidad tanto para el modelo básico VIMA(1,1) como para el modelo general VARIMA(p,1,q+1). En este último caso, se propone una corrección paramétrica basada en los residuos exactos del modelo, alternativa a las correcciones no paramétricas habituales en la literatura. / In this doctoral thesis a locally optimal testing procedure for the null of cointegration in multivariate ARIMA models is derived. If there are linear combinations of integrated variables that are stationary, simultaneously differencing them introduces an additional noninvertible MA(1) structure to the VARIMA model that describes the vector of time series. The procedure of analysis proposed in this thesis consists of fitting a VARIMA model to the vector of series and detecting the presence of cointegration testing the noninvertibility of the moving average polynomial. To this aim, the multivariate extension of the noninvertibility tests in the basic model VIMA(1,1) and in the general VARIMA(p,1,q+1) model are derived. In the latter case, a parametric correction based on the exact residuals of the model is proposed, alternative to the non parametric corrections common in the literature.