OpenRaiser/Intern-Atlas huggingface dataset:
Optical-Flow based Self-Supervised Learning of Obstacle Appearance applied to MAV Landing
Venue: arXiv cs.RO 2017
Year: 2017

Monocular optical flow has been widely used to detect obstacles in Micro Air Vehicles (MAVs) during visual navigation. However, this approach requires significant movement, which reduces the efficiency of navigation and may even introduce risks in narrow spaces. In this paper, we introduce a novel setup of self-supervised learning (SSL), in which optical flow cues serve as a scaffold to learn the visual appearance of obstacles in the environment. We apply it to a landing task, in which initially 'surface roughness' is estimated from the optical flow field in order to detect obstacles. Subsequently, a linear regression function is learned that maps appearance features represented by texton distributions to the roughness estimate. After learning, the MAV can detect obstacles by just analyzing a still image. This allows the MAV to search for a landing spot without moving. We first demonstrate this principle to work with offline tests involving images captured from an on-board camera, and then demonstrate the principle in flight. Although surface roughness is a property of the entire flow field in the global image, the appearance learning even allows for the pixel-wise segmentation of obstacles.
Newton-like method with diagonal correction for distributed optimization
Venue: arXiv cs.IT 2017
Year: 2017

We consider distributed optimization problems where networked nodes cooperatively minimize the sum of their locally known convex costs. A popular class of methods to solve these problems are the distributed gradient methods, which are attractive due to their inexpensive iterations, but have a drawback of slow convergence rates. This motivates the incorporation of second-order information in the distributed methods, but this task is challenging: although the Hessians which arise in the algorithm design respect the sparsity of the network, their inverses are dense, hence rendering distributed implementations difficult. We overcome this challenge and propose a class of distributed Newton-like methods, which we refer to as Distributed Quasi Newton (DQN). The DQN family approximates the Hessian inverse by: 1) splitting the Hessian into its diagonal and off-diagonal part, 2) inverting the diagonal part, and 3) approximating the inverse of the off-diagonal part through a weighted linear function. The approximation is parameterized by the tuning variables which correspond to different splittings of the Hessian and by different weightings of the off-diagonal Hessian part. Specific choices of the tuning variables give rise to different variants of the proposed general DQN method -- dubbed DQN-0, DQN-1 and DQN-2 -- which mutually trade-off communication and computational costs for convergence. Simulations demonstrate the effectiveness of the proposed DQN methods.
Precise Complexity of the Core in Dichotomous and Additive Hedonic Games
Venue: arXiv cs.GT 2017
Year: 2017

Hedonic games provide a general model of coalition formation, in which a set of agents is partitioned into coalitions, with each agent having preferences over which other players are in her coalition. We prove that with additively separable preferences, it is $Σ_2^p$-complete to decide whether a core- or strict-core-stable partition exists, extending a result of Woeginger (2013). Our result holds even if valuations are symmetric and non-zero only for a constant number of other agents. We also establish $Σ_2^p$-completeness of deciding non-emptiness of the strict core for hedonic games with dichotomous preferences. Such results establish that the core is much less tractable than solution concepts such as individual stability.
Inkdots as advice for finite automata
Venue: arXiv cs.FL 2017
Year: 2017

We examine inkdots placed on the input string as a way of providing advice to finite automata, and establish the relations between this model and the previously studied models of advised finite automata. The existence of an infinite hierarchy of classes of languages that can be recognized with the help of increasing numbers of inkdots as advice is shown. The effects of different forms of advice on the succinctness of the advised machines are examined. We also study randomly placed inkdots as advice to probabilistic finite automata, and demonstrate the superiority of this model over its deterministic version. Even very slowly growing amounts of space can become a resource of meaningful use if the underlying advised model is extended with access to secondary memory, while it is famously known that such small amounts of space are not useful for unadvised one-way Turing machines.
Project Beehive: A Hardware/Software Co-designed Stack for Runtime and Architectural Research
Venue: arXiv cs.DC 2017
Year: 2017

The end of Dennard scaling combined with stagnation in architectural and compiler optimizations makes it challenging to achieve significant performance deltas. Solutions based solely in hardware or software are no longer sufficient to maintain the pace of improvements seen during the past few decades. In hardware, the end of single-core scaling resulted in the proliferation of multi-core system architectures, however this has forced complex parallel programming techniques into the mainstream. To further exploit physical resources, systems are becoming increasingly heterogeneous with specialized computing elements and accelerators. Programming across a range of disparate architectures requires a new level of abstraction that programming languages will have to adapt to. In software, emerging complex applications, from domains such as Big Data and computer vision, run on multi-layered software stacks targeting hardware with a variety of constraints and resources. Hence, optimizing for the power-performance (and resiliency) space requires experimentation platforms that offer quick and easy prototyping of hardware/software co-designed techniques. To that end, we present Project Beehive: A Hardware/Software co-designed stack for runtime and architectural research. Project Beehive utilizes various state-of-the-art software and hardware components along with novel and extensible co-design techniques. The objective of Project Beehive is to provide a modern platform for experimentation on emerging applications, programming languages, compilers, runtimes, and low-power heterogeneous many-core architectures in a full-system co-designed manner.
BLC: Private Matrix Factorization Recommenders via Automatic Group Learning
Venue: arXiv cs.LG 2017
Year: 2017

We propose a privacy-enhanced matrix factorization recommender that exploits the fact that users can often be grouped together by interest. This allows a form of "hiding in the crowd" privacy. We introduce a novel matrix factorization approach suited to making recommendations in a shared group (or nym) setting and the BLC algorithm for carrying out this matrix factorization in a privacy-enhanced manner. We demonstrate that the increased privacy does not come at the cost of reduced recommendation accuracy.
Directional spin wavelets on the sphere
Venue: arXiv cs.IT 2017
Year: 2017

We construct a directional spin wavelet framework on the sphere by generalising the scalar scale-discretised wavelet transform to signals of arbitrary spin. The resulting framework is the only wavelet framework defined natively on the sphere that is able to probe the directional intensity of spin signals. Furthermore, directional spin scale-discretised wavelets support the exact synthesis of a signal on the sphere from its wavelet coefficients and satisfy excellent localisation and uncorrelation properties. Consequently, directional spin scale-discretised wavelets are likely to be of use in a wide range of applications and in particular for the analysis of the polarisation of the cosmic microwave background (CMB). We develop new algorithms to compute (scalar and spin) forward and inverse wavelet transforms exactly and efficiently for very large data-sets containing tens of millions of samples on the sphere. By leveraging a novel sampling theorem on the rotation group developed in a companion article, only half as many wavelet coefficients as alternative approaches need be computed, while still capturing the full information content of the signal under analysis. Our implementation of these algorithms is made publicly available.
Exploration and Exploitation of Victorian Science in Darwin's Reading Notebooks
Venue: arXiv cs.CL 2017
Year: 2017

Search in an environment with an uncertain distribution of resources involves a trade-off between exploitation of past discoveries and further exploration. This extends to information foraging, where a knowledge-seeker shifts between reading in depth and studying new domains. To study this decision-making process, we examine the reading choices made by one of the most celebrated scientists of the modern era: Charles Darwin. From the full-text of books listed in his chronologically-organized reading journals, we generate topic models to quantify his local (text-to-text) and global (text-to-past) reading decisions using Kullback-Liebler Divergence, a cognitively-validated, information-theoretic measure of relative surprise. Rather than a pattern of surprise-minimization, corresponding to a pure exploitation strategy, Darwin's behavior shifts from early exploitation to later exploration, seeking unusually high levels of cognitive surprise relative to previous eras. These shifts, detected by an unsupervised Bayesian model, correlate with major intellectual epochs of his career as identified both by qualitative scholarship and Darwin's own self-commentary. Our methods allow us to compare his consumption of texts with their publication order. We find Darwin's consumption more exploratory than the culture's production, suggesting that underneath gradual societal changes are the explorations of individual synthesis and discovery. Our quantitative methods advance the study of cognitive search through a framework for testing interactions between individual and collective behavior and between short- and long-term consumption choices. This novel application of topic modeling to characterize individual reading complements widespread studies of collective scientific behavior.
The VCG Mechanism for Bayesian Scheduling
Venue: arXiv cs.GT 2017
Year: 2017

We study the problem of scheduling $m$ tasks to $n$ selfish, unrelated machines in order to minimize the makespan, where the execution times are independent random variables, identical across machines. We show that the VCG mechanism, which myopically allocates each task to its best machine, achieves an approximation ratio of $O\left(\frac{\ln n}{\ln \ln n}\right)$. This improves significantly on the previously best known bound of $O\left(\frac{m}{n}\right)$ for prior-independent mechanisms, given by Chawla et al. [STOC'13] under the additional assumption of Monotone Hazard Rate (MHR) distributions. Although we demonstrate that this is in general tight, if we do maintain the MHR assumption, then we get improved, (small) constant bounds for $m\geq n\ln n$ i.i.d. tasks, while we also identify a sufficient condition on the distribution that yields a constant approximation ratio regardless of the number of tasks.
Fixed points and connections between positive and negative cycles in Boolean networks
Venue: arXiv cs.DM 2017
Year: 2017

We are interested in the relationships between the number fixed points in a Boolean network $f:\{0,1\}^n\to\{0,1\}^n$ and its interaction graph, which is the arc-signed digraph $G$ on $\{1,\dots,n\}$ that describes the positive and negative influences between the components of the network. A fundamental theorem of Aracena says that if $G$ has no positive (resp. negative) cycle, then $f$ has at most (resp. at least) one fixed point; the sign of a cycle being the product of the signs of its arcs. In this note, we generalize this result by taking into account the influence of connections between positive and negative cycles. In particular, we prove that if every positive (resp. negative) cycle of $G$ has an arc $a$ such that $G\setminus a$ has a non-trivial initial strongly connected component containing the terminal vertex of $a$ and only negative (resp. positive) cycles, then $f$ has at most (resp. at least) one fixed point. This is, up to our knowledge, the first generalization of Aracena's theorem where the conditions are expressed with $G$ only.
Kempe's Universality Theorem for Rational Space Curves
Venue: arXiv cs.CG 2017
Year: 2017

We prove that every bounded rational space curve of degree d and circularity c can be drawn by a linkage with 9/2 d - 6c + 1 revolute joints. Our proof is based on two ingredients. The first one is the factorization theory of motion polynomials. The second one is the construction of a motion polynomial of minimum degree with given orbit. Our proof also gives the explicity construction of the linkage.
On the Sensitivity of k-Uniform Hypergraph Properties
Venue: arXiv cs.CC 2017
Year: 2017

In this paper we present a graph property with sensitivity $Θ(\sqrt{n})$, where $n={v\choose2}$ is the number of variables, and generalize it to a $k$-uniform hypergraph property with sensitivity $Θ(\sqrt{n})$, where $n={v\choose k}$ is again the number of variables. This yields the smallest sensitivity yet achieved for a $k$-uniform hypergraph property. We then show that, for even $k$, there is a $k$-uniform hypergraph property that demonstrates a quadratic gap between sensitivity and block sensitivity. This matches the largest known gap found by Ambainis and Sun (2011) for Boolean functions in general, and is the first known example of such a gap for a graph or hypergraph property.
Baseband Equivalent Models and Digital Predistortion for Mitigating Dynamic Continuous-Time Perturbations in Phase-Amplitude Modulation-Demodulation Schemes (Expanded version)
Venue: arXiv cs.SY 2017
Year: 2017

We consider baseband equivalent representation of transmission circuits, in the form of a nonlinear dynamical system $\mathbf S$ in discrete time (DT) defined by a series interconnection of a phase-amplitude modulator, a nonlinear dynamical system $\mathbf F$ in continuous time (CT), and an ideal demodulator. We show that when $\mathbf F$ is a CT Volterra series model, the resulting $\mathbf S$ is a series interconnection of a DT Volterra series model of same degree and memory depth, and an LTI system with special properties. The result suggests a new, non-obvious, analytically motivated structure of digital pre-compensation of analog nonlinear distortions such as those caused by power amplifiers in digital communication systems. The baseband model and the corresponding digital compensation structure readily extend to OFDM modulation. MATLAB simulation is used to verify proposed baseband equivalent model and demonstrate effectiveness of the new compensation scheme, as compared to the standard Volterra series approach.
A Formal System: Rigorous Constructions of Computer Models
Venue: arXiv cs.LO 2017
Year: 2017

This book explores an alternative to the current dominant paradigm where a discrete computer model is constructed as an attempt to approximate some continuum theory. We focus on a class of discrete computer models that are based on simple deterministic rules and finite state arithmetic. Such models are highly compatible with the operational parameters of the real world computer on which they are executed and hence their validation can be associated with the allowable computations on the machine. A simple formal system based on a language of functional programs is employed as a tool of analysis.
An Efficient Polyphase Filter Based Resampling Method for Unifying the PRFs in SAR Data
Venue: arXiv cs.CE 2017
Year: 2017

Variable and higher pulse repetition frequencies (PRFs) are increasingly being used to meet the stricter requirements and complexities of current airborne and spaceborne synthetic aperture radar (SAR) systems associated with higher resolution and wider area products. POLYPHASE, the proposed resampling scheme, downsamples and unifies variable PRFs within a single look complex (SLC) SAR acquisition and across a repeat pass sequence of acquisitions down to an effective lower PRF. A sparsity condition of the received SAR data ensures that the uniformly resampled data approximates the spectral properties of a decimated densely sampled version of the received SAR data. While experiments conducted with both synthetically generated and real airborne SAR data show that POLYPHASE retains comparable performance to the state-of-the-art BLUI scheme in image quality, a polyphase filter-based implementation of POLYPHASE offers significant computational savings for arbitrary (not necessarily periodic) input PRF variations, thus allowing fully on-board, in-place, and real-time implementation.
Complexity of Conditional Term Rewriting
Venue: arXiv cs.LO 2017
Year: 2017

We propose a notion of complexity for oriented conditional term rewrite systems satisfying certain restrictions. This notion is realistic in the sense that it measures not only successful computations, but also partial computations that result in a failed rule application. A transformation to unconditional context-sensitive rewrite systems is presented which reflects this complexity notion, as well as a technique to derive runtime and derivational complexity bounds for the result of this transformation.
Global Games with Noisy Information Sharing
Venue: arXiv cs.SI 2017
Year: 2017

Global games form a subclass of games with incomplete information where a set of agents decide actions against a regime with an underlying fundamental $θ$ representing its power. Each agent has access to an independent noisy observation of $θ$. In order to capture the behavior of agents in a social network of information exchange we assume that agents share their observation in a noisy environment prior to making their decision. We show that global games with noisy sharing of information do not admit an intuitive type of threshold policy which only depends on agents' belief about the underlying $θ$. This is in contrast to the existing results on the threshold policy for the conventional set-up of global games. Motivated by this result, we investigate the existence of equilibrium strategies in a more general collection of threshold-type policies and show that such equilibrium strategies exist and are unique if the sharing of information happens over a sufficiently noisy environment.
A Certain Tendency Of The Database Community
Venue: arXiv cs.DC 2017
Year: 2017

We posit that striving for distributed systems that provide "single system image" semantics is fundamentally flawed and at odds with how systems operate in the physical world. We realize the database as an optimization of this system: a required, essential optimization in practice that facilitates central data placement and ease of access to participants in a system. We motivate a new model of computation that is designed to address the problems of computation over "eventually consistent" information in a large-scale distributed system.
An Information Theoretic Analysis of Sequential Decision-Making
Venue: arXiv cs.IT 2017
Year: 2017

We provide a novel analysis of Wald's sequential probability ratio test based on information theoretic measures for symmetric thresholds, symmetric noise, and equally likely hypotheses under the assumption that the test exactly terminates at one of the thresholds. This test is optimal in the sense that it yields the minimum mean decision time. To analyze the decision-making process we consider information densities, which represent the stochastic information content of the observations yielding a stochastic termination time of the test. Based on this, we show that the conditional probability to decide for hypothesis $\mathcal{H}_1$ (or the counter-hypothesis $\mathcal{H}_0$) given that the test terminates at time instant $k$ is independent of time $k$. An analogous property has been found for a continuous-time first passage problem with two absorbing boundaries in the contexts of non-equilibrium statistical physics and communication theory. Moreover, we study the evolution of the mutual information between the binary variable to be tested and the output of the Wald test. Notably, we show that the decision time of the Wald test contains no information on which hypothesis is true beyond the decision outcome.
An introduction to the NMPC-Graph as general schema for causal modelling of nonlinear, multivariate, dynamic, and recursive systems with focus on time-series prediction
Venue: arXiv cs.SY 2017
Year: 2017

While the disciplines of physics and engineering sciences in many cases have taken advantage from accurate time-series prediction of system behaviour by applying ordinary differential equation systems upon precise basic physical laws such approach hardly could be adopted by other scientific disciplines where precise mathematical basic laws are unknown. A new modelling schema, the NMPC-graph, opens the possibility of interdisciplinary and generic nonlinear, multivariate, dynamic, and recursive causal modelling in domains where basic laws are only known as qualitative relationships among parameters while their precise mathematical nature remains undisclosed at modelling time. The symbolism of NMPC-graph is kept simple and suited for analysts without advanced mathematical skills. This article presents the definition of the NMPC-graph modelling method and its six component types. Further, it shows how to solve the inverse problem of deriving a nonlinear ordinary differential equation system from any NMPC-graph in conjunction with historic calibration data by means of machine learning. This article further discusses how such a derived NMPC-model can be used for hypothesis testing and time-series prediction with the expectation of gaining prediction accuracy in comparison to conventional prediction methods.
Subcarrier grouping with environmental sensing for MIMO-OFDM systems over correlated double-selective fading channels
Venue: arXiv cs.IT 2017
Year: 2017

With the increase of physical antenna and subcarrier numbers in MIMO-OFDM systems, channel side information feedback amount and signal precoding complexity overburden will consume much more system resource, even become intolerable. To solve this problem, previous works mainly focused on fixed subcarrier grouping size and precoded MIMO signals in the same group with unitary channel state information (CSI). It could reduce the system overburden, but such a process would lead to system capacity loss due to the channel mismatch in precoding procedure. In this paper, we consider a MIMOOFDM system over double-selective i.i.d. Rayleigh channels and investigate the quantitative relation between group size and capacity loss theoretically. By exploiting our developed theoretical results, we also propose an adaptive subcarrier grouping algorithm, which not only enables to have a good control of system service quality but also to reduce system overburden significantly. Numerical results are shown to provide valuable insights on the system design of MIMO-OFDM systems and indicate that the proposed subcarrier grouping scheme is extremely efficient in some common scenarios.