-
Large-scale semi-discrete optimal transport with distributed Voronoi diagrams
Authors:
Bruno Lévy
Abstract:
In this article, I propose a numerical method to solve semi-discrete optimal transport problems for gigantic pointsets ($10^8$ points and more). By pushing the limits by several orders of magnitude, it opens the path to new applications in cosmology, fluid simulation and data science to name but a few. The method is based on a new algorithm that computes (generalized) Voronoi diagrams in parallel…
▽ More
In this article, I propose a numerical method to solve semi-discrete optimal transport problems for gigantic pointsets ($10^8$ points and more). By pushing the limits by several orders of magnitude, it opens the path to new applications in cosmology, fluid simulation and data science to name but a few. The method is based on a new algorithm that computes (generalized) Voronoi diagrams in parallel and in a distributed way. First I make the simple observation that the cells defined by a subgraph of the Delaunay graph contain the Voronoi cells, and that one can deduce the missing edges from the intersections between those cells. Based on this observation, I introduce the Distributed Voronoi Diagram algorithm (DVD) that can be used on a cluster and that exchanges vertices between the nodes as need be. I also report early experimental results, demonstrating that the DVD algorithm has the potential to solve some giga-scale semi-discrete optimal transport problems encountered in computational cosmology.
△ Less
Submitted 6 June, 2024;
originally announced June 2024.
-
Exact predicates, exact constructions and combinatorics for mesh CSG
Authors:
Bruno Lévy
Abstract:
This article introduces a general mesh intersection algorithm that exactly computes the so-called Weiler model and that uses it to implement boolean operations with arbitrary multi-operand expressions, CSG (constructive solid geometry) and some mesh repair operations. From an input polygon soup, the algorithm first computes the co-refinement, with an exact representation of the intersection points…
▽ More
This article introduces a general mesh intersection algorithm that exactly computes the so-called Weiler model and that uses it to implement boolean operations with arbitrary multi-operand expressions, CSG (constructive solid geometry) and some mesh repair operations. From an input polygon soup, the algorithm first computes the co-refinement, with an exact representation of the intersection points. Then, the decomposition of 3D space into volumetric regions (Weiler model) is constructed, by sorting the facets around the non-manifold intersection edges (radial sort), using specialized exact predicates. Finally, based on the input boolean expression, the triangular facets that belong to the boundary of the result are classified. This is, to our knowledge, the first algorithm that computes an exact Weiler model. To implement all the involved predicates and constructions, two geometric kernels are proposed, tested and discussed (arithmetic expansions and multi-precision floating-point). As a guiding principle,the combinatorial information shared between each step is kept as simple as possible. It is made possible by treating all the particular cases in the kernel. In particular, triangles with intersections are remeshed using the (uniquely defined) Constrained Delaunay Triangulation, with symbolic perturbations to disambiguate configurations with co-cyclic points. It makes it easy to discard the duplicated triangles that appear when remeshing overlapping facets. The method is tested and compared with previous work, on the existing "thingi10K" dataset (to test co-refinement and mesh repair) and on a new "thingiCSG" dataset made publicly available (to test the full CSG pipeline) on a variety of interesting examples featuring different types of "pathologies"
△ Less
Submitted 21 May, 2024;
originally announced May 2024.
-
Monge Ampère gravity: from the large deviation principle to cosmological simulations through optimal transport
Authors:
Bruno Lévy,
Yann Brenier,
Roya Mohayaee
Abstract:
We study Monge-Ampère gravity (MAG) as an effective theory of cosmological structure formation through optimal transport theory. MAG is based on the Monge-Ampère equation, a nonlinear version of the Poisson equation, that relates the Hessian determinant of the potential to the density field. We explain how MAG emerges from a conditioned system of independent and indistinguishable Brownian particle…
▽ More
We study Monge-Ampère gravity (MAG) as an effective theory of cosmological structure formation through optimal transport theory. MAG is based on the Monge-Ampère equation, a nonlinear version of the Poisson equation, that relates the Hessian determinant of the potential to the density field. We explain how MAG emerges from a conditioned system of independent and indistinguishable Brownian particles, through the large deviation principle, in the continuum limit. To numerically explore this highly non-linear theory, we develop a novel N-body simulation method based on semi-discrete optimal transport. Our results obtained from the very first N-body simulation of Monge-Ampère gravity with over 100 millions particles show that on large scales, Monge-Ampère gravity is similar to the Newtonian gravity but favours the formation of anisotropic structures such as filaments. At small scales, MAG has a weaker clustering and is screened in high-density regions. Although here we study the Monge-Ampère gravity as an effective rather than a fundamental theory, our novel highly-performant optimal transport algorithm can be used to run high-resolution simulations of a large class of modified theories of gravity, such as Galileons, in which the equations of motion are second-order and of Monge-Ampère type.
△ Less
Submitted 11 April, 2024;
originally announced April 2024.
-
Displacement Field Analysis via Optimal Transport: Multi-Tracer Approach to Cosmological Reconstruction
Authors:
Farnik Nikakhtar,
Ravi K. Sheth,
Nikhil Padmanabhan,
Bruno Lévy,
Roya Mohayaee
Abstract:
We demonstrate the effectiveness of one of the many multi-tracer analyses enabled by Optimal Transport (OT) reconstruction. Leveraging a semi-discrete OT algorithm, we determine the displacements between initial and observed positions of biased tracers and the remaining matter field. With only redshift-space distorted final positions of biased tracers and a simple premise for the remaining mass di…
▽ More
We demonstrate the effectiveness of one of the many multi-tracer analyses enabled by Optimal Transport (OT) reconstruction. Leveraging a semi-discrete OT algorithm, we determine the displacements between initial and observed positions of biased tracers and the remaining matter field. With only redshift-space distorted final positions of biased tracers and a simple premise for the remaining mass distribution as input, OT solves the displacement field. This extracted field, assuming asymptotically uniform density and a gradient flow displacement, enables reconstruction of the initial overdensity fluctuation field. We show that the divergence of the OT displacement field is a good proxy of the linear density field, even though the method never assumes the linear theory growth. Additionally, this divergence field can be combined with the reconstructed protohalos to provide a higher signal-to-noise measurement of the BAO standard ruler than was possible with either measurement individually.
△ Less
Submitted 18 March, 2024;
originally announced March 2024.
-
Comparative Analysis of Practical Identifiability Methods for an SEIR Model
Authors:
Omar Saucedo,
Amanda Laubmeier,
Tingting Tang,
Benjamin Levy,
Lale Asik,
Tim Pollington,
Olivia Prosper
Abstract:
Identifiability of a mathematical model plays a crucial role in parameterization of the model. In this study, we establish the structural identifiability of a Susceptible-Exposed-Infected-Recovered (SEIR) model given different combinations of input data and investigate practical identifiability with respect to different observable data, data frequency, and noise distributions. The practical identi…
▽ More
Identifiability of a mathematical model plays a crucial role in parameterization of the model. In this study, we establish the structural identifiability of a Susceptible-Exposed-Infected-Recovered (SEIR) model given different combinations of input data and investigate practical identifiability with respect to different observable data, data frequency, and noise distributions. The practical identifiability is explored by both Monte Carlo simulations and a Correlation Matrix approach. Our results show that practical identifiability benefits from higher data frequency and data from the peak of an outbreak. The incidence data gives the best practical identifiability results compared to prevalence and cumulative data. In addition, we compare and distinguish the practical identifiability by Monte Carlo simulations and a Correlation Matrix approach, providing insights for when to use which method for other applications.
△ Less
Submitted 24 February, 2024; v1 submitted 26 January, 2024;
originally announced January 2024.
-
Optimal Transport Reconstruction of Biased Tracers in Redshift Space
Authors:
Farnik Nikakhtar,
Nikhil Padmanabhan,
Bruno Lévy,
Ravi K. Sheth,
Roya Mohayaee
Abstract:
Recent research has emphasized the benefits of accurately reconstructing the initial Lagrangian positions of biased tracers from their positions at a later time, to gain cosmological information. A weighted semi-discrete optimal transport algorithm can achieve the required accuracy, provided the late-time positions are known, with minimal information about the background cosmology. The algorithm's…
▽ More
Recent research has emphasized the benefits of accurately reconstructing the initial Lagrangian positions of biased tracers from their positions at a later time, to gain cosmological information. A weighted semi-discrete optimal transport algorithm can achieve the required accuracy, provided the late-time positions are known, with minimal information about the background cosmology. The algorithm's performance relies on knowing the masses of the biased tracers, and depends on how one models the distribution of the remaining mass that is not associated with these tracers. We demonstrate that simple models of the remaining mass result in accurate retrieval of the initial Lagrangian positions, which we quantify using pair statistics and the void probability function. This is true even if the input positions are affected by redshift-space distortions. The most sophisticated models assume that the masses of the tracers, and the amount and clustering of the missing mass are known; we show that the method is robust to realistic errors in the masses of the tracers and remains so as the model for the missing mass becomes increasingly crude.
△ Less
Submitted 7 July, 2023;
originally announced July 2023.
-
Growing dendrites enhance a neuron's computational power and memory capacity
Authors:
William B Levy,
Robert A. Baxter
Abstract:
Neocortical pyramidal neurons have many dendrites, and such dendrites are capable of, in isolation of one-another, generating a neuronal spike. It is also now understood that there is a large amount of dendritic growth during the first years of a humans life, arguably a period of prodigious learning. These observations inspire the construction of a local, stochastic algorithm based on an earlier s…
▽ More
Neocortical pyramidal neurons have many dendrites, and such dendrites are capable of, in isolation of one-another, generating a neuronal spike. It is also now understood that there is a large amount of dendritic growth during the first years of a humans life, arguably a period of prodigious learning. These observations inspire the construction of a local, stochastic algorithm based on an earlier stochastic, Hebbian developmental theory. Here we investigate the neuro-computational advantages and limits on this novel algorithm that combines dendritogenesis with supervised adaptive synaptogenesis. Neurons created with this algorithm have enhanced memory capacity, can avoid catastrophic interference (forgetting), and have the ability to unmix mixture distributions. In particular, individual dendrites develop within each class, in an unsupervised manner, to become feature-clusters that correspond to the mixing elements of class-conditional mixture distribution. Although discriminative problems are used to understand the capabilities of the stochastic algorithm and the neuronal connectivity it produces, the algorithm is in the generative class, it thus seems ideal for decisions that require generalization, i.e., extrapolation beyond previous learning.
△ Less
Submitted 28 October, 2022;
originally announced October 2022.
-
In-vacuum microwave resonator for a compact cold atom frequency standard
Authors:
M. Givon,
L. Habib,
A. Waxman,
Y. Bar-Haim,
O. Amit,
Y. Cina,
G. Boneh,
D. Groswasser,
T. David,
B. Levy,
A. Stern,
R. Folman
Abstract:
A physics package for a compact cold atomic clock is hereby presented. The uniqueness of this package is its small dimensions that enable, for the first time, implementation of a primary cold atomic clock in a standard package of 3U height (=133mm). These dimensions are made possible by using an in-vacuum Microwave (MW) Loop Gap Resonator (LGR) whose length and diameter can be reduced from those o…
▽ More
A physics package for a compact cold atomic clock is hereby presented. The uniqueness of this package is its small dimensions that enable, for the first time, implementation of a primary cold atomic clock in a standard package of 3U height (=133mm). These dimensions are made possible by using an in-vacuum Microwave (MW) Loop Gap Resonator (LGR) whose length and diameter can be reduced from those of a typical resonator. Following our presentation of the design, we analyze the homogeneity of the MW field amplitude and phase. We find that the expected clock instability due to non-uniformity of the MW field is $\sim1.5\cdot10^{-14}$/day. Adding other clock errors, we estimate the total uncertainty of a cold atomic clock of this design will be around $\sim2\cdot10^{-14}$/day which results in a time drift of a few nanoseconds/day. Such a clock can serve as a primary-grade frequency reference, and may replace the cesium beam atomic clock and the GPS-disciplined rubidium atomic clocks.
△ Less
Submitted 18 August, 2022;
originally announced August 2022.
-
Symmetrized semi-discrete optimal transport
Authors:
Agathe Herrou,
Bruno Lévy,
Vincent Nivoliers,
Nicolas Bonneel,
Julie Digne
Abstract:
Interpolating between measures supported by polygonal or polyhedral domains is a problem that has been recently addressed by the semi-discrete optimal transport framework. Within this framework, one of the domains is discretized with a set of samples, while the other one remains continuous. In this paper we present a method to introduce some symmetry into the solution using coupled power diagrams.…
▽ More
Interpolating between measures supported by polygonal or polyhedral domains is a problem that has been recently addressed by the semi-discrete optimal transport framework. Within this framework, one of the domains is discretized with a set of samples, while the other one remains continuous. In this paper we present a method to introduce some symmetry into the solution using coupled power diagrams. This symmetry is key to capturing the discontinuities of the transport map reflected in the geometry of the power cells. We design our method as a fixed-point algorithm alternating between computations of semi-discrete transport maps and recentering of the sites. The resulting objects are coupled power diagrams with identical geometry, allowing us to approximate displacement interpolation through linear interpolation of the meshes vertices. Through these coupled power diagrams, we have a natural way of jointly sampling measures.
△ Less
Submitted 9 June, 2022;
originally announced June 2022.
-
Optimal Transport Reconstruction of Baryon Acoustic Oscillations
Authors:
Farnik Nikakhtar,
Ravi K. Sheth,
Bruno Lévy,
Roya Mohayaee
Abstract:
A weighted, semi-discrete, fast optimal transport (OT) algorithm for reconstructing the Lagrangian positions of proto-halos from their evolved Eulerian positions is presented. The algorithm makes use of a mass estimate of the biased tracers and of the distribution of the remaining mass (the `dust'), but is robust to errors in the mass estimates. Tests with state-of-art cosmological simulations sho…
▽ More
A weighted, semi-discrete, fast optimal transport (OT) algorithm for reconstructing the Lagrangian positions of proto-halos from their evolved Eulerian positions is presented. The algorithm makes use of a mass estimate of the biased tracers and of the distribution of the remaining mass (the `dust'), but is robust to errors in the mass estimates. Tests with state-of-art cosmological simulations show that if the dust is assumed to have a uniform spatial distribution, then the shape of the OT-reconstructed pair correlation function of the tracers is very close to linear theory, enabling sub-percent precision in the BAO distance scale that depends weakly, if at all, on a cosmological model. With a more sophisticated model for the dust, OT returns an estimate of the displacement field which yields superb reconstruction of the proto-halo positions, and hence of the shape and amplitude of the initial pair correlation function of the tracers. This enables direct and independent determinations of the bias factor $b$ and the smearing scale $Σ$, potentially providing new methods for breaking the degeneracy between $b$ and $σ_8$.
△ Less
Submitted 9 January, 2023; v1 submitted 3 March, 2022;
originally announced March 2022.
-
Accurate Baryon Acoustic Oscillations reconstruction via semi-discrete optimal transport
Authors:
Sebastian von Hausegger,
Bruno Lévy,
Roya Mohayaee
Abstract:
Optimal transport theory has recently reemerged as a vastly resourceful field of mathematics with elegant applications across physics and computer science. Harnessing methods from geometry processing, we report on the efficient implementation for a specific problem in cosmology -- the reconstruction of the linear density field from low redshifts, in particular the recovery of the Baryonic Acoustic…
▽ More
Optimal transport theory has recently reemerged as a vastly resourceful field of mathematics with elegant applications across physics and computer science. Harnessing methods from geometry processing, we report on the efficient implementation for a specific problem in cosmology -- the reconstruction of the linear density field from low redshifts, in particular the recovery of the Baryonic Acoustic Oscillation (BAO) scale. We demonstrate our algorithm's accuracy by retrieving the BAO scale in noise-less cosmological simulations that are dedicated to cancel cosmic variance; we find uncertainties to be reduced by a factor of 4.3 compared with performing no reconstruction, and a factor of 3.1 compared with standard reconstruction.
△ Less
Submitted 6 April, 2022; v1 submitted 17 October, 2021;
originally announced October 2021.
-
The Price of Mathematical Scepticism
Authors:
Paul Blain Levy
Abstract:
This paper argues that, insofar as we doubt the bivalence of the Continuum Hypothesis or the truth of the Axiom of Choice, we should also doubt the consistency of third-order arithmetic, both the classical and intuitionistic versions. Underlying this argument is the following philosophical view. Mathematical belief springs from certain intuitions, each of which can be either accepted or doubted in…
▽ More
This paper argues that, insofar as we doubt the bivalence of the Continuum Hypothesis or the truth of the Axiom of Choice, we should also doubt the consistency of third-order arithmetic, both the classical and intuitionistic versions. Underlying this argument is the following philosophical view. Mathematical belief springs from certain intuitions, each of which can be either accepted or doubted in its entirety, but not half-accepted. Therefore, our beliefs about reality, bivalence, choice and consistency should all be aligned.
△ Less
Submitted 25 May, 2022; v1 submitted 27 July, 2021;
originally announced July 2021.
-
Trend-Following Strategies via Dynamic Momentum Learning
Authors:
Bruno P. C. Levy,
Hedibert F. Lopes
Abstract:
Time series momentum strategies are widely applied in the quantitative financial industry and its academic research has grown rapidly since the work of Moskowitz, Ooi and Pedersen (2012). However, trading signals are usually obtained via simple observation of past return measurements. In this article we study the benefits of incorporating dynamic econometric models to sequentially learn the time-v…
▽ More
Time series momentum strategies are widely applied in the quantitative financial industry and its academic research has grown rapidly since the work of Moskowitz, Ooi and Pedersen (2012). However, trading signals are usually obtained via simple observation of past return measurements. In this article we study the benefits of incorporating dynamic econometric models to sequentially learn the time-varying importance of different look-back periods for individual assets. By the use of a dynamic binary classifier model, the investor is able to switch between time-varying or constant relations between past momentum and future returns, dynamically combining or selecting different momentum speeds during turning points, improving trading signals accuracy and portfolio performance. Using data from 56 future contracts we show that a mean-variance investor will be willing to pay a considerable management fee to switch from the traditional naive time series momentum strategy to the dynamic classifier approach.
△ Less
Submitted 5 November, 2021; v1 submitted 15 June, 2021;
originally announced June 2021.
-
Partial Optimal Transport for a Constant-Volume Lagrangian Mesh with Free Boundaries
Authors:
Bruno Lévy
Abstract:
This article introduces a representation of dynamic meshes, adapted to some numerical simulations that require controlling the volume of objects with free boundaries, such as incompressible fluid simulation, some astrophysical simulations at cosmological scale, and shape/topology optimization. The algorithm decomposes the simulated object into a set of convex cells called a Laguerre diagram, param…
▽ More
This article introduces a representation of dynamic meshes, adapted to some numerical simulations that require controlling the volume of objects with free boundaries, such as incompressible fluid simulation, some astrophysical simulations at cosmological scale, and shape/topology optimization. The algorithm decomposes the simulated object into a set of convex cells called a Laguerre diagram, parameterized by the position of $N$ points in 3D and $N$ additional parameters that control the volumes of the cells. These parameters are found as the (unique) solution of a convex optimization problem -- semi-discrete Monge-Ampère equation -- stemming from optimal transport theory. In this article, this setting is extended to objects with free boundaries and arbitrary topology, evolving in a domain of arbitrary shape, by solving a partial optimal transport problem. The resulting Lagrangian scheme makes it possible to accurately control the volume of the object, while precisely tracking interfaces, interactions, collisions, and topology changes.
△ Less
Submitted 3 June, 2021;
originally announced June 2021.
-
Dynamic Portfolio Allocation in High Dimensions using Sparse Risk Factors
Authors:
Bruno P. C. Levy,
Hedibert F. Lopes
Abstract:
We propose a fast and flexible method to scale multivariate return volatility predictions up to high-dimensions using a dynamic risk factor model. Our approach increases parsimony via time-varying sparsity on factor loadings and is able to sequentially learn the use of constant or time-varying parameters and volatilities. We show in a dynamic portfolio allocation problem with 452 stocks from the S…
▽ More
We propose a fast and flexible method to scale multivariate return volatility predictions up to high-dimensions using a dynamic risk factor model. Our approach increases parsimony via time-varying sparsity on factor loadings and is able to sequentially learn the use of constant or time-varying parameters and volatilities. We show in a dynamic portfolio allocation problem with 452 stocks from the S&P 500 index that our dynamic risk factor model is able to produce more stable and sparse predictions, achieving not just considerable portfolio performance improvements but also higher utility gains for the mean-variance investor compared to the traditional Wishart benchmark and the passive investment on the market index.
△ Less
Submitted 12 November, 2021; v1 submitted 13 May, 2021;
originally announced May 2021.
-
The evolving ecosystem of COVID-19 contact tracing applications
Authors:
Benjamin Levy,
Matthew Stewart
Abstract:
Since the outbreak of the novel coronavirus, COVID-19, there has been increased interest in the use of digital contact tracing as a means of stopping chains of viral transmission, provoking alarm from privacy advocates. Concerning the ethics of this technology, recent studies have predominantly focused on (1) the formation of guidelines for ethical contact tracing, (2) the analysis of specific imp…
▽ More
Since the outbreak of the novel coronavirus, COVID-19, there has been increased interest in the use of digital contact tracing as a means of stopping chains of viral transmission, provoking alarm from privacy advocates. Concerning the ethics of this technology, recent studies have predominantly focused on (1) the formation of guidelines for ethical contact tracing, (2) the analysis of specific implementations, or (3) the review of a select number of contact tracing applications and their relevant privacy or ethical implications. In this study, we provide a comprehensive survey of the evolving ecosystem of COVID-19 tracing applications, examining 152 contact tracing applications and assessing the extent to which they comply with existing guidelines for ethical contact tracing. The assessed criteria cover areas including data collection and storage, transparency and consent, and whether the implementation is open source. We find that although many apps released early in the pandemic fell short of best practices, apps released more recently, following the publication of the Apple/Google exposure notification protocol, have tended to be more closely aligned with ethical contact tracing principles. This dataset will be publicly available and may be updated as the pandemic continues.
△ Less
Submitted 18 March, 2021;
originally announced March 2021.
-
Using exoskeletons to assist medical staff during prone positioning of mechanically ventilated COVID-19 patients: a pilot study
Authors:
Serena Ivaldi,
Pauline Maurice,
Waldez Gomes,
Jean Theurel,
Liên Wioland,
Jean-Jacques Atain-Kouadio,
Laurent Claudon,
Hind Hani,
Antoine Kimmoun,
Jean-Marc Sellal,
Bruno Levy,
Jean Paysant,
Sergueï Malikov,
Bruno Chenuel,
Nicla Settembre
Abstract:
We conducted a pilot study to evaluate the potential and feasibility of back-support exoskeletons to help the caregivers in the Intensive Care Unit (ICU) of the University Hospital of Nancy (France) executing Prone Positioning (PP) maneuvers on patients suffering from severe COVID-19-related Acute Respiratory Distress Syndrome. After comparing four commercial exoskeletons, the Laevo passive exoske…
▽ More
We conducted a pilot study to evaluate the potential and feasibility of back-support exoskeletons to help the caregivers in the Intensive Care Unit (ICU) of the University Hospital of Nancy (France) executing Prone Positioning (PP) maneuvers on patients suffering from severe COVID-19-related Acute Respiratory Distress Syndrome. After comparing four commercial exoskeletons, the Laevo passive exoskeleton was selected and used in the ICU in April 2020. The first volunteers using the Laevo reported very positive feedback and reduction of effort, confirmed by EMG and ECG analysis. Laevo has been since used to physically assist during PP in the ICU of the Hospital of Nancy, following the recrudescence of COVID-19, with an overall positive feedback.
△ Less
Submitted 11 February, 2021;
originally announced February 2021.
-
Cerebral cortical communication overshadows computational energy-use, but these combine to predict synapse number
Authors:
William B Levy,
Victoria G. Calvert
Abstract:
Darwinian evolution tends to produce energy-efficient outcomes. On the other hand, energy limits computation, be it neural and probabilistic or digital and logical. Taking a particular energy-efficient viewpoint, we define neural computation and make use of an energy-constrained, computational function. This function can be optimized over a variable that is proportional to the number of synapses p…
▽ More
Darwinian evolution tends to produce energy-efficient outcomes. On the other hand, energy limits computation, be it neural and probabilistic or digital and logical. Taking a particular energy-efficient viewpoint, we define neural computation and make use of an energy-constrained, computational function. This function can be optimized over a variable that is proportional to the number of synapses per neuron. This function also implies a specific distinction between ATP-consuming processes, especially computation \textit{per se} vs the communication processes including action potentials and transmitter release. Thus to apply this mathematical function requires an energy audit with a partitioning of energy consumption that differs from earlier work. The audit points out that, rather than the oft-quoted 20 watts of glucose available to the brain \cite{sokoloff1960metabolism,sawada2013synapse}, the fraction partitioned to cortical computation is only 0.1 watts of ATP. On the other hand at 3.5 watts, long-distance communication costs are 35-fold greater. Other novel quantifications include (i) a finding that the biological vs ideal values of neural computational efficiency differ by a factor of $10^8$ and (ii) two predictions of $N$, the number of synaptic transmissions needed to fire a neuron (2500 vs 2000).
△ Less
Submitted 11 February, 2021;
originally announced February 2021.
-
Dynamic Ordering Learning in Multivariate Forecasting
Authors:
Bruno P. C. Levy,
Hedibert F. Lopes
Abstract:
In many fields where the main goal is to produce sequential forecasts for decision making problems, the good understanding of the contemporaneous relations among different series is crucial for the estimation of the covariance matrix. In recent years, the modified Cholesky decomposition appeared as a popular approach to covariance matrix estimation. However, its main drawback relies on the imposit…
▽ More
In many fields where the main goal is to produce sequential forecasts for decision making problems, the good understanding of the contemporaneous relations among different series is crucial for the estimation of the covariance matrix. In recent years, the modified Cholesky decomposition appeared as a popular approach to covariance matrix estimation. However, its main drawback relies on the imposition of the series ordering structure. In this work, we propose a highly flexible and fast method to deal with the problem of ordering uncertainty in a dynamic fashion with the use of Dynamic Order Probabilities. We apply the proposed method in two different forecasting contexts. The first is a dynamic portfolio allocation problem, where the investor is able to learn the contemporaneous relationships among different currencies improving final decisions and economic performance. The second is a macroeconomic application, where the econometrician can adapt sequentially to new economic environments, switching the contemporaneous relations among macroeconomic variables over time.
△ Less
Submitted 5 November, 2021; v1 submitted 11 January, 2021;
originally announced January 2021.
-
Broad Infinity and Generation Principles (Part 1: classical set theory)
Authors:
Paul Blain Levy
Abstract:
We introduce Broad Infinity, a new set-theoretic axiom scheme that may be considered plausible. It states that three-dimensional trees whose growth is controlled by a specified class function form a set; these trees are called "broad numbers".
Assuming the axiom of choice, or at least the weaker principle known as WISC, Broad Infinity is equivalent to Mahlo's principle: the class of all regular…
▽ More
We introduce Broad Infinity, a new set-theoretic axiom scheme that may be considered plausible. It states that three-dimensional trees whose growth is controlled by a specified class function form a set; these trees are called "broad numbers".
Assuming the axiom of choice, or at least the weaker principle known as WISC, Broad Infinity is equivalent to Mahlo's principle: the class of all regular limits is stationary. It also leads to a convenient principle for generating a subset of a class using a "rubric" (family of rules). This directly gives the existence of Grothendieck universes, without requiring a detour via ordinals.
In the absence of choice, Broad Infinity implies that the derivations of elements from a rubric form a set. This yields the existence of Tarski-style universes.
Additionally, the paper reveals a pattern of resemblance between "Broad" principles, that go beyond ZFC, and "Wide" principles , that are provable in ZFC.
△ Less
Submitted 2 August, 2023; v1 submitted 5 January, 2021;
originally announced January 2021.
-
A fast semi-discrete optimal transport algorithm for a unique reconstruction of the early Universe
Authors:
Bruno Lévy,
Roya Mohayaee,
Sebastian von Hausegger
Abstract:
We leverage powerful mathematical tools stemming from optimal transport theory and transform them into an efficient algorithm to reconstruct the fluctuations of the primordial density field, built on solving the Monge-Ampère-Kantorovich equation. Our algorithm computes the optimal transport between an initial uniform continuous density field, partitioned into Laguerre cells, and a final input set…
▽ More
We leverage powerful mathematical tools stemming from optimal transport theory and transform them into an efficient algorithm to reconstruct the fluctuations of the primordial density field, built on solving the Monge-Ampère-Kantorovich equation. Our algorithm computes the optimal transport between an initial uniform continuous density field, partitioned into Laguerre cells, and a final input set of discrete point masses, linking the early to the late Universe. While existing early universe reconstruction algorithms based on fully discrete combinatorial methods are limited to a few hundred thousand points, our algorithm scales up well beyond this limit, since it takes the form of a well-posed smooth convex optimization problem, solved using a Newton method. We run our algorithm on cosmological $N$-body simulations, from the AbacusCosmos suite, and reconstruct the initial positions of $\mathcal{O}(10^7)$ particles within a few hours with an off-the-shelf personal computer. We show that our method allows a unique, fast and precise recovery of subtle features of the initial power spectrum, such as the baryonic acoustic oscillations.
△ Less
Submitted 16 December, 2020;
originally announced December 2020.
-
A Theory of Particular Sets
Authors:
Paul Blain Levy
Abstract:
ZFC has sentences that quantify over all sets or all ordinals, without restriction. Some have argued that sentences of this kind lack a determinate meaning. We propose a set theory called TOPS, using Natural Deduction, that avoids this problem by speaking only about particular sets.
ZFC has sentences that quantify over all sets or all ordinals, without restriction. Some have argued that sentences of this kind lack a determinate meaning. We propose a set theory called TOPS, using Natural Deduction, that avoids this problem by speaking only about particular sets.
△ Less
Submitted 13 June, 2019; v1 submitted 7 May, 2019;
originally announced May 2019.
-
Simulating fluids with a computer: Introduction and recent advances
Authors:
Bruno Levy
Abstract:
In this article, I present recent methods for the numerical simulation of fluid dynamics and the associated computational algorithms. The goal of this article is to explain how to model an incompressible fluid, and how to write a computer program that simulates it. I will start from Newton laws "$F = ma$" applied to a bunch of particles, then show how Euler's equation can be deduced from them by "…
▽ More
In this article, I present recent methods for the numerical simulation of fluid dynamics and the associated computational algorithms. The goal of this article is to explain how to model an incompressible fluid, and how to write a computer program that simulates it. I will start from Newton laws "$F = ma$" applied to a bunch of particles, then show how Euler's equation can be deduced from them by "taking a step backward" and seeing the fluid as a continuum. Then I will show how to make a computer program. Incompressibility is one of the main difficulties to write a computer program that simulates a fluid. I will explain how recent advances in computational mathematics result in a computer object that can be used to represent a fluid and that naturally satisfies the incompressibility constraint. Equipped with this representation, the algorithm that simulates the fluid becomes extremely simple, and has been proved to converge to the solution of the equation (by Gallouet and Merigot).
△ Less
Submitted 13 November, 2018;
originally announced November 2018.
-
Robust Kalman Filtering: Asymptotic Analysis of the Least Favorable Model
Authors:
Mattia Zorzi,
Bernard C. Levy
Abstract:
We consider a robust filtering problem where the robust filter is designed according to the least favorable model belonging to a ball about the nominal model. In this approach, the ball radius specifies the modeling error tolerance and the least favorable model is computed by performing a Riccati-like backward recursion. We show that this recursion converges provided that the tolerance is sufficie…
▽ More
We consider a robust filtering problem where the robust filter is designed according to the least favorable model belonging to a ball about the nominal model. In this approach, the ball radius specifies the modeling error tolerance and the least favorable model is computed by performing a Riccati-like backward recursion. We show that this recursion converges provided that the tolerance is sufficiently small.
△ Less
Submitted 17 April, 2018;
originally announced April 2018.
-
Formulating Categorical Concepts using Classes
Authors:
Paul Blain Levy
Abstract:
We examine the use of classes to formulate several categorical notions. This leads to two proposals: an explicit structure for working with subobjects, and a hierarchy of $k$-classes. We apply the latter to both ordinary and higher categories.
We examine the use of classes to formulate several categorical notions. This leads to two proposals: an explicit structure for working with subobjects, and a hierarchy of $k$-classes. We apply the latter to both ordinary and higher categories.
△ Less
Submitted 26 July, 2018; v1 submitted 25 January, 2018;
originally announced January 2018.
-
Notions of optimal transport theory and how to implement them on a computer
Authors:
Bruno Levy,
Erica Schwindt
Abstract:
This article gives an introduction to optimal transport, a mathematical theory that makes it possible to measure distances between functions (or distances between more general objects), to interpolate between objects or to enforce mass/volume conservation in certain computational physics simulations. Optimal transport is a rich scientific domain, with active research communities, both on its theor…
▽ More
This article gives an introduction to optimal transport, a mathematical theory that makes it possible to measure distances between functions (or distances between more general objects), to interpolate between objects or to enforce mass/volume conservation in certain computational physics simulations. Optimal transport is a rich scientific domain, with active research communities, both on its theoretical aspects and on more applicative considerations, such as geometry processing and machine learning. This article aims at explaining the main principles behind the theory of optimal transport, introduce the different involved notions, and more importantly, how they relate, to let the reader grasp an intuition of the elegant theory that structures them. Then we will consider a specific setting, called semi-discrete, where a continuous function is transported to a discrete sum of Dirac masses. Studying this specific setting naturally leads to an efficient computational algorithm, that uses classical notions of computational geometry, such as a generalization of Voronoi diagrams called Laguerre diagrams.
△ Less
Submitted 7 October, 2017;
originally announced October 2017.
-
Effectful Applicative Bisimilarity: Monads, Relators, and Howe's Method (Long Version)
Authors:
Ugo Dal Lago,
Francesco Gavazzo,
Paul Blain Levy
Abstract:
We study Abramsky's applicative bisimilarity abstractly, in the context of call-by-value $λ$-calculi with algebraic effects. We first of all endow a computational $λ$-calculus with a monadic operational semantics. We then show how the theory of relators provides precisely what is needed to generalise applicative bisimilarity to such a calculus, and to single out those monads and relators for which…
▽ More
We study Abramsky's applicative bisimilarity abstractly, in the context of call-by-value $λ$-calculi with algebraic effects. We first of all endow a computational $λ$-calculus with a monadic operational semantics. We then show how the theory of relators provides precisely what is needed to generalise applicative bisimilarity to such a calculus, and to single out those monads and relators for which applicative bisimilarity is a congruence, thus a sound methodology for program equivalence. This is done by studying Howe's method in the abstract.
△ Less
Submitted 15 April, 2017;
originally announced April 2017.
-
A monad for full ground reference cells
Authors:
Ohad Kammar,
Paul B. Levy,
Sean K. Moss,
Sam Staton
Abstract:
We present a denotational account of dynamic allocation of potentially cyclic memory cells using a monad on a functor category. We identify the collection of heaps as an object in a different functor category equipped with a monad for adding hiding/encapsulation capabilities to the heaps. We derive a monad for full ground references supporting effect masking by applying a state monad transformer t…
▽ More
We present a denotational account of dynamic allocation of potentially cyclic memory cells using a monad on a functor category. We identify the collection of heaps as an object in a different functor category equipped with a monad for adding hiding/encapsulation capabilities to the heaps. We derive a monad for full ground references supporting effect masking by applying a state monad transformer to the encapsulation monad. To evaluate the monad, we present a denotational semantics for a call-by-value calculus with full ground references, and validate associated code transformations.
△ Less
Submitted 19 April, 2017; v1 submitted 16 February, 2017;
originally announced February 2017.
-
A Ghost at $ω_1$
Authors:
Paul Blain Levy
Abstract:
In the final chain of the countable powerset functor, we show that the set at index $ω_1$, regarded as a transition system, is not strongly extensional because it contains a "ghost" element that has no successor even though its component at each successor index is inhabited. The method, adapted from a construction of Forti and Honsell, also gives ghosts at larger ordinals in the final chain of oth…
▽ More
In the final chain of the countable powerset functor, we show that the set at index $ω_1$, regarded as a transition system, is not strongly extensional because it contains a "ghost" element that has no successor even though its component at each successor index is inhabited. The method, adapted from a construction of Forti and Honsell, also gives ghosts at larger ordinals in the final chain of other subfunctors of the powerset functor. This leads to a precise description of which sets in these final chains are strongly extensional.
△ Less
Submitted 25 July, 2018; v1 submitted 30 December, 2016;
originally announced December 2016.
-
Complexity Leads to Simplicity: A Consensus Layer V Pyramidal Neuron Can Sustain Interpulse-Interval Coding
Authors:
Chandan Singh,
William B. Levy
Abstract:
In terms of the long-distance communication of a single neuron, interpulse intervals (IPIs) are a possible alternative to rate and binary codes. As a proxy for IPI, the time-to-spike (TTS) for a neuron can be found in the biophysical and experimental literature. Using the current, consensus layer V pyramidal neuron, the present study examines the feasibility of IPI-coding and examines the noise so…
▽ More
In terms of the long-distance communication of a single neuron, interpulse intervals (IPIs) are a possible alternative to rate and binary codes. As a proxy for IPI, the time-to-spike (TTS) for a neuron can be found in the biophysical and experimental literature. Using the current, consensus layer V pyramidal neuron, the present study examines the feasibility of IPI-coding and examines the noise sources that limit the information rate of such an encoding. In descending order of noise intensity, the noise sources are (i) synaptic variability, (ii) sodium channel shot-noise, followed by (iii) thermal noise with synaptic noise much greater than the sodium channel-noise. More importantly, the biophysical model demonstrates a linear relationship between input intensity and inverse TTS. This linear observation contradicts the assumption that a neuron should be treated as a passive, electronic circuit (an RC circuit, as in the Stein model). Finally, the biophysical simulations allow the calculation of mutual information, which is about 3.0 bits/spike.
△ Less
Submitted 26 September, 2016;
originally announced September 2016.
-
Neural computation from first principles: Using the maximum entropy method to obtain an optimal bits-per-joule neuron
Authors:
William B Levy,
Toby Berger,
Mustafa Sungkar
Abstract:
Optimization results are one method for understanding neural computation from Nature's perspective and for defining the physical limits on neuron-like engineering. Earlier work looks at individual properties or performance criteria and occasionally a combination of two, such as energy and information. Here we make use of Jaynes' maximum entropy method and combine a larger set of constraints, possi…
▽ More
Optimization results are one method for understanding neural computation from Nature's perspective and for defining the physical limits on neuron-like engineering. Earlier work looks at individual properties or performance criteria and occasionally a combination of two, such as energy and information. Here we make use of Jaynes' maximum entropy method and combine a larger set of constraints, possibly dimensionally distinct, each expressible as an expectation. The method identifies a likelihood-function and a sufficient statistic arising from each such optimization. This likelihood is a first-hitting time distribution in the exponential class. Particular constraint sets are identified that, from an optimal inference perspective, justify earlier neurocomputational models. Interactions between constraints, mediated through the inferred likelihood, restrict constraint-set parameterizations, e.g., the energy-budget limits estimation performance which, in turn, matches an axonal communication constraint. Such linkages are, for biologists, experimental predictions of the method. In addition to the related likelihood, at least one type of constraint set implies marginal distributions, and in this case, a Shannon bits/joule statement arises.
△ Less
Submitted 19 December, 2017; v1 submitted 6 June, 2016;
originally announced June 2016.
-
Low-order continuous finite element spaces on hybrid non-conforming hexahedral-tetrahedral meshes
Authors:
Maxence Reberol,
Bruno Lévy
Abstract:
This article deals with solving partial differential equations with the finite element method on hybrid non-conforming hexahedral-tetrahedral meshes. By non-conforming, we mean that a quadrangular face of a hexahedron can be connected to two triangular faces of tetrahedra. We introduce a set of low-order continuous (C0) finite element spaces defined on these meshes. They are built from standard…
▽ More
This article deals with solving partial differential equations with the finite element method on hybrid non-conforming hexahedral-tetrahedral meshes. By non-conforming, we mean that a quadrangular face of a hexahedron can be connected to two triangular faces of tetrahedra. We introduce a set of low-order continuous (C0) finite element spaces defined on these meshes. They are built from standard tri-linear and quadratic Lagrange finite elements with an extra set of constraints at non-conforming hexahedra-tetrahedra junctions to recover continuity. We consider both the continuity of the geometry and the continuity of the function basis as follows: the continuity of the geometry is achieved by using quadratic mappings for tetrahedra connected to tri-affine hexahedra and the continuity of interpolating functions is enforced in a similar manner by using quadratic Lagrange basis on tetrahedra with constraints at non-conforming junctions to match tri-linear hexahedra. The so-defined function spaces are validated numerically on simple Poisson and linear elasticity problems for which an analytical solution is known. We observe that using a hybrid mesh with the proposed function spaces results in an accuracy significantly better than when using linear tetrahedra and slightly worse than when solely using tri-linear hexahedra. As a consequence, the proposed function spaces may be a promising alternative for complex geometries that are out of reach of existing full hexahedral meshing methods.
△ Less
Submitted 9 May, 2016;
originally announced May 2016.
-
A Proof of the Thue-Siegel Theorem about the Approximation of Algebraic Numbers for Binomial Equations
Authors:
Kurt Mahler,
translated from the German by Karl Levy
Abstract:
In 1908 Thue (1) showed that algebraic numbers of the special form $ξ=\sqrt[n]{\frac{a}{b}}$ can, for every positive $ε$, only be sharply approximated by finitely many rational numbers $\frac{p}{q}$ with the following inequality holding \[ \left|ξ-\frac{p}{q}\right|\leq q^{-(\frac{n}{2}+1+ε)} .\] The proof uses, if perhaps in a somewhat hidden way, the continued fraction expansion of the binomial…
▽ More
In 1908 Thue (1) showed that algebraic numbers of the special form $ξ=\sqrt[n]{\frac{a}{b}}$ can, for every positive $ε$, only be sharply approximated by finitely many rational numbers $\frac{p}{q}$ with the following inequality holding \[ \left|ξ-\frac{p}{q}\right|\leq q^{-(\frac{n}{2}+1+ε)} .\] The proof uses, if perhaps in a somewhat hidden way, the continued fraction expansion of the binomial series $(1-z)^ω$. In further work about the approximation of algebraic numbers (2,3) famously Thue used instead a completely different tool, the drawer method of Dirichlet, and showed further that the above statement holds for any algebraic number. Thue's methods were later generalized by Siegel(4,5,6,7) who showed, among other things, that for every algebraic number in the above inequality the exponent $\frac{n}{2}+1+ε$ could be replaced by $\frac{n}{m}+m-1+ε$, where $m$ is some natural number.
This note demonstrates a generalization of Thue's methods in (1); Like Thue I restrict myself to the roots $ξ=\sqrt[n]{\frac{a}{b}}$ of the binomial equations. The continued fraction expansion of the binomial series is generalized and algebraic approximation functions are given instead of rational approximation functions. In doing so I proceed exactly as in my work on the exponential function(8). Integrals are set up for the approximation functions; thus the estimates become much easier and you can prove Thue's theorem with Siegel's Exponents for the binomial algebraic equations without difficulty and without use of the pigeonhole principle.
△ Less
Submitted 11 June, 2015;
originally announced July 2015.
-
On the convergence of a Risk Sensitive like Filter
Authors:
Mattia Zorzi,
Bernard C. Levy
Abstract:
In this paper, we analyze the convergence of a risk sensitive like filter where the risk sensitivity parameter is time varying. Such filter has a Kalman like structure and its gain matrix is updated according to a Riccati like iteration. We show that the iteration converges to a fixed point by using the contraction analysis.
In this paper, we analyze the convergence of a risk sensitive like filter where the risk sensitivity parameter is time varying. Such filter has a Kalman like structure and its gain matrix is updated according to a Riccati like iteration. We show that the iteration converges to a fixed point by using the contraction analysis.
△ Less
Submitted 26 September, 2015; v1 submitted 25 March, 2015;
originally announced March 2015.
-
Coproducts of Monads on Set
Authors:
Jiří Adámek,
Nathan Bowler,
Paul B. Levy,
Stefan Milius
Abstract:
Coproducts of monads on Set have arisen in both the study of computational effects and universal algebra.
We describe coproducts of consistent monads on Set by an initial algebra formula, and prove also the converse: if the coproduct exists, so do the required initial algebras. That formula was, in the case of ideal monads, also used by Ghani and Uustalu. We deduce that coproduct embeddings of c…
▽ More
Coproducts of monads on Set have arisen in both the study of computational effects and universal algebra.
We describe coproducts of consistent monads on Set by an initial algebra formula, and prove also the converse: if the coproduct exists, so do the required initial algebras. That formula was, in the case of ideal monads, also used by Ghani and Uustalu. We deduce that coproduct embeddings of consistent monads are injective; and that a coproduct of injective monad morphisms is injective.
Two consistent monads have a coproduct iff either they have arbitrarily large common fixpoints, or one is an exception monad, possibly modified to preserve the empty set. Hence a consistent monad has a coproduct with every monad iff it is an exception monad, possibly modified to preserve the empty set. We also show other fixpoint results, including that a functor (not constant on nonempty sets) is finitary iff every sufficiently large cardinal is a fixpoint.
△ Less
Submitted 11 September, 2014;
originally announced September 2014.
-
A numerical algorithm for $L_2$ semi-discrete optimal transport in 3D
Authors:
Bruno Levy
Abstract:
This paper introduces a numerical algorithm to compute the $L_2$ optimal transport map between two measures $μ$ and $ν$, where $μ$ derives from a density $ρ$ defined as a piecewise linear function (supported by a tetrahedral mesh), and where $ν$ is a sum of Dirac masses.
I first give an elementary presentation of some known results on optimal transport and then observe a relation with another pr…
▽ More
This paper introduces a numerical algorithm to compute the $L_2$ optimal transport map between two measures $μ$ and $ν$, where $μ$ derives from a density $ρ$ defined as a piecewise linear function (supported by a tetrahedral mesh), and where $ν$ is a sum of Dirac masses.
I first give an elementary presentation of some known results on optimal transport and then observe a relation with another problem (optimal sampling). This relation gives simple arguments to study the objective functions that characterize both problems.
I then propose a practical algorithm to compute the optimal transport map between a piecewise linear density and a sum of Dirac masses in 3D. In this semi-discrete setting, Aurenhammer et.al [\emph{8th Symposium on Computational Geometry conf. proc.}, ACM (1992)] showed that the optimal transport map is determined by the weights of a power diagram. The optimal weights are computed by minimizing a convex objective function with a quasi-Newton method. To evaluate the value and gradient of this objective function, I propose an efficient and robust algorithm, that computes at each iteration the intersection between a power diagram and the tetrahedral mesh that defines the measure $μ$.
The numerical algorithm is experimented and evaluated on several datasets, with up to hundred thousands tetrahedra and one million Dirac masses.
△ Less
Submitted 3 September, 2014;
originally announced September 2014.
-
Neural computation at the thermal limit
Authors:
William B. Levy,
Toby Berger,
Ilya A. Fleidervish
Abstract:
Although several measurements and analyses support the idea that the brain is energy-optimized, there is one disturbing, contradictory observation: In theory, computation limited by thermal noise can occur as cheaply as ~$2.9\cdot 10^{-21}$ joules per bit (kTln2). Unfortunately, for a neuron the ostensible discrepancy from this minimum is startling - ignoring inhibition the discrepancy is $10^7$ t…
▽ More
Although several measurements and analyses support the idea that the brain is energy-optimized, there is one disturbing, contradictory observation: In theory, computation limited by thermal noise can occur as cheaply as ~$2.9\cdot 10^{-21}$ joules per bit (kTln2). Unfortunately, for a neuron the ostensible discrepancy from this minimum is startling - ignoring inhibition the discrepancy is $10^7$ times this amount and taking inhibition into account $>10^9$. Here we point out that what has been defined as neural computation is actually a combination of computation and neural communication: the communication costs, transmission from each excitatory postsynaptic activation to the S4-gating-charges of the fast Na+ channels of the initial segment (fNa's), dominate the joule-costs. Making this distinction between communication to the initial segment and computation at the initial segment (i.e., adding up of the activated fNa's) implies that the size of the average synaptic event reaching the fNa's is the size of the standard deviation of the thermal noise. Moreover, defining computation as the addition of activated fNa's, yields a biophysically plausible mechanism for approaching the desired minimum. This mechanism, requiring something like the electrical engineer's equalizer (not much more than the action potential generating conductances), only operates at threshold. This active filter modifies the last few synaptic excitations, providing barely enough energy to allow the last sub-threshold gating charge to transport. That is, the last, threshold-achieving S4-subunit activation requires an energy that matches the information being provided by the last few synaptic events, a ratio that is near kTln2 joules per bit.
△ Less
Submitted 20 November, 2014; v1 submitted 28 August, 2014;
originally announced August 2014.
-
Exploring the Boundaries of Monad Tensorability on Set
Authors:
Nathan Bowler,
Sergey Goncharov,
Paul Blain Levy,
Lutz Schröder
Abstract:
We study a composition operation on monads, equivalently presented as large equational theories. Specifically, we discuss the existence of tensors, which are combinations of theories that impose mutual commutation of the operations from the component theories. As such, they extend the sum of two theories, which is just their unrestrained combination. Tensors of theories arise in several contexts;…
▽ More
We study a composition operation on monads, equivalently presented as large equational theories. Specifically, we discuss the existence of tensors, which are combinations of theories that impose mutual commutation of the operations from the component theories. As such, they extend the sum of two theories, which is just their unrestrained combination. Tensors of theories arise in several contexts; in particular, in the semantics of programming languages, the monad transformer for global state is given by a tensor. We present two main results: we show that the tensor of two monads need not in general exist by presenting two counterexamples, one of them involving finite powerset (i.e. the theory of join semilattices); this solves a somewhat long-standing open problem, and contrasts with recent results that had ruled out previously expected counterexamples. On the other hand, we show that tensors with bounded powerset monads do exist from countable powerset upwards.
△ Less
Submitted 17 September, 2013; v1 submitted 9 September, 2013;
originally announced September 2013.
-
A Contraction Analysis of the Convergence of Risk-Sensitive Filters
Authors:
Bernard C. Levy,
Mattia Zorzi
Abstract:
A contraction analysis of risk-sensitive Riccati equations is proposed. When the state-space model is reachable and observable, a block-update implementation of the risk-sensitive filter is used to show that the N-fold composition of the Riccati map is strictly contractive with respect to the Riemannian metric of positive definite matrices, when N is larger than the number of states. The range of…
▽ More
A contraction analysis of risk-sensitive Riccati equations is proposed. When the state-space model is reachable and observable, a block-update implementation of the risk-sensitive filter is used to show that the N-fold composition of the Riccati map is strictly contractive with respect to the Riemannian metric of positive definite matrices, when N is larger than the number of states. The range of values of the risk-sensitivity parameter for which the map remains contractive can be estimated a priori. It is also found that a second condition must be imposed on the risk-sensitivity parameter and on the initial error variance to ensure that the solution of the risk-sensitive Riccati equation remains positive definite at all times. The two conditions obtained can be viewed as extending to the multivariable case an earlier analysis of Whittle for the scalar case.
△ Less
Submitted 6 May, 2013;
originally announced May 2013.
-
Proceedings Fourth Workshop on Mathematically Structured Functional Programming
Authors:
James Chapman,
Paul Blain Levy
Abstract:
This volume contains the proceedings of the Fourth Workshop on Mathematically Structured Functional Programming (MSFP 2012), taking place on 25 March, 2012 in Tallinn, Estonia, as a satellite event of the European Joint Conferences on Theory and Practice of Software, ETAPS 2012.
MSFP is devoted to the derivation of functionality from structure. It highlights concepts from algebra, semantic…
▽ More
This volume contains the proceedings of the Fourth Workshop on Mathematically Structured Functional Programming (MSFP 2012), taking place on 25 March, 2012 in Tallinn, Estonia, as a satellite event of the European Joint Conferences on Theory and Practice of Software, ETAPS 2012.
MSFP is devoted to the derivation of functionality from structure. It highlights concepts from algebra, semantics and type theory as they are increasingly reflected in programming practice, especially functional programming. The workshop consists of two invited presentations and eight contributed papers on a range of topics at that interface.
△ Less
Submitted 10 February, 2012;
originally announced February 2012.
-
Robust State Space Filtering under Incremental Model Perturbations Subject to a Relative Entropy Tolerance
Authors:
Bernard C. Levy,
Ramine Nikoukhah
Abstract:
This paper considers robust filtering for a nominal Gaussian state-space model, when a relative entropy tolerance is applied to each time increment of a dynamical model. The problem is formulated as a dynamic minimax game where the maximizer adopts a myopic strategy. This game is shown to admit a saddle point whose structure is characterized by applying and extending results presented earlier in […
▽ More
This paper considers robust filtering for a nominal Gaussian state-space model, when a relative entropy tolerance is applied to each time increment of a dynamical model. The problem is formulated as a dynamic minimax game where the maximizer adopts a myopic strategy. This game is shown to admit a saddle point whose structure is characterized by applying and extending results presented earlier in [1] for static least-squares estimation. The resulting minimax filter takes the form of a risk-sensitive filter with a time varying risk sensitivity parameter, which depends on the tolerance bound applied to the model dynamics and observations at the corresponding time index. The least-favorable model is constructed and used to evaluate the performance of alternative filters. Simulations comparing the proposed risk-sensitive filter to a standard Kalman filter show a significant performance advantage when applied to the least-favorable model, and only a small performance loss for the nominal model.
△ Less
Submitted 22 September, 2011; v1 submitted 14 April, 2010;
originally announced April 2010.
-
Robust Hypothesis Testing with a Relative Entropy Tolerance
Authors:
Bernard C. Levy
Abstract:
This paper considers the design of a minimax test for two hypotheses where the actual probability densities of the observations are located in neighborhoods obtained by placing a bound on the relative entropy between actual and nominal densities. The minimax problem admits a saddle point which is characterized. The robust test applies a nonlinear transformation which flattens the nominal likelih…
▽ More
This paper considers the design of a minimax test for two hypotheses where the actual probability densities of the observations are located in neighborhoods obtained by placing a bound on the relative entropy between actual and nominal densities. The minimax problem admits a saddle point which is characterized. The robust test applies a nonlinear transformation which flattens the nominal likelihood ratio in the vicinity of one. Results are illustrated by considering the transmission of binary data in the presence of additive noise.
△ Less
Submitted 1 April, 2008; v1 submitted 19 July, 2007;
originally announced July 2007.
