OpenRaiser/Intern-Atlas huggingface dataset:
Two-tier Spatial Modeling of Base Stations in Cellular Networks
Venue: arXiv cs.NI 2014
Year: 2014

Poisson Point Process (PPP) has been widely adopted as an efficient model for the spatial distribution of base stations (BSs) in cellular networks. However, real BSs deployment are rarely completely random, due to environmental impact on actual site planning. Particularly, for multi-tier heterogeneous cellular networks, operators have to place different BSs according to local coverage and capacity requirement, and the diversity of BSs' functions may result in different spatial patterns on each networking tier. In this paper, we consider a two-tier scenario that consists of macrocell and microcell BSs in cellular networks. By analyzing these two tiers separately and applying both classical statistics and network performance as evaluation metrics, we obtain accurate spatial model of BSs deployment for each tier. Basically, we verify the inaccuracy of using PPP in BS locations modeling for either macrocells or microcells. Specifically, we find that the first tier with macrocell BSs is dispersed and can be precisely modelled by Strauss point process, while Matern cluster process captures the second tier's aggregation nature very well. These statistical models coincide with the inherent properties of macrocell and microcell BSs respectively, thus providing a new perspective in understanding the relationship between spatial structure and operational functions of BSs.
Reliable Reporting for Massive M2M Communications with Periodic Resource Pooling
Venue: arXiv cs.IT 2014
Year: 2014

This letter considers a wireless M2M communication scenario with a massive number of M2M devices. Each device needs to send its reports within a given deadline and with certain reliability, e. g. 99.99%. A pool of resources available to all M2M devices is periodically available for transmission. The number of transmissions required by an M2M device within the pool is random due to two reasons - random number of arrived reports since the last reporting opportunity and requests for retransmission due to random channel errors. We show how to dimension the pool of M2M-dedicated resources in order to guarantee the desired reliability of the report delivery within the deadline. The fact that the pool of resources is used by a massive number of devices allows to base the dimensioning on the central limit theorem. The results are interpreted in the context of LTE, but they are applicable to any M2M communication system.
Cost minimization for fading channels with energy harvesting and conventional energy
Venue: arXiv cs.IT 2014
Year: 2014

In this paper, we investigate resource allocation strategies for a point-to-point wireless communications system with hybrid energy sources consisting of an energy harvester and a conventional energy source. In particular, as an incentive to promote the use of renewable energy, we assume that the renewable energy has a lower cost than the conventional energy. Then, by assuming that the non-causal information of the energy arrivals and the channel power gains are available, we minimize the total energy cost of such a system over $N$ fading slots under a proposed outage constraint together with the energy harvesting constraints. The outage constraint requires a minimum fixed number of slots to be reliably decoded, and thus leads to a mixed-integer programming formulation for the optimization problem. This constraint is useful, for example, if an outer code is used to recover all the data bits. Optimal linear time algorithms are obtained for two extreme cases, i.e., the number of outage slot is $1$ or $N-1$. For the general case, a lower bound based on the linear programming relaxation, and two suboptimal algorithms are proposed. It is shown that the proposed suboptimal algorithms exhibit only a small gap from the lower bound. We then extend the proposed algorithms to the multi-cycle scenario in which the outage constraint is imposed for each cycle separately. Finally, we investigate the resource allocation strategies when only causal information on the energy arrivals and only channel statistics is available. It is shown that the greedy energy allocation is optimal for this scenario.
Experiences in Developing Time-Critical Systems - The Case Study "Production Cell"
Venue: arXiv cs.SE 2014
Year: 2014

Starting from an informal requirements description of a toy production cell used in an intra-project competition in 1994, we give a formal specification that is as close as possible to requirements. We use the deductive program synthesis approach by Manna and Waldinger (1980) to obtain a verified TTL-like circuitery to control the cell. The formal specification also covers mechanical aspects and thus allows to reason not only about software issues but also about issues of mechanical engineering. Besides an approach confined to first order predicate logic with explicit, continuous time, an attempt is presented to employ application specific user-defined logical operators to get a more concise specification as well as proof.
Operational Rate-Distortion Performance of Single-source and Distributed Compressed Sensing
Venue: arXiv cs.IT 2014
Year: 2014

We consider correlated and distributed sources without cooperation at the encoder. For these sources, we derive the best achievable performance in the rate-distortion sense of any distributed compressed sensing scheme, under the constraint of high--rate quantization. Moreover, under this model we derive a closed--form expression of the rate gain achieved by taking into account the correlation of the sources at the receiver and a closed--form expression of the average performance of the oracle receiver for independent and joint reconstruction. Finally, we show experimentally that the exploitation of the correlation between the sources performs close to optimal and that the only penalty is due to the missing knowledge of the sparsity support as in (non distributed) compressed sensing. Even if the derivation is performed in the large system regime, where signal and system parameters tend to infinity, numerical results show that the equations match simulations for parameter values of practical interest.
The Kinetic Basis of Self-Organized Pattern Formation
Venue: arXiv cs.FL 2014
Year: 2014

In his seminal paper on morphogenesis (1952), Alan Turing demonstrated that different spatio-temporal patterns can arise due to instability of the homogeneous state in reaction-diffusion systems, but at least two species are necessary to produce even the simplest stationary patterns. This paper is aimed to propose a novel model of the analog (continuous state) kinetic automaton and to show that stationary and dynamic patterns can arise in one-component networks of kinetic automata. Possible applicability of kinetic networks to modeling of real-world phenomena is also discussed.
Review of Face Detection Systems Based Artificial Neural Networks Algorithms
Venue: arXiv cs.CV 2014
Year: 2014

Face detection is one of the most relevant applications of image processing and biometric systems. Artificial neural networks (ANN) have been used in the field of image processing and pattern recognition. There is lack of literature surveys which give overview about the studies and researches related to the using of ANN in face detection. Therefore, this research includes a general review of face detection studies and systems which based on different ANN approaches and algorithms. The strengths and limitations of these literature studies and systems were included also.
Robust Video Watermarking Schemes in Phase domain Using Binary Phase Shift Keying
Venue: arXiv cs.MM 2014
Year: 2014

This paper presents a robust video watermarking scheme in Discrete Fourier Transform (DFT) and Sequencyordered Complex Hadamard Transform (SCHT). The DFT and SCHT coefficients are complex and consist of both magnitude and phase and are well suited to adopt phase shift keying techniques to embed the watermark. In the proposed schemes, the phases of DFT and SCHT coefficients are modified to convey watermark information using binary phase shift keying in cover video. Low amplitude block selection (LABS) is used to improve transparency, amplitude boost to improve the resistance of watermark from signal processing and compression attacks and spread spectrum technique is used for encrypting watermark in order to protect it from third party. It is observed that both algorithms showing more or less same robustness but SCHT offers high transparency, simple implementation and less computational cost than DFT.
Draining our Glass: An Energy and Heat Characterization of Google Glass
Venue: arXiv cs.HC 2014
Year: 2014

The Google Glass is a mobile device designed to be worn as eyeglasses. This form factor enables new usage possibilities, such as hands-free video chats and instant web search. However, its shape also hampers its potential: (1) battery size, and therefore lifetime, is limited by a need for the device to be lightweight, and (2) high-power processing leads to significant heat, which should be limited, due to the Glass' compact form factor and close proximity to the user's skin. We use the Glass in a case study of the power and thermal characteristics of optical head-mounted display devices. We share insights and implications to limit power consumption to increase the safety and utility of head-mounted devices.
Orthogonal Rank-One Matrix Pursuit for Low Rank Matrix Completion
Venue: arXiv cs.LG 2014
Year: 2014

In this paper, we propose an efficient and scalable low rank matrix completion algorithm. The key idea is to extend orthogonal matching pursuit method from the vector case to the matrix case. We further propose an economic version of our algorithm by introducing a novel weight updating rule to reduce the time and storage complexity. Both versions are computationally inexpensive for each matrix pursuit iteration, and find satisfactory results in a few iterations. Another advantage of our proposed algorithm is that it has only one tunable parameter, which is the rank. It is easy to understand and to use by the user. This becomes especially important in large-scale learning problems. In addition, we rigorously show that both versions achieve a linear convergence rate, which is significantly better than the previous known results. We also empirically compare the proposed algorithms with several state-of-the-art matrix completion algorithms on many real-world datasets, including the large-scale recommendation dataset Netflix as well as the MovieLens datasets. Numerical results show that our proposed algorithm is more efficient than competing algorithms while achieving similar or better prediction performance.
Android Security Framework: Enabling Generic and Extensible Access Control on Android
Venue: arXiv cs.CR 2014
Year: 2014

We introduce the Android Security Framework (ASF), a generic, extensible security framework for Android that enables the development and integration of a wide spectrum of security models in form of code-based security modules. The design of ASF reflects lessons learned from the literature on established security frameworks (such as Linux Security Modules or the BSD MAC Framework) and intertwines them with the particular requirements and challenges from the design of Android's software stack. ASF provides a novel security API that supports authors of Android security extensions in developing their modules. This overcomes the current unsatisfactory situation to provide security solutions as separate patches to the Android software stack or to embed them into Android's mainline codebase. As a result, ASF provides different practical benefits such as a higher degree of acceptance, adaptation, and maintenance of security solutions than previously possible on Android. We present a prototypical implementation of ASF and demonstrate its effectiveness and efficiency by modularizing different security models from related work, such as context-aware access control, inlined reference monitoring, and type enforcement.
On the Existence of Optimal Policies for a Class of Static and Sequential Dynamic Teams
Venue: arXiv cs.SY 2014
Year: 2014

In this paper, we identify sufficient conditions under which static teams and a class of sequential dynamic teams admit team-optimal solutions. We first investigate the existence of optimal solutions in static teams where the observations of the decision makers are conditionally independent or satisfy certain regularity conditions. Building on these findings and the static reduction method of Witsenhausen, we then extend the analysis to sequential dynamic teams. In particular, we show that a large class of dynamic LQG team problems, including the vector version of the well-known Witsenhausen's counterexample and the Gaussian relay channel problem viewed as a dynamic team, admit team-optimal solutions. Results in this paper substantially broaden the class of stochastic control and team problems with non-classical information known to have optimal solutions.
An Improvement over the GVW Algorithm for Inhomogeneous Polynomial Systems
Venue: arXiv cs.SC 2014
Year: 2014

The GVW algorithm is a signature-based algorithm for computing Gröbner bases. If the input system is not homogeneous, some J-pairs with higher signatures but lower degrees are rejected by GVW's Syzygy Criterion, instead, GVW have to compute some J-pairs with lower signatures but higher degrees. Consequently, degrees of polynomials appearing during the computations may unnecessarily grow up higher and the computation become more expensive. In this paper, a variant of the GVW algorithm, called M-GVW, is proposed and mutant pairs are introduced to overcome inconveniences brought by inhomogeneous input polynomials. Some techniques from linear algebra are used to improve the efficiency. Both GVW and M-GVW have been implemented in C++ and tested by many examples from boolean polynomial rings. The timings show M-GVW usually performs much better than the original GVW algorithm when mutant pairs are found. Besides, M-GVW is also compared with intrinsic Gröbner bases functions on Maple, Singular and Magma. Due to the efficient routines from the M4RI library, the experimental results show that M-GVW is very efficient.
Buchi Determinization Made Tighter
Venue: arXiv cs.FL 2014
Year: 2014

By separating the principal acceptance mechanism from the concrete acceptance condition of a given Büchi automaton with $n$ states,Schewe presented the construction of an equivalent deterministic Rabin transition automaton with $o((1.65n)^n)$ states via \emph{history trees}, which can be simply translated to a standard Rabin automaton with $o((2.26n)^n)$ states. Apart from the inherent simplicity, Schewe's construction improved Safra's construction (which requires $12^nn^{2n}$ states). However, the price that is paid is the use of $2^{n-1}$ Rabin pairs (instead of $n$ in Safra's construction). Further, by introducing the \emph{later introduction record} as a record tailored for ordered trees, deterministic automata with Parity acceptance condition is constructed which exactly resembles Piterman's determinization with Parity acceptance condition where the state complexity is $O((n!)^2)$ and the index complexity is $2n$.In this paper, we improve Schewe's construction to $2^{\lceil (n-1)/2\rceil}$ Rabin pairs with the same state complexity. Meanwhile, we give a new determinization construction of Parity automata with the state complexity being $o(n^2(0.69n\sqrt{n})^n)$ and index complexity being $n$.
Why walking the dog takes time: Frechet distance has no strongly subquadratic algorithms unless SETH fails
Venue: arXiv cs.CG 2014
Year: 2014

The Frechet distance is a well-studied and very popular measure of similarity of two curves. Many variants and extensions have been studied since Alt and Godau introduced this measure to computational geometry in 1991. Their original algorithm to compute the Frechet distance of two polygonal curves with n vertices has a runtime of O(n^2 log n). More than 20 years later, the state of the art algorithms for most variants still take time more than O(n^2 / log n), but no matching lower bounds are known, not even under reasonable complexity theoretic assumptions. To obtain a conditional lower bound, in this paper we assume the Strong Exponential Time Hypothesis or, more precisely, that there is no O*((2-delta)^N) algorithm for CNF-SAT for any delta > 0. Under this assumption we show that the Frechet distance cannot be computed in strongly subquadratic time, i.e., in time O(n^{2-delta}) for any delta > 0. This means that finding faster algorithms for the Frechet distance is as hard as finding faster CNF-SAT algorithms, and the existence of a strongly subquadratic algorithm can be considered unlikely. Our result holds for both the continuous and the discrete Frechet distance. We extend the main result in various directions. Based on the same assumption we (1) show non-existence of a strongly subquadratic 1.001-approximation, (2) present tight lower bounds in case the numbers of vertices of the two curves are imbalanced, and (3) examine realistic input assumptions (c-packed curves).
MIMO Multiway Relaying with Clustered Full Data Exchange: Signal Space Alignment and Degrees of Freedom
Venue: arXiv cs.IT 2014
Year: 2014

We investigate achievable degrees of freedom (DoF) for a multiple-input multiple-output (MIMO) multiway relay channel (mRC) with $L$ clusters and $K$ users per cluster. Each user is equipped with $M$ antennas and the relay with $N$ antennas. We assume a new data exchange model, termed \emph{clustered full data exchange}, i.e., each user in a cluster wants to learn the messages of all the other users in the same cluster. Novel signal alignment techniques are developed to systematically construct the beamforming matrices at the users and the relay for efficient physical-layer network coding. Based on that, we derive an achievable DoF of the MIMO mRC with an arbitrary network configuration of $L$ and $K$, as well as with an arbitrary antenna configuration of $M$ and $N$. We show that our proposed scheme achieves the DoF capacity when $\frac{M}{N} \leq \frac{1}{LK-1}$ and $\frac{M}{N} \geq \frac{(K-1)L+1}{KL}$.
An Efficient Feature Selection in Classification of Audio Files
Venue: arXiv cs.LG 2014
Year: 2014

In this paper we have focused on an efficient feature selection method in classification of audio files. The main objective is feature selection and extraction. We have selected a set of features for further analysis, which represents the elements in feature vector. By extraction method we can compute a numerical representation that can be used to characterize the audio using the existing toolbox. In this study Gain Ratio (GR) is used as a feature selection measure. GR is used to select splitting attribute which will separate the tuples into different classes. The pulse clarity is considered as a subjective measure and it is used to calculate the gain of features of audio files. The splitting criterion is employed in the application to identify the class or the music genre of a specific audio file from testing database. Experimental results indicate that by using GR the application can produce a satisfactory result for music genre classification. After dimensionality reduction best three features have been selected out of various features of audio file and in this technique we will get more than 90% successful classification result.
Two algorithms for compressed sensing of sparse tensors
Venue: arXiv cs.IT 2014
Year: 2014

Compressed sensing (CS) exploits the sparsity of a signal in order to integrate acquisition and compression. CS theory enables exact reconstruction of a sparse signal from relatively few linear measurements via a suitable nonlinear minimization process. Conventional CS theory relies on vectorial data representation, which results in good compression ratios at the expense of increased computational complexity. In applications involving color images, video sequences, and multi-sensor networks, the data is intrinsically of high-order, and thus more suitably represented in tensorial form. Standard applications of CS to higher-order data typically involve representation of the data as long vectors that are in turn measured using large sampling matrices, thus imposing a huge computational and memory burden. In this chapter, we introduce Generalized Tensor Compressed Sensing (GTCS)--a unified framework for compressed sensing of higher-order tensors which preserves the intrinsic structure of tensorial data with reduced computational complexity at reconstruction. We demonstrate that GTCS offers an efficient means for representation of multidimensional data by providing simultaneous acquisition and compression from all tensor modes. In addition, we propound two reconstruction procedures, a serial method (GTCS-S) and a parallelizable method (GTCS-P), both capable of recovering a tensor based on noiseless and noisy observations. We then compare the performance of the proposed methods with Kronecker compressed sensing (KCS) and multi-way compressed sensing (MWCS). We demonstrate experimentally that GTCS outperforms KCS and MWCS in terms of both reconstruction accuracy (within a range of compression ratios) and processing speed. The major disadvantage of our methods (and of MWCS as well), is that the achieved compression ratios may be worse than those offered by KCS.
MTD(f), A Minimax Algorithm Faster Than NegaScout
Venue: arXiv cs.AI 2014
Year: 2014

MTD(f) is a new minimax search algorithm, simpler and more efficient than previous algorithms. In tests with a number of tournament game playing programs for chess, checkers and Othello it performed better, on average, than NegaScout/PVS (the AlphaBeta variant used in practically all good chess, checkers, and Othello programs). One of the strongest chess programs of the moment, MIT's parallel chess program Cilkchess uses MTD(f) as its search algorithm, replacing NegaScout, which was used in StarSocrates, the previous version of the program.
SSS* = Alpha-Beta + TT
Venue: arXiv cs.AI 2014
Year: 2014

In 1979 Stockman introduced the SSS* minimax search algorithm that domi- nates Alpha-Beta in the number of leaf nodes expanded. Further investigation of the algorithm showed that it had three serious drawbacks, which prevented its use by practitioners: it is difficult to understand, it has large memory requirements, and it is slow. This paper presents an alternate formulation of SSS*, in which it is implemented as a series of Alpha-Beta calls that use a transposition table (AB- SSS*). The reformulation solves all three perceived drawbacks of SSS*, making it a practical algorithm. Further, because the search is now based on Alpha-Beta, the extensive research on minimax search enhancements can be easily integrated into AB-SSS*. To test AB-SSS* in practise, it has been implemented in three state-of-the- art programs: for checkers, Othello and chess. AB-SSS* is comparable in performance to Alpha-Beta on leaf node count in all three games, making it a viable alternative to Alpha-Beta in practise. Whereas SSS* has usually been regarded as being entirely different from Alpha-Beta, it turns out to be just an Alpha-Beta enhancement, like null-window searching. This runs counter to published simulation results. Our research leads to the surprising result that iterative deepening versions of Alpha-Beta can expand fewer leaf nodes than iterative deepening versions of SSS* due to dynamic move re-ordering.