title: The probabilities of extinction in a branching random walk on a strip

abstract: We consider a class of multitype Galton-Watson branching processes with a countably infinite type set $\mathcal{X}_d$ whose mean progeny matrices have a block lower Hessenberg form. For these processes, the probability $\boldsymbol{q}(A)$ of extinction in subsets of types $A\subseteq \mathcal{X}_d$ may differ from the global extinction probability $\boldsymbol{q}$ and the partial extinction probability $\tilde{\boldsymbol{q}}$. After deriving partial and global extinction criteria, we develop conditions for $\boldsymbol{q}<\boldsymbol{q}(A)<\tilde{\boldsymbol{q}}$. We then present an iterative method to compute the vector $\boldsymbol{q}(A)$ for any set $A$. Finally, we investigate the location of the vectors $\boldsymbol{q}(A)$ in the set of fixed points of the progeny generating vector.


title: Yoneda lemma for enriched infinity categories

abstract: We continue the study of enriched infinity categories, using a definition equivalent to that of Gepner and Haugseng. In our approach enriched infinity categories are associative monoids in an especially designed monoidal category of enriched quivers. We prove that, in case the monoidal structure in the basic category M comes from direct product, our definition is essentially equivalent to the approach via Segal objects. Furthermore, we compare our notion with the notion of category left-tensored over M, and prove a version of Yoneda lemma in this context. Version 2: An error in 2.6.2 corrected. Version 3: a few minor corrections. Version 4: Section 8 added, describing correspondences of enriched categories. In case the basic monoidal category M is a prototopos with a cartesian structure, we prove that the category of correspondences is equivalent to the category of enriched categories over [1]. Version 5: terminology changed (former bicartesian fibrations became bifibrations), a few misprints corrected. Version 6: Section 2.11 added, dealing with operadic sieves. A number of corrections and clarifications made per referee's request. Version 7: final version, accepted to Advances in Math. Version 8: a minor correction of 2.8.9-2.8.10.


title: Simplicial and dimension groups with group action and their realization

abstract: We define simplicial and dimension $\Gamma$-groups, the generalizations of simplicial and dimension groups to the case when these groups have an action of an arbitrary group $\Gamma.$ Assuming that the integral group ring of $\Gamma$ is Noetherian, we show that every dimension $\Gamma$-group is isomorphic to a direct limit of a directed system of simplicial $\Gamma$-groups and that the limit can be taken in the category of ordered groups with order-units or generating intervals. We adapt Hazrat's definition of the Grothendieck $\Gamma$-group $K_0^{\Gamma}(R)$ for a $\Gamma$-graded ring $R$ to the case when $\Gamma$ is not necessarily abelian. If $G$ is a pre-ordered abelian group with an action of $\Gamma$ which agrees with the pre-ordered structure, we say that $G$ is {\em realized} by a $\Gamma$-graded ring $R$ if $K_0^{\Gamma}(R)$ and $G$ are isomorphic as pre-ordered $\Gamma$-groups with an isomorphism which preserves order-units or generating intervals. We show that every simplicial $\Gamma$-group with an order-unit can be realized by a graded matricial ring over a $\Gamma$-graded division ring. If the integral group ring of $\Gamma$ is Noetherian, we realize a countable dimension $\Gamma$-group with an order-unit or a generating interval by a $\Gamma$-graded ultramatricial ring over a $\Gamma$-graded division ring. We also relate our results to graded rings with involution which give rise to Grothendieck $\Gamma$-groups with actions of both $\Gamma$ and $\mathbb Z_2$. We adapt the Realization Problem for von Neumann regular rings to graded rings and concepts from this work and discuss some other questions.


title: Continuum limits of sparse coupling patterns

abstract: We exhibit simple lattice systems, motivated by recently proposed cold atom experiments, whose continuum limits interpolate between real and $p$-adic smoothness as a spectral exponent is varied. A real spatial dimension emerges in the continuum limit if the spectral exponent is negative, while a $p$-adic extra dimension emerges if the spectral exponent is positive. We demonstrate Holder continuity conditions, both in momentum space and in position space, which quantify how smooth or ragged the two-point Green's function is as a function of the spectral exponent. The underlying discrete dynamics of our model is defined in terms of a Gaussian partition function as a classical statistical mechanical lattice model. The couplings between lattice sites are sparse in the sense that as the number of sites becomes large, a vanishing fraction of them couple to one another. This sparseness property is useful for possible experimental realizations of related systems.


title: Selections and Higher Separation Axioms

abstract: This survey presents some historical background and recent developments in the area of selections for set-valued mappings along with several open questions. It was written with the hope that the presented material may pique an interest in the selection problem for set-valued mappings --- a problem with a fascinating history and appealing applications.


title: Nonlinear Invariants of Planar Point Clouds Transformed by Matrices

abstract: The goal of this paper is to present invariants of planar point clouds, that is functions which take the same value before and after a linear transformation of a planar point cloud via a $2 \times 2$ invertible matrix. In the approach we adopt here, these invariants are functions of two variables derived from the least squares straight line of the planar point cloud under consideration. A linear transformation of a point cloud induces a nonlinear transformation of these variables. The said invariants are solutions to certain Partial Differential Equations, which are obtained by employing Lie theory. We find cloud invariants in the general case of a four$-$parameter transformation matrix, as well as, cloud invariants of various one$-$parameter sets of transformations which can be practically implemented. Case studies and simulations which verify our findings are also provided.


title: Comments on "Momentum fractional LMS for power signal parameter estimation"

abstract: The purpose of this paper is to indicate that the recently proposed Momentum fractional least mean squares (mFLMS) algorithm has some serious flaws in its design and analysis. Our apprehensions are based on the evidence we found in the derivation and analysis in the paper titled: \textquotedblleft \textit{Momentum fractional LMS for power signal parameter estimation}\textquotedblright. In addition to the theoretical bases our claims are also verified through extensive simulation results. The experiments clearly show that the new method does not have any advantage over the classical least mean square (LMS) method.


title: Learning Sampling Policies for Domain Adaptation

abstract: We address the problem of semi-supervised domain adaptation of classification algorithms through deep Q-learning. The core idea is to consider the predictions of a source domain network on target domain data as noisy labels, and learn a policy to sample from this data so as to maximize classification accuracy on a small annotated reward partition of the target domain. Our experiments show that learned sampling policies construct labeled sets that improve accuracies of visual classifiers over baselines.


title: On testing substitutability

abstract: The papers~\cite{hatfimmokomi11} and~\cite{azizbrilharr13} propose algorithms for testing whether the choice function induced by a (strict) preference list of length $N$ over a universe $U$ is substitutable. The running time of these algorithms is $O(|U|^3\cdot N^3)$, respectively $O(|U|^2\cdot N^3)$. In this note we present an algorithm with running time $O(|U|^2\cdot N^2)$. Note that $N$ may be exponential in the size $|U|$ of the universe.


title: Energy Efficiency and Emission Testing for Connected and Automated Vehicles Using Real-World Driving Data

abstract: By using the onboard sensing and external connectivity technology, connected and automated vehicles (CAV) could lead to improved energy efficiency, better routing, and lower traffic congestion. With the rapid development of the technology and adaptation of CAV, it is more critical to develop the universal evaluation method and the testing standard which could evaluate the impacts on energy consumption and environmental pollution of CAV fairly, especially under the various traffic conditions. In this paper, we proposed a new method and framework to evaluate the energy efficiency and emission of the vehicle based on the unsupervised learning methods. Both the real-world driving data of the evaluated vehicle and the large naturalistic driving dataset are used to perform the driving primitive analysis and coupling. Then the linear weighted estimation method could be used to calculate the testing result of the evaluated vehicle. The results show that this method can successfully identify the typical driving primitives. The couples of the driving primitives from the evaluated vehicle and the typical driving primitives from the large real-world driving dataset coincide with each other very well. This new method could enhance the standard development of the energy efficiency and emission testing of CAV and other off-cycle credits.


title: Capturing human category representations by sampling in deep feature spaces

abstract: Understanding how people represent categories is a core problem in cognitive science. Decades of research have yielded a variety of formal theories of categories, but validating them with naturalistic stimuli is difficult. The challenge is that human category representations cannot be directly observed and running informative experiments with naturalistic stimuli such as images requires a workable representation of these stimuli. Deep neural networks have recently been successful in solving a range of computer vision tasks and provide a way to compactly represent image features. Here, we introduce a method to estimate the structure of human categories that combines ideas from cognitive science and machine learning, blending human-based algorithms with state-of-the-art deep image generators. We provide qualitative and quantitative results as a proof-of-concept for the method's feasibility. Samples drawn from human distributions rival those from state-of-the-art generative models in quality and outperform alternative methods for estimating the structure of human categories.


title: Regularized Loss Minimizers with Local Data Perturbation: Consistency and Data Irrecoverability

abstract: We introduce a new concept, data irrecoverability, and show that the well-studied concept of data privacy is sufficient but not necessary for data irrecoverability. We show that there are several regularized loss minimization problems that can use perturbed data with theoretical guarantees of generalization, i.e., loss consistency. Our results quantitatively connect the convergence rates of the learning problems to the impossibility for any adversary for recovering the original data from perturbed observations. In addition, we show several examples where the convergence rates with perturbed data only increase the convergence rates with original data within a constant factor related to the amount of perturbation, i.e., noise.


title: Long-term face tracking in the wild using deep learning

abstract: This paper investigates long-term face tracking of a specific person given his/her face image in a single frame as a query in a video stream. Through taking advantage of pre-trained deep learning models on big data, a novel system is developed for accurate video face tracking in the unconstrained environments depicting various people and objects moving in and out of the frame. In the proposed system, we present a detection-verification-tracking method (dubbed as 'DVT') which accomplishes the long-term face tracking task through the collaboration of face detection, face verification, and (short-term) face tracking. An offline trained detector based on cascaded convolutional neural networks localizes all faces appeared in the frames, and an offline trained face verifier based on deep convolutional neural networks and similarity metric learning decides if any face or which face corresponds to the queried person. An online trained tracker follows the face from frame to frame. When validated on a sitcom episode and a TV show, the DVT method outperforms tracking-learning-detection (TLD) and face-TLD in terms of recall and precision. The proposed system is also tested on many other types of videos and shows very promising results.


title: Learning Hierarchical Visual Representations in Deep Neural Networks Using Hierarchical Linguistic Labels

abstract: Modern convolutional neural networks (CNNs) are able to achieve human-level object classification accuracy on specific tasks, and currently outperform competing models in explaining complex human visual representations. However, the categorization problem is posed differently for these networks than for humans: the accuracy of these networks is evaluated by their ability to identify single labels assigned to each image. These labels often cut arbitrarily across natural psychological taxonomies (e.g., dogs are separated into breeds, but never jointly categorized as "dogs"), and bias the resulting representations. By contrast, it is common for children to hear both "dog" and "Dalmatian" to describe the same stimulus, helping to group perceptually disparate objects (e.g., breeds) into a common mental class. In this work, we train CNN classifiers with multiple labels for each image that correspond to different levels of abstraction, and use this framework to reproduce classic patterns that appear in human generalization behavior.


title: On Attention Models for Human Activity Recognition

abstract: Most approaches that model time-series data in human activity recognition based on body-worn sensing (HAR) use a fixed size temporal context to represent different activities. This might, however, not be apt for sets of activities with individ- ually varying durations. We introduce attention models into HAR research as a data driven approach for exploring relevant temporal context. Attention models learn a set of weights over input data, which we leverage to weight the temporal context being considered to model each sensor reading. We construct attention models for HAR by adding attention layers to a state- of-the-art deep learning HAR model (DeepConvLSTM) and evaluate our approach on benchmark datasets achieving sig- nificant increase in performance. Finally, we visualize the learned weights to better understand what constitutes relevant temporal context.


title: Kinematic censorship as a constraint on allowed scenarios of high energy particle collisions

abstract: In recent years, it was found that the energy $E_{c.m.}$ in the centre of mass frame of two colliding particles can be unbounded near black holes. If collision occurs exactly on the horizon, $E_{c.m.}$ is formally infinite. However, in any physically reasonable situation this is impossible. We collect different scenarios of such a kind and show why in every act of collision $E_{c.m.}$ is indeed finite (although it can be as large as one likes). The factors preventing infinite energy are diverse: the necessity of infinite proper time, infinite tidal forces, potential barrier, etc. This prompts us to formulate a general principle according to which the limits in which $E_{c.m.}$ becomes infinite are never achieved. We call this the kinematic censorship (KC). Although by itself the validity of KC is quite natural, its application allows one to forbid scenarios of collisions predicting infinite $E_{c.m.}$ without going into details. The KC is valid even in the test particle approximation, so explanation of why $E_{c.m.}$ cannot be infinite, does not require references (common in literature) to the non-linear regime, backreaction, etc. The KC remains valid not only for free moving particles but also if particles experience the action of a finite force. For an individual particle, we consider a light-like continuous limit of a time-like trajectory in which the effective mass turns into zero. We show that it cannot be accelerated to an infinite energy during a finite proper time under the action of such a force. As an example, we consider dynamics of a scalar particle interacting with a background scalar field.


title: Regular frames and particle's rotation near a black hole

abstract: We consider a particle moving towards a rotating black hole. We are interested in the number of its revolution $n$ around a black hole. In our previous work (Pavlov and Zaslavskii in Gen Relativ Gravit 50: 14, 2018. arXiv:1707.02860) we considered this issue in the Boyer-Lindquist type of coordinates with a subsequent procedure of subtraction. Now, we reconsider this issue using from the very beginning the frames regular on the horizon. For a nonextremal black hole, regularity of a coordinate frame leads to the finiteness of a number of revolutions around a black hole without a subtraction procedure. Meanwhile, for extremal black holes comparison of $n$ calculated in the regular frame with some subtraction procedures used by us earlier shows that the results can be different.


title: Do You Like What I Like? Similarity Estimation in Proximity-based Mobile Social Networks

abstract: While existing social networking services tend to connect people who know each other, people show a desire to also connect to yet unknown people in physical proximity. Existing research shows that people tend to connect to similar people. Utilizing technology in order to stimulate human interaction between strangers, we consider the scenario of two strangers meeting. On the example of similarity in musical taste, we develop a solution for the problem of similarity estimation in proximity-based mobile social networks. We show that a single exchange of a probabilistic data structure between two devices can closely estimate the similarity of two users - without the need to contact a third-party server.We introduce metrics for fast and space-efficient approximation of the Dice coefficient of two multisets - based on the comparison of two Counting Bloom Filters or two Count-Min Sketches. Our analysis shows that utilizing a single hash function minimizes the error when comparing these probabilistic data structures. The size that should be chosen for the data structure depends on the expected average number of unique input elements. Using real user data, we show that a Counting Bloom Filter with a single hash function and a length of 128 is sufficient to accurately estimate the similarity between two multisets representing the musical tastes of two users. Our approach is generalizable for any other similarity estimation of frequencies represented as multisets.


title: Security Performance Analysis of Physical Layer over Fisher-Snedecor $\mathcal{F}$ Fading Channels

abstract: In this letter, the performance analysis of physical layer security over Fisher-Snedecor $\mathcal{F}$ fading channels is investigated. In particular, the average secrecy capacity (ASC), the secure outage probability (SOP), the lower bound of the SOP (SOP$^L$), and the strictly positive secure capacity (SPSC) are derived in exact closed-from expressions. The Fisher-Snedecor $\mathcal{F}$ fading channel is a composite of multipath/shadowed fading that are represented by the Nakagami-$m$ distribution. Moreover, it provides close results to the practical measurements than the generalised $K$ ($K_G$) fading channels. To validate our analysis, the numerical results are affirmed by the Monte Carlo simulations.


title: Learning a face space for experiments on human identity

abstract: Generative models of human identity and appearance have broad applicability to behavioral science and technology, but the exquisite sensitivity of human face perception means that their utility hinges on the alignment of the model's representation to human psychological representations and the photorealism of the generated images. Meeting these requirements is an exacting task, and existing models of human identity and appearance are often unworkably abstract, artificial, uncanny, or biased. Here, we use a variational autoencoder with an autoregressive decoder to learn a face space from a uniquely diverse dataset of portraits that control much of the variation irrelevant to human identity and appearance. Our method generates photorealistic portraits of fictive identities with a smooth, navigable latent space. We validate our model's alignment with human sensitivities by introducing a psychophysical Turing test for images, which humans mostly fail. Lastly, we demonstrate an initial application of our model to the problem of fast search in mental space to obtain detailed "police sketches" in a small number of trials.


title: Sampling-Free Variational Inference of Bayesian Neural Networks by Variance Backpropagation

abstract: We propose a new Bayesian Neural Net formulation that affords variational inference for which the evidence lower bound is analytically tractable subject to a tight approximation. We achieve this tractability by (i) decomposing ReLU nonlinearities into the product of an identity and a Heaviside step function, (ii) introducing a separate path that decomposes the neural net expectation from its variance. We demonstrate formally that introducing separate latent binary variables to the activations allows representing the neural network likelihood as a chain of linear operations. Performing variational inference on this construction enables a sampling-free computation of the evidence lower bound which is a more effective approximation than the widely applied Monte Carlo sampling and CLT related techniques. We evaluate the model on a range of regression and classification tasks against BNN inference alternatives, showing competitive or improved performance over the current state-of-the-art.


title: Coboundaries of nonconventional ergodic averages

abstract: Let $(X,\mathcal{A}, \mu)$ be a probability measure space and let $T_i,$ $1\leq i\leq H,$ be invertible bi measurable measure preserving transformations on this measure space. We give a sufficient condition for the product of $H$ bounded functions $f_1, f_2, ..., f_H$ to be a coboundary. This condition turns out to be also necessary when one seeks bounded coboundaries.


title: BART with Targeted Smoothing: An analysis of patient-specific stillbirth risk

abstract: This article introduces BART with Targeted Smoothing, or tsBART, a new Bayesian tree-based model for nonparametric regression. The goal of tsBART is to introduce smoothness over a single target covariate t, while not necessarily requiring smoothness over other covariates x. TsBART is based on the Bayesian Additive Regression Trees (BART) model, an ensemble of regression trees. TsBART extends BART by parameterizing each tree's terminal nodes with smooth functions of t, rather than independent scalars. Like BART, tsBART captures complex nonlinear relationships and interactions among the predictors. But unlike BART, tsBART guarantees that the response surface will be smooth in the target covariate. This improves interpretability and helps regularize the estimate. After introducing and benchmarking the tsBART model, we apply it to our motivating example: pregnancy outcomes data from the National Center for Health Statistics. Our aim is to provide patient-specific estimates of stillbirth risk across gestational age (t), based on maternal and fetal risk factors (x). Obstetricians expect stillbirth risk to vary smoothly over gestational age, but not necessarily over other covariates, and tsBART has been designed precisely to reflect this structural knowledge. The results of our analysis show the clear superiority of the tsBART model for quantifying stillbirth risk, thereby providing patients and doctors with better information for managing the risk of perinatal mortality. All methods described here are implemented in the R package tsbart.


title: Solving singular generalized eigenvalue problems by a rank-completing perturbation

abstract: Generalized eigenvalue problems involving a singular pencil are very challenging to solve, both with respect to accuracy and efficiency. The existing package Guptri is very elegant but may sometimes be time-demanding, even for small and medium-sized matrices. We propose a simple method to compute the eigenvalues of singular pencils, based on one perturbation of the original problem of a certain specific rank. For many problems, the method is both fast and robust. This approach may be seen as a welcome alternative to staircase methods.


title: From a cell model with active motion to a Hele-Shaw-like system. A numerical approach

abstract: In this paper we deal with the numerical solution of a Hele--Shaw-like system via a cell model with active motion. Convergence of approximations is established for well-posed initial data. These data are chosen in such a way the time derivate is positive at the initial time. The numerical method is constructed by means of a finite element procedure together with the use of a closed-nodal integration. This gives rise to an algorithm which preserves positivity whenever a right-angled triangulation is considered. As a result, uniform-in-time a priori estimates are proven which allows us to pass to limit towards a solution to the Hele--Shaw problem.


title: Compact Finite Differences and Cubic Splines

abstract: In this paper I uncover and explain---using contour integrals and residues---a connection between cubic splines and a popular compact finite difference formula. The connection is that on a uniform mesh the simplest Pad\'e scheme for generating fourth-order accurate compact finite differences gives \textsl{exactly} the derivatives at the interior nodes needed to guarantee twice-continuous differentiability for cubic splines. %I found this connection surprising, because the two problems being solved are different. I also introduce an apparently new spline-like interpolant that I call a compact cubic interpolant; this is similar to one introduced in 1972 by Swartz and Varga, but has higher order accuracy at the edges. I argue that for mildly nonuniform meshes the compact cubic approach offers some potential advantages, and even for uniform meshes offers a simple way to treat the edge conditions, relieving the user of the burden of deciding to use one of the three standard options: free (natural), complete (clamped), or "not-a-knot" conditions. Finally, I establish that the matrices defining the compact cubic splines (equivalently, the fourth-order compact finite difference formul\ae) are positive definite, and in fact totally nonnegative, if all mesh widths are the same sign.


title: Complex Engel Structures

abstract: We study the geometry of Engel structures, which are 2-plane fields on 4-manifolds satisfying a generic condition, that are compatible with other geometric structures. A complex Engel structure is an Engel 2-plane field on a complex surface for which the 2-planes are complex lines. We solve the equivalence problems for complex Engel structures and use the resulting structure equations to classify homogeneous complex Engel structures. This allows us to determine all compact, homogeneous examples. Compact manifolds that support homogeneous complex Engel structures are diffeomorphic to $S^1\times SU(2)$ or quotients of $\mathbb{C}^2$, $S^1\times SU(2)$, $S^1\times G$ or $H$ by co-compact lattices, where $G$ is the connected and simply-connected Lie group with Lie algebra $\mathfrak{sl}_2(\mathbb{R})$ and $H$ is a solvable Lie group.


title: Measuring neuronal avalanches in disordered systems with absorbing states

abstract: Power-law-shaped avalanche-size distributions are widely used to probe for critical behavior in many different systems, particularly in neural networks. The definition of avalanche is ambiguous. Usually, theoretical avalanches are defined as the activity between a stimulus and the relaxation to an inactive absorbing state. On the other hand, experimental neuronal avalanches are defined by the activity between consecutive silent states. We claim that the latter definition may be extended to some theoretical models to characterize their power-law avalanches and critical behavior. We study a system in which the separation of driving and relaxation time scales emerges from its structure. We apply both definitions of avalanche to our model. Both yield power-law-distributed avalanches that scale with system size in the critical point as expected. Nevertheless, we find restricted power-law-distributed avalanches outside of the critical region within the experimental procedure, which is not expected by the standard theoretical definition. We remark that these results are dependent on the model details.

categories: physics.bio-ph cond-mat.dis-nn cond-mat.stat-mech nlin.AO q-bio.NC


title: DFCV: A Novel Approach for Message Dissemination in Connected Vehicles using Dynamic Fog

abstract: Vehicular Ad-hoc Network (VANET) has emerged as a promising solution for enhancing road safety. Routing of messages in VANET is challenging due to packet delays arising from high mobility of vehicles, frequently changing topology, and high density of vehicles, leading to frequent route breakages and packet losses. Previous researchers have used either mobility in vehicular fog computing or cloud computing to solve the routing issue, but they suffer from large packet delays and frequent packet losses. We propose Dynamic Fog for Connected Vehicles (DFCV), a fog computing based scheme which dynamically creates, increments and destroys fog nodes depending on the communication needs. The novelty of DFCV lies in providing lower delays and guaranteed message delivery at high vehicular densities. Simulations were conducted using hybrid simulation consisting of ns-2, SUMO, and Cloudsim. Results show that DFCV ensures efficient resource utilization, lower packet delays and losses at high vehicle densities.


title: An Evaluation of Trajectory Prediction Approaches and Notes on the TrajNet Benchmark

abstract: In recent years, there is a shift from modeling the tracking problem based on Bayesian formulation towards using deep neural networks. Towards this end, in this paper the effectiveness of various deep neural networks for predicting future pedestrian paths are evaluated. The analyzed deep networks solely rely, like in the traditional approaches, on observed tracklets without human-human interaction information. The evaluation is done on the publicly available TrajNet benchmark dataset, which builds up a repository of considerable and popular datasets for trajectory-based activity forecasting. We show that a Recurrent-Encoder with a Dense layer stacked on top, referred to as RED-predictor, is able to achieve sophisticated results compared to elaborated models in such scenarios. Further, we investigate failure cases and give explanations for observed phenomena and give some recommendations for overcoming demonstrated shortcomings.


title: Generating adjoint groups

abstract: We prove two approximations of the open problem of whether the adjoint group of a non-nilpotent nil ring can be finitely generated: We show that the adjoint group of a non-nilpotent Jacobson radical cannot be boundedly generated, and on the other hand construct a finitely generated, infinite dimensional nil algebra whose adjoint group is generated by elements of bounded torsion.


title: An investigation of the photometric variability of confirmed and candidate Galactic Be stars using ASAS-3 data

abstract: We present an investigation of a large sample of confirmed (N=233) and candidate (N=54) Galactic classical Be stars (mean V magnitude range of 6.4 to 12.6 mag), with the main aim of characterizing their photometric variability. Our sample stars were preselected among early-type variables using light curve morphology criteria. Spectroscopic information was gleaned from the literature, and archival and newly-acquired spectra. Photometric variability was analyzed using archival ASAS-3 time series data. To enable a comparison of results, we have largely adopted the methodology of Labadie-Bartz et al. (2017), who carried out a similar investigation based on KELT data. Complex photometric variations were established in most stars: outbursts on different time-scales (in 73$\pm$5% of stars), long-term variations (36$\pm$6%), periodic variations on intermediate time-scales (1$\pm$1%) and short-term periodic variations (6$\pm$3%). 24$\pm$6% of the outbursting stars exhibit (semi)periodic outbursts. We close the apparent void of rare outbursters reported by Labadie-Bartz et al. (2017) and show that Be stars with infrequent outbursts are not rare. While we do not find a significant difference in the percentage of stars showing outbursts among early-type, mid-type and late-type Be stars, we show that early-type Be stars exhibit much more frequent outbursts. We have measured rising and falling times for well-covered and well-defined outbursts. Nearly all outburst events are characterized by falling times that exceed the rising times. No differences were found between early-, mid- and late-type stars; a single non-linear function adequately describes the ratio of falling time to rising time across all spectral subtypes, with the ratio being larger for short events.


title: On the global solvability of porous media equations with general (spatially dependent) advection terms

abstract: We show that advection-diffusion equations with porous media type diffusion and integrable initial data are globally solvable under very mild conditions. Some generalizations and related results are also given.


title: The anatomy of a Web of Trust: the Bitcoin-OTC market

abstract: Bitcoin-otc is a peer to peer (over-the-counter) marketplace for trading with bit- coin crypto-currency. To mitigate the risks of the p2p unsupervised exchanges, the establishment of a reliable reputation systems is needed: for this reason, a web of trust is implemented on the website. The availability of all the historic of the users interaction data makes this dataset a unique playground for studying reputation dynamics through others evaluations. We analyze the structure and the dynamics of this web of trust with a multilayer network approach distin- guishing the rewarding and the punitive behaviors. We show that the rewarding and the punitive behavior have similar emergent topological properties (apart from the clustering coefficient being higher for the rewarding layer) and that the resultant reputation originates from the complex interaction of the more regular behaviors on the layers. We show which are the behaviors that correlate (i.e. the rewarding activity) or not (i.e. the punitive activity) with reputation. We show that the network activity presents bursty behaviors on both the layers and that the inequality reaches a steady value (higher for the rewarding layer) with the network evolution. Finally, we characterize the reputation trajectories and we identify prototypical behaviors associated to three classes of users: trustworthy, untrusted and controversial.


title: An a priori bound of rational functions on the Berkovich projective line

abstract: We establish a locally uniform a priori bound on the dynamics of a rational function $f$ of degree $>1$ on the Berkovich projective line over an algebraically closed field of any characteristic that is complete with respect to a non-trivial and non-archimedean absolute value, and deduce an equidistribution result for moving targets towards the equilibrium (or canonical) measure $\mu_f$, under the no potentially good reductions condition. This partly answers a question posed by Favre and Rivera-Letelier.


title: Optically driven spin pumping mediating collective magnetization dynamics in a spin valve structure

abstract: We demonstrate spin pumping, i.e. the generation of a pure spin current by precessing magnetization, without application of microwave radiation commonly used in spin pumping experiments. We use femtosecond laser pulses to simultaneously launch the magnetization precession in each of two ferromagnetic layers of a Galfenol-based spin valve and monitor the temporal evolution of the magnetizations. The spin currents generated by the precession cause a dynamic coupling of the two layers. This coupling has dissipative character and is especially efficient when the precession frequencies in the two layers are in resonance, where coupled modes with strongly different decay rates are formed.


title: Incidence hypergraphs: The categorical inconsistency of set-systems and a characterization of quiver exponentials

abstract: This paper considers the difficulty in the set-system approach to generalizing graph theory. These difficulties arise categorically as the category of set-system hypergraphs is shown not to be cartesian closed and lacks enough projective objects, unlike the category of directed multigraphs (i.e. quivers). The category of incidence hypergraphs is introduced as a "graph-like" remedy for the set-system issues so that hypergraphs may be studied by their locally graphic behavior via homomorphisms that allow an edge of the domain to be mapped into a subset of an edge in the codomain. Moreover, it is shown that the category of quivers embeds into the category of incidence hypergraphs via a logical functor that is the inverse image of an essential geometric morphism between the topoi. Consequently, the quiver exponential is shown to be simply represented using incidence hypergraph homomorphisms.


title: Homogenization of time-harmonic Maxwell's equations in nonhomogeneous plasmonic structures

abstract: We carry out the homogenization of time-harmonic Maxwell's equations in a periodic, layered structure made of two-dimensional (2D) metallic sheets immersed in a heterogeneous and in principle anisotropic dielectric medium. In this setting, the tangential magnetic field exhibits a jump across each sheet. Our goal is the rigorous derivation of the effective dielectric permittivity of the system from the solution of a local cell problem via suitable averages. Each sheet has a fine-scale, inhomogeneous and possibly anisotropic surface conductivity that scales linearly with the microstructure scale, $d$. Starting with the weak formulation of the requisite boundary value problem, we prove the convergence of its solution to a homogenization limit as $d$ approaches zero. The effective permittivity and cell problem express a bulk average from the host dielectric and a surface average germane to the 2D material (metallic layer). We discuss implications of this analysis in the modeling of plasmonic crystals.


title: An Extended Poisson Family of Life Distribution: A Unified Approach in Competitive and Complementary Risks

abstract: In this paper, we introduce a new approach to generate flexible parametric families of distributions. These models arise on competitive and complementary risks scenario, in which the lifetime associated with a particular risk is not observable, rather, we observe only the minimum/maximum lifetime value among all risks. The latent variables have a zero truncated Poisson distribution. For the proposed family of distribution, the extra shape parameter has an important physical interpretation in the competing and complementary risks scenario. The mathematical properties and inferential procedures are discussed. The proposed approach is applied in some existing distributions in which it is fully illustrated by an important data set.


title: Columnar structures of soft spheres: Metastability and hysteresis

abstract: Previously we reported on the stable (i.e. minimal enthalpy) structures of soft monodisperse spheres in a long cylindrical channel. Here, we present further simulations, which significantly extend the original phase diagram up to D/d = 2.714 (ratio of cylinder and sphere diameters), where the nature of densest sphere packing changes. However, macroscopic systems of this kind are not confined to the ideal equilibrium states of this diagram. Consequently, we explore some of the structural transitions to be expected as experimental conditions are varied; these are in general hysteretic. We represent these transitions in a stability diagram for a representative case. Illustrative videos are included in the supplemental material.


title: BourGAN: Generative Networks with Metric Embeddings

abstract: This paper addresses the mode collapse for generative adversarial networks (GANs). We view modes as a geometric structure of data distribution in a metric space. Under this geometric lens, we embed subsamples of the dataset from an arbitrary metric space into the l2 space, while preserving their pairwise distance distribution. Not only does this metric embedding determine the dimensionality of the latent space automatically, it also enables us to construct a mixture of Gaussians to draw latent space random vectors. We use the Gaussian mixture model in tandem with a simple augmentation of the objective function to train GANs. Every major step of our method is supported by theoretical analysis, and our experiments on real and synthetic data confirm that the generator is able to produce samples spreading over most of the modes while avoiding unwanted samples, outperforming several recent GAN variants on a number of metrics and offering new features.


title: Instrumentation Amplifier design: Comparison of CMOS-memristive to CMOS design

abstract: An instrumentation amplifier (InAmp) is an electronic device used in many applications, where test and measuring accuracy is required. However, one of the drawbacks of an InAmp is limited operation gain range. In this paper, we investigate the possibility of replacing CMOS transistors in InAmp with memristive devices. The application of memristors in CMOS instrumentation amplifier design has lead to reduction of on-chip area and power consumption, comparing to the original design. The memristor based implementation of InAmp design has an improved gain. The advantages of memristor application are shown, and DC and operation gain range are discussed in this paper. Furthermore, variability analysis and performance variation with respect to the temperature variation is provided. In addition, the noise sensitivity analysis is performed. Moreover, varying values of resistance levels of memristors, the operation gain range, gain accuracy as well as a the noise reduction can be improved.


title: Sense amplifier design using CMOS-memristor circuits

abstract: With the increase of the speed of computers, timing and power requirements are becoming crucial for memory devices. The main objective of the paper is to modify 180nm CMOS sense amplifier design by using memristive devices and improve the design in terms of on-chip area, power efficiency, resistance to temperatures and speed. To achieve this, NOT gates in the circuit were constructed using memristor and CMOS. The main aim of the paper is to check the effect of memristors on characteristics of sense amplifier. The design was tested on Conventional Current Sense Amplifier (CSA) circuit. Changes in power, area, sensing delay and offset are reported in the paper.


title: On Integrability of the Geodesic Deviation Equation

abstract: The Jacobi equation for geodesic deviation describes finite size effects due to the gravitational tidal forces. In this paper we show how one can integrate the Jacobi equation in any spacetime admitting completely integrable geodesics. Namely, by linearizing the geodesic equation and its conserved charges, we arrive at the invariant Wronskians for the Jacobi system that are linear in the `deviation momenta' and thus yield a system of first-order differential equations that can be integrated. The procedure is illustrated on an example of a rotating black hole spacetime described by the Kerr geometry and its higher-dimensional generalizations. A number of related topics, including the phase space formulation of the theory and the derivation of the covariant Hamiltonian for the Jacobi system are also discussed.


title: Perceptron Linear Function Design with CMOS-Memristive Circuits

abstract: In the last decade, the interest to emulation of the functionality and structure of the human brain to solve the problems related to image processing and pattern recognition, especially using to Artificial Neural Network (ANN), has increased. Since the capability of ANN to compute at high-speed has been proven to be very useful for various computational problems. One of the simple ANN models is perceptron. Since the perceptron is the basic form of a neural network, the efficient implementation of analog activation functions is required. As various works introduce the design of sigmoid and tangent activation functions, the other activation functions remain an open research problem. This paper describes the design of the perception circuit with the linear activation function using operational amplifier and memristive crossbar. Additionally, the variation of performance with temperature, noise of the circuit is presented.


title: Variability analysis of Memristor-based Sigmoid Function

abstract: Activation functions are widely used in neural networks to decide the activation value of the neural unit based upon linear combinations of the weighted inputs. The effective implementation of activation function is highly important, as they help to represent non-linear complex functional mappings between inputs and outputs of the neural network. One of the non-linear approaches is to use a sigmoid function. Therefore, there is a growing need in enhancing the performance of sigmoid circuits. In this paper, the main objective is to modify existing current mirror based sigmoid model by replacing CMOS transistors with memristor devices. This model was tested varying different circuit parameters, transistor size and temperature. The the area, power and noise in the modified CMOS-memristive sigmoid circuit are shown. The application of memristors in the sigmoid circuit results in higher component density in an on-chip area, allowing a reduction of power and area by 7$\%$. The proposed sigmoid circuit was simulated in SPICE using 180nm TSMC CMOS technology.


title: Analog multiplier design with CMOS-memristor circuits

abstract: CMOS-transistors circuits have been used as a conventional approach for designing an analog multiplier in modern era of industrial electronics. However, previous studies have shown, that based on the working region of transistors, such as saturation or weak inversion regions, the circuit may face issues with output ranges and accuracy. One possible solution to that problem could be choosing CMOS-memristors as a basis for the circuit. Although memristor research is still a growing and promising field, one could argue that its implementation could bring many benefits such as increased circuit density and superior computation speeds, etc. Additionally, the era of Moore's Law of downscaling the size of transistors is to eventually come to an end. No one knows whether the end of a scaling paradigm is to happen within the next five or twenty years. Hence, the research on this particular subject is quite important. This paper proposes an analog multiplier design with CMOS and memristive components. Mainly, the aim of the paper is to compare the power consumption and overall characteristic of the multiplier such as the accuracy and the output range to that of the conventional multiplier. The designed circuit is expected to be suitable for low power applications, and it is built using 18um CMOS technology. The circuit simulations will be conducted using SPICE software. Finally, the effects of channel modulation and temperature on the multiplier performance will be discussed.


title: Periodicity of Grover walks on distance-regular graphs

abstract: Characterizations graphs of some classes to induce periodic Grover walks have been studied for recent years. In particular, for the strongly regular graphs, it has been known that there are only three kinds of such graphs. Here, we focus on the periodicity of the Grover walks on distance-regular graphs. The distance-regular graph can be regarded as a kind of generalization of the strongly regular graphs and the typical graph with an equitable partition. In this paper, we find some classes of such distance-regular graphs and obtain some useful necessary conditions to induce periodic Grover walks on the general distance-regular graphs. Also, we apply this necessary condition to give another proof for the strong regular graphs.


title: The Generalized Lasso Problem and Uniqueness

abstract: We study uniqueness in the generalized lasso problem, where the penalty is the $\ell_1$ norm of a matrix $D$ times the coefficient vector. We derive a broad result on uniqueness that places weak assumptions on the predictor matrix $X$ and penalty matrix $D$; the implication is that, if $D$ is fixed and its null space is not too large (the dimension of its null space is at most the number of samples), and $X$ and response vector $y$ jointly follow an absolutely continuous distribution, then the generalized lasso problem has a unique solution almost surely, regardless of the number of predictors relative to the number of samples. This effectively generalizes previous uniqueness results for the lasso problem (which corresponds to the special case $D=I$). Further, we extend our study to the case in which the loss is given by the negative log-likelihood from a generalized linear model. In addition to uniqueness results, we derive results on the local stability of generalized lasso solutions that might be of interest in their own right.


title: Learning Graph-Level Representations with Recurrent Neural Networks

abstract: Recently a variety of methods have been developed to encode graphs into low-dimensional vectors that can be easily exploited by machine learning algorithms. The majority of these methods start by embedding the graph nodes into a low-dimensional vector space, followed by using some scheme to aggregate the node embeddings. In this work, we develop a new approach to learn graph-level representations, which includes a combination of unsupervised and supervised learning components. We start by learning a set of node representations in an unsupervised fashion. Graph nodes are mapped into node sequences sampled from random walk approaches approximated by the Gumbel-Softmax distribution. Recurrent neural network (RNN) units are modified to accommodate both the node representations as well as their neighborhood information. Experiments on standard graph classification benchmarks demonstrate that our proposed approach achieves superior or comparable performance relative to the state-of-the-art algorithms in terms of convergence speed and classification accuracy. We further illustrate the effectiveness of the different components used by our approach.


title: Consistent Estimation of Propensity Score Functions with Oversampled Exposed Subjects

abstract: Observational cohort studies with oversampled exposed subjects are typically implemented to understand the causal effect of a rare exposure. Because the distribution of exposed subjects in the sample differs from the source population, estimation of a propensity score function (i.e., probability of exposure given baseline covariates) targets a nonparametrically nonidentifiable parameter. Consistent estimation of propensity score functions is an important component of various causal inference estimators, including double robust machine learning and inverse probability weighted estimators. This paper develops the use of the probability of exposure from the source population in a flexible computational implementation that can be used with any algorithm that allows observation weighting to produce consistent estimators of propensity score functions. Simulation studies and a hypothetical health policy intervention data analysis demonstrate low empirical bias and variance for these propensity score function estimators with observation weights in finite samples.


title: Fighting Offensive Language on Social Media with Unsupervised Text Style Transfer

abstract: We introduce a new approach to tackle the problem of offensive language in online social media. Our approach uses unsupervised text style transfer to translate offensive sentences into non-offensive ones. We propose a new method for training encoder-decoders using non-parallel data that combines a collaborative classifier, attention and the cycle consistency loss. Experimental results on data from Twitter and Reddit show that our method outperforms a state-of-the-art text style transfer system in two out of three quantitative metrics and produces reliable non-offensive transferred sentences.


title: SRPT for Multiserver Systems

abstract: The Shortest Remaining Processing Time (SRPT) scheduling policy and its variants have been extensively studied in both theoretical and practical settings. While beautiful results are known for single-server SRPT, much less is known for multiserver SRPT. In particular, stochastic analysis of the M/G/k under multiserver SRPT is entirely open. Intuition suggests that multiserver SRPT should be optimal or near-optimal for minimizing mean response time. However, the only known analysis of multiserver SRPT is in the worst-case adversarial setting, where SRPT can be far from optimal. In this paper, we give the first stochastic analysis bounding mean response time of the M/G/k under multiserver SRPT. Using our response time bound, we show that multiserver SRPT has asymptotically optimal mean response time in the heavy-traffic limit. The key to our bounds is a strategic combination of stochastic and worst-case techniques. Beyond SRPT, we prove similar response time bounds and optimality results for several other multiserver scheduling policies.


title: Machine Teaching for Inverse Reinforcement Learning: Algorithms and Applications

abstract: Inverse reinforcement learning (IRL) infers a reward function from demonstrations, allowing for policy improvement and generalization. However, despite much recent interest in IRL, little work has been done to understand the minimum set of demonstrations needed to teach a specific sequential decision-making task. We formalize the problem of finding maximally informative demonstrations for IRL as a machine teaching problem where the goal is to find the minimum number of demonstrations needed to specify the reward equivalence class of the demonstrator. We extend previous work on algorithmic teaching for sequential decision-making tasks by showing a reduction to the set cover problem which enables an efficient approximation algorithm for determining the set of maximally-informative demonstrations. We apply our proposed machine teaching algorithm to two novel applications: providing a lower bound on the number of queries needed to learn a policy using active IRL and developing a novel IRL algorithm that can learn more efficiently from informative demonstrations than a standard IRL approach.


title: Bayesian Modeling and Computation for Analyte Quantification in Complex Mixtures Using Raman Spectroscopy

abstract: In this work, we propose a two-stage algorithm based on Bayesian modeling and computation aiming at quantifying analyte concentrations or quantities in complex mixtures with Raman spectroscopy. A hierarchical Bayesian model is built for spectral signal analysis, and reversible-jump Markov chain Monte Carlo (RJMCMC) computation is carried out for model selection and spectral variable estimation. Processing is done in two stages. In the first stage, the peak representations for a target analyte spectrum are learned. In the second, the peak variables learned from the first stage are used to estimate the concentration or quantity of the target analyte in a mixture. Numerical experiments validated its quantification performance over a wide range of simulation conditions and established its advantages for analyte quantification tasks under the small training sample size regime over conventional multivariate regression algorithms. We also used our algorithm to analyze experimental spontaneous Raman spectroscopy data collected for glucose concentration estimation in biopharmaceutical process monitoring applications. Our work shows that this algorithm can be a promising complementary tool alongside conventional multivariate regression algorithms in Raman spectroscopy-based mixture quantification studies, especially when collecting a large training dataset with high quality is challenging or resource-intensive.


title: A continuous family of fully-frustrated Heisenberg model on the Kagome lattice

abstract: We find that the antiferromagnetic Heisenberg model on the Kagome lattice with nearest neighboring exchange coupling(NN-KAFH) belongs to a continuous family of fully-frustrated Heisenberg model on the Kagome lattice, which has no preferred classical ordering pattern. The model within this family consists of the first, second and the third neighboring exchange coupling $J_{1}$, $J_{2}$, and $J_{3}$, with $J_{2}=J_{3}$. We find that when $-J_{1}\leq J_{2}=J_{3}\leq 0.2J_{1}$, the lowest band of $J(\mathbf{q})$, namely, the Fourier transform of the exchange coupling, is totally non-dispersive. Exact diagonalization calculation indicates that the ground state of the spin-$\frac{1}{2}$ NN-KAFH is locally stable under the perturbation of $J_{2}$ and $J_{3}$ when and only when $J_{2}=J_{3}$. Interestingly, we find that the same flat band physics is also playing an important role in the RVB description of the spin liquid state on the Kagome lattice. In particular, we show that the extensively studied $U(1)$ Dirac spin liquid state on the Kagome lattice can actually be generated from a continuous family of gauge inequivalent RVB mean field ansatz, which host very different mean field spinon dispersion.


title: Minimal length and the flow of entropy from black holes

abstract: The existence of a minimal length, predicted by different theories of quantum gravity, can be phenomenologically described in terms of a generalized uncertainty principle. We consider the impact of this quantum gravity motivated effect onto the information budget of a black hole and the sparsity of Hawking radiation during the black hole evaporation process. We show that the information is not transmitted at the same rate during the final stages of the evaporation and that the Hawking radiation is not sparse anymore when the black hole approaches the Planck mass.


title: News on the nuclear structure of neutron-rich nuclei at and beyond N=28

abstract: The nuclear potential and resulting shell structure are well established for the valley of stability, however, dramatic modifications to the familiar ordering of single-particle orbitals in rare isotopes with a large imbalance of proton and neutron numbers have been found: new shell gaps emerge and conventional magic numbers are no longer valid. This article outlines some of the recent in-beam gamma-ray spectroscopy measurements at NSCL aimed at shedding light on the evolution of nuclear structure around neutron number N = 28 in neutron-rich Ar and S isotopes.


title: Gravitational energy is well defined

abstract: The energy of gravitating systems has been an issue since Einstein proposed general relativity: considered to be ill defined, having no proper local density. Energy-momentum is now regarded as \emph{quasi-local} (associated with a closed 2-surface). We consider the pseudotensor and quasi-local proposals in the Lagrangian-Noether-Hamiltonian formulations. There are two ambiguities: (i) many expressions, (ii) each depends on some non-dynamical structure, e.g., a reference frame. The Hamiltonian approach gives a handle on both problems. Our remarkable discovery is that with a 4D isometric Minkowski reference a large class of expressions---those that agree with the Einstein pseudotensor's Freud superpotential to linear order---give a common quasi-local energy value. With a best-matched reference on the boundary this value is the non-negative Wang-Yau mass.


title: Left counital Hopf algebras on free Nijenhuis algebras

abstract: Factorization in algebra is an important problem. In this paper, we first obtain a unique factorization in free Nijenhuis algebras. By using of this unique factorization, we then define a coproduct and a left counital bialgebraic structure on a free Nijenhuis algebra. Finally, we prove that this left counital bialgebra is connected and hence obtain a left counital Hopf algebra on a free Nijenhuis algebra.


title: Two-Stream Adaptive Graph Convolutional Networks for Skeleton-Based Action Recognition

abstract: In skeleton-based action recognition, graph convolutional networks (GCNs), which model the human body skeletons as spatiotemporal graphs, have achieved remarkable performance. However, in existing GCN-based methods, the topology of the graph is set manually, and it is fixed over all layers and input samples. This may not be optimal for the hierarchical GCN and diverse samples in action recognition tasks. In addition, the second-order information (the lengths and directions of bones) of the skeleton data, which is naturally more informative and discriminative for action recognition, is rarely investigated in existing methods. In this work, we propose a novel two-stream adaptive graph convolutional network (2s-AGCN) for skeleton-based action recognition. The topology of the graph in our model can be either uniformly or individually learned by the BP algorithm in an end-to-end manner. This data-driven method increases the flexibility of the model for graph construction and brings more generality to adapt to various data samples. Moreover, a two-stream framework is proposed to model both the first-order and the second-order information simultaneously, which shows notable improvement for the recognition accuracy. Extensive experiments on the two large-scale datasets, NTU-RGBD and Kinetics-Skeleton, demonstrate that the performance of our model exceeds the state-of-the-art with a significant margin.


title: Numerical analyses of emission of a single-photon pulse based on single-atom cavity quantum electrodynamics

abstract: We numerically investigate an on-demand single-photon source, which is implemented with a strongly coupled atom-cavity system, proposed by Kuhn {\it et al}., Appl. Phys. B \textbf{69}, 373 (1999). In the scheme of Kuhn {\it et al}., a $\Lambda$-type three-level atom is captured in a single-mode optical cavity. Considering the three atomic levels, the ground state $u$, the first excited state $g$ accompanying the cavity mode, and the second excited state $e$, in the $\Lambda$-configuration, we assume that a classical field and a quantized cavity field lead to the transition between $u$ and $e$ and that between $e$ and $g$, respectively. The classical light pulse rising sufficiently slowly triggers an adiabatic process of the system and lets a single photon of the cavity mode emerge. We simulate this adiabatic evolution and transmission of the single photon through an imperfect mirror of the cavity using the master equation. We concentrate on examining physical properties of the efficiency of single-photon generation, the fluctuation of the duration of the photon emission, and the time of the emission measured from a peak of the trigger pulse. We find a function that approximates to the efficiency closely and the upper bound of the fluctuation of the duration.


title: RGB-Depth SLAM Review

abstract: Simultaneous Localization and Mapping (SLAM) have made the real-time dense reconstruction possible increasing the prospects of navigation, tracking, and augmented reality problems. Some breakthroughs have been achieved in this regard during past few decades and more remarkable works are still going on. This paper presents an overview of SLAM approaches that have been developed till now. Kinect Fusion algorithm, its variants, and further developed approaches are discussed in detailed. The algorithms and approaches are compared for their effectiveness in tracking and mapping based on Root Mean Square error over online available datasets.


title: The UN Parallel Corpus Annotated for Translation Direction

abstract: This work distinguishes between translated and original text in the UN protocol corpus. By modeling the problem as classification problem, we can achieve up to 95% classification accuracy. We begin by deriving a parallel corpus for different language-pairs annotated for translation direction, and then classify the data by using various feature extraction methods. We compare the different methods as well as the ability to distinguish between translated and original texts in the different languages. The annotated corpus is publicly available.


title: Density-Adaptive Kernel based Efficient Reranking Approaches for Person Reidentification

abstract: Person reidentification (ReID) refers to the task of verifying the identity of a pedestrian observed from nonoverlapping views in a surveillance camera network. It has recently been validated that reranking can achieve remarkable performance improvements in person ReID systems. However, current reranking approaches either require feedback from users or suffer from burdensome computational costs. In this paper, we propose to exploit a density-adaptive smooth kernel technique to achieve efficient and effective reranking. Specifically, we adopt a smooth kernel function to formulate the neighbor relationships among data samples with a density-adaptive parameter. Based on this new formulation, we present two simple yet effective reranking methods, termed \emph{inverse} density-adaptive kernel based reranking (inv-DAKR) and \emph{bidirectional} density-adaptive kernel based reranking (bi-DAKR), in which the local density information in the vicinity of each gallery sample is elegantly exploited. Moreover, we extend the proposed inv-DAKR and bi-DAKR methods to incorporate the available extra probe samples and demonstrate that when and why these extra probe samples are able to improve the local neighborhood and thus further refine the ranking results. Extensive experiments are conducted on six benchmark datasets, including: PRID450s, VIPeR, CUHK03, GRID, Market-1501 and Mars. The experimental results demonstrate that our proposals are effective and efficient.


title: Network synchronization with periodic coupling

abstract: The synchronization behavior of networked chaotic oscillators with periodic coupling is investigated. It is observed in simulations that the network synchronizability could be significantly influenced by tuning the coupling frequency, even making the network alternated between the synchronous and non-synchronous states. By the method of master stability function, we conduct a detailed analysis on the influence of coupling frequency on network synchronizability, and find that the network synchronizability is maximized at some characteristic frequencies comparable to the intrinsic frequency of the local dynamics. Moremore, it is found that as the amplitude of the coupling increases, the characteristic frequencies are gradually decreased. By the technique of finite-time Lyapunov exponent, we investigate further the mechanism for the maximized synchronizability, and find that at the characteristic frequencies the power spectrum of the finite-time Lyapunov exponent is abruptly changed from the localized to broad distributions. When this feature is absent or not prominent, the network synchronizability is less influenced by the periodic coupling. Our study shows the efficiency of finite-time Lyapunov exponent in exploring the synchronization behavior of temporally coupled oscillators, and sheds lights on the interplay between the system dynamics and structure in the general temporal networks.


title: A Doob-type maximal inequality and its applications to various stochastic processes

abstract: We generalize the notion of the submartingale property and Doob's inequality. Furthermore, we show how the latter leads to new inequalities for several stochastic processes: certain time series, Levy processes, random walks, processes with independent increments, branching processes and continuous state branching processes, branching diffusions and superdiffusions, as well as some Markov processes, including geometric Brownian motion.


title: Energy-minimizing maps from manifolds with nonnegative Ricci curvature

abstract: The energy of any $C^1$ representative of a homotopy class of maps from a compact and connected Riemannian manifold with nonnegative Ricci curvature into a complete Riemannian manifold with no conjugate points is bounded below by a constant determined by the asymptotic geometry of the target, with equality if and only if the original map is totally geodesic. This conclusion also holds under the weaker assumption that the domain is finitely covered by a diffeomorphic product, and its universal covering space splits isometrically as a product with a flat factor, in a commutative diagram that follows from the Cheeger-Gromoll splitting theorem.


title: Predicting drug response of tumors from integrated genomic profiles by deep neural networks

abstract: The study of high-throughput genomic profiles from a pharmacogenomics viewpoint has provided unprecedented insights into the oncogenic features modulating drug response. A recent screening of ~1,000 cancer cell lines to a collection of anti-cancer drugs illuminated the link between genotypes and vulnerability. However, due to essential differences between cell lines and tumors, the translation into predicting drug response in tumors remains challenging. Here we proposed a DNN model to predict drug response based on mutation and expression profiles of a cancer cell or a tumor. The model contains a mutation and an expression encoders pre-trained using a large pan-cancer dataset to abstract core representations of high-dimension data, followed by a drug response predictor network. Given a pair of mutation and expression profiles, the model predicts IC50 values of 265 drugs. We trained and tested the model on a dataset of 622 cancer cell lines and achieved an overall prediction performance of mean squared error at 1.96 (log-scale IC50 values). The performance was superior in prediction error or stability than two classical methods and four analog DNNs of our model. We then applied the model to predict drug response of 9,059 tumors of 33 cancer types. The model predicted both known, including EGFR inhibitors in non-small cell lung cancer and tamoxifen in ER+ breast cancer, and novel drug targets. The comprehensive analysis further revealed the molecular mechanisms underlying the resistance to a chemotherapeutic drug docetaxel in a pan-cancer setting and the anti-cancer potential of a novel agent, CX-5461, in treating gliomas and hematopoietic malignancies. Overall, our model and findings improve the prediction of drug response and the identification of novel therapeutic options.


title: Lightweight Unsupervised Deep Loop Closure

abstract: Robust efficient loop closure detection is essential for large-scale real-time SLAM. In this paper, we propose a novel unsupervised deep neural network architecture of a feature embedding for visual loop closure that is both reliable and compact. Our model is built upon the autoencoder architecture, tailored specifically to the problem at hand. To train our network, we inflict random noise on our input data as the denoising autoencoder does, but, instead of applying random dropout, we warp images with randomized projective transformations to emulate natural viewpoint changes due to robot motion. Moreover, we utilize the geometric information and illumination invariance provided by histogram of oriented gradients (HOG), forcing the encoder to reconstruct a HOG descriptor instead of the original image. As a result, our trained model extracts features robust to extreme variations in appearance directly from raw images, without the need for labeled training data or environment-specific training. We perform extensive experiments on various challenging datasets, showing that the proposed deep loop-closure model consistently outperforms the state-of-the-art methods in terms of effectiveness and efficiency. Our model is fast and reliable enough to close loops in real time with no dimensionality reduction, and capable of replacing generic off-the-shelf networks in state-of-the-art ConvNet-based loop closure systems.


title: A note on the writhe polynomial and the virtual crossing number

abstract: In this note we give a new lower bound on the virtual crossing number via the writhe polynomial, which refines a result of B. Mellor. The proof is based on a new interpretation of the writhe polynomial. The characterization of the writhe polynomial is also discussed.


title: The Hard State of the Highly Absorbed High Inclination Black Hole Binary Candidate Swift J1658.2-4242 Observed by NuSTAR and Swift

abstract: We present a spectral and timing analysis of the newly reported Galactic X-ray transient Swift J1658.2-4242 observed by NuSTAR and Swift. The broad-band X-ray continuum is typical of a black hole binary in the bright hard state, with a photon index of $\Gamma=1.63\pm0.02$ and a low coronal temperature of $kT_{\rm e}=22\pm1$ keV, corresponding to a low spectral cutoff well constrained by NuSTAR. Spectral modeling of the relativistic disk reflection features, consisting of a broad Fe K$\alpha$ line and the Compton reflection hump, reveals that the black hole is rapidly spinning with the spin parameter of $a^{*}>0.96$, and the inner accretion disk is viewed at a high inclination angle of $i=64^{+2}_{-3}{^\circ}$ (statistical errors, 90% confidence). The high inclination is independently confirmed by dips in the light curves, which can be explained by absorbing material located near the disk plane temporarily obscuring the central region. In addition, we detect an absorption line in the NuSTAR spectra centered at $7.03^{+0.04}_{-0.03}$ keV. If associated with ionized Fe K absorption lines, this provides evidence for the presence of outflowing material in the low/hard state of a black hole binary candidate. A timing analysis shows the presence of a type-C QPO in the power spectrum, with the frequency increasing from $\sim0.14$ Hz to $\sim0.21$ Hz during the single NuSTAR exposure. Our analysis reveals that Swift J1658.2-4242 displays characteristics typical for a black hole binary that is viewed at a high inclination angle, making it a good system for studying the accretion geometry in black hole binaries.


title: Object Localization with a Weakly Supervised CapsNet

abstract: Inspired by CapsNet's routing-by-agreement mechanism with its ability to learn object properties, we explore if those properties in turn can determine new properties of the objects, such as the locations. We then propose a CapsNet architecture with object coordinate atoms and a modified routing-by-agreement algorithm with unevenly distributed initial routing probabilities. The model is based on CapsNet but uses a routing algorithm to find the objects' approximate positions in the image coordinate system. We also discussed how to derive the property of translation through coordinate atoms and we show the importance of sparse representation. We train our model on the single moving MNIST dataset with class labels. Our model can learn and derive the coordinates of the digits better than its convolution counterpart that lacks a routing-by-agreement algorithm, and can also perform well when testing on the multi-digit moving MNIST and KTH datasets. The results show our method reaches the state-of-art performance on object localization without any extra localization techniques and modules as in prior work.


title: Imaging and spectral performance of CdTe double-sided strip detectors for the Hard X-ray Imager onboard ASTRO-H

abstract: The imaging and spectral performance of CdTe double-sided strip detectors (CdTe-DSDs) was evaluated for the ASTRO-H mission. The charcterized CdTe-DSDs have a strip pitch of 0.25 mm, an imaging area of 3.2 cm$\times$3.2 cm and a thickness of 0.75 mm. The detector was successfully operated at a temperature of $-20^\circ$C and with an applied bias voltage of 250 V. By using two-strip events as well as one-strip events for the event reconstruction, a good energy resolution of 2.0 keV at 59.5 keV and a sub-strip spatial resolution was achieved. The hard X-ray and gamma-ray response of CdTe-DSDs is complex due to the properties of CdTe and the small pixel effect. Therefore, one of the issues to investigate is the response of the CdTe-DSD. In order to investigate the spatial dependence of the detector response, we performed fine beam scan experiments at SPring-8, a synchrotron radiation facility. From these experiments, the depth structure of the electric field was determined as well as properties of carriers in the detector and successfully reproduced the experimental data with simulated spectra.


title: A Lyapunov-based Approach to Safe Reinforcement Learning

abstract: In many real-world reinforcement learning (RL) problems, besides optimizing the main objective function, an agent must concurrently avoid violating a number of constraints. In particular, besides optimizing performance it is crucial to guarantee the safety of an agent during training as well as deployment (e.g. a robot should avoid taking actions - exploratory or not - which irrevocably harm its hardware). To incorporate safety in RL, we derive algorithms under the framework of constrained Markov decision problems (CMDPs), an extension of the standard Markov decision problems (MDPs) augmented with constraints on expected cumulative costs. Our approach hinges on a novel \emph{Lyapunov} method. We define and present a method for constructing Lyapunov functions, which provide an effective way to guarantee the global safety of a behavior policy during training via a set of local, linear constraints. Leveraging these theoretical underpinnings, we show how to use the Lyapunov approach to systematically transform dynamic programming (DP) and RL algorithms into their safe counterparts. To illustrate their effectiveness, we evaluate these algorithms in several CMDP planning and decision-making tasks on a safety benchmark domain. Our results show that our proposed method significantly outperforms existing baselines in balancing constraint satisfaction and performance.


title: Dynamically Unfolding Recurrent Restorer: A Moving Endpoint Control Method for Image Restoration

abstract: In this paper, we propose a new control framework called the moving endpoint control to restore images corrupted by different degradation levels in one model. The proposed control problem contains a restoration dynamics which is modeled by an RNN. The moving endpoint, which is essentially the terminal time of the associated dynamics, is determined by a policy network. We call the proposed model the dynamically unfolding recurrent restorer (DURR). Numerical experiments show that DURR is able to achieve state-of-the-art performances on blind image denoising and JPEG image deblocking. Furthermore, DURR can well generalize to images with higher degradation levels that are not included in the training stage.


title: Study of the rare earth effects on the magnetic fluctuations in RbLn$_2$Fe$_4$As$_4$O$_2$ (Ln = Tb, Dy and Ho) by M\"ossbauer spectroscopy

abstract: In the current work, we report the investigation of RbLn$_2$Fe$_4$As$_4$O$_2$ (Ln = Tb, Dy and Ho) and RbFe$_2$As$_2$ by $^{57}$Fe M\"ossbauer spectroscopy. Singlet pattern has been observed for all the samples indicating the absence of static magnetic ordering down to 5.9\,K on the Fe sublattice. The observed intermediate value of the isomer shift confirms the effective self charge transfer effect for the studied superconductors. Debye temperatures of these samples have been determined by the temperature dependence of the isomer shift. Most importantly, we observe different spectral line width broadening behaviors for samples with different rare earth elements, and no line width broadenings for samples Ln=Tb and Ho. These results suggest that the observed magnetic fluctuations at the Fe site might be sensitive to the magnetic behaviors of the rare earth magnetic moments.


title: Analytic representation of discrete and continuous mechanical systems

abstract: We investigate how the theory of self-adjoint differential equations alone can be used to provide a satisfactory solution of the inverse vatiational problem. For the discrete system, the self-adjoint form of the Newtonian equation allows one to find an explicitly time-dependent Lagrangian representation. On the other hand, the same Newtonian equation in conjunction with its adjoint forms a natural basis to construct an explicitly time-independent analytic representation of the system. This approach when applied to the equation of damped harmonic oscillator help one disclose the mathematical origin of the Bateman image equation. We have made use of a continuum analog of the same approach to find the Lagrangian or analytic representation of nonlinear evolution equations.


title: A new electron-multiplier-tube-based beam monitor for muon monitoring at the T2K experiment

abstract: Muon beam monitoring is indispensable for indirectly monitoring accelerator-produced neutrino beams in real time. Though Si photodiodes and ionization chambers have been successfully used as muon monitors at the T2K experiment, sensors that are more radiation tolerant are desired for future operation. We have investigated the electron-multiplier tube (EMT) as a new sensor for muon monitoring. Secondary electrons produced by the passage of muons at dynodes are multiplied in the tube and produce signal. Two prototype detectors were installed at the T2K muon monitor location, and various EMT properties were studied based on in situ data taken with the T2K muon beam. The signal size is as expected based on calculation, and the EMTs show a sufficiently fast time response for bunch-by-bunch beam monitoring. The spill-by-spill intensity resolution is 0.4%, better than the required value (1%). Signal linearity within $\pm$1% is achieved at proton beam powers up to 460 kW (with +250 kA focusing horn operation). A gradual signal decrease was observed during the initial exposure, due to the stabilization of dynode materials, before the response became stable within $\pm$1%. This work demonstrates that EMTs are a good candidate for future muon monitoring at T2K, and may also have other more general applications.


title: Spin structure of heavy-quark hybrids

abstract: A unique feature of quantum chromodynamics (QCD), the theory of strong interactions, is the possibility for gluonic degrees of freedom to participate in the construction of physical hadrons, which are color singlets, in an analogous manner to valence quarks. Hadrons with no valence quarks are called glueballs, while hadrons where both gluons and valence quarks combine to form a color singlet are called hybrids. The unambiguous identification of such states among the experimental hadron spectrum has been thus far not possible. Glueballs are particularly difficult to establish experimentally since the lowest lying ones are expected to strongly mix with conventional mesons. On the other hand, hybrids should be easier to single out because the set of quantum numbers available to their lowest excitations may be exotic, i.e., not realized in conventional quark-antiquark systems. Particularly promising for discovery appear to be heavy hybrids, which are made of gluons and a heavy-quark-antiquark pair (charm or bottom). In the heavy-quark sector systematic tools can be used that are not available in the light-quark sector. In this paper we use a nonrelativistic effective field theory to uncover for the first time the full spin structure of heavy-quark hybrids up to $1/m^2$-terms in the heavy-quark-mass expansion. We show that such terms display novel characteristics at variance with our consolidated experience on the fine and hyperfine splittings in atomic, molecular and nuclear physics. We determine the nonperturbative contributions to the matching coefficients of the effective field theory by fitting our results to lattice-QCD determinations of the charmonium hybrid spectrum and extrapolate the results to the bottomonium hybrid sector where lattice-QCD determinations are still challenging.


title: On a General Class of Discrete Bivariate Distributions

abstract: In this paper we develop a very general class of bivariate discrete distributions. The basic idea is very simple. The marginals are obtained by taking the random geometric sum of a baseline distribution function. The proposed class of distributions is a very flexible class of distributions in the sense the marginals can take variety of shapes. It can be multimodal as well as heavy tailed also. It can be both over dispersed as well as under dispersed. Moreover, the correlation can be of a wide range. We discuss different properties of the proposes class of bivariate distributions. The proposed distribution has some interesting physical interpretations also. Further, we consider two specific base line distributions namely; Poisson and negative binomial distributions for illustrative purposes. Both of them are infinitely divisible. The maximum likelihood estimators of the unknown parameters cannot be obtained in closed form. They can be obtained by solving three and five dimensional non-linear optimizations problems, respectively. To avoid that we propose to use the method of moment estimators and they can be obtained quite conveniently. The analyses of two real data sets have been performed to show the effectiveness of the proposed class of models. Finally, we discuss some open problems and conclude the paper.


title: An Online RFID Localization in the Manufacturing Shopfloor

abstract: {Radio Frequency Identification technology has gained popularity for cheap and easy deployment. In the realm of manufacturing shopfloor, it can be used to track the location of manufacturing objects to achieve better efficiency. The underlying challenge of localization lies in the non-stationary characteristics of manufacturing shopfloor which calls for an adaptive life-long learning strategy in order to arrive at accurate localization results. This paper presents an evolving model based on a novel evolving intelligent system, namely evolving Type-2 Quantum Fuzzy Neural Network (eT2QFNN), which features an interval type-2 quantum fuzzy set with uncertain jump positions. The quantum fuzzy set possesses a graded membership degree which enables better identification of overlaps between classes. The eT2QFNN works fully in the evolving mode where all parameters including the number of rules are automatically adjusted and generated on the fly. The parameter adjustment scenario relies on decoupled extended Kalman filter method. Our numerical study shows that eT2QFNN is able to deliver comparable accuracy compared to state-of-the-art algorithms.


title: Inverse eigenvalues problem of nonnegative matrices via unit lower triangular matrices

abstract: The main of this work is to use the unit lower triangular matrices for solving inverse eigenvalue problem of nonnegative matrices and present the easier method to solve this problem.


title: Comparison of three methods to compute optical absorption spectra of organic molecules and solids

abstract: We compare the performance of an approach using real frequency dependent polarizability to compute optical absorption spectra to linear-response time-dependent density functional theory (TD-DFT) for small organic dyes, oligomers of different length (oligothiophenes), and molecular clusters representing a molecular crystal (pentacene). For pentacene, the spectra computed with the two methods are also compared to the spectrum computed for clusters and the periodic solid using the dipole approximation. The approach based on real polarizability produces spectra in good agreement with TD-DFT for small molecules. The (artificial) redshift for longer oligomers is more significant with the polarizability-based method than with TD-DFT. For pentacene clusters, TD-DFT produces reasonable spectra with a hybrid functional, but a significant redshift is introduced with a GGA functional due to the presence of charge transfer transitions. This problem is slightly attenuated with the polarizability-based method. The dipole approximation results in spectra much redshifted vs both TD-DFT and the polarizability-based method and in a different trend with cluster size.


title: CIAO: Cache Interference-Aware Throughput-Oriented Architecture and Scheduling for GPUs

abstract: A modern GPU aims to simultaneously execute more warps for higher Thread-Level Parallelism (TLP) and performance. When generating many memory requests, however, warps contend for limited cache space and thrash cache, which in turn severely degrades performance. To reduce such cache thrashing, we may adopt cache locality-aware warp scheduling which gives higher execution priority to warps with higher potential of data locality. However, we observe that warps with high potential of data locality often incurs far more cache thrashing or interference than warps with low potential of data locality. Consequently, cache locality-aware warp scheduling may undesirably increase cache interference and/or unnecessarily decrease TLP. In this paper, we propose Cache Interference-Aware throughput-Oriented (CIAO) on-chip memory architecture and warp scheduling which exploit unused shared memory space and take insight opposite to cache locality-aware warp scheduling. Specifically, CIAO on-chip memory architecture can adaptively redirect memory requests of severely interfering warps to unused shared memory space to isolate memory requests of these interfering warps from those of interfered warps. If these interfering warps still incur severe cache interference, CIAO warp scheduling then begins to selectively throttle execution of these interfering warps. Our experiment shows that CIAO can offer 54% higher performance than prior cache locality-aware scheduling at a small chip cost.


title: Balancing Shared Autonomy with Human-Robot Communication

abstract: Robotic agents that share autonomy with a human should leverage human domain knowledge and account for their preferences when completing a task. This extra knowledge can dramatically improve plan efficiency and user-satisfaction, but these gains are lost if communicating with a robot is taxing and unnatural. In this paper, we show how viewing humanrobot language through the lens of shared autonomy explains the efficiency versus cognitive load trade-offs humans make when deciding how cooperative and explicit to make their instructions.


title: A Deep Structure of Person Re-Identification using Multi-Level Gaussian Models

abstract: Person re-identification is being widely used in the forensic, and security and surveillance system, but person re-identification is a challenging task in real life scenario. Hence, in this work, a new feature descriptor model has been proposed using a multilayer framework of Gaussian distribution model on pixel features, which include color moments, color space values and Schmid filter responses. An image of a person usually consists of distinct body regions, usually with differentiable clothing followed by local colors and texture patterns. Thus, the image is evaluated locally by dividing the image into overlapping regions. Each region is further fragmented into a set of local Gaussians on small patches. A global Gaussian encodes, these local Gaussians for each region creating a multi-level structure. Hence, the global picture of a person is described by local level information present in it, which is often ignored. Also, we have analyzed the efficiency of earlier metric learning methods on this descriptor. The performance of the descriptor is evaluated on four public available challenging datasets and the highest accuracy achieved on these datasets are compared with similar state-of-the-arts, which demonstrate the superior performance.


title: Drinfeld-Gaitsgory-Vinberg interpolation Grassmannian and geometric Satake equivalence (with appendix by Dennis Gaitsgory)

abstract: Let $G$ be a reductive complex algebraic group. We fix a pair of opposite Borel subgroups and consider the corresponding semiinfinite orbits in the affine Grassmannian $Gr_G$. We prove Simon Schieder's conjecture identifying his bialgebra formed by the top compactly supported cohomology of the intersections of opposite semiinfinite orbits with $U(\check{\mathfrak n})$ (the universal enveloping algebra of the positive nilpotent subalgebra of the Langlands dual Lie algebra $\check{\mathfrak g}$). To this end we construct an action of Schieder bialgebra on the geometric Satake fiber functor. We propose a conjectural construction of Schieder bialgebra for an arbitrary symmetric Kac-Moody Lie algebra in terms of Coulomb branch of the corresponding quiver gauge theory.


title: Task-Agnostic Meta-Learning for Few-shot Learning

abstract: Meta-learning approaches have been proposed to tackle the few-shot learning problem.Typically, a meta-learner is trained on a variety of tasks in the hopes of being generalizable to new tasks. However, the generalizability on new tasks of a meta-learner could be fragile when it is over-trained on existing tasks during meta-training phase. In other words, the initial model of a meta-learner could be too biased towards existing tasks to adapt to new tasks, especially when only very few examples are available to update the model. To avoid a biased meta-learner and improve its generalizability, we propose a novel paradigm of Task-Agnostic Meta-Learning (TAML) algorithms. Specifically, we present an entropy-based approach that meta-learns an unbiased initial model with the largest uncertainty over the output labels by preventing it from over-performing in classification tasks. Alternatively, a more general inequality-minimization TAML is presented for more ubiquitous scenarios by directly minimizing the inequality of initial losses beyond the classification tasks wherever a suitable loss can be defined.Experiments on benchmarked datasets demonstrate that the proposed approaches outperform compared meta-learning algorithms in both few-shot classification and reinforcement learning tasks.


title: Minimax Lower Bounds for Cost Sensitive Classification

abstract: The cost-sensitive classification problem plays a crucial role in mission-critical machine learning applications, and differs with traditional classification by taking the misclassification costs into consideration. Although being studied extensively in the literature, the fundamental limits of this problem are still not well understood. We investigate the hardness of this problem by extending the standard minimax lower bound of balanced binary classification problem (due to \cite{massart2006risk}), and emphasize the impact of cost terms on the hardness.


title: Hardness of Segment Cover, Contiguous SAT and Visibility with Uncertain Obstacles

abstract: We define the problem segment cover as follows. We are given a set of pairs of sub-intervals of the unit interval. The problem asks if there is a choice of a single interval from each pair such that the union of the chosen intervals covers the entire unit interval. This problem arises naturally while attempting to compute visibility between a point and a line segment in the plane in the presence of uncertain obstacles. Segment cover is equivalent to a restricted version of SAT which we call contiguous SAT. Consider a SAT with the following restrictions. An input formula is in CNF form and an ordering of the clauses is given in which clauses containing any fixed literal appear contiguously. We call this restricted problem contiguous SAT. Our main result is that the problems segment cover and contiguous SAT are NP-hard. We also discuss hardness of approximation for these problems.


title: Human-guided data exploration using randomisation

abstract: An explorative data analysis system should be aware of what the user already knows and what the user wants to know of the data: otherwise the system cannot provide the user with the most informative and useful views of the data. We propose a principled way to do exploratory data analysis, where the user's background knowledge is modeled by a distribution parametrised by subsets of rows and columns in the data, called tiles. The user can also use tiles to describe his or her interests concerning relations in the data. We provide a computationally efficient implementation of this concept based on constrained randomisation. The implementation is used to model both the background knowledge and the user's information request and is a necessary prerequisite for any interactive system. Furthermore, we describe a novel linear projection pursuit method to find and show the views most informative to the user, which at the limit of no background knowledge and with generic objectives reduces to PCA. We show that our method is robust under noise and fast enough for interactive use. We also show that the method gives understandable and useful results when analysing real-world data sets. We will release an open source library implementing the idea, including the experiments presented in this paper. We show that our method can outperform standard projection pursuit visualisation methods in exploration tasks. Our framework makes it possible to construct human-guided data exploration systems which are fast, powerful, and give results that are easy to comprehend.