OpenRaiser/Intern-Atlas huggingface dataset:
TBC-Net: A real-time detector for infrared small target detection using semantic constraint
Venue: arXiv cs.CV 2019
Year: 2019

Infrared small target detection is a key technique in infrared search and tracking (IRST) systems. Although deep learning has been widely used in the vision tasks of visible light images recently, it is rarely used in infrared small target detection due to the difficulty in learning small target features. In this paper, we propose a novel lightweight convolutional neural network TBC-Net for infrared small target detection. The TBCNet consists of a target extraction module (TEM) and a semantic constraint module (SCM), which are used to extract small targets from infrared images and to classify the extracted target images during the training, respectively. Meanwhile, we propose a joint loss function and a training method. The SCM imposes a semantic constraint on TEM by combining the high-level classification task and solve the problem of the difficulty to learn features caused by class imbalance problem. During the training, the targets are extracted from the input image and then be classified by SCM. During the inference, only the TEM is used to detect the small targets. We also propose a data synthesis method to generate training data. The experimental results show that compared with the traditional methods, TBC-Net can better reduce the false alarm caused by complicated background, the proposed network structure and joint loss have a significant improvement on small target feature learning. Besides, TBC-Net can achieve real-time detection on the NVIDIA Jetson AGX Xavier development board, which is suitable for applications such as field research with drones equipped with infrared sensors.
Cross Layer Design for Maximizing Network Utility in Multiple Gateways Wireless Mesh Networks
Venue: arXiv cs.NI 2019
Year: 2019

We investigate the problem of network utility maximization in multiple gateways wireless mesh networks by considering Signal to Interference plus Noise Ratio (SINR) as the interference model. The aim is a cross layer design that considers joint rate control, traffic splitting, routing, scheduling, link rate allocation and power control to formulate the network utility maximization problem. As this problem is computationally complex, we propose the Joint dynamic Gateway selection, link Rate allocation and Power control (JGRP) algorithm based on the differential backlog as a sub-optimal solution. This algorithm first constructs the initial network topology, and then in each time slot, determines the generation rate and destination gateway of each traffic flow, simultaneously. The other main task of this algorithm is joint routing, scheduling, links rate allocation and node power allocation in each time slot. Moreover, for improving the fairness, we propose some new parameters instead of the differential backlog in JGRP algorithm. Simulation results show that using the proposed parameters in JGRP algorithm improves fairness from throughput and delay point of views.
Blockchain as a Service for Multi-Access Edge Computing: A Deep Reinforcement Learning Approach
Venue: arXiv cs.NI 2019
Year: 2019

Recently, blockchain has gained momentum in the academic community thanks to its decentralization, immutability, transparency and security. As an emerging paradigm, Multi-access Edge Computing (MEC) has been widely used to provide computation and storage resources to mobile user equipments (UE) at the edge of the network for improving the performance of mobile applications. In this paper, we propose a novel blockchain-based MEC architecture where UEs can offload their computation tasks to the MEC servers. In particular, a blockchain network is deployed and hosted on the MEC platform as Blockchain as a Service (BaaS) that supports smart contract-based resource trading and transaction mining services for mobile task offloading. To enhance the performance of the blockchain-empowered MEC system, we propose a joint scheme of computation offloading and blockchain mining. Accordingly, an optimization problem is formulated to maximize edge service revenue and blockchain mining reward while minimizing the service computation latency with respect to constraints of user service demands and hash power resource. We then propose a novel Deep Reinforcement Learning (DRL) approach using a double deep Q-network (DQN) algorithm to solve the proposed problem. Numerical results demonstrate that the proposed scheme outperforms the other baseline methods in terms of better system utility with computational efficiency. Experiment results also verify that the trading contract design is efficient with low operation cost, showing the feasibility of the proposed scheme.
Testability of Reversible Iterative Logic Arrays
Venue: arXiv cs.OH 2020
Year: 2020

Iterative Logic Arrays (ILAs) are ideal as VLSI sub-systems because of their regular structure and its close resemblance with FPGAs (Field Programmable Gate Arrays). Reversible circuits are of interest in the design of very low power circuits where energy loss implied by high frequency switching is not of much consideration. Reversibility is essential for Quantum Computing. This paper examines the testability of Reversible Iterative Logic Arrays (ILAs) composed of reversible k-CNOT gates. For certain ILAs it is possible to find a test set whose size remains constant irrespective of the size of the ILA, while for others it varies with array size. Former type of ILAs is known as Constant-Testable, i.e. C-Testable. It has been shown that Reversible Logic Arrays are C-Testable and size of test set is equal to number of entries in cells truth table implying that the reversible ILAs are also Optimal-Testable, i.e. O-Testable. Uniform-Testability, i.e. U-Testability has been defined and Reversible Heterogeneous ILAs have been characterized as U-Testable. The test generation problem has been shown to be related to certain properties of cycles in a set of graphs derived from cell truth table. By careful analysis of these cycles an efficient test generation technique that can be easily converted to an ATPG program has been presented for both 1-D and 2D ILAs. The same algorithms can be easily extended for n-Dimensional Reversible ILAs.
Approximating Tverberg Points in Linear Time for Any Fixed Dimension
Venue: arXiv cs.CG 2020
Year: 2020

Let P be a d-dimensional n-point set. A Tverberg-partition of P is a partition of P into r sets P_1, ..., P_r such that the convex hulls conv(P_1), ..., conv(P_r) have non-empty intersection. A point in the intersection of the conv(P_i)'s is called a Tverberg point of depth r for P. A classic result by Tverberg implies that there always exists a Tverberg partition of size n/(d+1), but it is not known how to find such a partition in polynomial time. Therefore, approximate solutions are of interest. We describe a deterministic algorithm that finds a Tverberg partition of size n/4(d+1)^3 in time d^{O(log d)} n. This means that for every fixed dimension we can compute an approximate Tverberg point (and hence also an approximate centerpoint) in linear time. Our algorithm is obtained by combining a novel lifting approach with a recent result by Miller and Sheehy (2010).
Zur iterativen Loesung von linearen Gleichungssystemen
Venue: arXiv cs.NA 2020
Year: 2020

It is well known that a fixed point iteration for solving a linear equation system converges if and only if the spectral radius of the iteration matrix is less than one. A method is presented which guarantees the Fixed Point, even if this condition is not ("spectral radius <1") fulfilled and demonstrated through calculation examples.
A Perceptual Alphabet for the 10-dimensional Phonetic-prosodic Space
Venue: arXiv cs.SD 2020
Year: 2020

We define an alphabet, the IHA, of the 10-D phonetic-prosodic space. The dimensions of this space are perceptual observables, rather than articulatory specifications. Speech is defined as a random chain in time of the 4-D phonetic subspace, that is, a symbolic sequence, augmented with diacritics of the remaining 6-D prosodic subspace. The definitions here are based on the model of speech of oral billiards, and supersedes an earlier version. This paper only enumerates the IHA in detail as a supplement to the exposition of oral billiards in a separate paper. The IHA has been implemented as the target random variable in a speech recognizer.
On the Heisenberg principle at macroscopic scales: understanding classical negative information. Towards a general physical theory of information
Venue: arXiv cs.IT 2020
Year: 2020

With the aid of a toy model, the Monty Hall Problem (MHP), the counterintuitive and theoretically problematic concept of negative information in classical systems is well understood. It is shown that, as its quantum counterpart, classical local mutual information, obtained through a measurement, can be expressed as the difference between the information gained with the evidence and the negative information generated due to the inefficiency of the measurement itself; a novel local Shannon metric, the transfer information content, is defined as this difference, which is negative if the measurement generates more disturbance than the evidence, i.e., generates a classical measurement back action. This metric is valid for both, Classical and Quantum measurements, and it is proposed as a starting point towards a general physical theory of information. This information-disturbance trade-off in classical measurements is a kind of Heisenberg principle at macroscopic scales, and it is proposed, as further work, to incorporate this result in the already existing generalized uncertainty principles in the field of quantum gravity.
Complete and Easy Bidirectional Typechecking for Higher-Rank Polymorphism
Venue: arXiv cs.PL 2020
Year: 2020

Bidirectional typechecking, in which terms either synthesize a type or are checked against a known type, has become popular for its scalability (unlike Damas-Milner type inference, bidirectional typing remains decidable even for very expressive type systems), its error reporting, and its relative ease of implementation. Following design principles from proof theory, bidirectional typing can be applied to many type constructs. The principles underlying a bidirectional approach to polymorphism, however, are less obvious. We give a declarative, bidirectional account of higher-rank polymorphism, grounded in proof theory; this calculus enjoys many properties such as eta-reduction and predictability of annotations. We give an algorithm for implementing the declarative system; our algorithm is remarkably simple and well-behaved, despite being both sound and complete.
Towards a Uniform Theory of Effectful State Machines
Venue: arXiv cs.LO 2020
Year: 2020

Using recent developments in coalgebraic and monad-based semantics, we present a uniform study of various notions of machines, e.g. finite state machines, multi-stack machines, Turing machines, valence automata, and weighted automata. They are instances of Jacobs' notion of a T-automaton, where T is a monad. We show that the generic language semantics for T-automata correctly instantiates the usual language semantics for a number of known classes of machines/languages, including regular, context-free, recursively-enumerable and various subclasses of context free languages (e.g. deterministic and real-time ones). Moreover, our approach provides new generic techniques for studying the expressivity power of various machine-based models.
Storage Capacity of Repairable Networks
Venue: arXiv cs.IT 2020
Year: 2020

In this paper, we introduce a model of a distributed storage system that is locally recoverable from any single server failure. Unlike the usual local recovery model of codes for distributed storage, this model accounts for the fact that each server or storage node in a network is connectible to only some, and not all other, nodes. This may happen for reasons such as physical separation, inhomogeneity in storage platforms etc. We estimate the storage capacity of both undirected and directed networks under this model and propose some constructive schemes. From a coding theory point of view, we show that this model is approximately dual of the well-studied index coding problem. Further in this paper, we extend the above model to handle multiple server failures. Among other results, we provide an upper bound on the minimum pairwise distance of a set of words that can be stored in a graph with the local repair guarantee. The well-known impossibility bounds on the distance of locally recoverable codes follow from our result.
Instance Significance Guided Multiple Instance Boosting for Robust Visual Tracking
Venue: arXiv cs.CV 2020
Year: 2020

Multiple Instance Learning (MIL) recently provides an appealing way to alleviate the drifting problem in visual tracking. Following the tracking-by-detection framework, an online MILBoost approach is developed that sequentially chooses weak classifiers by maximizing the bag likelihood. In this paper, we extend this idea towards incorporating the instance significance estimation into the online MILBoost framework. First, instead of treating all instances equally, with each instance we associate a significance-coefficient that represents its contribution to the bag likelihood. The coefficients are estimated by a simple Bayesian formula that jointly considers the predictions from several standard MILBoost classifiers. Next, we follow the online boosting framework, and propose a new criterion for the selection of weak classifiers. Experiments with challenging public datasets show that the proposed method outperforms both existing MIL based and boosting based trackers.
Evacuating Robots from a Disk Using Face-to-Face Communication
Venue: arXiv cs.DS 2020
Year: 2020

Assume that two robots are located at the centre of a unit disk. Their goal is to evacuate from the disk through an exit at an unknown location on the boundary of the disk. At any time the robots can move anywhere they choose on the disk, independently of each other, with maximum speed $1$. The robots can cooperate by exchanging information whenever they meet. We study algorithms for the two robots to minimize the evacuation time: the time when both robots reach the exit. In [CGGKMP14] the authors gave an algorithm defining trajectories for the two robots yielding evacuation time at most $5.740$ and also proved that any algorithm has evacuation time at least $3+ \fracπ{4} + \sqrt{2} \approx 5.199$. We improve both the upper and lower bound on the evacuation time of a unit disk. Namely, we present a new non-trivial algorithm whose evacuation time is at most $5.628$ and show that any algorithm has evacuation time at least $3+ \fracπ{6} + \sqrt{3} \approx 5.255$. To achieve the upper bound, we designed an algorithm which proposes a forced meeting between the two robots, even if the exit has not been found by either of them. We also show that such a strategy is provably optimal for a related problem of searching for an exit placed at the vertices of a regular hexagon.
Optimizing Neural Networks with Kronecker-factored Approximate Curvature
Venue: arXiv cs.LG 2020
Year: 2020

We propose an efficient method for approximating natural gradient descent in neural networks which we call Kronecker-Factored Approximate Curvature (K-FAC). K-FAC is based on an efficiently invertible approximation of a neural network's Fisher information matrix which is neither diagonal nor low-rank, and in some cases is completely non-sparse. It is derived by approximating various large blocks of the Fisher (corresponding to entire layers) as being the Kronecker product of two much smaller matrices. While only several times more expensive to compute than the plain stochastic gradient, the updates produced by K-FAC make much more progress optimizing the objective, which results in an algorithm that can be much faster than stochastic gradient descent with momentum in practice. And unlike some previously proposed approximate natural-gradient/Newton methods which use high-quality non-diagonal curvature matrices (such as Hessian-free optimization), K-FAC works very well in highly stochastic optimization regimes. This is because the cost of storing and inverting K-FAC's approximation to the curvature matrix does not depend on the amount of data used to estimate it, which is a feature typically associated only with diagonal or low-rank approximations to the curvature matrix.
High Speed Hashing for Integers and Strings
Venue: arXiv cs.DS 2020
Year: 2020

These notes describe the most efficient hash functions currently known for hashing integers and strings. These modern hash functions are often an order of magnitude faster than those presented in standard text books. They are also simpler to implement, and hence a clear win in practice, but their analysis is harder. Some of the most practical hash functions have only appeared in theory papers, and some of them requires combining results from different theory papers. The goal here is to combine the information in lecture-style notes that can be used by theoreticians and practitioners alike, thus making these practical fruits of theory more widely accessible.
Bracketing numbers of convex and $m$-monotone functions on polytopes
Venue: arXiv cs.IT 2020
Year: 2020

We study bracketing covering numbers for spaces of bounded convex functions in the $L_p$ norms. Bracketing numbers are crucial quantities for understanding asymptotic behavior for many statistical nonparametric estimators. Bracketing number upper bounds in the supremum distance are known for bounded classes that also have a fixed Lipschitz constraint. However, in most settings of interest, the classes that arise do not include Lipschitz constraints, and so standard techniques based on known bracketing numbers cannot be used. In this paper, we find upper bounds for bracketing numbers of classes of convex functions without Lipschitz constraints on arbitrary polytopes. Our results are of particular interest in many multidimensional estimation problems based on convexity shape constraints. Additionally, we show other applications of our proof methods; in particular we define a new class of multivariate functions, the so-called $m$-monotone functions. Such functions have been considered mathematically and statistically in the univariate case but never in the multivariate case. We show how our proof for convex bracketing upper bounds also applies to the $m$-monotone case.
Elicitation Complexity of Statistical Properties
Venue: arXiv cs.LG 2020
Year: 2020

A property, or statistical functional, is said to be elicitable if it minimizes expected loss for some loss function. The study of which properties are elicitable sheds light on the capabilities and limitations of point estimation and empirical risk minimization. While recent work asks which properties are elicitable, we instead advocate for a more nuanced question: how many dimensions are required to indirectly elicit a given property? This number is called the elicitation complexity of the property. We lay the foundation for a general theory of elicitation complexity, including several basic results about how elicitation complexity behaves, and the complexity of standard properties of interest. Building on this foundation, our main result gives tight complexity bounds for the broad class of Bayes risks. We apply these results to several properties of interest, including variance, entropy, norms, and several classes of financial risk measures. We conclude with discussion and open directions.
Adaptive Online Learning
Venue: arXiv cs.LG 2020
Year: 2020

We propose a general framework for studying adaptive regret bounds in the online learning framework, including model selection bounds and data-dependent bounds. Given a data- or model-dependent bound we ask, "Does there exist some algorithm achieving this bound?" We show that modifications to recently introduced sequential complexity measures can be used to answer this question by providing sufficient conditions under which adaptive rates can be achieved. In particular each adaptive rate induces a set of so-called offset complexity measures, and obtaining small upper bounds on these quantities is sufficient to demonstrate achievability. A cornerstone of our analysis technique is the use of one-sided tail inequalities to bound suprema of offset random processes. Our framework recovers and improves a wide variety of adaptive bounds including quantile bounds, second-order data-dependent bounds, and small loss bounds. In addition we derive a new type of adaptive bound for online linear optimization based on the spectral norm, as well as a new online PAC-Bayes theorem that holds for countably infinite sets.
Reversible Denoising and Lifting Based Color Component Transformation for Lossless Image Compression
Venue: arXiv cs.MM 2020
Year: 2020

An undesirable side effect of reversible color space transformation, which consists of lifting steps (LSs), is that while removing correlation it contaminates transformed components with noise from other components. Noise affects particularly adversely the compression ratios of lossless compression algorithms. To remove correlation without increasing noise, a reversible denoising and lifting step (RDLS) was proposed that integrates denoising filters into LS. Applying RDLS to color space transformation results in a new image component transformation that is perfectly reversible despite involving the inherently irreversible denoising; the first application of such a transformation is presented in this paper. For the JPEG-LS, JPEG 2000, and JPEG XR standard algorithms in lossless mode, the application of RDLS to the RDgDb color space transformation with simple denoising filters is especially effective for images in the native optical resolution of acquisition devices. It results in improving compression ratios of all those images in cases when unmodified color space transformation either improves or worsens ratios compared with the untransformed image. The average improvement is 5.0-6.0\% for two out of the three sets of such images, whereas average ratios of images from standard test-sets are improved by up to 2.2\%. For the efficient image-adaptive determination of filters for RDLS, a couple of fast entropy-based estimators of compression effects that may be used independently of the actual compression algorithm are investigated and an immediate filter selection method based on the detector precision characteristic model driven by image acquisition parameters is introduced.
Line-of-Sight Pursuit in Monotone and Scallop Polygons
Venue: arXiv cs.CG 2020
Year: 2020

We study a turn-based game in a simply connected polygonal environment $Q$ between a pursuer $P$ and an adversarial evader $E$. Both players can move in a straight line to any point within unit distance during their turn. The pursuer $P$ wins by capturing the evader, meaning that their distance satisfies $d(P, E) \leq 1$, while the evader wins by eluding capture forever. Both players have a map of the environment, but they have different sensing capabilities. The evader $E$ always knows the location of $P$. Meanwhile, $P$ only has line-of-sight visibility: $P$ observes the evader's position only when the line segment connecting them lies entirely within the polygon. Therefore $P$ must search for $E$ when the evader is hidden from view. We provide a winning strategy for $P$ in two families of polygons: monotone polygons and scallop polygons. In both families, a straight line $L$ can be moved continuously over $Q$ so that (1) $L \cap Q$ is a line segment and (2) every point on the boundary $\partial Q$ is swept exactly once. These are both subfamilies of strictly sweepable polygons. The sweeping motion for a monotone polygon is a single translation, and the sweeping motion for a scallop polygon is a single rotation. Our algorithms use rook's strategy during its pursuit phase, rather than the well-known lion's strategy. The rook's strategy is crucial for obtaining a capture time that is linear in the area of $Q$. For both monotone and scallop polygons, our algorithm has a capture time of $O(n(Q) + \mbox{area}(Q))$, where $n(Q)$ is the number of polygon vertices.