OpenRaiser/Intern-Atlas huggingface dataset:
A Stable FDTD Method with Embedded Reduced-Order Models
Venue: arXiv cs.CE 2021
Year: 2021

The computational efficiency of the Finite-Difference Time-Domain (FDTD) method can be significantly reduced by the presence of complex objects with fine features. Small geometrical details impose a fine mesh and a reduced time step, significantly increasing computational cost. Model order reduction has been proposed as a systematic way to generate compact models for complex objects, that one can then instantiate into a main FDTD mesh. However, the stability of FDTD with embedded reduced models remains an open problem. We propose a systematic method to generate reduced models for FDTD domains, and embed them into a main FDTD mesh with guaranteed stability up to the Courant-Friedrichs-Lewy (CFL) limit of the fine mesh. With a simple perturbation technique, the CFL of the whole scheme can be further extended beyond the fine grid's CFL limit. Reduced models can be created for arbitrary domains containing inhomogeneous and lossy materials. Numerical tests confirm the stability of the proposed method, and its potential to accelerate multiscale FDTD simulations.
Generalized Entropy Concentration for Counts
Venue: arXiv cs.IT 2021
Year: 2021

The phenomenon of entropy concentration provides strong support for the maximum entropy method, MaxEnt, for inferring a probability vector from information in the form of constraints. Here we extend this phenomenon, in a discrete setting, to non-negative integral vectors not necessarily summing to 1. We show that linear constraints that simply bound the allowable sums suffice for concentration to occur even in this setting. This requires a new, `generalized' entropy measure in which the sum of the vector plays a role. We measure the concentration in terms of deviation from the maximum generalized entropy value, or in terms of the distance from the maximum generalized entropy vector. We provide non-asymptotic bounds on the concentration in terms of various parameters, including a tolerance on the constraints which ensures that they are always satisfied by an integral vector. Generalized entropy maximization is not only compatible with ordinary MaxEnt, but can also be considered an extension of it, as it allows us to address problems that cannot be formulated as MaxEnt problems.
Fractal Intersections and Products via Algorithmic Dimension
Venue: arXiv cs.CC 2021
Year: 2021

Algorithmic fractal dimensions quantify the algorithmic information density of individual points and may be defined in terms of Kolmogorov complexity. This work uses these dimensions to bound the classical Hausdorff and packing dimensions of intersections and Cartesian products of fractals in Euclidean spaces. This approach shows that two prominent, fundamental results about the dimension of Borel or analytic sets also hold for arbitrary sets.
Green-Blue Stripe Pattern for Range Sensing from a Single Image
Venue: arXiv cs.CV 2021
Year: 2021

In this paper, we present a novel method for rapid high-resolution range sensing using green-blue stripe pattern. We use green and blue for designing high-frequency stripe projection pattern. For accurate and reliable range recovery, we identify the stripe patterns by our color-stripe segmentation and unwrapping algorithms. The experimental result for a naked human face shows the effectiveness of our method.
WebSelect: A Research Prototype for Optimizing Ad Exposures based on Network Structure
Venue: arXiv cs.SI 2021
Year: 2021

This paper describes a Research Prototype, WebSelect, designed to assist online media planners in deciding which websites to target for a media campaign. The salient feature of the prototype is its ability to capture and utilize the overlap information in website traffic and use it for media planning exercises. In addition, the prototype possesses the capability to include targeting parameters like users age group and income along with the varying advertising costs across different websites. The prototype uses a genetic algorithm at the backend to select the final subset to target from the possible website set.
Ensemble Estimation of Generalized Mutual Information with Applications to Genomics
Venue: arXiv cs.IT 2021
Year: 2021

Mutual information is a measure of the dependence between random variables that has been used successfully in myriad applications in many fields. Generalized mutual information measures that go beyond classical Shannon mutual information have also received much interest in these applications. We derive the mean squared error convergence rates of kernel density-based plug-in estimators of general mutual information measures between two multidimensional random variables $\mathbf{X}$ and $\mathbf{Y}$ for two cases: 1) $\mathbf{X}$ and $\mathbf{Y}$ are continuous; 2) $\mathbf{X}$ and $\mathbf{Y}$ may have any mixture of discrete and continuous components. Using the derived rates, we propose an ensemble estimator of these information measures called GENIE by taking a weighted sum of the plug-in estimators with varied bandwidths. The resulting ensemble estimators achieve the $1/N$ parametric mean squared error convergence rate when the conditional densities of the continuous variables are sufficiently smooth. To the best of our knowledge, this is the first nonparametric mutual information estimator known to achieve the parametric convergence rate for the mixture case, which frequently arises in applications (e.g. variable selection in classification). The estimator is simple to implement and it uses the solution to an offline convex optimization problem and simple plug-in estimators. A central limit theorem is also derived for the ensemble estimators and minimax rates are derived for the continuous case. We demonstrate the ensemble estimator for the mixed case on simulated data and apply the proposed estimator to analyze gene relationships in single cell data.
Distributed Dual Coordinate Ascent in General Tree Networks and Communication Network Effect on Synchronous Machine Learning
Venue: arXiv cs.DC 2021
Year: 2021

Due to the big size of data and limited data storage volume of a single computer or a single server, data are often stored in a distributed manner. Thus, performing large-scale machine learning operations with the distributed datasets through communication networks is often required. In this paper, we study the convergence rate of the distributed dual coordinate ascent for distributed machine learning problems in a general tree-structured network. Since a tree network model can be understood as the generalization of a star network model, our algorithm can be thought of as the generalization of the distributed dual coordinate ascent in a star network model. We provide the convergence rate of the distributed dual coordinate ascent over a general tree network in a recursive manner and analyze the network effect on the convergence rate. Secondly, by considering network communication delays, we optimize the distributed dual coordinate ascent algorithm to maximize its convergence speed. From our analytical result, we can choose the optimal number of local iterations depending on the communication delay severity to achieve the fastest convergence speed. In numerical experiments, we consider machine learning scenarios over communication networks, where local workers cannot directly reach to a central node due to constraints in communication, and demonstrate that the usability of our distributed dual coordinate ascent algorithm in tree networks. Additionally, we show that adapting number of local and global iterations to network communication delays in the distributed dual coordinated ascent algorithm can improve its convergence speed.
FaSTrack: a Modular Framework for Fast and Guaranteed Safe Motion Planning
Venue: arXiv cs.RO 2021
Year: 2021

Fast and safe navigation of dynamical systems through a priori unknown cluttered environments is vital to many applications of autonomous systems. However, trajectory planning for autonomous systems is computationally intensive, often requiring simplified dynamics that sacrifice safety and dynamic feasibility in order to plan efficiently. Conversely, safe trajectories can be computed using more sophisticated dynamic models, but this is typically too slow to be used for real-time planning. We propose a new algorithm FaSTrack: Fast and Safe Tracking for High Dimensional systems. A path or trajectory planner using simplified dynamics to plan quickly can be incorporated into the FaSTrack framework, which provides a safety controller for the vehicle along with a guaranteed tracking error bound. This bound captures all possible deviations due to high dimensional dynamics and external disturbances. Note that FaSTrack is modular and can be used with most current path or trajectory planners. We demonstrate this framework using a 10D nonlinear quadrotor model tracking a 3D path obtained from an RRT planner.
Unifying Message Passing Algorithms Under the Framework of Constrained Bethe Free Energy Minimization
Venue: arXiv cs.IT 2021
Year: 2021

Variational message passing (VMP), belief propagation (BP) and expectation propagation (EP) have found their wide applications in complex statistical signal processing problems. In addition to viewing them as a class of algorithms operating on graphical models, this paper unifies them under an optimization framework, namely, Bethe free energy minimization with differently and appropriately imposed constraints. This new perspective in terms of constraint manipulation can offer additional insights on the connection between different message passing algorithms and is valid for a generic statistical model. It also founds a theoretical framework to systematically derive message passing variants. Taking the sparse signal recovery (SSR) problem as an example, a low-complexity EP variant can be obtained by simple constraint reformulation, delivering better estimation performance with lower complexity than the standard EP algorithm. Furthermore, we can resort to the framework for the systematic derivation of hybrid message passing for complex inference tasks. Notably, a hybrid message passing algorithm is exemplarily derived for joint SSR and statistical model learning with near-optimal inference performance and scalable complexity.
On the k-Means/Median Cost Function
Venue: arXiv cs.DS 2021
Year: 2021

In this work, we study the $k$-means cost function. Given a dataset $X \subseteq \mathbb{R}^d$ and an integer $k$, the goal of the Euclidean $k$-means problem is to find a set of $k$ centers $C \subseteq \mathbb{R}^d$ such that $Φ(C, X) \equiv \sum_{x \in X} \min_{c \in C} ||x - c||^2$ is minimized. Let $Δ(X,k) \equiv \min_{C \subseteq \mathbb{R}^d} Φ(C, X)$ denote the cost of the optimal $k$-means solution. For any dataset $X$, $Δ(X,k)$ decreases as $k$ increases. In this work, we try to understand this behaviour more precisely. For any dataset $X \subseteq \mathbb{R}^d$, integer $k \geq 1$, and a precision parameter $\varepsilon > 0$, let $L(X, k, \varepsilon)$ denote the smallest integer such that $Δ(X, L(X, k, \varepsilon)) \leq \varepsilon \cdot Δ(X,k)$. We show upper and lower bounds on this quantity. Our techniques generalize for the metric $k$-median problem in arbitrary metric spaces and we give bounds in terms of the doubling dimension of the metric. Finally, we observe that for any dataset $X$, we can compute a set $S$ of size $O \left(L(X, k, \varepsilon/c) \right)$ using $D^2$-sampling such that $Φ(S,X) \leq \varepsilon \cdot Δ(X,k)$ for some fixed constant $c$. We also discuss some applications of our bounds.
Distribution Bisimilarity via the Power of Convex Algebras
Venue: arXiv cs.LO 2021
Year: 2021

Probabilistic automata (PA), also known as probabilistic nondeterministic labelled transition systems, combine probability and nondeterminism. They can be given different semantics, like strong bisimilarity, convex bisimilarity, or (more recently) distribution bisimilarity. The latter is based on the view of PA as transformers of probability distributions, also called belief states, and promotes distributions to first-class citizens. We give a coalgebraic account of distribution bisimilarity, and explain the genesis of the belief-state transformer from a PA. To do so, we make explicit the convex algebraic structure present in PA and identify belief-state transformers as transition systems with state space that carries a convex algebra. As a consequence of our abstract approach, we can give a sound proof technique which we call bisimulation up-to convex hull.
Learning Neural Network Classifiers with Low Model Complexity
Venue: arXiv cs.LG 2021
Year: 2021

Modern neural network architectures for large-scale learning tasks have substantially higher model complexities, which makes understanding, visualizing and training these architectures difficult. Recent contributions to deep learning techniques have focused on architectural modifications to improve parameter efficiency and performance. In this paper, we derive a continuous and differentiable error functional for a neural network that minimizes its empirical error as well as a measure of the model complexity. The latter measure is obtained by deriving a differentiable upper bound on the Vapnik-Chervonenkis (VC) dimension of the classifier layer of a class of deep networks. Using standard backpropagation, we realize a training rule that tries to minimize the error on training samples, while improving generalization by keeping the model complexity low. We demonstrate the effectiveness of our formulation (the Low Complexity Neural Network - LCNN) across several deep learning algorithms, and a variety of large benchmark datasets. We show that hidden layer neurons in the resultant networks learn features that are crisp, and in the case of image datasets, quantitatively sharper. Our proposed approach yields benefits across a wide range of architectures, in comparison to and in conjunction with methods such as Dropout and Batch Normalization, and our results strongly suggest that deep learning techniques can benefit from model complexity control methods such as the LCNN learning rule.
Gaussian Process-Based Model Predictive Control of Blood Glucose for Patients with Type 1 Diabetes Mellitus
Venue: arXiv cs.SY 2021
Year: 2021

The insulin sensitivity (IS) of the human body changes with a circadian rhythm. This adds to the time-varying feature of the glucose metabolism process and places challenges on the blood glucose (BG) control of patients with Type 1 Diabetes Mellitus. This paper presents a Model Predictive Controller that takes the periodic IS into account, in order to enhance BG control. The future effect of the IS is predicted using a machine learning technique, namely, a customized Gaussian Process (GP), based on historical training data. The training data for the GP is continuously updated during closed-loop control, which enables the control scheme to learn and adapt to intra-individual and inter-individual changes of the circadian IS rhythm. The necessary state information is provided by an Unscented Kalman Filter. The closed-loop performance of the proposed control scheme is evaluated for different scenarios (including fasting, announced meals and skipped meals) through in silico studies on simulation models of Göttingen Minipigs.
Fundamental diagram of urban rail transit considering train-passenger interaction
Venue: arXiv cs.SY 2021
Year: 2021

Urban rail transit often operates with high service frequencies to serve heavy passenger demand during rush hours. Such operations can be delayed by two types of congestion: train congestion and passenger congestion, both of which interact with each other. This delay is problematic for many transit systems, since it can be amplified due to the interaction. However, there are no tractable models describing them; and it makes difficult to analyze management strategies of congested transit systems in general and tractable ways. To fill this gap, this article proposes simple yet physical and dynamic model of urban rail transit. First, a fundamental diagram of transit system (i.e., theoretical relation among train-flow, train-density, and passenger-flow) is analytically derived considering the aforementioned physical interaction. Then, a macroscopic model of transit system for dynamic transit assignment is developed based on the fundamental diagram. Finally, accuracy of the macroscopic model is investigated by comparing to microscopic simulation. The proposed models would be useful for mathematical analysis on management strategies of urban rail transit systems, in a similar way that the macroscopic fundamental diagram of urban traffic did.
Exact and Approximate Algorithms for Computing Betweenness Centrality in Directed Graphs
Venue: arXiv cs.DS 2021
Year: 2021

Graphs (networks) are an important tool to model data in different domains. Real-world graphs are usually directed, where the edges have a direction and they are not symmetric. Betweenness centrality is an important index widely used to analyze networks. In this paper, first given a directed network $G$ and a vertex $r \in V(G)$, we propose an exact algorithm to compute betweenness score of $r$. Our algorithm pre-computes a set $\mathcal{RV}(r)$, which is used to prune a huge amount of computations that do not contribute to the betweenness score of $r$. Time complexity of our algorithm depends on $|\mathcal{RV}(r)|$ and it is respectively $Θ(|\mathcal{RV}(r)|\cdot|E(G)|)$ and $Θ(|\mathcal{RV}(r)|\cdot|E(G)|+|\mathcal{RV}(r)|\cdot|V(G)|\log |V(G)|)$ for unweighted graphs and weighted graphs with positive weights. $|\mathcal{RV}(r)|$ is bounded from above by $|V(G)|-1$ and in most cases, it is a small constant. Then, for the cases where $\mathcal{RV}(r)$ is large, we present a simple randomized algorithm that samples from $\mathcal{RV}(r)$ and performs computations for only the sampled elements. We show that this algorithm provides an $(ε,δ)$-approximation to the betweenness score of $r$. Finally, we perform extensive experiments over several real-world datasets from different domains for several randomly chosen vertices as well as for the vertices with the highest betweenness scores. Our experiments reveal that for estimating betweenness score of a single vertex, our algorithm significantly outperforms the most efficient existing randomized algorithms, in terms of both running time and accuracy. Our experiments also reveal that our algorithm improves the existing algorithms when someone is interested in computing betweenness values of the vertices in a set whose cardinality is very small.
Structural properties of biclique graphs and the distance formula
Venue: arXiv cs.DM 2021
Year: 2021

A \textit{biclique} is a maximal induced complete bipartite subgraph of $G$. The \textit{biclique graph} of a graph $G$, denoted by $KB(G)$, is the intersection graph of the family of all bicliques of $G$. In this work we study some structural properties of biclique graphs which are necessary conditions for a graph to be a biclique graph. In particular, we prove that for biclique graphs that are neither a $K_3$ nor a \textit{diamond}, the number of vertices of degree $2$ is less than half the number of vertices in the graph. Also, we present forbidden structures. For this, we introduce a natural definition of the distance between bicliques in a graph. We give a formula that relates the distance between bicliques in a graph $G$ and the distance between their respective vertices in $KB(G)$. Using these results, we can prove not only this new necessary condition involving the degree, but also that some graphs are not biclique graphs. For example, we show that the \textit{crown} is the smallest graph that is not a biclique graph although the known necessary condition for biclique graphs holds, answering an open problem about biclique graphs. Finally, we present some interesting related conjectures and open problems.
Any strongly controllable group system or group shift or any linear block code is a linear system whose input is a generator group
Venue: arXiv cs.IT 2021
Year: 2021

Consider any sequence of finite groups $A^t$, where $t$ takes values in an integer index set $\mathbf{Z}$. A group system $A$ is a set of sequences with components in $A^t$ that forms a group under componentwise addition in $A^t$, for each $t\in\mathbf{Z}$. In the setting of group systems, a natural definition of a linear system is a homomorphism from a group of inputs to an output group system $A$. We show that any group can be the input group of a linear system and some group system. In general the kernel of the homomorphism is nontrivial. We show that any $\ell$-controllable complete group system $A$ is a linear system whose input group is a generator group $({\mathcal{U}},\circ)$, deduced from $A$, and then the kernel is always trivial. The input set ${\mathcal{U}}$ is a set of tensors, a double Cartesian product space of sets $R_{0,k}^t$, with indices $k$, for $0\le k\le\ell$, and time $t$, for $t\in\mathbf{Z}$. $R_{0,k}^t$ is a set of unique generator labels for the generators in $A$ with nontrivial span for the time interval $[t,t+k]$. We show the generator group contains an elementary system, an infinite collection of elementary groups, one for each $k$ and $t$, defined on small subsets of ${\mathcal{U}}$, in the shape of triangles, which form a tile like structure over ${\mathcal{U}}$. There is a homomorphism from each elementary group to any elementary group defined on smaller tiles of the former group. Any elementary system is sufficient to define a unique generator group up to isomorphism, and therefore is sufficient to construct a linear system and group system as well. Any linear block code is a strongly controllable group system. Then we can obtain new results on the structure of block codes using the generator group. There is a harmonic theory of group systems which we study using the generator group.
Handling state space explosion in verification of component-based systems: A review
Venue: arXiv cs.SE 2021
Year: 2021

Component-based software development (CBSD) is an alternative approach to constructing software systems that offers numerous benefits, particularly in decreasing the complexity of system design. However, deploying components into a system is a challenging and error-prone task. Model-checking is one of the reliable methods to systematically analyze the correctness of a system. It is a bruce-force checking of the system's state space that assists to significantly expand the level of confidence in the system. Nevertheless, model-checking is limited by a critical problem called state-space explosion (SSE). To benefit from model-checking, an appropriate method is required to reduce SSE. In the past two decades, a great number of SSE reduction methods have been proposed containing many similarities, dissimilarities, and unclear concepts in some cases. This research, firstly, plans to present a review of SSE handling methods and classify them based on their similarities, principle, and characteristics. Second, it investigates the methods for handling the SSE problem in the verification process of CBSD and provides insight into the potential limitations, underlining the key challenges for future research efforts.
Unsupervised Classification of Intrusive Igneous Rock Thin Section Images using Edge Detection and Colour Analysis
Venue: arXiv cs.CV 2021
Year: 2021

Classification of rocks is one of the fundamental tasks in a geological study. The process requires a human expert to examine sampled thin section images under a microscope. In this study, we propose a method that uses microscope automation, digital image acquisition, edge detection and colour analysis (histogram). We collected 60 digital images from 20 standard thin sections using a digital camera mounted on a conventional microscope. Each image is partitioned into a finite number of cells that form a grid structure. Edge and colour profile of pixels inside each cell determine its classification. The individual cells then determine the thin section image classification via a majority voting scheme. Our method yielded successful results as high as 90% to 100% precision.