OpenRaiser/Intern-Atlas huggingface dataset:
A random algorithm for low-rank decomposition of large-scale matrices with missing entries
Venue: arXiv cs.NA 2014
Year: 2014

A Random SubMatrix method (RSM) is proposed to calculate the low-rank decomposition of large-scale matrices with known entry percentage ρ. RSM is very fast as the floating-point operations (flops) required are compared favorably with the state-of-the-art algorithms. Meanwhile RSM is very memory-saving. With known entries homogeneously distributed in the given matrix, sub-matrices formed by known entries are randomly selected. According to the just proved theorem that subspace related to smaller singular values is less perturbed by noise, the null vectors or the right singular vectors associated with the minor singular values are calculated for each submatrix. The vectors are the null vectors of the corresponding submatrix in the ground truth of the given large-scale matrix. If enough sub-matrices are randomly chosen, the low-rank decomposition is estimated. The experimental results on random synthetical matrices with sizes such as 131072X1024 and on real data sets indicate that RSM is much faster and memory-saving, and, meanwhile, has considerable high precision achieving or approximating to the best.
Analysis of an attenuator artifact in an experimental attack by Gunn-Allison-Abbott against the Kirchhoff-law-Johnson-noise (KLJN) secure key exchange system
Venue: arXiv cs.CR 2014
Year: 2014

A recent paper by Gunn-Allison-Abbott (GAA) [L.J. Gunn et al., Scientific Reports 4 (2014) 6461] argued that the Kirchhoff-law-Johnson-noise (KLJN) secure key exchange system could experience a severe information leak. Here we refute their results and demonstrate that GAA's arguments ensue from a serious design flaw in their system. Specifically, an attenuator broke the single Kirchhoff-loop into two coupled loops, which is an incorrect operation since the single loop is essential for the security in the KLJN system, and hence GAA's asserted information leak is trivial. Another consequence is that a fully defended KLJN system would not be able to function due to its built-in current-comparison defense against active (invasive) attacks. In this paper we crack GAA's scheme via an elementary current comparison attack which yields negligible error probability for Eve even without averaging over the correlation time of the noise.
A Multi-Heuristic Approach for Solving the Pre-Marshalling Problem
Venue: arXiv cs.AI 2014
Year: 2014

Minimizing the number of reshuffling operations at maritime container terminals incorporates the Pre-Marshalling Problem (PMP) as an important problem. Based on an analysis of existing solution approaches we develop new heuristics utilizing specific properties of problem instances of the PMP. We show that the heuristic performance is highly dependent on these properties. We introduce a new method that exploits a greedy heuristic of four stages, where for each of these stages several different heuristics may be applied. Instead of using randomization to improve the performance of the heuristic, we repetitively generate a number of solutions by using a combination of different heuristics for each stage. In doing so, only a small number of solutions is generated for which we intend that they do not have undesirable properties, contrary to the case when simple randomization is used. Our experiments show that such a deterministic algorithm significantly outperforms the original nondeterministic method when the quality of found solutions is observed, with a much lower number of generated solutions.
Optimal program-size complexity for self-assembly at temperature 1 in 3D
Venue: arXiv cs.CG 2014
Year: 2014

Working in a three-dimensional variant of Winfree's abstract Tile Assembly Model, we show that, for all $N \in \mathbb{N}$, there is a tile set that uniquely self-assembles into an $N \times N$ square shape at temperature 1 with optimal program-size complexity of $O(\log N / \log \log N)$ (the program-size complexity, also known as tile complexity, of a shape is the minimum number of unique tile types required to uniquely self-assemble it). Moreover, our construction is "just barely" 3D in the sense that it works even when the placement of tiles is restricted to the $z = 0$ and $z = 1$ planes. This result affirmatively answers an open question from Cook, Fu, Schweller (SODA 2011). To achieve this result, we develop a general 3D temperature 1 optimal encoding construction, reminiscent of the 2D temperature 2 optimal encoding construction of Soloveichik and Winfree (SICOMP 2007), and perhaps of independent interest.
On the Complexity of Learning with Kernels
Venue: arXiv cs.LG 2014
Year: 2014

A well-recognized limitation of kernel learning is the requirement to handle a kernel matrix, whose size is quadratic in the number of training examples. Many methods have been proposed to reduce this computational cost, mostly by using a subset of the kernel matrix entries, or some form of low-rank matrix approximation, or a random projection method. In this paper, we study lower bounds on the error attainable by such methods as a function of the number of entries observed in the kernel matrix or the rank of an approximate kernel matrix. We show that there are kernel learning problems where no such method will lead to non-trivial computational savings. Our results also quantify how the problem difficulty depends on parameters such as the nature of the loss function, the regularization parameter, the norm of the desired predictor, and the kernel matrix rank. Our results also suggest cases where more efficient kernel learning might be possible.
BigExcel: A Web-Based Framework for Exploring Big Data in Social Sciences
Venue: arXiv cs.DC 2014
Year: 2014

This paper argues that there are three fundamental challenges that need to be overcome in order to foster the adoption of big data technologies in non-computer science related disciplines: addressing issues of accessibility of such technologies for non-computer scientists, supporting the ad hoc exploration of large data sets with minimal effort and the availability of lightweight web-based frameworks for quick and easy analytics. In this paper, we address the above three challenges through the development of 'BigExcel', a three tier web-based framework for exploring big data to facilitate the management of user interactions with large data sets, the construction of queries to explore the data set and the management of the infrastructure. The feasibility of BigExcel is demonstrated through two Yahoo Sandbox datasets. The first dataset is the Yahoo Buzz Score data set we use for quantitatively predicting trending technologies and the second is the Yahoo n-gram corpus we use for qualitatively inferring the coverage of important events. A demonstration of the BigExcel framework and source code is available at http://bigdata.cs.st-andrews.ac.uk/projects/bigexcel-exploring-big-data-for-social-sciences/.
Kalman Filtering over Gilbert-Elliott Channels: Stability Conditions and the Critical Curve
Venue: arXiv cs.SY 2014
Year: 2014

This paper investigates the stability of Kalman filtering over Gilbert-Elliott channels where random packet drop follows a time-homogeneous two-state Markov chain whose state transition is determined by a pair of failure and recovery rates. First of all, we establish a relaxed condition guaranteeing peak-covariance stability described by an inequality in terms of the spectral radius of the system matrix and transition probabilities of the Markov chain. We further show that that condition can be interpreted using a linear matrix inequality feasibility problem. Next, we prove that the peak-covariance stability implies mean-square stability, if the system matrix has no defective eigenvalues on the unit circle. This connection between the two stability notions holds for any random packet drop process. We prove that there exists a critical curve in the failure-recovery rate plane, below which the Kalman filter is mean-square stable and no longer mean-square stable above, via a coupling method in stochastic processes. Finally, a lower bound for this critical failure rate is obtained making use of the relationship we establish between the two stability criteria, based on an approximate relaxation of the system matrix.
An Interesting Property of LPCs for Sonorant Vs Fricative Discrimination
Venue: arXiv cs.SD 2014
Year: 2014

Linear prediction (LP) technique estimates an optimum all-pole filter of a given order for a frame of speech signal. The coefficients of the all-pole filter, 1/A(z) are referred to as LP coefficients (LPCs). The gain of the inverse of the all-pole filter, A(z) at z = 1, i.e, at frequency = 0, A(1) corresponds to the sum of LPCs, which has the property of being lower (higher) than a threshold for the sonorants (fricatives). When the inverse-tan of A(1), denoted as T(1), is used a feature and tested on the sonorant and fricative frames of the entire TIMIT database, an accuracy of 99.07% is obtained. Hence, we refer to T(1) as sonorant-fricative discrimination index (SFDI). This property has also been tested for its robustness for additive white noise and on the telephone quality speech of the NTIMIT database. These results are comparable to, or in some respects, better than the state-of-the-art methods proposed for a similar task. Such a property may be used for segmenting a speech signal or for non-uniform frame-rate analysis.
Storms in Mobile Networks
Venue: arXiv cs.NI 2014
Year: 2014

Mobile networks are vulnerable to signalling attacks and storms that are caused by traffic patterns that overload the control plane, and differ from distributed denial of service (DDoS) attacks in the Internet since they directly attack the control plane, and also reserve wireless bandwidth without actually using it. Such attacks can result from malware and mobile botnets, as well as from poorly designed applications, and can cause service outages in 3G and 4G networks which have been experienced by mobile operators. Since the radio resource control (RRC) protocol in 3G and 4G networks is particularly susceptible to such attacks, we analyze their effect with a mathematical model that helps to predict the congestion that is caused by an attack. A detailed simulation model of a mobile network is used to better understand the temporal dynamics of user behavior and signalling in the network and to show how RRC based signalling attacks and storms cause significant problems in the control plane and the user plane of the network. Our analysis also serves to identify how storms can be detected, and to propose how system parameters can be chosen to mitigate their effect.
Rapid Skill Capture in a First-Person Shooter
Venue: arXiv cs.HC 2014
Year: 2014

Various aspects of computer game design, including adaptive elements of game levels, characteristics of 'bot' behavior, and player matching in multiplayer games, would ideally be sensitive to a player's skill level. Yet, while difficulty and player learning have been explored in the context of games, there has been little work analyzing skill per se, and how it pertains to a player's input. To this end, we present a data set of 476 game logs from over 40 players of a first-person shooter game (Red Eclipse) as a basis of a case study. We then analyze different metrics of skill and show that some of these can be predicted using only a few seconds of keyboard and mouse input. We argue that the techniques used here are useful for adapting games to match players' skill levels rapidly, perhaps more rapidly than solutions based on performance averaging such as TrueSkill.
Discrete-Time Models Resulting From Dynamic Continuous-Time Perturbations In Phase-Amplitude Modulation-Demodulation Schemes
Venue: arXiv cs.SY 2014
Year: 2014

We consider discrete-time (DT) systems S in which a DT input is first tranformed to a continuous-time (CT) format by phase-amplitude modulation, then modified by a non-linear CT dynamical transformation F, and finally converted back to DT output using an ideal de-modulation scheme. Assuming that F belongs to a special class of CT Volterra series models with fixed degree and memory depth, we provide a complete characterization of S as a series connection of a DT Volterra series model of fixed degree and memory depth, and an LTI system with special properties. The result suggests a new, non-obvious, analytically motivated structure of digital compensation of analog nonlinear distortions (for example, those caused by power amplifiers) in digital communication systems. Results from a MATLAB simulation are used to demonstrate effectiveness of the new compensation scheme, as compared to the standard Volterra series approach.
Electrocardiography Separation of Mother and Baby
Venue: arXiv cs.CV 2014
Year: 2014

Extraction of Electrocardiography (ECG or EKG) signals of mother and baby is a challenging task, because one single device is used and it receives a mixture of multiple heart beats. In this paper, we would like to design a filter to separate the signals from each other.
The Spaces of Data, Information, and Knowledge
Venue: arXiv cs.AI 2014
Year: 2014

We study the data space $D$ of any given data set $X$ and explain how functions and relations are defined over $D$. From $D$ and for a specific domain $Δ$ we construct the information space $I$ of $X$ by interpreting variables, functions, and explicit relations over $D$ in $Δ$ and by including other relations that $D$ implies under the interpretation in $Δ$. Then from $I$ we build up the knowledge space $K$ of $X$ as the product of two spaces $K_T$ and $K_P$, where $K_T$ is obtained from $I$ by using the induction principle to generalize propositional relations to quantified relations, the deduction principle to generate new relations, and standard mechanisms to validate relations and $K_P$ is the space of specifications of methods with operational instructions which are valid in $K_T$. Through our construction of the three topological spaces the following key observation is made clear: the retrieval of information from the given data set for $Δ$ consists essentially in mining domain objects and relations, and the discovery of knowledge from the retrieved information consists essentially in applying the induction and deduction principles to generate propositions, synthesizing and modeling the information to generate specifications of methods with operational instructions, and validating the propositions and specifications. Based on this observation, efficient approaches may be designed to discover profound knowledge automatically from simple data, as demonstrated by the result of our study in the case of geometry.
A Codebook-Based Limited Feedback System for Large-Scale MIMO
Venue: arXiv cs.IT 2014
Year: 2014

In this paper, we consider limited feedback systems for FDD large-scale (massive) MIMO. A new codebook-based framework for multiuser (MU) MIMO downlink systems is introduced and then compared with an ideal non-codebook based system. We are particularly interested in the less-known finite-rate feedback regime where the number $M$ of transmit antennas and the number of users are of the same order of magnitude and $M$ is large but finite, which is a typical scenario of large-scale MIMO. We provide new findings in this regime and identify some benefits of the new framework in terms of scheduling gain and downlink dedicated pilot overhead.
Distributed DTX Alignment with Memory
Venue: arXiv cs.IT 2014
Year: 2014

This paper addresses the assignment of transmission and sleep time slots between interfering transmitters with the objective of minimal power consumption. In particular, we address the constructive alignment of Discontinuous Transmission (DTX) time slots under link rate constraints. Due to the complexity of the combinatorial optimization problem at hand, we resort to heuristic assignment strategies. We derive four time slot alignment solutions (sequential alignment, random alignment, p-persistent ranking and DTX alignment with memory) and identify trade-offs. One solution, DTX alignment with memory, addresses trade-offs of the other three by maintaining memory of past alignment and channel quality to buffer short term changes in channel quality. All strategies are found to exhibit similar convergence behavior, but different power consumption and retransmission probabilities. DTX alignment with memory is shown to achieve up to 40% savings in power consumption and more than 20% lower retransmission probability than the state of the art.
A Hybrid Recurrent Neural Network For Music Transcription
Venue: arXiv cs.LG 2014
Year: 2014

We investigate the problem of incorporating higher-level symbolic score-like information into Automatic Music Transcription (AMT) systems to improve their performance. We use recurrent neural networks (RNNs) and their variants as music language models (MLMs) and present a generative architecture for combining these models with predictions from a frame level acoustic classifier. We also compare different neural network architectures for acoustic modeling. The proposed model computes a distribution over possible output sequences given the acoustic input signal and we present an algorithm for performing a global search for good candidate transcriptions. The performance of the proposed model is evaluated on piano music from the MAPS dataset and we observe that the proposed model consistently outperforms existing transcription methods.
Space-Time Encoded MISO Broadcast Channel with Outdated CSIT: An Error Rate and Diversity Performance Analysis
Venue: arXiv cs.IT 2014
Year: 2014

Studies of the MISO Broadcast Channel (BC) with delayed Channel State Information at the Transmitter (CSIT) have so far focused on the sum-rate and Degrees-of-Freedom (DoF) region analysis. In this paper, we investigate for the first time the error rate performance at finite SNR and the diversity-multiplexing tradeoff (DMT) at infinite SNR of a space-time encoded transmission over a two-user MISO BC with delayed CSIT. We consider the so-called MAT protocol obtained by Maddah-Ali and Tse, which was shown to provide 33% DoF enhancement over TDMA. While the asymptotic DMT analysis shows that MAT is always preferable to TDMA, the Pairwise Error Probability analysis at finite SNR shows that MAT is in fact not always a better alternative to TDMA. Benefits can be obtained over TDMA only at very high rate or once concatenated with a full-rate full-diversity space-time code. The analysis is also extended to spatially correlated channels and the influence of transmit correlation matrices and user pairing strategies on the performance are discussed. Relying on statistical CSIT, signal constellations are further optimized to improve the error rate performance of MAT and make it insensitive to user orthogonality. Finally, other transmission strategies relying on delayed CSIT are discussed.
Footprint-Driven Locomotion Composition
Venue: arXiv cs.GR 2014
Year: 2014

One of the most efficient ways of generating goal-directed walking motions is synthesising the final motion based on footprints. Nevertheless, current implementations have not examined the generation of continuous motion based on footprints, where different behaviours can be generated automatically. Therefore, in this paper a flexible approach for footprint-driven locomotion composition is presented. The presented solution is based on the ability to generate footprint-driven locomotion, with flexible features like jumping, running, and stair stepping. In addition, the presented system examines the ability of generating the desired motion of the character based on predefined footprint patterns that determine which behaviour should be performed. Finally, it is examined the generation of transition patterns based on the velocity of the root and the number of footsteps required to achieve the target behaviour smoothly and naturally.
Hardware and Software manual for Evolution of Oil Droplets in a Chemo-Robotic Platform
Venue: arXiv cs.RO 2014
Year: 2014

This manual outlines a fully automated liquid handling robot to enable physically-embodied evolution within a chemical oil-droplet system. The robot is based upon the REPRAP3D printer system and makes the droplets by mixing chemicals and then placing them in a petri dish after which they are recorded using a camera and the behaviour of the droplets analysed using image recognition software. This manual accompanies the open access publication published in Nature Communications DOI: 10.1038/ncomms6571.
Investigation of the relationship between code change set n-grams and change in energy consumption
Venue: arXiv cs.PF 2014
Year: 2014

The amount of software running on mobile devices is constantly growing as consumers and industry purchase more battery powered devices. On the other hand, tools that provide developers with feed- back on how their software changes affect battery life are not widely available. This work employs Green Mining, the study of the rela- tionship between energy consumption and software changesets, and n-gram language models to evaluate if source code changeset perplex- ity correlates with change in energy consumption. A correlation be- tween perplexity and change in energy consumption would permit the development of a tool that predicts the impact a code changeset may have on a software applications energy consumption. The case study results show that there is weak to no correlation between cross en- tropy and change in energy consumption. Therefore, future areas of investigation are proposed.
Cloud Network Management Model A Novel Approach to Manage Cloud Traffic
Venue: arXiv cs.NI 2014
Year: 2014

Cloud is in the air. More and More companies and personals are connecting to cloud with so many variety of offering provided by the companies. The cloud services are based on Internet i.e. TCP IP. The paper discusses limitations of one of the main existing network management protocol i.e. Simple Network Management Protocol (SNMP) with respect to the current network conditions. The network traffic is growing at a high speed. When we talk about the networked environment of cloud, the monitoring tool should be capable of handling the traffic tribulations efficiently and represent a correct scenario of the network condition. The proposed Model Cloud Network Management Model provides a comprehensive solution to manage the growing traffic in cloud and trying to improve communication of manager and agents as in SNMP (the traditional TCP IP network management protocol). Firstly CNMM concentrates on reduction of packet exchange between manager and agent. Secondly it eliminates the counter problems exist in SNMP by having periodic updates from agent without querying by the manager. For better management we are including managers using virtualized technology. CNMM is a proposed model with efficient communication, secure packet delivery and reduced traffic. Though the proposed model supposed to manage the cloud traffic in a better and efficient way, the model is still a theoretical study, its implementation and results are yet to discover. The model however is the first step towards development of supported algorithms and protocol. Our further study will concentrate on development of supported algorithms.
The Sum-Product Algorithm for Degree-2 Check Nodes and Trapping Sets
Venue: arXiv cs.IT 2014
Year: 2014

The sum-product algorithm for decoding of binary codes is analyzed for bipartite graphs in which the check nodes all have degree $2$. The algorithm simplifies dramatically and may be expressed using linear algebra. Exact results about the convergence of the algorithm are derived and applied to trapping sets.