OpenRaiser/Intern-Atlas huggingface dataset:
Bibliometric Indicators of Young Authors in Astrophysics: Can Later Stars be Predicted?
Venue: arXiv cs.DL 2014
Year: 2014

We test 16 bibliometric indicators with respect to their validity at the level of the individual researcher by estimating their power to predict later successful researchers. We compare the indicators of a sample of astrophysics researchers who later co-authored highly cited papers before their first landmark paper with the distributions of these indicators over a random control group of young authors in astronomy and astrophysics. We find that field and citation-window normalisation substantially improves the predicting power of citation indicators. The two indicators of total influence based on citation numbers normalised with expected citation numbers are the only indicators which show differences between later stars and random authors significant on a 1% level. Indicators of paper output are not very useful to predict later stars. The famous $h$-index makes no difference at all between later stars and the random control group.
FAST-PPR: Scaling Personalized PageRank Estimation for Large Graphs
Venue: arXiv cs.DS 2014
Year: 2014

We propose a new algorithm, FAST-PPR, for estimating personalized PageRank: given start node $s$ and target node $t$ in a directed graph, and given a threshold $δ$, FAST-PPR estimates the Personalized PageRank $π_s(t)$ from $s$ to $t$, guaranteeing a small relative error as long $π_s(t)>δ$. Existing algorithms for this problem have a running-time of $Ω(1/δ)$; in comparison, FAST-PPR has a provable average running-time guarantee of ${O}(\sqrt{d/δ})$ (where $d$ is the average in-degree of the graph). This is a significant improvement, since $δ$ is often $O(1/n)$ (where $n$ is the number of nodes) for applications. We also complement the algorithm with an $Ω(1/\sqrtδ)$ lower bound for PageRank estimation, showing that the dependence on $δ$ cannot be improved. We perform a detailed empirical study on numerous massive graphs, showing that FAST-PPR dramatically outperforms existing algorithms. For example, on the 2010 Twitter graph with 1.5 billion edges, for target nodes sampled by popularity, FAST-PPR has a $20$ factor speedup over the state of the art. Furthermore, an enhanced version of FAST-PPR has a $160$ factor speedup on the Twitter graph, and is at least $20$ times faster on all our candidate graphs.
UAV Circumnavigating an Unknown Target Under a GPS-denied Environment with Range-only Measurements
Venue: arXiv cs.SY 2014
Year: 2014

One typical application of unmanned aerial vehicles is the intelligence, surveillance, and reconnaissance mission, where the objective is to improve situation awareness through information acquisition. For examples, an efficient way to gather information regarding a target is to deploy UAV in such a way that it orbits around this target at a desired distance. Such a UAV motion is called circumnavigation. The objective of the paper is to design a UAV control algorithm such that this circumnavigation mission is achieved under a GPS-denied environment using range-only measurement. The control algorithm is constructed in two steps. The first step is to design a UAV control algorithm by assuming the availability of both range and range rate measurements, where the associated control input is always bounded. The second step is to further eliminate the use of range rate measurement by using an estimated range rate, obtained via a sliding-mode estimator using range measurement, to replace actual range rate measurement. Such a controller design technique is applicable in the control design of other UAV navigation and control missions under a GPS-denied environment.
Bounds on Distance Estimation via Diffusive Molecular Communication
Venue: arXiv cs.IT 2014
Year: 2014

This paper studies distance estimation for diffusive molecular communication. The Cramer-Rao lower bound on the variance of the distance estimation error is derived. The lower bound is derived for a physically unbounded environment with molecule degradation and steady uniform flow. The maximum likelihood distance estimator is derived and its accuracy is shown via simulation to perform very close to the Cramer-Rao lower bound. An existing protocol is shown to be equivalent to the maximum likelihood distance estimator if only one observation is made. Simulation results also show the accuracy of existing protocols with respect to the Cramer-Rao lower bound.
Motion-Compensated Coding and Frame-Rate Up-Conversion: Models and Analysis
Venue: arXiv cs.MM 2014
Year: 2014

Block-based motion estimation (ME) and compensation (MC) techniques are widely used in modern video processing algorithms and compression systems. The great variety of video applications and devices results in numerous compression specifications. Specifically, there is a diversity of frame-rates and bit-rates. In this paper, we study the effect of frame-rate and compression bit-rate on block-based ME and MC as commonly utilized in inter-frame coding and frame-rate up conversion (FRUC). This joint examination yields a comprehensive foundation for comparing MC procedures in coding and FRUC. First, the video signal is modeled as a noisy translational motion of an image. Then, we theoretically model the motion-compensated prediction of an available and absent frames as in coding and FRUC applications, respectively. The theoretic MC-prediction error is further analyzed and its autocorrelation function is calculated for coding and FRUC applications. We show a linear relation between the variance of the MC-prediction error and temporal-distance. While the affecting distance in MC-coding is between the predicted and reference frames, MC-FRUC is affected by the distance between the available frames used for the interpolation. Moreover, the dependency in temporal-distance implies an inverse effect of the frame-rate. FRUC performance analysis considers the prediction error variance, since it equals to the mean-squared-error of the interpolation. However, MC-coding analysis requires the entire autocorrelation function of the error; hence, analytic simplicity is beneficial. Therefore, we propose two constructions of a separable autocorrelation function for prediction error in MC-coding. We conclude by comparing our estimations with experimental results.
Cost-Effective HITs for Relative Similarity Comparisons
Venue: arXiv cs.CV 2014
Year: 2014

Similarity comparisons of the form "Is object a more similar to b than to c?" are useful for computer vision and machine learning applications. Unfortunately, an embedding of $n$ points is specified by $n^3$ triplets, making collecting every triplet an expensive task. In noticing this difficulty, other researchers have investigated more intelligent triplet sampling techniques, but they do not study their effectiveness or their potential drawbacks. Although it is important to reduce the number of collected triplets, it is also important to understand how best to display a triplet collection task to a user. In this work we explore an alternative display for collecting triplets and analyze the monetary cost and speed of the display. We propose best practices for creating cost effective human intelligence tasks for collecting triplets. We show that rather than changing the sampling algorithm, simple changes to the crowdsourcing UI can lead to much higher quality embeddings. We also provide a dataset as well as the labels collected from crowd workers.
Embed System for Robotic Arm with 3 Degree of Freedom Controller using Computational Vision on Real-Time
Venue: arXiv cs.RO 2014
Year: 2014

This Paper deals with robotic arm embed controller system, with distributed system based on protocol communication between one server supporting multiple points and mobile applications trough sockets .The proposed system utilizes hand with glove gesture in three-dimensional recognition using fuzzy implementation to set x,y,z coordinates. This approach present all implementation over: two raspberry PI arm based computer running client program, x64 PC running server program, and one robot arm controlled by ATmega328p based board.
A Weighted Correlation Index for Rankings with Ties
Venue: arXiv cs.SI 2014
Year: 2014

Understanding the correlation between two different scores for the same set of items is a common problem in information retrieval, and the most commonly used statistics that quantifies this correlation is Kendall's $τ$. However, the standard definition fails to capture that discordances between items with high rank are more important than those between items with low rank. Recently, a new measure of correlation based on average precision has been proposed to solve this problem, but like many alternative proposals in the literature it assumes that there are no ties in the scores. This is a major deficiency in a number of contexts, and in particular while comparing centrality scores on large graphs, as the obvious baseline, indegree, has a very large number of ties in web and social graphs. We propose to extend Kendall's definition in a natural way to take into account weights in the presence of ties. We prove a number of interesting mathematical properties of our generalization and describe an $O(n\log n)$ algorithm for its computation. We also validate the usefulness of our weighted measure of correlation using experimental data.
Supremum-Norm Convergence for Step-Asynchronous Successive Overrelaxation on M-matrices
Venue: arXiv cs.DS 2014
Year: 2014

Step-asynchronous successive overrelaxation updates the values contained in a single vector using the usual Gauß-Seidel-like weighted rule, but arbitrarily mixing old and new values, the only constraint being temporal coherence: you cannot use a value before it has been computed. We show that given a nonnegative real matrix $A$, a $σ\geqρ(A)$ and a vector $\boldsymbol w>0$ such that $A\boldsymbol w\leqσ\boldsymbol w$, every iteration of step-asynchronous successive overrelaxation for the problem $(sI- A)\boldsymbol x=\boldsymbol b$, with $s >σ$, reduces geometrically the $\boldsymbol w$-norm of the current error by a factor that we can compute explicitly. Then, we show that given a $σ>ρ(A)$ it is in principle always possible to compute such a $\boldsymbol w$. This property makes it possible to estimate the supremum norm of the absolute error at each iteration without any additional hypothesis on $A$, even when $A$ is so large that computing the product $A\boldsymbol x$ is feasible, but estimating the supremum norm of $(sI-A)^{-1}$ is not.
Complexity theoretic limitations on learning DNF's
Venue: arXiv cs.LG 2014
Year: 2014

Using the recently developed framework of [Daniely et al, 2014], we show that under a natural assumption on the complexity of refuting random K-SAT formulas, learning DNF formulas is hard. Furthermore, the same assumption implies the hardness of learning intersections of $ω(\log(n))$ halfspaces, agnostically learning conjunctions, as well as virtually all (distribution free) learning problems that were previously shown hard (under complexity assumptions).
Modeling the Temperature Bias of Power Consumption for Nanometer-Scale CPUs in Application Processors
Venue: arXiv cs.AR 2014
Year: 2014

We introduce and experimentally validate a new macro-level model of the CPU temperature/power relationship within nanometer-scale application processors or system-on-chips. By adopting a holistic view, this model is able to take into account many of the physical effects that occur within such systems. Together with two algorithms described in the paper, our results can be used, for instance by engineers designing power or thermal management units, to cancel the temperature-induced bias on power measurements. This will help them gather temperature-neutral power data while running multiple instance of their benchmarks. Also power requirements and system failure rates can be decreased by controlling the CPU's thermal behavior. Even though it is usually assumed that the temperature/power relationship is exponentially related, there is however a lack of publicly available physical temperature/power measurements to back up this assumption, something our paper corrects. Via measurements on two pertinent platforms sporting nanometer-scale application processors, we show that the power/temperature relationship is indeed very likely exponential over a 20°C to 85°C temperature range. Our data suggest that, for application processors operating between 20°C and 50°C, a quadratic model is still accurate and a linear approximation is acceptable.
Adjacency labeling schemes and induced-universal graphs
Venue: arXiv cs.DS 2014
Year: 2014

We describe a way of assigning labels to the vertices of any undirected graph on up to $n$ vertices, each composed of $n/2+O(1)$ bits, such that given the labels of two vertices, and no other information regarding the graph, it is possible to decide whether or not the vertices are adjacent in the graph. This is optimal, up to an additive constant, and constitutes the first improvement in almost 50 years of an $n/2+O(\log n)$ bound of Moon. As a consequence, we obtain an induced-universal graph for $n$-vertex graphs containing only $O(2^{n/2})$ vertices, which is optimal up to a multiplicative constant, solving an open problem of Vizing from 1968. We obtain similar tight results for directed graphs, tournaments and bipartite graphs.
Achievable Secrecy Rates over MIMOME Gaussian Channels with GMM Signals in Low-Noise Regime
Venue: arXiv cs.IT 2014
Year: 2014

We consider a wiretap multiple-input multiple-output multiple-eavesdropper (MIMOME) channel, where agent Alice aims at transmitting a secret message to agent Bob, while leaking no information on it to an eavesdropper agent Eve. We assume that Alice has more antennas than both Bob and Eve, and that she has only statistical knowledge of the channel towards Eve. We focus on the low-noise regime, and assess the secrecy rates that are achievable when the secret message determines the distribution of a multivariate Gaussian mixture model (GMM) from which a realization is generated and transmitted over the channel. In particular, we show that if Eve has fewer antennas than Bob, secret transmission is always possible at low-noise. Moreover, we show that in the low-noise limit the secrecy capacity of our scheme coincides with its unconstrained capacity, by providing a class of covariance matrices that allow to attain such limit without the need of wiretap coding.
Using Wireless Network Coding to Replace a Wired with Wireless Backhaul
Venue: arXiv cs.IT 2014
Year: 2014

Cellular networks are evolving towards dense deployment of small cells. This in turn demands flexible and efficient backhauling solutions. A viable solution that reuses the same spectrum is wireless backhaul where the Small Base Station (SBS) acts as a relay. In this paper we consider a reference system that uses wired backhaul and each Mobile Station (MS) in the small cell has its uplink and downlink rates defined. The central question is: if we remove the wired backhaul, how much extra power should the wireless backhaul use in order to support the same uplink/downlink rates? We introduce the idea of wireless-emulated wire (WEW), based on two-way relaying and network coding. Furthermore, in a scenario where two SBSs are served simultaneously, WEW gives rise to new communication strategies, partially inspired by the private/public messages from the Han-Kobayashi scheme for interference channel. We formulate and solve the associated optimization problems. The proposed approach provides a convincing argument that two-way communication is the proper context to design and optimize wireless backhauling solutions.
BeSpaceD: Towards a Tool Framework and Methodology for the Specification and Verification of Spatial Behavior of Distributed Software Component Systems
Venue: arXiv cs.SE 2014
Year: 2014

In this report, we present work towards a framework for modeling and checking behavior of spatially distributed component systems. Design goals of our framework are the ability to model spatial behavior in a component oriented, simple and intuitive way, the possibility to automatically analyse and verify systems and integration possibilities with other modeling and verification tools. We present examples and the verification steps necessary to prove properties such as range coverage or the absence of collisions between components and technical details.
PCANet: A Simple Deep Learning Baseline for Image Classification?
Venue: arXiv cs.CV 2014
Year: 2014

In this work, we propose a very simple deep learning network for image classification which comprises only the very basic data processing components: cascaded principal component analysis (PCA), binary hashing, and block-wise histograms. In the proposed architecture, PCA is employed to learn multistage filter banks. It is followed by simple binary hashing and block histograms for indexing and pooling. This architecture is thus named as a PCA network (PCANet) and can be designed and learned extremely easily and efficiently. For comparison and better understanding, we also introduce and study two simple variations to the PCANet, namely the RandNet and LDANet. They share the same topology of PCANet but their cascaded filters are either selected randomly or learned from LDA. We have tested these basic networks extensively on many benchmark visual datasets for different tasks, such as LFW for face verification, MultiPIE, Extended Yale B, AR, FERET datasets for face recognition, as well as MNIST for hand-written digits recognition. Surprisingly, for all tasks, such a seemingly naive PCANet model is on par with the state of the art features, either prefixed, highly hand-crafted or carefully learned (by DNNs). Even more surprisingly, it sets new records for many classification tasks in Extended Yale B, AR, FERET datasets, and MNIST variations. Additional experiments on other public datasets also demonstrate the potential of the PCANet serving as a simple but highly competitive baseline for texture classification and object recognition.
A Game-Theoretic Framework for Decentralized Cooperative Data Exchange using Network Coding
Venue: arXiv cs.IT 2014
Year: 2014

In this paper, we introduce a game theoretic framework for studying the problem of minimizing the delay of instantly decodable network coding (IDNC) for cooperative data exchange (CDE) in decentralized wireless network. In this configuration, clients cooperate with each other to recover the erased packets without a central controller. Game theory is employed herein as a tool for improving the distributed solution by overcoming the need for a central controller or additional signaling in the system. We model the session by self-interested players in a non-cooperative potential game. The utility functions are designed such that increasing individual payoff results in a collective behavior achieving both a desirable system performance in a shared network environment and the Nash bargaining solution. Three games are developed: the first aims to reduce the completion time, the second to reduce the maximum decoding delay and the third the sum decoding delay. We improve these formulations to include punishment policy upon collision occurrence and achieve the Nash bargaining solution. Through extensive simulations, our framework is tested against the best performance that could be found in the conventional point-to-multipoint (PMP) recovery process in numerous cases: first we simulate the problem with complete information. We, then, simulate with incomplete information and finally we test it in lossy feedback scenario. Numerical results show that our formulation with complete information largely outperforms the conventional PMP scheme in most situations and achieves a lower delay. They also show that the completion time formulation with incomplete information also outperforms the conventional PMP.
Meta-evaluation of comparability metrics using parallel corpora
Venue: arXiv cs.CL 2014
Year: 2014

Metrics for measuring the comparability of corpora or texts need to be developed and evaluated systematically. Applications based on a corpus, such as training Statistical MT systems in specialised narrow domains, require finding a reasonable balance between the size of the corpus and its consistency, with controlled and benchmarked levels of comparability for any newly added sections. In this article we propose a method that can meta-evaluate comparability metrics by calculating monolingual comparability scores separately on the 'source' and 'target' sides of parallel corpora. The range of scores on the source side is then correlated (using Pearson's r coefficient) with the range of 'target' scores; the higher the correlation - the more reliable is the metric. The intuition is that a good metric should yield the same distance between different domains in different languages. Our method gives consistent results for the same metrics on different data sets, which indicates that it is reliable and can be used for metric comparison or for optimising settings of parametrised metrics.
Changing Bases: Multistage Optimization for Matroids and Matchings
Venue: arXiv cs.DS 2014
Year: 2014

This paper is motivated by the fact that many systems need to be maintained continually while the underlying costs change over time. The challenge is to continually maintain near-optimal solutions to the underlying optimization problems, without creating too much churn in the solution itself. We model this as a multistage combinatorial optimization problem where the input is a sequence of cost functions (one for each time step); while we can change the solution from step to step, we incur an additional cost for every such change. We study the multistage matroid maintenance problem, where we need to maintain a base of a matroid in each time step under the changing cost functions and acquisition costs for adding new elements. The online version of this problem generalizes online paging. E.g., given a graph, we need to maintain a spanning tree $T_t$ at each step: we pay $c_t(T_t)$ for the cost of the tree at time $t$, and also $| T_t\setminus T_{t-1} |$ for the number of edges changed at this step. Our main result is an $O(\log m \log r)$-approximation, where $m$ is the number of elements/edges and $r$ is the rank of the matroid. We also give an $O(\log m)$ approximation for the offline version of the problem. These bounds hold when the acquisition costs are non-uniform, in which caseboth these results are the best possible unless P=NP. We also study the perfect matching version of the problem, where we must maintain a perfect matching at each step under changing cost functions and costs for adding new elements. Surprisingly, the hardness drastically increases: for any constant $ε>0$, there is no $O(n^{1-ε})$-approximation to the multistage matching maintenance problem, even in the offline case.