OpenRaiser/Intern-Atlas huggingface dataset:
CSVideoNet: A Real-time End-to-end Learning Framework for High-frame-rate Video Compressive Sensing
Venue: arXiv cs.CV 2018
Year: 2018

This paper addresses the real-time encoding-decoding problem for high-frame-rate video compressive sensing (CS). Unlike prior works that perform reconstruction using iterative optimization-based approaches, we propose a non-iterative model, named "CSVideoNet". CSVideoNet directly learns the inverse mapping of CS and reconstructs the original input in a single forward propagation. To overcome the limitations of existing CS cameras, we propose a multi-rate CNN and a synthesizing RNN to improve the trade-off between compression ratio (CR) and spatial-temporal resolution of the reconstructed videos. The experiment results demonstrate that CSVideoNet significantly outperforms the state-of-the-art approaches. With no pre/post-processing, we achieve 25dB PSNR recovery quality at 100x CR, with a frame rate of 125 fps on a Titan X GPU. Due to the feedforward and high-data-concurrency natures of CSVideoNet, it can take advantage of GPU acceleration to achieve three orders of magnitude speed-up over conventional iterative-based approaches. We share the source code at https://github.com/PSCLab-ASU/CSVideoNet.
All the λ-Terms are Meaningful for the Infinitary Relational Model
Venue: arXiv cs.PL 2018
Year: 2018

Infinite types and formulas are known to have really curious and unsound behaviors. For instance, they allow to type Ω, the auto- autoapplication and they thus do not ensure any form of normalization/productivity. Moreover, in most infinitary frameworks, it is not difficult to define a type R that can be assigned to every λ-term. However, these observations do not say much about what coinductive (i.e. infinitary) type grammars are able to provide: it is for instance very difficult to know what types (besides R) can be assigned to a given term in this setting. We begin with a discussion on the expressivity of different forms of infinite types. Then, using the resource-awareness of sequential intersection types (system S) and tracking, we prove that infinite types are able to characterize the order (arity) of every λ-terms and that, in the infinitary extension of the relational model, every term has a "meaning" i.e. a non-empty denotation. From the technical point of view, we must deal with the total lack of productivity guarantee for typable terms: we do so by importing methods inspired by first order model theory.
Two-weight and three-weight linear codes based on Weil sums
Venue: arXiv cs.IT 2018
Year: 2018

Linear codes with few weights have applications in secret sharing, authentication codes, association schemes and strongly regular graphs. In this paper, several classes of two-weight and three-weight linear codes are presented and their weight distributions are determined using Weil sums. Some of the linear codes obtained are optimal or almost optimal with respect to the Griesmer bound.
Extension by Conservation. Sikorski's Theorem
Venue: arXiv cs.LO 2018
Year: 2018

Constructive meaning is given to the assertion that every finite Boolean algebra is an injective object in the category of distributive lattices. To this end, we employ Scott's notion of entailment relation, in which context we describe Sikorski's extension theorem for finite Boolean algebras and turn it into a syntactical conservation result. As a by-product, we can facilitate proofs of several related classical principles.
Equations in oligomorphic clones and the Constraint Satisfaction Problem for $ω$-categorical structures
Venue: arXiv cs.LO 2018
Year: 2018

There exist two conjectures for constraint satisfaction problems (CSPs) of reducts of finitely bounded homogeneous structures: the first one states that tractability of the CSP of such a structure is, when the structure is a model-complete core, equivalent to its polymorphism clone satisfying a certain non-trivial linear identity modulo outer embeddings. The second conjecture, challenging the approach via model-complete cores by reflections, states that tractability is equivalent to the linear identities (without outer embeddings) satisfied by its polymorphisms clone, together with the natural uniformity on it, being non-trivial. We prove that the identities satisfied in the polymorphism clone of a structure allow for conclusions about the orbit growth of its automorphism group, and apply this to show that the two conjectures are equivalent. We contrast this with a counterexample showing that $ω$-categoricity alone is insufficient to imply the equivalence of the two conditions above in a model-complete core. Taking a different approach, we then show how the Ramsey property of a homogeneous structure can be utilized for obtaining a similar equivalence under different conditions. We then prove that any polymorphism of sufficiently large arity which is totally symmetric modulo outer embeddings of a finitely bounded structure can be turned into a non-trivial system of linear identities, and obtain non-trivial linear identities for all tractable cases of reducts of the rational order, the random graph, and the random poset. Finally, we provide a new and short proof, in the language of monoids, of the theorem stating that every $ω$-categorical structure is homomorphically equivalent to a model-complete core.
Accurate numerical simulation of moisture front in porous material
Venue: arXiv cs.CE 2018
Year: 2018

When comparing measurements to numerical simulations of moisture transfer through porous materials a rush of the experimental moisture front is commonly observed in several works shown in the literature, with transient models that consider only the diffusion process. Thus, to overcome the discrepancies between the experimental and the numerical models, this paper proposes to include the moisture advection transfer in the governing equation. To solve the advection-diffusion differential equation, it is first proposed two efficient numerical schemes and their efficiencies are investigated for both linear and nonlinear cases. The first scheme, Scharfetter-Gummel (SG), presents a Courant-Friedrichs-Lewy (CFL) condition but is more accurate and faster than the second scheme, the well-known Crank-Nicolson approach. Furthermore, the SG scheme has the advantages of being well-balanced and asymptotically preserved. Then, to conclude, results of the convective moisture transfer problem obtained with the SG numerical scheme are compared to experimental data from the literature. The inclusion of an advective term in the model may clearly lead to better results than purely diffusive models.
A discrete-time Pontryagin maximum principle on matrix Lie groups
Venue: arXiv cs.SY 2018
Year: 2018

In this article we derive a Pontryagin maximum principle (PMP) for discrete-time optimal control problems on matrix Lie groups. The PMP provides first order necessary conditions for optimality; these necessary conditions typically yield two point boundary value problems, and these boundary value problems can then solved to extract optimal control trajectories. Constrained optimal control problems for mechanical systems, in general, can only be solved numerically, and this motivates the need to derive discrete-time models that are accurate and preserve the non-flat manifold structures of the underlying continuous-time controlled systems. The PMPs for discrete-time systems evolving on Euclidean spaces are not readily applicable to discrete-time models evolving on non-flat manifolds. In this article we bridge this lacuna and establish a discrete-time PMP on matrix Lie groups. Our discrete-time models are derived via discrete mechanics, (a structure preserving discretization scheme,) leading to the preservation of the underlying manifold over time, thereby resulting in greater numerical accuracy of our technique. This PMP caters to a class of constrained optimal control problems that includes point-wise state and control action constraints, and encompasses a large class of control problems that arise in various field of engineering and the applied sciences.
Families of DFAs as Acceptors of $ω$-Regular Languages
Venue: arXiv cs.FL 2018
Year: 2018

Families of DFAs (FDFAs) provide an alternative formalism for recognizing $ω$-regular languages. The motivation for introducing them was a desired correlation between the automaton states and right congruence relations, in a manner similar to the Myhill-Nerode theorem for regular languages. This correlation is beneficial for learning algorithms, and indeed it was recently shown that $ω$-regular languages can be learned from membership and equivalence queries, using FDFAs as the acceptors. In this paper, we look into the question of how suitable FDFAs are for defining omega-regular languages. Specifically, we look into the complexity of performing Boolean operations, such as complementation and intersection, on FDFAs, the complexity of solving decision problems, such as emptiness and language containment, and the succinctness of FDFAs compared to standard deterministic and nondeterministic $ω$-automata. We show that FDFAs enjoy the benefits of deterministic automata with respect to Boolean operations and decision problems. Namely, they can all be performed in nondeterministic logarithmic space. We provide polynomial translations of deterministic Büchi and co-Büchi automata to FDFAs and of FDFAs to nondeterministic Büchi automata (NBAs). We show that translation of an NBA to an FDFA may involve an exponential blowup. Last, we show that FDFAs are more succinct than deterministic parity automata (DPAs) in the sense that translating a DPA to an FDFA can always be done with only a polynomial increase, yet the other direction involves an inevitable exponential blowup in the worst case.
Codes in the Space of Multisets---Coding for Permutation Channels with Impairments
Venue: arXiv cs.IT 2018
Year: 2018

Motivated by communication channels in which the transmitted sequences are subject to random permutations, as well as by certain DNA storage systems, we study the error control problem in settings where the information is stored/transmitted in the form of multisets of symbols from a given finite alphabet. A general channel model is assumed in which the transmitted multisets are potentially impaired by insertions, deletions, substitutions, and erasures of symbols. Several constructions of error-correcting codes for this channel are described, and bounds on the size of optimal codes correcting any given number of errors derived. The construction based on the notion of Sidon sets in finite Abelian groups is shown to be optimal, in the sense of the asymptotic scaling of code redundancy, for any "error radius" and any alphabet size. It is also shown to be optimal in the stronger sense of maximal code cardinality in various cases.
Computation of effective electrical conductivity of composite materials: a novel approach based on analysis of graphs
Venue: arXiv cs.CE 2018
Year: 2018

In this work we continue the investigation of different approaches to conception and modeling of composite materials. The global method we focus on, is called 'stochastic homogenization'. In this approach, the classical deterministic homogenization techniques and procedures are used to compute the macroscopic parameters of a composite starting from its microscopic properties. The stochastic part is due to averaging over some series of samples, and the fact that these samples fit into the concept of RVE (Representative Volume Element) in order to reduce the variance effect. In this article, we present a novel method for computation of effective electric properties of composites -- it is based on the analysis of the connectivity graph (and the respective adjacency matrix) for each sample of a composite material. We describe how this matrix is constructed in order to take into account complex microscopic geometry. We also explain what we mean by homogenization procedure for electrical conductivity, and how the constructed matrix is related to the problem. The developed method is applied to a test study of the influence of micromorphology of composites materials on their conductivity.
Super-Resolution Reconstruction of Electrical Impedance Tomography Images
Venue: arXiv cs.CV 2018
Year: 2018

Electrical Impedance Tomography (EIT) systems are becoming popular because they present several advantages over competing systems. However, EIT leads to images with very low resolution. Moreover, the nonuniform sampling characteristic of EIT precludes the straightforward application of traditional image ruper-resolution techniques. In this work, we propose a resampling based Super-Resolution method for EIT image quality improvement. Preliminary results show that the proposed technique can lead to substantial improvements in EIT image resolution, making it more competitive with other technologies.
Learning from Synthetic Humans
Venue: arXiv cs.CV 2018
Year: 2018

Estimating human pose, shape, and motion from images and videos are fundamental challenges with many applications. Recent advances in 2D human pose estimation use large amounts of manually-labeled training data for learning convolutional neural networks (CNNs). Such data is time consuming to acquire and difficult to extend. Moreover, manual labeling of 3D pose, depth and motion is impractical. In this work we present SURREAL (Synthetic hUmans foR REAL tasks): a new large-scale dataset with synthetically-generated but realistic images of people rendered from 3D sequences of human motion capture data. We generate more than 6 million frames together with ground truth pose, depth maps, and segmentation masks. We show that CNNs trained on our synthetic dataset allow for accurate human depth estimation and human part segmentation in real RGB images. Our results and the new dataset open up new possibilities for advancing person analysis using cheap and large-scale synthetic data.
A Lower Bound on the Probability of Error of Polar Codes over BMS Channels
Venue: arXiv cs.IT 2018
Year: 2018

Polar codes are a family of capacity-achieving codes that have explicit and low-complexity construction, encoding, and decoding algorithms. Decoding of polar codes is based on the successive-cancellation decoder, which decodes in a bit- wise manner. A decoding error occurs when at least one bit is erroneously decoded. The various codeword bits are correlated, yet performance analysis of polar codes ignores this dependence: the upper bound is based on the union bound, and the lower bound is based on the worst-performing bit. Improvement of the lower bound is afforded by considering error probabilities of two bits simultaneously. These are difficult to compute explicitly due to the large alphabet size inherent to polar codes. In this research we propose a method to lower-bound the error probabilities of bit pairs. We develop several transformations on pairs of synthetic channels that make the resultant synthetic channels amenable to alphabet reduction. Our method yields lower bounds that significantly improve upon currently known lower bounds for polar codes under successive-cancellation decoding.
Toward Quantum Combinatorial Games
Venue: arXiv cs.DM 2018
Year: 2018

In this paper, we propose a Quantum variation of combinatorial games, generalizing the Quantum Tic-Tac-Toe proposed by Allan Goff. A combinatorial game is a two-player game with no chance and no hidden information, such as Go or Chess. In this paper, we consider the possibility of playing superpositions of moves in such games. We propose different rulesets depending on when superposed moves should be played, and prove that all these rulesets may lead similar games to different outcomes. We then consider Quantum variations of the game of Nim. We conclude with some discussion on the relative interest of the different rulesets.
On the Tanner Graph Cycle Distribution of Random LDPC, Random Protograph-Based LDPC, and Random Quasi-Cyclic LDPC Code Ensembles
Venue: arXiv cs.IT 2018
Year: 2018

In this paper, we study the cycle distribution of random low-density parity-check (LDPC) codes, randomly constructed protograph-based LDPC codes, and random quasi-cyclic (QC) LDPC codes. We prove that for a random bipartite graph, with a given (irregular) degree distribution, the distributions of cycles of different length tend to independent Poisson distributions, as the size of the graph tends to infinity. We derive asymptotic upper and lower bounds on the expected values of the Poisson distributions that are independent of the size of the graph, and only depend on the degree distribution and the cycle length. For a random lift of a bi-regular protograph, we prove that the asymptotic cycle distributions are essentially the same as those of random bipartite graphs as long as the degree distributions are identical. For random QC-LDPC codes, however, we show that the cycle distribution can be quite different from the other two categories. In particular, depending on the protograph and the value of $c$, the expected number of cycles of length $c$, in this case, can be either $Θ(N)$ or $Θ(1)$, where $N$ is the lifting degree (code length). We also provide numerical results that match our theoretical derivations. Our results provide a theoretical foundation for emperical results that were reported in the literature but were not well-justified. They can also be used for the analysis and design of LDPC codes and associated algorithms that are based on cycles.
Reconstructing Subject-Specific Effect Maps
Venue: arXiv cs.CV 2018
Year: 2018

Predictive models allow subject-specific inference when analyzing disease related alterations in neuroimaging data. Given a subject's data, inference can be made at two levels: global, i.e. identifiying condition presence for the subject, and local, i.e. detecting condition effect on each individual measurement extracted from the subject's data. While global inference is widely used, local inference, which can be used to form subject-specific effect maps, is rarely used because existing models often yield noisy detections composed of dispersed isolated islands. In this article, we propose a reconstruction method, named RSM, to improve subject-specific detections of predictive modeling approaches and in particular, binary classifiers. RSM specifically aims to reduce noise due to sampling error associated with using a finite sample of examples to train classifiers. The proposed method is a wrapper-type algorithm that can be used with different binary classifiers in a diagnostic manner, i.e. without information on condition presence. Reconstruction is posed as a Maximum-A-Posteriori problem with a prior model whose parameters are estimated from training data in a classifier-specific fashion. Experimental evaluation is performed on synthetically generated data and data from the Alzheimer's Disease Neuroimaging Initiative (ADNI) database. Results on synthetic data demonstrate that using RSM yields higher detection accuracy compared to using models directly or with bootstrap averaging. Analyses on the ADNI dataset show that RSM can also improve correlation between subject-specific detections in cortical thickness data and non-imaging markers of Alzheimer's Disease (AD), such as the Mini Mental State Examination Score and Cerebrospinal Fluid amyloid-$β$ levels. Further reliability studies on the longitudinal ADNI dataset show improvement on detection reliability when RSM is used.
Computing Abelian regularities on RLE strings
Venue: arXiv cs.DS 2018
Year: 2018

Two strings x and y are said to be Abelian equivalent if x is a permutation of y, or vice versa. If a string z satisfies z = xy with x and y being Abelian equivalent, then z is said to be an Abelian square. If a string w can be factorized into a sequence v_1,...,v_s of strings such that v_1 ,..., v_{s-1} are all Abelian equivalent and vs is a substring of a permutation of v_1, then w is said to have a regular Abelian period (p,t) where p = |v_1| and t = |v_s|. If a substring w_1[i..i+l-1] of a string w_1 and a substring w_2[j..j+l-1] of another string w_2 are Abelian equivalent, then the substrings are said to be a common Abelian factor of w_1 and w_2 and if the length l is the maximum of such then the substrings are said to be a longest common Abelian factor of w_1 and w_2. We propose efficient algorithms which compute these Abelian regularities using the run length encoding (RLE) of strings. For a given string w of length n whose RLE is of size m, we propose algorithms which compute all Abelian squares occurring in w in O(mn) time, and all regular Abelian periods of w in O(mn) time. For two given strings w_1 and w_2 of total length n and of total RLE size m, we propose an algorithm which computes all longest common Abelian factors in O(m^2n) time.
On the Impact of Transposition Errors in Diffusion-Based Channels
Venue: arXiv cs.IT 2018
Year: 2018

In this work, we consider diffusion-based molecular communication with and without drift between two static nano-machines. We employ type-based information encoding, releasing a single molecule per information bit. At the receiver, we consider an asynchronous detection algorithm which exploits the arrival order of the molecules. In such systems, transposition errors fundamentally undermine reliability and capacity. Thus, in this work we study the impact of transpositions on the system performance. Towards this, we present an analytical expression for the exact bit error probability (BEP) caused by transpositions and derive computationally tractable approximations of the BEP for diffusion-based channels with and without drift. Based on these results, we analyze the BEP when background is not negligible and derive the optimal bit interval that minimizes the BEP. Simulation results confirm the theoretical results and show the error and goodput performance for different parameters such as block size or noise generation rate.
Focusing on a Probability Element: Parameter Selection of Message Importance Measure in Big Data
Venue: arXiv cs.IT 2018
Year: 2018

Message importance measure (MIM) is applicable to characterize the importance of information in the scenario of big data, similar to entropy in information theory. In fact, MIM with a variable parameter can make an effect on the characterization of distribution. Furthermore, by choosing an appropriate parameter of MIM, it is possible to emphasize the message importance of a certain probability element in a distribution. Therefore, parametric MIM can play a vital role in anomaly detection of big data by focusing on probability of an anomalous event. In this paper, we propose a parameter selection method of MIM focusing on a probability element and then present its major properties. In addition, we discuss the parameter selection with prior probability, and investigate the availability in a statistical processing model of big data for anomaly detection problem.
Model Theory and Proof Theory of Coalgebraic Predicate Logic
Venue: arXiv cs.LO 2018
Year: 2018

We propose a generalization of first-order logic originating in a neglected work by C.C. Chang: a natural and generic correspondence language for any types of structures which can be recast as Set-coalgebras. We discuss axiomatization and completeness results for several natural classes of such logics. Moreover, we show that an entirely general completeness result is not possible. We study the expressive power of our language, both in comparison with coalgebraic hybrid logics and with existing first-order proposals for special classes of Set-coalgebras (apart from relational structures, also neighbourhood frames and topological spaces). Basic model-theoretic constructions and results, in particular ultraproducts, obtain for the two classes that allow completeness---and in some cases beyond that. Finally, we discuss a basic sequent system, for which we establish a syntactic cut-elimination result.