This paper describes the development of finite abstractions of Max-Plus-Linear (MPL) systems using tropical operations. The idea of tropical abstraction is inspired by the fact that an MPL system is a discrete-event model updating its state with operations in the tropical algebra. The abstract model is a finite-state transition system: we show that the abstract states can be generated by operations on the tropical algebra, and that the generation of transitions can be established by tropical multiplications of matrices. The complexity of the algorithms based on tropical algebra is discussed and their performance is tested on a numerical benchmark against an existing alternative abstraction approach.
The computation of image and of inverse image of a DBM is described in @cite_7 . These computations are used to perform forward and backward reachability analysis, respectively. The worst-case complexity of both procedures is @math , where @math is the number of variables in @math excluding @math . A more detailed explanation about image and inverse image computation of a DBM is in Section 3.3.
@cite_7
105974170
In this paper, we propose a novel deep convolutional neural network (CNN)-based algorithm for solving ill-posed inverse problems. Regularized iterative algorithms have emerged as the standard approach to ill-posed inverse problems in the past few decades. These methods produce excellent results, but can be challenging to deploy in practice due to factors including the high computational cost of the forward and adjoint operators and the difficulty of hyperparameter selection. The starting point of this paper is the observation that unrolled iterative methods have the form of a CNN (filtering followed by pointwise non-linearity) when the normal operator ( @math , where @math is the adjoint of the forward imaging operator, @math ) of the forward model is a convolution. Based on this observation, we propose using direct inversion followed by a CNN to solve normal-convolutional inverse problems. The direct inversion encapsulates the physical model of the system, but leads to artifacts when the problem is ill posed; the CNN combines multiresolution decomposition and residual learning in order to learn to remove these artifacts while preserving image structure. We demonstrate the performance of the proposed network in sparse-view reconstruction (down to 50 views) on parallel beam X-ray computed tomography in synthetic phantoms as well as in real experimental sinograms. The proposed network outperforms total variation-regularized iterative reconstruction for the more realistic phantoms and requires less than a second to reconstruct a @math image on the GPU. In cryo-electron microscopy, the three-dimensional (3D) electric potentials of an ensemble of molecules are projected along arbitrary viewing directions to yield noisy two-dimensional images. The volume maps representing these potentials typically exhibit a great deal of structural variability, which is described by their 3D covariance matrix. Typically, this covariance matrix is approximately low rank and can be used to cluster the volumes or estimate the intrinsic geometry of the conformation space. We formulate the estimation of this covariance matrix as a linear inverse problem, yielding a consistent least-squares estimator. For @math images of size @math -by- @math pixels, we propose an algorithm for calculating this covariance estimator with computational complexity @math , where the condition number @math is empirically in the range 10--200. Its efficiency relies on the observation that the normal equations are equivalent to a deconvolution problem in six dimensions.... Two central limit theorems for sample Fr 'echet means are derived, both significant for nonparametric inference on non-Euclidean spaces. The first one, Theorem 2.2, encompasses and improves upon most earlier CLTs on Fr 'echet means and broadens the scope of the methodology beyond manifolds to diverse new non-Euclidean data including those on certain stratified spaces which are important in the study of phylogenetic trees. It does not require that the underlying distribution @math have a density, and applies to both intrinsic and extrinsic analysis. The second theorem, Theorem 3.3, focuses on intrinsic means on Riemannian manifolds of dimensions @math and breaks new ground by providing a broad CLT without any of the earlier restrictive support assumptions. It makes the statistically reasonable assumption of a somewhat smooth density of @math . The excluded case of dimension @math proves to be an enigma, although the first theorem does provide a CLT in this case as well under a support restriction. Theorem 3.3 immediately applies to spheres @math , @math , which are also of considerable importance in applications to axial spaces and to landmarks based image analysis, as these spaces are quotients of spheres under a Lie group @math of isometries of @math . A new bound (Theorem ) for the duration of the chip-firing game with @math chips on a @math -vertex graph is obtained, by a careful analysis of the pseudo-inverse of the discrete Laplacian matrix of the graph. This new bound is expressed in terms of the entries of the pseudo-inverse. It is shown (Section 5) to be always better than the classic bound due to Bj "o rner, Lov ' a sz and Shor. In some cases the improvement is dramatic. For instance: for strongly regular graphs the classic and the new bounds reduce to @math and @math , respectively. For dense regular graphs - @math - the classic and the new bounds reduce to @math and @math , respectively. This is a snapshot of a work in progress, so further results in this vein are in the works.