OpenRaiser/Intern-Atlas huggingface dataset:
Power Control for Multi-Cell Networks with Non-Orthogonal Multiple Access
Venue: arXiv cs.IT 2017
Year: 2017

In this paper, we investigate the problems of sum power minimization and sum rate maximization for multi-cell networks with non-orthogonal multiple access. Considering the sum power minimization, we obtain closed-form solutions to the optimal power allocation strategy and then successfully transform the original problem to a linear one with a much smaller size, which can be optimally solved by using the standard interference function. To solve the nonconvex sum rate maximization problem, we first prove that the power allocation problem for a single cell is a convex problem. By analyzing the Karush-Kuhn-Tucker conditions, the optimal power allocation for users in a single cell is derived in closed form. Based on the optimal solution in each cell, a distributed algorithm is accordingly proposed to acquire efficient solutions. Numerical results verify our theoretical findings showing the superiority of our solutions compared to the orthogonal frequency division multiple access and broadcast channel.
Quality-Driven Resource Allocation for Full-Duplex Delay-Constrained Wireless Video Transmissions
Venue: arXiv cs.IT 2017
Year: 2017

In this paper, wireless video transmission over full-duplex channels under total bandwidth and minimum required quality constraints is studied. In order to provide the desired performance levels to the end-users in real-time video transmissions, quality of service (QoS) requirements such as statistical delay constraints are also considered. Effective capacity (EC) is used as the throughput metric in the presence of such statistical delay constraints since deterministic delay bounds are difficult to guarantee due to the time-varying nature of wireless fading channels. A communication scenario with multiple pairs of users in which different users have different delay requirements is addressed. Following characterizations from the rate-distortion (R-D) theory, a logarithmic model of the quality-rate relation is used for predicting the quality of the reconstructed video in terms of the peak signal-to-noise ratio (PSNR) at the receiver side. Since the optimization problem is not concave or convex, the optimal bandwidth and power allocation policies that maximize the weighted sum video quality subject to total bandwidth, maximum transmission power level and minimum required quality constraints are derived by using monotonic optimization (MO) theory.
SLEEPNET: Automated Sleep Staging System via Deep Learning
Venue: arXiv cs.LG 2017
Year: 2017

Sleep disorders, such as sleep apnea, parasomnias, and hypersomnia, affect 50-70 million adults in the United States (Hillman et al., 2006). Overnight polysomnography (PSG), including brain monitoring using electroencephalography (EEG), is a central component of the diagnostic evaluation for sleep disorders. While PSG is conventionally performed by trained technologists, the recent rise of powerful neural network learning algorithms combined with large physiological datasets offers the possibility of automation, potentially making expert-level sleep analysis more widely available. We propose SLEEPNET (Sleep EEG neural network), a deployed annotation tool for sleep staging. SLEEPNET uses a deep recurrent neural network trained on the largest sleep physiology database assembled to date, consisting of PSGs from over 10,000 patients from the Massachusetts General Hospital (MGH) Sleep Laboratory. SLEEPNET achieves human-level annotation performance on an independent test set of 1,000 EEGs, with an average accuracy of 85.76% and algorithm-expert inter-rater agreement (IRA) of kappa = 79.46%, comparable to expert-expert IRA.
Graph-Based Classification of Omnidirectional Images
Venue: arXiv cs.CV 2017
Year: 2017

Omnidirectional cameras are widely used in such areas as robotics and virtual reality as they provide a wide field of view. Their images are often processed with classical methods, which might unfortunately lead to non-optimal solutions as these methods are designed for planar images that have different geometrical properties than omnidirectional ones. In this paper we study image classification task by taking into account the specific geometry of omnidirectional cameras with graph-based representations. In particular, we extend deep learning architectures to data on graphs; we propose a principled way of graph construction such that convolutional filters respond similarly for the same pattern on different positions of the image regardless of lens distortions. Our experiments show that the proposed method outperforms current techniques for the omnidirectional image classification problem.
Structure-Preserving Image Super-resolution via Contextualized Multi-task Learning
Venue: arXiv cs.CV 2017
Year: 2017

Single image super resolution (SR), which refers to reconstruct a higher-resolution (HR) image from the observed low-resolution (LR) image, has received substantial attention due to its tremendous application potentials. Despite the breakthroughs of recently proposed SR methods using convolutional neural networks (CNNs), their generated results usually lack of preserving structural (high-frequency) details. In this paper, regarding global boundary context and residual context as complimentary information for enhancing structural details in image restoration, we develop a contextualized multi-task learning framework to address the SR problem. Specifically, our method first extracts convolutional features from the input LR image and applies one deconvolutional module to interpolate the LR feature maps in a content-adaptive way. Then, the resulting feature maps are fed into two branched sub-networks. During the neural network training, one sub-network outputs salient image boundaries and the HR image, and the other sub-network outputs the local residual map, i.e., the residual difference between the generated HR image and ground-truth image. On several standard benchmarks (i.e., Set5, Set14 and BSD200), our extensive evaluations demonstrate the effectiveness of our SR method on achieving both higher restoration quality and computational efficiency compared with several state-of-the-art SR approaches. The source code and some SR results can be found at: http://hcp.sysu.edu.cn/structure-preserving-image-super-resolution/
Detecting and classifying lesions in mammograms with Deep Learning
Venue: arXiv cs.CV 2017
Year: 2017

In the last two decades Computer Aided Diagnostics (CAD) systems were developed to help radiologists analyze screening mammograms. The benefits of current CAD technologies appear to be contradictory and they should be improved to be ultimately considered useful. Since 2012 deep convolutional neural networks (CNN) have been a tremendous success in image recognition, reaching human performance. These methods have greatly surpassed the traditional approaches, which are similar to currently used CAD solutions. Deep CNN-s have the potential to revolutionize medical image analysis. We propose a CAD system based on one of the most successful object detection frameworks, Faster R-CNN. The system detects and classifies malignant or benign lesions on a mammogram without any human intervention. The proposed method sets the state of the art classification performance on the public INbreast database, AUC = 0.95 . The approach described here has achieved the 2nd place in the Digital Mammography DREAM Challenge with AUC = 0.85 . When used as a detector, the system reaches high sensitivity with very few false positive marks per image on the INbreast dataset. Source code, the trained model and an OsiriX plugin are availaible online at https://github.com/riblidezso/frcnn_cad .
Fast Distributed Approximation for Max-Cut
Venue: arXiv cs.DS 2017
Year: 2017

Finding a maximum cut is a fundamental task in many computational settings. Surprisingly, it has been insufficiently studied in the classic distributed settings, where vertices communicate by synchronously sending messages to their neighbors according to the underlying graph, known as the $\mathcal{LOCAL}$ or $\mathcal{CONGEST}$ models. We amend this by obtaining almost optimal algorithms for Max-Cut on a wide class of graphs in these models. In particular, for any $ε> 0$, we develop randomized approximation algorithms achieving a ratio of $(1-ε)$ to the optimum for Max-Cut on bipartite graphs in the $\mathcal{CONGEST}$ model, and on general graphs in the $\mathcal{LOCAL}$ model. We further present efficient deterministic algorithms, including a $1/3$-approximation for Max-Dicut in our models, thus improving the best known (randomized) ratio of $1/4$. Our algorithms make non-trivial use of the greedy approach of Buchbinder et al. (SIAM Journal on Computing, 2015) for maximizing an unconstrained (non-monotone) submodular function, which may be of independent interest.
Analyzing IO Amplification in Linux File Systems
Venue: arXiv cs.OS 2017
Year: 2017

We present the first systematic analysis of read, write, and space amplification in Linux file systems. While many researchers are tackling write amplification in key-value stores, IO amplification in file systems has been largely unexplored. We analyze data and metadata operations on five widely-used Linux file systems: ext2, ext4, XFS, btrfs, and F2FS. We find that data operations result in significant write amplification (2-32X) and that metadata operations have a large IO cost. For example, a single rename requires 648 KB write IO in btrfs. We also find that small random reads result in read amplification of 2-13X. Based on these observations, we present the CReWS conjecture about the relationship between IO amplification, consistency, and storage space utilization. We hope this paper spurs people to design future file systems with less IO amplification, especially for non-volatile memory technologies.
Interpatient Respiratory Motion Model Transfer for Virtual Reality Simulations of Liver Punctures
Venue: arXiv cs.CV 2017
Year: 2017

Current virtual reality (VR) training simulators of liver punctures often rely on static 3D patient data and use an unrealistic (sinusoidal) periodic animation of the respiratory movement. Existing methods for the animation of breathing motion support simple mathematical or patient-specific, estimated breathing models. However with personalized breathing models for each new patient, a heavily dose relevant or expensive 4D data acquisition is mandatory for keyframe-based motion modeling. Given the reference 4D data, first a model building stage using linear regression motion field modeling takes place. Then the methodology shown here allows the transfer of existing reference respiratory motion models of a 4D reference patient to a new static 3D patient. This goal is achieved by using non-linear inter-patient registration to warp one personalized 4D motion field model to new 3D patient data. This cost- and dose-saving new method is shown here visually in a qualitative proof-of-concept study.
Wisture: RNN-based Learning of Wireless Signals for Gesture Recognition in Unmodified Smartphones
Venue: arXiv cs.HC 2017
Year: 2017

This paper introduces Wisture, a new online machine learning solution for recognizing touch-less dynamic hand gestures on a smartphone. Wisture relies on the standard Wi-Fi Received Signal Strength (RSS) using a Long Short-Term Memory (LSTM) Recurrent Neural Network (RNN), thresholding filters and traffic induction. Unlike other Wi-Fi based gesture recognition methods, the proposed method does not require a modification of the smartphone hardware or the operating system, and performs the gesture recognition without interfering with the normal operation of other smartphone applications. We discuss the characteristics of Wisture, and conduct extensive experiments to compare its performance against state-of-the-art machine learning solutions in terms of both accuracy and time efficiency. The experiments include a set of different scenarios in terms of both spatial setup and traffic between the smartphone and Wi-Fi access points (AP). The results show that Wisture achieves an online recognition accuracy of up to 94% (average 78%) in detecting and classifying three hand gestures.
Effects of Contact Network Models on Stochastic Epidemic Simulations
Venue: arXiv cs.SI 2017
Year: 2017

The importance of modeling the spread of epidemics through a population has led to the development of mathematical models for infectious disease propagation. A number of empirical studies have collected and analyzed data on contacts between individuals using a variety of sensors. Typically one uses such data to fit a probabilistic model of network contacts over which a disease may propagate. In this paper, we investigate the effects of different contact network models with varying levels of complexity on the outcomes of simulated epidemics using a stochastic Susceptible-Infectious-Recovered (SIR) model. We evaluate these network models on six datasets of contacts between people in a variety of settings. Our results demonstrate that the choice of network model can have a significant effect on how closely the outcomes of an epidemic simulation on a simulated network match the outcomes on the actual network constructed from the sensor data. In particular, preserving degrees of nodes appears to be much more important than preserving cluster structure for accurate epidemic simulations.
A Note on IC-Planar Graphs
Venue: arXiv cs.DM 2017
Year: 2017

A graph is IC-planar if it admits a drawing in the plane with at most one crossing per edge and such that two pairs of crossing edges share no common end vertex. IC-planarity specializes both NIC-planarity, which allows a pair of crossing edges to share at most one vertex, and 1-planarity, where each edge may be crossed at most once. We show that there are infinitely maximal IC-planar graphs with n vertices and 3n-5 edges and thereby prove a tight lower bound on the density of this class of graphs.
Algebraic Relations and Triangulation of Unlabeled Image Points
Venue: arXiv cs.CV 2017
Year: 2017

In multiview geometry when correspondences among multiple views are unknown the image points can be understood as being unlabeled. This is a common problem in computer vision. We give a novel approach to handle such a situation by regarding unlabeled point configurations as points on the Chow variety $\text{Sym}_m(\mathbb{P}^2)$. For two unlabeled points we design an algorithm that solves the triangulation problem with unknown correspondences. Further the unlabeled multiview variety $\text{Sym}_m(V_A)$ is studied.
An Improved Subsumption Testing Algorithm for the Optimal-Size Sorting Network Problem
Venue: arXiv cs.DS 2017
Year: 2017

In this paper a new method for checking the subsumption relation for the optimal-size sorting network problem is described. The new approach is based on creating a bipartite graph and modelling the subsumption test as the problem of enumerating all perfect matchings in this graph. Experiments showed significant improvements over the previous approaches when considering the number of subsumption checks and the time needed to find optimal-size sorting networks. We were able to generate all the complete sets of filters for comparator networks with 9 channels, confirming that the 25-comparators sorting network is optimal. The running time was reduced more than 10 times, compared to the state-of-the-art results.
A Logic for Global and Local Announcements
Venue: arXiv cs.LO 2017
Year: 2017

In this paper we introduce {\em global and local announcement logic} (GLAL), a dynamic epistemic logic with two distinct announcement operators -- $[ϕ]^+_A$ and $[ϕ]^-_A$ indexed to a subset $A$ of the set $Ag$ of all agents -- for global and local announcements respectively. The boundary case $[ϕ]^+_{Ag}$ corresponds to the public announcement of $ϕ$, as known from the literature. Unlike standard public announcements, which are {\em model transformers}, the global and local announcements are {\em pointed model transformers}. In particular, the update induced by the announcement may be different in different states of the model. Therefore, the resulting computations are trees of models, rather than the typical sequences. A consequence of our semantics is that modally bisimilar states may be distinguished in our logic. Then, we provide a stronger notion of bisimilarity and we show that it preserves modal equivalence in GLAL. Additionally, we show that GLAL is strictly more expressive than public announcement logic with common knowledge. We prove a wide range of validities for GLAL involving the interaction between dynamics and knowledge, and show that the satisfiability problem for GLAL is decidable. We illustrate the formal machinery by means of detailed epistemic scenarios.
Relaxing Exclusive Control in Boolean Games
Venue: arXiv cs.AI 2017
Year: 2017

In the typical framework for boolean games (BG) each player can change the truth value of some propositional atoms, while attempting to make her goal true. In standard BG goals are propositional formulas, whereas in iterated BG goals are formulas of Linear Temporal Logic. Both notions of BG are characterised by the fact that agents have exclusive control over their set of atoms, meaning that no two agents can control the same atom. In the present contribution we drop the exclusivity assumption and explore structures where an atom can be controlled by multiple agents. We introduce Concurrent Game Structures with Shared Propositional Control (CGS-SPC) and show that they ac- count for several classes of repeated games, including iterated boolean games, influence games, and aggregation games. Our main result shows that, as far as verification is concerned, CGS-SPC can be reduced to concurrent game structures with exclusive control. This result provides a polynomial reduction for the model checking problem of specifications in Alternating-time Temporal Logic on CGS-SPC.
A Formal Approach to the Problem of Logical Non-Omniscience
Venue: arXiv cs.LO 2017
Year: 2017

We present the logical induction criterion for computable algorithms that assign probabilities to every logical statement in a given formal language, and refine those probabilities over time. The criterion is motivated by a series of stock trading analogies. Roughly speaking, each logical sentence phi is associated with a stock that is worth $1 per share if phi is true and nothing otherwise, and we interpret the belief-state of a logically uncertain reasoner as a set of market prices, where pt_N(phi)=50% means that on day N, shares of phi may be bought or sold from the reasoner for 50%. A market is then called a logical inductor if (very roughly) there is no polynomial-time computable trading strategy with finite risk tolerance that earns unbounded profits in that market over time. We then describe how this single criterion implies a number of desirable properties of bounded reasoners; for example, logical inductors outpace their underlying deductive process, perform universal empirical induction given enough time to think, and place strong trust in their own reasoning process.
Ramsey Spanning Trees and their Applications
Venue: arXiv cs.DS 2017
Year: 2017

The metric Ramsey problem asks for the largest subset $S$ of a metric space that can be embedded into an ultrametric (more generally into a Hilbert space) with a given distortion. Study of this problem was motivated as a non-linear version of Dvoretzky theorem. Mendel and Naor 2007 devised the so called Ramsey Partitions to address this problem, and showed the algorithmic applications of their techniques to approximate distance oracles and ranking problems. In this paper we study the natural extension of the metric Ramsey problem to graphs, and introduce the notion of Ramsey Spanning Trees. We ask for the largest subset $S\subseteq V$ of a given graph $G=(V,E)$, such that there exists a spanning tree of $G$ that has small stretch for $S$. Applied iteratively, this provides a small collection of spanning trees, such that each vertex has a tree providing low stretch paths to all other vertices. The union of these trees serves as a special type of spanner, a tree-padding spanner. We use this spanner to devise the first compact stateless routing scheme with $O(1)$ routing decision time, and labels which are much shorter than in all currently existing schemes. We first revisit the metric Ramsey problem, and provide a new deterministic construction. We prove that for every $k$, any $n$-point metric space has a subset $S$ of size at least $n^{1-1/k}$ which embeds into an ultrametric with distortion $8k$. This results improves the best previous result of Mendel and Naor that obtained distortion $128k$ and required randomization. In addition, it provides the state-of-the-art deterministic construction of a distance oracle. Building on this result, we prove that for every $k$, any $n$-vertex graph $G=(V,E)$ has a subset $S$ of size at least $n^{1-1/k}$, and a spanning tree of $G$, that has stretch $O(k \log \log n)$ between any point in $S$ and any point in $V$.
Runtime Model Based Approach to Smart Home System Development
Venue: arXiv cs.SE 2017
Year: 2017

When developing smart home systems, developers integrate and compose smart devices and software applications. Because of their diversity and heterogeneity, developers usually encounter many problems. In this paper, we present a runtime model based approach to smart home system development. First, we analyze mobile applications associated with smart devices and then extract some device control APIs. Second, we use SM@RT framework to build the device runtime model. Third, we define the scenario model, that is an abstraction of devices and objects which the system consists of. Fourth, we specify mapping rules from the scenario model to the runtime model and employ a synchronizer, which can interpret the mapping rules, to keep the synchronization between the scenario model and the device runtime model. The mapping handler reads the mapping rules that are defined by developers and does the mapping in terms of them. At last, developers can program smart home systems upon the MOF-compliant scenario model using the state-of-the-art model driven technologies. https://youtu.be/SP12OtmHj50
Spike sorting using non-volatile metal-oxide memristors
Venue: arXiv cs.ET 2017
Year: 2017

Electrophysiological techniques have improved substantially over the past years to the point that neuroprosthetics applications are becoming viable. This evolution has been fuelled by the advancement of implantable microelectrode technologies that have followed their own version of Moore's scaling law. Similarly to electronics, however, excessive data-rates and strained power budgets require the development of more efficient computation paradigms for handling neural data in-situ, in particular the computationally heavy task of events classification. Here, we demonstrate how the intrinsic analogue programmability of memristive devices can be exploited to perform spike-sorting. We then show how combining memristors with standard logic enables efficient in-silico template matching. Leveraging the physical properties of nanoscale memristors allows us to implement ultra-compact analogue circuits for neural signal processing at the power cost of digital.