OpenRaiser/Intern-Atlas huggingface dataset:
Mbps Experimental Acoustic Through-Tissue Communications: MEAT-COMMS
Venue: arXiv cs.IT 2016
Year: 2016

Methods for digital, phase-coherent acoustic communication date to at least the work of Stojanjovic, et al [20], and the added robustness afforded by improved phase tracking and compensation of Johnson, et al [21]. This work explores the use of such methods for communications through tissue for potential biomedical applications, using the tremendous bandwidth available in commercial medical ultrasound transducers. While long-range ocean acoustic experiments have been at rates of under 100kbps, typically on the order of 1- 10kbps, data rates in excess of 120Mb/s have been achieved over cm-scale distances in ultrasonic testbeds [19]. This paper describes experimental transmission of digital communication signals through samples of real pork tissue and beef liver, achieving data rates of 20-30Mbps, demonstrating the possibility of real-time video-rate data transmission through tissue for inbody ultrasonic communications with implanted medical devices.
Cascading Bandits for Large-Scale Recommendation Problems
Venue: arXiv cs.LG 2016
Year: 2016

Most recommender systems recommend a list of items. The user examines the list, from the first item to the last, and often chooses the first attractive item and does not examine the rest. This type of user behavior can be modeled by the cascade model. In this work, we study cascading bandits, an online learning variant of the cascade model where the goal is to recommend $K$ most attractive items from a large set of $L$ candidate items. We propose two algorithms for solving this problem, which are based on the idea of linear generalization. The key idea in our solutions is that we learn a predictor of the attraction probabilities of items from their features, as opposing to learning the attraction probability of each item independently as in the existing work. This results in practical learning algorithms whose regret does not depend on the number of items $L$. We bound the regret of one algorithm and comprehensively evaluate the other on a range of recommendation problems. The algorithm performs well and outperforms all baselines.
A Survey on High-Speed Railway Communications: A Radio Resource Management Perspective
Venue: arXiv cs.IT 2016
Year: 2016

High-speed railway (HSR) communications will become a key feature supported by intelligent transportation communication systems. The increasing demand for HSR communications leads to significant attention on the study of radio resource management (RRM), which enables efficient resource utilization and improved system performance. RRM design is a challenging problem due to heterogenous quality of service (QoS) requirements and dynamic characteristics of HSR wireless communications. The objective of this paper is to provide an overview on the key issues that arise in the RRM design for HSR wireless communications. A detailed description of HSR communication systems is first presented, followed by an introduction on HSR channel models and characteristics, which are vital to the cross-layer RRM design. Then we provide a literature survey on state-of-the-art RRM schemes for HSR wireless communications, with an in-depth discussion on various RRM aspects including admission control, mobility management, power control and resource allocation. Finally, this paper outlines the current challenges and open issues in the area of RRM design for HSR wireless communications.
Degree reduction of composite Bézier curves
Venue: arXiv cs.GR 2016
Year: 2016

This paper deals with the problem of multi-degree reduction of a composite Bézier curve with the parametric continuity constraints at the endpoints of the segments. We present a novel method which is based on the idea of using constrained dual Bernstein polynomials to compute the control points of the reduced composite curve. In contrast to other methods, ours minimizes the $L_2$-error for the whole composite curve instead of minimizing the $L_2$-errors for each segment separately. As a result, an additional optimization is possible. Examples show that the new method gives much better results than multiple application of the degree reduction of a single Bézier curve.
Polymorphic Type Inference for Machine Code
Venue: arXiv cs.PL 2016
Year: 2016

For many compiled languages, source-level types are erased very early in the compilation process. As a result, further compiler passes may convert type-safe source into type-unsafe machine code. Type-unsafe idioms in the original source and type-unsafe optimizations mean that type information in a stripped binary is essentially nonexistent. The problem of recovering high-level types by performing type inference over stripped machine code is called type reconstruction, and offers a useful capability in support of reverse engineering and decompilation. In this paper, we motivate and develop a novel type system and algorithm for machine-code type inference. The features of this type system were developed by surveying a wide collection of common source- and machine-code idioms, building a catalog of challenging cases for type reconstruction. We found that these idioms place a sophisticated set of requirements on the type system, inducing features such as recursively-constrained polymorphic types. Many of the features we identify are often seen only in expressive and powerful type systems used by high-level functional languages. Using these type-system features as a guideline, we have developed Retypd: a novel static type-inference algorithm for machine code that supports recursive types, polymorphism, and subtyping. Retypd yields more accurate inferred types than existing algorithms, while also enabling new capabilities such as reconstruction of pointer const annotations with 98% recall. Retypd can operate on weaker program representations than the current state of the art, removing the need for high-quality points-to information that may be impractical to compute.
Steering Macro-Scale Network Community Structure by Micro-Scale Features
Venue: arXiv cs.SI 2016
Year: 2016

Network science plays an increasingly important role to model complex data in many scientific disciplines. One notable feature of network organization is community structure, which refers to clusters of tightly interconnected nodes. A prominent problem is how to investigate the relationship between macro-scale modules that are retrieved by optimizing global network measures, and micro-scale structure that are defined by specific queries of the analysis (e.g., nodal features). By generalizing fundamental concepts of joint space-frequency localization to network theory, here we propose a flexible framework to study interactions between micro- and macro-structure. Similar to pointing and focusing a magnifying glass, the analysis can be directed to specific micro-scale structure, while the degree of interaction with the macro-scale community structure can be seamlessly controlled. In addition, the method is computationally efficient as a result of the underlying low-dimensional optimization problem.
Two-variable Logic with a Between Predicate
Venue: arXiv cs.LO 2016
Year: 2016

We study an extension of FO^2[<], first-order logic interpreted in finite words, in which formulas are restricted to use only two variables. We adjoin to this language two-variable atomic formulas that say, `the letter a appears between positions x and y'. This is, in a sense, the simplest property that is not expressible using only two variables. We present several logics, both first-order and temporal, that have the same expressive power, and find matching lower and upper bounds for the complexity of satisfiability for each of these formulations. We also give an effective necessary condition, in terms of the syntactic monoid of a regular language, for a property to be expressible in this logic. We show that this condition is also sufficient for words over a two-letter alphabet. This algebraic analysis allows us us to prove, among other things, that our new logic has strictly less expressive power than full first-order logic FO[<].
Semidefinite Relaxation and Approximation Analysis of a Beamformed Alamouti Scheme for Relay Beamforming Networks
Venue: arXiv cs.IT 2016
Year: 2016

In this paper, we study the amplify-and-forward (AF) schemes in two-hop one-way relay networks. In particular, we consider the multigroup multicast transmission between long-distance users. Given that perfect channel state information is perceived, our goal is to design the AF process so that the max-min-fair (MMF) signal-to-interference-plus-noise ratio (SINR) is optimized subject to generalized power constraints. We propose a rank-two beamformed Alamouti (BFA) AF scheme and formulate the corresponding AF design problem as a \emph{two-variable} fractional quadratically-constrained quadratic program (QCQP), which is further tackled by the semidefinite relaxation (SDR) technique. We analyze the approximation quality of two-variable fractional SDRs under the Gaussian randomization algorithm. These results are fundamentally new and reveal that the proposed BFA AF scheme can outperform the traditional BF AF scheme, especially when there are many users in the system or many generalized power constraints in the problem formulation. From a practical perspective, the BFA AF scheme offers two degrees of freedom (DoFs) in beamformer design, as opposed to the one DoF offered by the BF AF scheme, to improve the receivers' SINR. In the latter part of this paper, we demonstrate how this extra DoF leads to provable performance gains by considering two special cases of multicasting, where the AF process is shown to employ a special structure. The numerical simulations further validate that the proposed BFA AF scheme outperforms the BF AF scheme and works well for large-scale relay systems.
Unsupervised Cross-Media Hashing with Structure Preservation
Venue: arXiv cs.CV 2016
Year: 2016

Recent years have seen the exponential growth of heterogeneous multimedia data. The need for effective and accurate data retrieval from heterogeneous data sources has attracted much research interest in cross-media retrieval. Here, given a query of any media type, cross-media retrieval seeks to find relevant results of different media types from heterogeneous data sources. To facilitate large-scale cross-media retrieval, we propose a novel unsupervised cross-media hashing method. Our method incorporates local affinity and distance repulsion constraints into a matrix factorization framework. Correspondingly, the proposed method learns hash functions that generates unified hash codes from different media types, while ensuring intrinsic geometric structure of the data distribution is preserved. These hash codes empower the similarity between data of different media types to be evaluated directly. Experimental results on two large-scale multimedia datasets demonstrate the effectiveness of the proposed method, where we outperform the state-of-the-art methods.
The emergence of cooperation in public goods games on randomly growing dynamic networks
Venue: arXiv cs.GT 2016
Year: 2016

According to evolutionary game theory, cooperation in public goods games is eliminated by free-riders, yet in nature, cooperation is ubiquitous. Artificial models resolve this contradiction via the mechanism of network reciprocity. However, existing research only addresses pre-existing networks and does not specifically consider their origins. Further, much work has focused on scale-free networks and so pre-supposes attachment mechanisms which may not exist in nature. We present a coevolutionary model of public goods games in networks, growing by random attachment, from small founding populations of simple agents. The model demonstrates the emergence of cooperation in moderately heterogeneous networks, regardless of original founders' behaviour, and absent higher cognitive abilities such as recognition or memory. It may thus illustrate a more general mechanism for the evolution of cooperation, from early origins, in minimally cognitive organisms. It is the first example of a model explaining cooperation in public goods games on growing networks.
On cyclic DNA codes over $\mathbb{F}_2+u\mathbb{F}_2+u^2\mathbb{F}_2$
Venue: arXiv cs.IT 2016
Year: 2016

In the present paper we study the structure of cyclic DNA codes of even lenght over the ring $\mathbb{F}_2+u\mathbb{F}_2+u^2\mathbb{F}_2$ where $u^3=0$. We investigate two presentations of cyclic codes of even lenght over $\mathbb{F}_2+u\mathbb{F}_2+u^2\mathbb{F}_2$ satisfying the reverse constraint and reverse-complement constraint.
Uplink FBMC/OQAM-based Multiple Access Channel: Distortion Analysis under Strong Frequency Selectivity
Venue: arXiv cs.IT 2016
Year: 2016

This paper computes the distortion power at the receiver side of an FBMC/OQAM-based OFDMA uplink channel under strong frequency selectivity and/or user timing errors. More precisely, it provides a distortion expression that is valid for a wide class of prototype pulses (not necessarily perfect-reconstruction ones) when the number of subcarriers is sufficiently large. This result is a valuable instrument for analyzing how users interfere to one another and to justify, formally, the common choice of placing an empty guard band between adjacent users. Interestingly, the number of out-band subcarriers contaminated by each user only depends on the prototype pulses and not on the channel nor on the equalizer. To conclude, the distortion analysis presented in this paper, together with some simulation results for a realistic scenario, also provide convincing evidence that FBMC/OQAM-based OFDMA is superior to classic circular-prefix OFDMA in the case of asynchronous users.
You Really Need A Good Ruler to Measure Caching Performance in Information-Centric Networks
Venue: arXiv cs.NI 2016
Year: 2016

Information-centric networks are an interesting new paradigm for distributing content on the Internet. They bring up many research challenges, such as addressing content by name, securing content, and wide-spread caching of content. Caching has caught a lot of attention in the research community, but a lot of the work suffers from a poor understanding of the different metrics with which caching performance can be measured. In this paper we not only present a comprehensive overview of different caching metrics that have been proposed for information-centric networks, but also propose the coupling factor as a new metric to capture the relation- ship between content popularity and network topology. As we show, many commonly used metrics have several failure modes which are largely ignored in literature. We identify these problems and propose remedies and new metrics to address these failures. Our work highlights the fundamental differences between information-centric caches and "traditional" cache networks and we demonstrate the need for a systematic understanding of the metrics for information- centric caching. We also discuss how experimental work should be done when evaluating networks of caches.
A Message Passing Algorithm for the Problem of Path Packing in Graphs
Venue: arXiv cs.DS 2016
Year: 2016

We consider the problem of packing node-disjoint directed paths in a directed graph. We consider a variant of this problem where each path starts within a fixed subset of root nodes, subject to a given bound on the length of paths. This problem is motivated by the so-called kidney exchange problem, but has potential other applications and is interesting in its own right. We propose a new algorithm for this problem based on the message passing/belief propagation technique. A priori this problem does not have an associated graphical model, so in order to apply a belief propagation algorithm we provide a novel representation of the problem as a graphical model. Standard belief propagation on this model has poor scaling behavior, so we provide an efficient implementation that significantly decreases the complexity. We provide numerical results comparing the performance of our algorithm on both artificially created graphs and real world networks to several alternative algorithms, including algorithms based on integer programming (IP) techniques. These comparisons show that our algorithm scales better to large instances than IP-based algorithms and often finds better solutions than a simple algorithm that greedily selects the longest path from each root node. In some cases it also finds better solutions than the ones found by IP-based algorithms even when the latter are allowed to run significantly longer than our algorithm.
The Computational Power of Dynamic Bayesian Networks
Venue: arXiv cs.AI 2016
Year: 2016

This paper considers the computational power of constant size, dynamic Bayesian networks. Although discrete dynamic Bayesian networks are no more powerful than hidden Markov models, dynamic Bayesian networks with continuous random variables and discrete children of continuous parents are capable of performing Turing-complete computation. With modified versions of existing algorithms for belief propagation, such a simulation can be carried out in real time. This result suggests that dynamic Bayesian networks may be more powerful than previously considered. Relationships to causal models and recurrent neural networks are also discussed.
An Observation About Passphrases: Syntax vs Entropy
Venue: arXiv cs.CR 2016
Year: 2016

On the premise that we are using passwords composed of multiple English words, we argue that using syntactically correct passphrases has no significant impact on the security in comparison to randomly arranged collections of words. We only analyze the contribution of the syntax itself. A comparison to the other kinds of passwords is out of the scope.
Grouping Time-varying Data for Interactive Exploration
Venue: arXiv cs.CG 2016
Year: 2016

We present algorithms and data structures that support the interactive analysis of the grouping structure of one-, two-, or higher-dimensional time-varying data while varying all defining parameters. Grouping structures characterise important patterns in the temporal evaluation of sets of time-varying data. We follow Buchin et al. [JoCG 2015] who define groups using three parameters: group-size, group-duration, and inter-entity distance. We give upper and lower bounds on the number of maximal groups over all parameter values, and show how to compute them efficiently. Furthermore, we describe data structures that can report changes in the set of maximal groups in an output-sensitive manner. Our results hold in $\mathbb{R}^d$ for fixed $d$.
A Diplexer-Based Receiver for Simultaneous Wireless Information and Power Transfer
Venue: arXiv cs.IT 2016
Year: 2016

Simultaneous wireless information and power transfer (SWIPT) is an appealing research area because both information and energy can be delivered to wireless devices simultaneously. In this paper, we propose a diplexer-based receiver architecture that can utilizes both the doubling frequency and baseband signals after the mixer. The baseband signals are used for information decoding and the doubling frequency signals are converted to direct current for energy harvesting. We analyze the signal in the receiver and find that the power of the energy harvested is equal to that of information decoded. Therefore, the diplexer can be used as a power splitter with a power splitting factor of 0.5. Specifically, we consider a multiuser multi-input single-output (MISO) system, in which each user is equipped with the newly proposed receiver. The problem is formulated as an optimization problem that minimizes the total transmitted power subject to some constraints on each user's quality of service and energy harvesting demand. We show that the problem thus formulated is a non-convex quadratically constrained quadratic program (QCQP), which can be solved by semi-definite relaxation.
Online Learning with Low Rank Experts
Venue: arXiv cs.LG 2016
Year: 2016

We consider the problem of prediction with expert advice when the losses of the experts have low-dimensional structure: they are restricted to an unknown $d$-dimensional subspace. We devise algorithms with regret bounds that are independent of the number of experts and depend only on the rank $d$. For the stochastic model we show a tight bound of $Θ(\sqrt{dT})$, and extend it to a setting of an approximate $d$ subspace. For the adversarial model we show an upper bound of $O(d\sqrt{T})$ and a lower bound of $Ω(\sqrt{dT})$.
A Discontinuous Neural Network for Non-Negative Sparse Approximation
Venue: arXiv cs.NE 2016
Year: 2016

This paper investigates a discontinuous neural network which is used as a model of the mammalian olfactory system and can more generally be applied to solve non-negative sparse approximation problems. By inherently limiting the systems integrators to having non-negative outputs, the system function becomes discontinuous since the integrators switch between being inactive and being active. It is shown that the presented network converges to equilibrium points which are solutions to general non-negative least squares optimization problems. We specify a Caratheodory solution and prove that the network is stable, provided that the system matrix has full column-rank. Under a mild condition on the equilibrium point, we show that the network converges to its equilibrium within a finite number of switches. Two applications of the neural network are shown. Firstly, we apply the network as a model of the olfactory system and show that in principle it may be capable of performing complex sparse signal recovery tasks. Secondly, we generalize the application to include non-negative sparse approximation problems and compare the recovery performance to a classical non-negative basis pursuit denoising algorithm. We conclude that the recovery performance differs only marginally from the classical algorithm, while the neural network has the advantage that no performance critical regularization parameter has to be chosen prior to recovery.
Beyond Sharing Weights for Deep Domain Adaptation
Venue: arXiv cs.CV 2016
Year: 2016

The performance of a classifier trained on data coming from a specific domain typically degrades when applied to a related but different one. While annotating many samples from the new domain would address this issue, it is often too expensive or impractical. Domain Adaptation has therefore emerged as a solution to this problem; It leverages annotated data from a source domain, in which it is abundant, to train a classifier to operate in a target domain, in which it is either sparse or even lacking altogether. In this context, the recent trend consists of learning deep architectures whose weights are shared for both domains, which essentially amounts to learning domain invariant features. Here, we show that it is more effective to explicitly model the shift from one domain to the other. To this end, we introduce a two-stream architecture, where one operates in the source domain and the other in the target domain. In contrast to other approaches, the weights in corresponding layers are related but not shared. We demonstrate that this both yields higher accuracy than state-of-the-art methods on several object recognition and detection tasks and consistently outperforms networks with shared weights in both supervised and unsupervised settings.