OpenRaiser/Intern-Atlas huggingface dataset:
Optimal Beamforming and Time Allocation for Partially Wireless Powered Sensor Networks with Downlink SWIPT
Venue: arXiv cs.IT 2018
Year: 2018

Wireless powered sensor networks (WPSNs) have emerged as a key development towards the future self-sustainable Internet of Things (IoT) networks. To achieve a good balance between self-sustainability and reliability, partially WPSNs with a mixed power solution are desirable for practical applications. Specifically, most of the sensor nodes are wireless powered but the key sensor node adopts traditional wire/battery power for reliability. As a result, this paper mainly investigates optimal design for the partially WPSNs in which simultaneous wireless information and power transfer (SWIPT) is adopted in the downlink. Two scenarios with space division multiple access (SDMA) and time division multiple access (TDMA) in the uplink are considered. For both the SDMA-enabled and TDMA-enabled partially WPSNs, joint design of downlink beamforming, uplink beamforming and time allocation is investigated to maximize the uplink sum rate while guaranteeing the quality-of-service (i.e., satisfying the downlink rate constraint) at the key sensor node. After analyzing the feasibility of uplink sum rate maximization problems and the influence of the downlink rate constraint, semi-closed-form optimal solutions for both SDMA-enabled and TDMA-enabled WPSNs are proposed with guaranteed global optimality. Complexity analysis is also provided to justify the advantage of the proposed solutions in low complexity. The effectiveness and optimality of the proposed optimal solutions are finally demonstrated by simulations.
Approximate Nearest Neighbor Search in High Dimensions
Venue: arXiv cs.DS 2018
Year: 2018

The nearest neighbor problem is defined as follows: Given a set $P$ of $n$ points in some metric space $(X,D)$, build a data structure that, given any point $q$, returns a point in $P$ that is closest to $q$ (its "nearest neighbor" in $P$). The data structure stores additional information about the set $P$, which is then used to find the nearest neighbor without computing all distances between $q$ and $P$. The problem has a wide range of applications in machine learning, computer vision, databases and other fields. To reduce the time needed to find nearest neighbors and the amount of memory used by the data structure, one can formulate the {\em approximate} nearest neighbor problem, where the the goal is to return any point $p' \in P$ such that the distance from $q$ to $p'$ is at most $c \cdot \min_{p \in P} D(q,p)$, for some $c \geq 1$. Over the last two decades, many efficient solutions to this problem were developed. In this article we survey these developments, as well as their connections to questions in geometric functional analysis and combinatorial geometry.
Virtual Carrier Sensing Based Random Access in Massive MIMO Systems
Venue: arXiv cs.IT 2018
Year: 2018

The 5th generation mobile communication systems aim to support massive access for future wireless applications. Unfortunately, wireless resource scarcity in random access (RA) is a fundamental bottleneck for enabling massive access. To address this problem, we propose a virtual carrier sensing (VCS) based RA scheme in massive MIMO systems. The essence of the proposed scheme lies in exploiting wireless spatial resources of uplink channels occupied by assigned user equipments (UEs) to increase channel resources for RA. With the proposed scheme, RA UEs are able to exploit the spatial resources that are approximately orthogonal to those of assigned UEs, thus sharing the uplink channel resource with assigned UEs without causing significant interference to them. Specifically, to ensure RA UEs avoid serious interference with assigned UEs, base station (BS) sends tailored virtual carriers to RA UEs on behalf of assigned UEs. RA UEs then conduct VCS to determine whether or not the uplink channel resource is available for RA. Closed-form approximations for probability of channel availability and uplink achievable rate with the proposed scheme are derived. Theoretical analysis and simulation results show that the proposed scheme is able to significantly increase channel resources of RA for massive access.
On the Capacity Region of a Cache-Aided Gaussian Broadcast Channel with Multi-Layer Messages
Venue: arXiv cs.IT 2018
Year: 2018

A cache-aided $K$-user Gaussian broadcast channel (BC) is studied. The transmitter has a library of $N$ files, from which each user requests one. The users are equipped with caches of different sizes, which are filled without the knowledge of the user requests in a centralized manner. Differently from the literature, it is assumed that each file can be delivered to different users at different rates, which may correspond to different quality representations of the underlying content, e.g., scalable coded video segments. Accordingly, instead of a single achievable rate, the system performance is characterized by a rate tuple, which corresponds to the vector of rates users' requests can be delivered at. The goal is to characterize the set of all achievable rate tuples for a given total cache capacity by designing joint cache and channel coding schemes together with cache allocation across users. Assuming that the users are ordered in increasing channel quality, each file is coded into $K$ layers, and only the first $k$ layers of the requested file are delivered to user $k$, $k=1,...,K$. Three different coding schemes are proposed, which differ in the way they deliver the coded contents over the BC; in particular, time-division, superposition, and dirty paper coding schemes are studied. Corresponding achievable rate regions are characterized, and compared with a novel outer bound. To the best of our knowledge, this is the first work studying the delivery of files at different rates over a cache-aided noisy BC.
Online Signature Verification using Deep Representation: A new Descriptor
Venue: arXiv cs.CV 2018
Year: 2018

This paper presents an accurate method for verifying online signatures. The main difficulty of signature verification come from: (1) Lacking enough training samples (2) The methods must be spatial change invariant. To deal with these difficulties and modeling the signatures efficiently, we propose a method that a one-class classifier per each user is built on discriminative features. First, we pre-train a sparse auto-encoder using a large number of unlabeled signatures, then we applied the discriminative features, which are learned by auto-encoder to represent the training and testing signatures as a self-thought learning method (i.e. we have introduced a signature descriptor). Finally, user's signatures are modeled and classified using a one-class classifier. The proposed method is independent on signature datasets thanks to self-taught learning. The experimental results indicate significant error reduction and accuracy enhancement in comparison with state-of-the-art methods on SVC2004 and SUSIG datasets.
Delay Performance of the Multiuser MISO Downlink under Imperfect CSI and Finite Length Coding
Venue: arXiv cs.IT 2018
Year: 2018

We use stochastic network calculus to investigate the delay performance of a multiuser MISO system with zero-forcing beamforming. First, we consider ideal assumptions with long codewords and perfect CSI at the transmitter, where we observe a strong channel hardening effect that results in very high reliability with respect to the maximum delay of the application. We then study the system under more realistic assumptions with imperfect CSI and finite blocklength channel coding. These effects lead to interference and to transmission errors, and we derive closed-form lower and upper bounds on the resulting error probability. Compared to the ideal case, imperfect CSI and finite length coding cause massive degradations in the average transmission rate. Surprisingly, the system nevertheless maintains the same qualitative behavior as in the ideal case: as long as the average transmission rate is higher than the arrival rate, the system can still achieve very high reliability with respect to the maximum delay.
Fully Dynamic Maximal Independent Set with Sublinear in n Update Time
Venue: arXiv cs.DS 2018
Year: 2018

The first fully dynamic algorithm for maintaining a maximal independent set (MIS) with update time that is sublinear in the number of edges was presented recently by the authors of this paper [Assadi et.al. STOC'18]. The algorithm is deterministic and its update time is $O(m^{3/4})$, where $m$ is the (dynamically changing) number of edges. Subsequently, Gupta and Khan and independently Du and Zhang [arXiv, April 2018] presented deterministic algorithms for dynamic MIS with update times of $O(m^{2/3})$ and $O(m^{2/3} \sqrt{\log m})$, respectively. Du and Zhang also gave a randomized algorithm with update time $\widetilde{O}(\sqrt{m})$. Moreover, they provided some partial (conditional) hardness results hinting that update time of $m^{1/2-ε}$, and in particular $n^{1-ε}$ for $n$-vertex dense graphs, is a natural barrier for this problem for any constant $ε>0$, for both deterministic and randomized algorithms that satisfy a certain natural property. In this paper, we break this natural barrier and present the first fully dynamic (randomized) algorithm for maintaining an MIS with update time that is always sublinear in the number of vertices, namely, an $\widetilde{O}(\sqrt{n})$ expected amortized update time algorithm. We also show that a simpler variant of our algorithm can already achieve an $\widetilde{O}(m^{1/3})$ expected amortized update time, which results in an improved performance over our $\widetilde{O}(\sqrt{n})$ update time algorithm for sufficiently sparse graphs, and breaks the $m^{1/2}$ barrier of Du and Zhang for all values of $m$.
Is your function low-dimensional?
Venue: arXiv cs.CC 2018
Year: 2018

We study the problem of testing if a function depends on a small number of linear directions of its input data. We call a function $f$ a linear $k$-junta if it is completely determined by some $k$-dimensional subspace of the input space. In this paper, we study the problem of testing whether a given $n$ variable function $f : \mathbb{R}^n \to \{0,1\}$, is a linear $k$-junta or $ε$-far from all linear $k$-juntas, where the closeness is measured with respect to the Gaussian measure on $\mathbb{R}^n$. Linear $k$-juntas are a common generalization of two fundamental classes from Boolean function analysis (both of which have been studied in property testing) $\textbf{1.}$ $k$- juntas which are functions on the Boolean cube which depend on at most k of the variables and $\textbf{2.}$ intersection of $k$ halfspaces, a fundamental geometric concept class. We show that the class of linear $k$-juntas is not testable, but adding a surface area constraint makes it testable: we give a $\mathsf{poly}(k \cdot s/ε)$-query non-adaptive tester for linear $k$-juntas with surface area at most $s$. We show that the polynomial dependence on $s$ is necessary. Moreover, we show that if the function is a linear $k$-junta with surface area at most $s$, we give a $(s \cdot k)^{O(k)}$-query non-adaptive algorithm to learn the function up to a rotation of the basis. In particular, this implies that we can test the class of intersections of $k$ halfspaces in $\mathbb{R}^n$ with query complexity independent of $n$.
Self-Reproducing Coins as Universal Turing Machine
Venue: arXiv cs.CR 2018
Year: 2018

Turing-completeness of smart contract languages in blockchain systems is often associated with a variety of language features (such as loops). In opposite, we show that Turing-completeness of a blockchain system can be achieved through unwinding the recursive calls between multiple transactions and blocks instead of using a single one. We prove it by constructing a simple universal Turing machine using a small set of language features in the unspent transaction output (UTXO) model, with explicitly given relations between input and output transaction states. Neither unbounded loops nor possibly infinite validation time are needed in this approach.
Leveraging Disease Progression Learning for Medical Image Recognition
Venue: arXiv cs.CV 2018
Year: 2018

Unlike natural images, medical images often have intrinsic characteristics that can be leveraged for neural network learning. For example, images that belong to different stages of a disease may continuously follow a certain progression pattern. In this paper, we propose a novel method that leverages disease progression learning for medical image recognition. In our method, sequences of images ordered by disease stages are learned by a neural network that consists of a shared vision model for feature extraction and a long short-term memory network for the learning of stage sequences. Auxiliary vision outputs are also included to capture stage features that tend to be discrete along the disease progression. Our proposed method is evaluated on a public diabetic retinopathy dataset, and achieves about 3.3% improvement in disease staging accuracy, compared to the baseline method that does not use disease progression learning.
Do Political Detachment Users Receive Various Political Information on Social Media?
Venue: arXiv cs.SI 2018
Year: 2018

In the election, political parties communicate political information to people through social media. The followers receive the information, but can users who are not followers, political detachment users, receive the information? We focus on political detachment users who do not follow any political parties, and tackle the following research question: do political detachment users receive various political information during the election period? The results indicate that the answer is No. We determined that the political detachment users only receive the information of a few political parties.
Practical Access to Dynamic Programming on Tree Decompositions
Venue: arXiv cs.DS 2018
Year: 2018

Parameterized complexity theory has lead to a wide range of algorithmic breakthroughs within the last decades, but the practicability of these methods for real-world problems is still not well understood. We investigate the practicability of one of the fundamental approaches of this field: dynamic programming on tree decompositions. Indisputably, this is a key technique in parameterized algorithms and modern algorithm design. Despite the enormous impact of this approach in theory, it still has very little influence on practical implementations. The reasons for this phenomenon are manifold. One of them is the simple fact that such an implementation requires a long chain of non-trivial tasks (as computing the decomposition, preparing it,...). We provide an easy way to implement such dynamic programs that only requires the definition of the update rules. With this interface, dynamic programs for various problems, such as 3-coloring, can be implemented easily in about 100 lines of structured Java code. The theoretical foundation of the success of dynamic programming on tree decompositions is well understood due to Courcelle's celebrated theorem, which states that every MSO-definable problem can be efficiently solved if a tree decomposition of small width is given. We seek to provide practical access to this theorem as well, by presenting a lightweight model-checker for a small fragment of MSO. This fragment is powerful enough to describe many natural problems, and our model-checker turns out to be very competitive against similar state-of-the-art tools.
Multi-Merge Budget Maintenance for Stochastic Gradient Descent SVM Training
Venue: arXiv cs.LG 2018
Year: 2018

Budgeted Stochastic Gradient Descent (BSGD) is a state-of-the-art technique for training large-scale kernelized support vector machines. The budget constraint is maintained incrementally by merging two points whenever the pre-defined budget is exceeded. The process of finding suitable merge partners is costly; it can account for up to 45% of the total training time. In this paper we investigate computationally more efficient schemes that merge more than two points at once. We obtain significant speed-ups without sacrificing accuracy.
Indexing Operators to Extend the Reach of Symbolic Execution
Venue: arXiv cs.SE 2018
Year: 2018

Traditional program analysis analyses a program language, that is, all programs that can be written in the language. There is a difference, however, between all possible programs that can be written and the corpus of actual programs written in a language. We seek to exploit this difference: for a given program, we apply a bespoke program transformation Indexify to convert expressions that current SMT solvers do not, in general, handle, such as constraints on strings, into equisatisfiable expressions that they do handle. To this end, Indexify replaces operators in hard-to-handle expressions with homomorphic versions that behave the same on a finite subset of the domain of the original operator, and return bottom denoting unknown outside of that subset. By focusing on what literals and expressions are most useful for analysing a given program, Indexify constructs a small, finite theory that extends the power of a solver on the expressions a target program builds. Indexify's bespoke nature necessarily means that its evaluation must be experimental, resting on a demonstration of its effectiveness in practice. We have developed Indexif}, a tool for Indexify. We demonstrate its utility and effectiveness by applying it to two real world benchmarks --- string expressions in coreutils and floats in fdlibm53. Indexify reduces time-to-completion on coreutils from Klee's 49.5m on average to 6.0m. It increases branch coverage on coreutils from 30.10% for Klee and 14.79% for Zesti to 66.83%. When indexifying floats in fdlibm53, Indexifyl increases branch coverage from 34.45% to 71.56% over Klee. For a restricted class of inputs, Indexify permits the symbolic execution of program paths unreachable with previous techniques: it covers more than twice as many branches in coreutils as Klee.
Collaborative Annotation of Semantic Objects in Images with Multi-granularity Supervisions
Venue: arXiv cs.CV 2018
Year: 2018

Per-pixel masks of semantic objects are very useful in many applications, which, however, are tedious to be annotated. In this paper, we propose a human-agent collaborative annotation approach that can efficiently generate per-pixel masks of semantic objects in tagged images with multi-granularity supervisions. Given a set of tagged image, a computer agent is first dynamically generated to roughly localize the semantic objects described by the tag. The agent first extracts massive object proposals from an image and then infer the tag-related ones under the weak and strong supervisions from linguistically and visually similar images and previously annotated object masks. By representing such supervisions by over-complete dictionaries, the tag-related object proposals can pop-out according to their sparse coding length, which are then converted to superpixels with binary labels. After that, human annotators participate in the annotation process by flipping labels and dividing superpixels with mouse clicks, which are used as click supervisions that teach the agent to recover false positives/negatives in processing images with the same tags. Experimental results show that our approach can facilitate the annotation process and generate object masks that are highly consistent with those generated by the LabelMe toolbox.
Optimal Scheduling of Electrolyzer in Power Market with Dynamic Prices
Venue: arXiv cs.LG 2018
Year: 2018

Optimal scheduling of hydrogen production in dynamic pricing power market can maximize the profit of hydrogen producer; however, it highly depends on the accurate forecast of hydrogen consumption. In this paper, we propose a deep leaning based forecasting approach for predicting hydrogen consumption of fuel cell vehicles in future taxi industry. The cost of hydrogen production is minimized by utilizing the proposed forecasting tool to reduce the hydrogen produced during high cost on-peak hours and guide hydrogen producer to store sufficient hydrogen during low cost off-peak hours.
A Generalized Data Representation and Training-Performance Analysis for Deep Learning-Based Communications Systems
Venue: arXiv cs.IT 2018
Year: 2018

Deep learning (DL)-based autoencoder is a potential architecture to implement end-to-end communication systems. In this letter, we first give a brief introduction to the autoencoder-represented communication system. Then, we propose a novel generalized data representation (GDR) aiming to improve the data rate of DL-based communication systems. Finally, simulation results show that the proposed GDR scheme has lower training complexity, comparable block error rate performance and higher channel capacity than the conventional one-hot vector scheme. Furthermore, we investigate the effect of signal-to-noise ratio (SNR) in DL-based communication systems and prove that training at a high SNR could produce a good training performance for autoencoder.
Disparity Image Segmentation For ADAS
Venue: arXiv cs.CV 2018
Year: 2018

We present a simple solution for segmenting grayscale images using existing Connected Component Labeling (CCL) algorithms (which are generally applied to binary images), which was efficient enough to be implemented in a constrained (embedded automotive) architecture. Our solution customizes the region growing and merging approach, and is primarily targeted for stereoscopic disparity images where nearer objects carry more relevance. We provide results from a standard OpenCV implementation for some basic cases and an image from the Tsukuba stereo-pair dataset.
A Proof of the Front-Door Adjustment Formula
Venue: arXiv cs.AI 2018
Year: 2018

We provide a proof of the the Front-Door adjustment formula using the do-calculus.
Evaluating author name disambiguation for digital libraries: A case of DBLP
Venue: arXiv cs.DL 2018
Year: 2018

Author name ambiguity in a digital library may affect the findings of research that mines authorship data of the library. This study evaluates author name disambiguation in DBLP, a widely used but insufficiently evaluated digital library for its disambiguation performance. In doing so, this study takes a triangulation approach that author name disambiguation for a digital library can be better evaluated when its performance is assessed on multiple labeled datasets with comparison to baselines. Tested on three types of labeled data containing 5,000 ~ 700K disambiguated names and 6M pairs of disambiguated names, DBLP is shown to assign author names quite accurately to distinct authors, resulting in pairwise precision, recall, and F1 measures around 0.90 or above overall. DBLP's author name disambiguation performs well even on large ambiguous name blocks but deficiently on distinguishing authors with the same names. When compared to other disambiguation algorithms, DBLP's disambiguation performance is quite competitive, possibly due to its hybrid disambiguation approach combining algorithmic disambiguation and manual error correction. A discussion follows on strengths and weaknesses of labeled datasets used in this study for future efforts to evaluate author name disambiguation on a digital library scale.