OpenRaiser/Intern-Atlas huggingface dataset:
Factorized schemes of second-order accuracy for numerical solving unsteady problems
Venue: arXiv cs.NA 2015
Year: 2015

Schemes with the second-order approximation in time are considered for numerical solving the Cauchy problem for an evolutionary equation of first order with a self-adjoint operator. The implicit two-level scheme based on the Padé polynomial approximation is unconditionally stable. It demonstrates good asymptotic properties in time and provides an adequate evolution in time for individual harmonics of the solution (has spectral mimetic stability). In fact, the only drawback of this scheme is the necessity to solve an equation with an operator polynomial of second degree at each time level. We consider modifications of these schemes, which are based on solving equations with operator polynomials of first degree. Such computational implementations occur, for example, if we apply the fully implicit two-level scheme (the backward Euler scheme). A three-level modification of the SM-stable scheme is proposed. Its unconditional stability is established in the corresponding norms. The emphasis is on the scheme, where the numerical algorithm involves two stages, namely, the backward Euler scheme of first order at the first (prediction) stage and the following correction of the approximate solution using a factorized operator. The SM-stability is established for the proposed scheme. To illustrate the theoretical results of the work, a model problem is solved numerically.
Concurrent codes: A holographic-type encoding robust against noise and loss
Venue: arXiv cs.IT 2015
Year: 2015

Concurrent coding is an encoding scheme with "holographic" type properties that are shown here to be robust against a significant amount of noise and signal loss. This single encoding scheme is able to correct for random errors and burst errors simultaneously, but does not rely on cyclic codes. A simple and practical scheme has been tested that displays perfect decoding when the signal to noise ratio is of order -18dB. The same scheme also displays perfect reconstruction when a contiguous block of 40% of the transmission is missing. In addition this scheme is 50% more efficient in terms of transmitted power requirements than equivalent cyclic codes. A simple model is presented that describes the process of decoding and can determine the computational load that would be expected, as well as describing the critical levels of noise and missing data at which false messages begin to be generated.
On the Capacity of Level and Type Modulation in Molecular Communication with Ligand Receptors
Venue: arXiv cs.IT 2015
Year: 2015

In this paper, we consider the bacterial point-to-point communication problem with one transmitter and one receiver by considering the ligand receptor binding process. The most commonly investigated signalling model, referred to as the Level Scenario (LS), uses one type of a molecule with different concentration levels for signaling. An alternative approach is to employ multiple types of molecules with a single concentration level, referred to as the Type Scenario (TS). We investigate the trade-offs between the two scenarios for the ligand receptor from the capacity point of view. For this purpose, we evaluate the capacity using numerical algorithms. Moreover, we derive an upper bound on the capacity of the ligand receptor using a Binomial Channel (BIC) model using symmetrized Kullback-Leibler (KL) divergence. A lower bound is also derived when the environment noise is negligible. Finally, we analyse the effect of blocking of a receptor by a molecule of a different type, by proposing a new Markov model in the multiple-type signalling.
Caffe con Troll: Shallow Ideas to Speed Up Deep Learning
Venue: arXiv cs.LG 2015
Year: 2015

We present Caffe con Troll (CcT), a fully compatible end-to-end version of the popular framework Caffe with rebuilt internals. We built CcT to examine the performance characteristics of training and deploying general-purpose convolutional neural networks across different hardware architectures. We find that, by employing standard batching optimizations for CPU training, we achieve a 4.5x throughput improvement over Caffe on popular networks like CaffeNet. Moreover, with these improvements, the end-to-end training time for CNNs is directly proportional to the FLOPS delivered by the CPU, which enables us to efficiently train hybrid CPU-GPU systems for CNNs.
Benford's Law Applies To Online Social Networks
Venue: arXiv cs.SI 2015
Year: 2015

Benford's Law states that the frequency of first digits of numbers in naturally occurring systems is not evenly distributed. Numbers beginning with a 1 occur roughly 30\% of the time, and are six times more common than numbers beginning with a 9. We show that Benford's Law applies to social and behavioral features of users in online social networks. We consider social data from five major social networks: Facebook, Twitter, Google Plus, Pinterest, and Live Journal. We show that the distribution of first significant digits of friend and follower counts for users in these systems follow Benford's Law. The same holds for the number of posts users make. We extend this to egocentric networks, showing that friend counts among the people in an individual's social network also follow the expected distribution. We discuss how this can be used to detect suspicious or fraudulent activity online and to validate datasets.
Two-Phase Cooperative Broadcasting Based on Batched Network Code
Venue: arXiv cs.IT 2015
Year: 2015

In this paper, we consider the wireless broadcasting scenario with a source node sending some common information to a group of closely located users, where each link is subject to certain packet erasures. To ensure reliable information reception by all users, the conventional approach generally requires repeated transmission by the source until all the users are able to decode the information, which is inefficient in many practical scenarios. In this paper, by exploiting the close proximity among the users, we propose a novel two-phase wireless broadcasting protocol with user cooperations based on an efficient batched network code, known as batched sparse (BATS) code. In the first phase, the information packets are encoded into batches with BATS encoder and sequentially broadcasted by the source node until certain terminating criterion is met. In the second phase, the users cooperate with each other by exchanging the network-coded information via peer-to-peer (P2P) communications based on their respective received packets. A fully distributed and light-weight scheduling algorithm is proposed to improve the efficiency of the P2P communication in the second phase. The performance of the proposed two-phase protocol is analyzed and the channel rank distribution at the instance of decoding is derived, based on which the optimal BATS code is designed. Simulation results demonstrate that the proposed protocol significantly outperforms the existing schemes. Lastly, the performance of the proposed scheme is further verified via testbed experiments.
Simpler, faster and shorter labels for distances in graphs
Venue: arXiv cs.DS 2015
Year: 2015

We consider how to assign labels to any undirected graph with n nodes such that, given the labels of two nodes and no other information regarding the graph, it is possible to determine the distance between the two nodes. The challenge in such a distance labeling scheme is primarily to minimize the maximum label lenght and secondarily to minimize the time needed to answer distance queries (decoding). Previous schemes have offered different trade-offs between label lengths and query time. This paper presents a simple algorithm with shorter labels and shorter query time than any previous solution, thereby improving the state-of-the-art with respect to both label length and query time in one single algorithm. Our solution addresses several open problems concerning label length and decoding time and is the first improvement of label length for more than three decades. More specifically, we present a distance labeling scheme with label size (log 3)/2 + o(n) (logarithms are in base 2) and O(1) decoding time. This outperforms all existing results with respect to both size and decoding time, including Winkler's (Combinatorica 1983) decade-old result, which uses labels of size (log 3)n and O(n/log n) decoding time, and Gavoille et al. (SODA'01), which uses labels of size 11n + o(n) and O(loglog n) decoding time. In addition, our algorithm is simpler than the previous ones. In the case of integral edge weights of size at most W, we present almost matching upper and lower bounds for label sizes. For r-additive approximation schemes, where distances can be off by an additive constant r, we give both upper and lower bounds. In particular, we present an upper bound for 1-additive approximation schemes which, in the unweighted case, has the same size (ignoring second order terms) as an adjacency scheme: n/2. We also give results for bipartite graphs and for exact and 1-additive distance oracles.
Hyperspectral pansharpening: a review
Venue: arXiv cs.CV 2015
Year: 2015

Pansharpening aims at fusing a panchromatic image with a multispectral one, to generate an image with the high spatial resolution of the former and the high spectral resolution of the latter. In the last decade, many algorithms have been presented in the literature for pansharpening using multispectral data. With the increasing availability of hyperspectral systems, these methods are now being adapted to hyperspectral images. In this work, we compare new pansharpening techniques designed for hyperspectral data with some of the state of the art methods for multispectral pansharpening, which have been adapted for hyperspectral data. Eleven methods from different classes (component substitution, multiresolution analysis, hybrid, Bayesian and matrix factorization) are analyzed. These methods are applied to three datasets and their effectiveness and robustness are evaluated with widely used performance indicators. In addition, all the pansharpening techniques considered in this paper have been implemented in a MATLAB toolbox that is made available to the community.
One-Bit Massive MIMO: Channel Estimation and High-Order Modulations
Venue: arXiv cs.IT 2015
Year: 2015

We investigate the information-theoretic throughout achievable on a fading communication link when the receiver is equipped with one-bit analog-to-digital converters (ADCs). The analysis is conducted for the setting where neither the transmitter nor the receiver have a priori information on the realization of the fading channels. This means that channel-state information needs to be acquired at the receiver on the basis of the one-bit quantized channel outputs. We show that least-squares (LS) channel estimation combined with joint pilot and data processing is capacity achieving in the single-user, single-receive-antenna case. We also investigate the achievable uplink throughput in a massive multiple-input multiple-output system where each element of the antenna array at the receiver base-station feeds a one-bit ADC. We show that LS channel estimation and maximum-ratio combining are sufficient to support both multiuser operation and the use of high-order constellations. This holds in spite of the severe nonlinearity introduced by the one-bit ADCs.
Polynomial Interrupt Timed Automata
Venue: arXiv cs.FL 2015
Year: 2015

Interrupt Timed Automata (ITA) form a subclass of stopwatch automata where reachability and some variants of timed model checking are decidable even in presence of parameters. They are well suited to model and analyze real-time operating systems. Here we extend ITA with polynomial guards and updates, leading to the class of polynomial ITA (PolITA). We prove the decidability of the reachability and model checking of a timed version of CTL by an adaptation of the cylindrical decomposition method for the first-order theory of reals. Compared to previous approaches, our procedure handles parameters and clocks in a unified way. Moreover, we show that PolITA are incomparable with stopwatch automata. Finally additional features are introduced while preserving decidability.
Real-time correction of panoramic images using hyperbolic Möbius transformations
Venue: arXiv cs.GR 2015
Year: 2015

Wide-angle images gained a huge popularity in the last years due to the development of computational photography and imaging technological advances. They present the information of a scene in a way which is more natural for the human eye but, on the other hand, they introduce artifacts such as bent lines. These artifacts become more and more unnatural as the field of view increases. In this work, we present a technique aimed to improve the perceptual quality of panorama visualization. The main ingredients of our approach are, on one hand, considering the viewing sphere as a Riemann sphere, what makes natural the application of Möbius (complex) transformations to the input image, and, on the other hand, a projection scheme which changes in function of the field of view used. We also introduce an implementation of our method, compare it against images produced with other methods and show that the transformations can be done in real-time, which makes our technique very appealing for new settings, as well as for existing interactive panorama applications.
Gender Issues & Information Communication Technology for Development (ICT4D): Prospects and Challenges for Women in Nigeria
Venue: arXiv cs.CY 2015
Year: 2015

Information and Communication Technology is a compendium of interrelated applications, products and services that can either deepen or alter gender equality. It has successfully transformed education, businesses, healthcare, entertainment, politics and good governance within the Global North; providing equitable access to developmental framework driven by ICTs. However, in drafting the core developmental objectives of sustainable development, there has been considerable gender digital divide limiting women access to resources based on their gender, ethnicity, socio-cultural bias and the rights to utilize such resources for development. In realization of the United Nation Millennium Development Goals within the Global South specifically Nigeria, women are often marginalized or excluded from ICT policy drafting and imbalance associated with ICT. This paper identifies and evaluates gender issues and information communication technology, with focus on the challenges and prospects for women empowerment in Nigeria. The study critically examined research literatures and conducted research survey on the prospects and challenges of promoting gender equality and women empowerment through ICTs; and identifies policy implication for Nigeria. The research survey used a random sampling technique with a target sample size of eighty respondents. Data gathered from the questionnaire was analyzed using Statistical Package for Social Science version 19, and the result was presented using ANOVA, and descriptive analysis. The study reveal gender inclusiveness in policy drafting as a key driver for socio-economic development, improved healthcare and women empowerment in Nigeria. We recommend a deliberate ICT policy that attract and encourages women participation in ICT developmental framework.
A Faster FPTAS for the Unbounded Knapsack Problem
Venue: arXiv cs.DS 2015
Year: 2015

The Unbounded Knapsack Problem (UKP) is a well-known variant of the famous 0-1 Knapsack Problem (0-1 KP). In contrast to 0-1 KP, an arbitrary number of copies of every item can be taken in UKP. Since UKP is NP-hard, fully polynomial time approximation schemes (FPTAS) are of great interest. Such algorithms find a solution arbitrarily close to the optimum $\mathrm{OPT}(I)$, i.e. of value at least $(1-\varepsilon) \mathrm{OPT}(I)$ for $\varepsilon > 0$, and have a running time polynomial in the input length and $\frac{1}{\varepsilon}$. For over thirty years, the best FPTAS was due to Lawler with a running time in $O(n + \frac{1}{\varepsilon^3})$ and a space complexity in $O(n + \frac{1}{\varepsilon^2})$, where $n$ is the number of knapsack items. We present an improved FPTAS with a running time in $O(n + \frac{1}{\varepsilon^2} \log^3 \frac{1}{\varepsilon})$ and a space bound in $O(n + \frac{1}{\varepsilon} \log^2 \frac{1}{\varepsilon})$. This directly improves the running time of the fastest known approximation schemes for Bin Packing and Strip Packing, which have to approximately solve UKP instances as subproblems.
Fast optimization of Multithreshold Entropy Linear Classifier
Venue: arXiv cs.LG 2015
Year: 2015

Multithreshold Entropy Linear Classifier (MELC) is a density based model which searches for a linear projection maximizing the Cauchy-Schwarz Divergence of dataset kernel density estimation. Despite its good empirical results, one of its drawbacks is the optimization speed. In this paper we analyze how one can speed it up through solving an approximate problem. We analyze two methods, both similar to the approximate solutions of the Kernel Density Estimation querying and provide adaptive schemes for selecting a crucial parameters based on user-specified acceptable error. Furthermore we show how one can exploit well known conjugate gradients and L-BFGS optimizers despite the fact that the original optimization problem should be solved on the sphere. All above methods and modifications are tested on 10 real life datasets from UCI repository to confirm their practical usability.
On the consistency of Multithreshold Entropy Linear Classifier
Venue: arXiv cs.LG 2015
Year: 2015

Multithreshold Entropy Linear Classifier (MELC) is a recent classifier idea which employs information theoretic concept in order to create a multithreshold maximum margin model. In this paper we analyze its consistency over multithreshold linear models and show that its objective function upper bounds the amount of misclassified points in a similar manner like hinge loss does in support vector machines. For further confirmation we also conduct some numerical experiments on five datasets.
Gradual Classical Logic for Attributed Objects - Extended in Re-Presentation
Venue: arXiv cs.AI 2015
Year: 2015

Our understanding about things is conceptual. By stating that we reason about objects, it is in fact not the objects but concepts referring to them that we manipulate. Now, so long just as we acknowledge infinitely extending notions such as space, time, size, colour, etc, - in short, any reasonable quality - into which an object is subjected, it becomes infeasible to affirm atomicity in the concept referring to the object. However, formal/symbolic logics typically presume atomic entities upon which other expressions are built. Can we reflect our intuition about the concept onto formal/symbolic logics at all? I assure that we can, but the usual perspective about the atomicity needs inspected. In this work, I present gradual logic which materialises the observation that we cannot tell apart whether a so-regarded atomic entity is atomic or is just atomic enough not to be considered non-atomic. The motivation is to capture certain phenomena that naturally occur around concepts with attributes, including presupposition and contraries. I present logical particulars of the logic, which is then mapped onto formal semantics. Two linguistically interesting semantics will be considered. Decidability is shown.
Algorithms and Throughput Analysis for MDS-Coded Switches
Venue: arXiv cs.IT 2015
Year: 2015

Network switches and routers need to serve packet writes and reads at rates that challenge the most advanced memory technologies. As a result, scaling the switching rates is commonly done by parallelizing the packet I/Os using multiple memory units. For improved read rates, packets can be coded with an [n,k] MDS code, thus giving more flexibility at read time to achieve higher utilization of the memory units. In the paper, we study the usage of [n,k] MDS codes in a switching environment. In particular, we study the algorithmic problem of maximizing the instantaneous read rate given a set of packet requests and the current layout of the coded packets in memory. The most interesting results from practical standpoint show how the complexity of reaching optimal read rate depends strongly on the writing policy of the coded packets.
Complex Integration of Digital Collections into Scientific Information Space
Venue: arXiv cs.DL 2015
Year: 2015

The article considers the solution of problems of accumulation and integration of scientific electronic collections into information space of scientific researches. On the basis of the analysis of the existing standards and solutions the choice of methodology and technologies of representation of electronic materials of the scientific conference 'Internet and Modern Society' locates. The concept of the project of integration of the created electronic collection into the main world and domestic information systems and aggregators of scientific information is considered.
Projection-based list detection in Generalized Spatial Modulation MIMO systems
Venue: arXiv cs.IT 2015
Year: 2015

This letter presents a novel detection strategy for Spatially-Multiplexed Generalized Spatial Modulation systems. It is a multi-stage detection that produces a list of candidates of the transmitted signal vector, sorted according to the proximity of the data vector to one of the possible vector subspaces. The quality metric and list-length metric selects the best candidate and manages the list length, respectively. Performance results show that it significantly reduces the performance gap to the optimal maximum likelihood detector, while maintaining significant computational cost reduction.
Weakly Supervised Fine-Grained Image Categorization
Venue: arXiv cs.CV 2015
Year: 2015

In this paper, we categorize fine-grained images without using any object / part annotation neither in the training nor in the testing stage, a step towards making it suitable for deployments. Fine-grained image categorization aims to classify objects with subtle distinctions. Most existing works heavily rely on object / part detectors to build the correspondence between object parts by using object or object part annotations inside training images. The need for expensive object annotations prevents the wide usage of these methods. Instead, we propose to select useful parts from multi-scale part proposals in objects, and use them to compute a global image representation for categorization. This is specially designed for the annotation-free fine-grained categorization task, because useful parts have shown to play an important role in existing annotation-dependent works but accurate part detectors can be hardly acquired. With the proposed image representation, we can further detect and visualize the key (most discriminative) parts in objects of different classes. In the experiment, the proposed annotation-free method achieves better accuracy than that of state-of-the-art annotation-free and most existing annotation-dependent methods on two challenging datasets, which shows that it is not always necessary to use accurate object / part annotations in fine-grained image categorization.