OpenRaiser/Intern-Atlas huggingface dataset:
Tucker Decomposition For Rotated Codebook in 3D MIMO System Under Spatially Correlated Channel
Venue: arXiv cs.IT 2015
Year: 2015

This correspondence proposes a new rotated codebook for three-dimensional (3D) multi-input-multi-output (MIMO) system under spatially correlated channel. To avoid the problem of high dimensionality led by large antenna array, the rotation matrix in the rotated codebook is proposed to be decomposed by Tucker decomposition into three lowdimensional units, i.e., statistical channel direction information in horizontal and vertical directions respectively, and statistical channel power in the joint horizontal and vertical direction. A closed-form suboptimal solution is provided to reduce the computational complexity in Tucker decomposition. The proposed codebook has a significant dimension reduction from conventional rotated codebooks, and is applicable for 3D MIMO system with arbitrary form of antenna array. Simulation results demonstrate that the proposed codebook works very well for various 3D MIMO systems.
Definability Equals Recognizability for $k$-Outerplanar Graphs
Venue: arXiv cs.LO 2015
Year: 2015

One of the most famous algorithmic meta-theorems states that every graph property that can be defined by a sentence in counting monadic second order logic (CMSOL) can be checked in linear time for graphs of bounded treewidth, which is known as Courcelle's Theorem. These algorithms are constructed as finite state tree automata, and hence every CMSOL-definable graph property is recognizable. Courcelle also conjectured that the converse holds, i.e. every recognizable graph property is definable in CMSOL for graphs of bounded treewidth. We prove this conjecture for $k$-outerplanar graphs, which are known to have treewidth at most $3k-1$.
On the geometry of border rank algorithms for n x 2 by 2 x 2 matrix multiplication
Venue: arXiv cs.NA 2015
Year: 2015

We make an in-depth study of the known border rank (i.e. approximate) algorithms for the matrix multiplication tensor encoding the multiplication of an n x 2 matrix by a 2 x 2 matrix.
Optimal Estimation with Limited Measurements and Noisy Communication
Venue: arXiv cs.SY 2015
Year: 2015

This paper considers a sequential estimation and sensor scheduling problem with one sensor and one estimator. The sensor makes sequential observations about the state of an underlying memoryless stochastic process, and makes a decision as to whether or not to send this measurement to the estimator. The sensor and the estimator have the common objective of minimizing expected distortion in the estimation of the state of the process, over a finite time horizon, with the constraint that the sensor can transmit its observation only a limited number of times. As opposed to the prior work where communication between the sensor and the estimator was assumed to be perfect (noiseless), in this work an additive noise channel with fixed power constraint is considered; hence, the sensor has to encode its message before transmission. For some specific source and channel noise densities, we obtain the optimal encoding and estimation policies in conjunction with the optimal transmission schedule. The impact of the presence of a noisy channel is analyzed numerically based on dynamic programming. This analysis yields some rather surprising results such as a phase-transition phenomenon in the number of used transmission opportunities, which was not encountered in the noiseless communication setting.
Skin Effect Modeling in Conductors of Arbitrary Shape Through a Surface Admittance Operator and the Contour Integral Method
Venue: arXiv cs.CE 2015
Year: 2015

An accurate modeling of skin effect inside conductors is of capital importance to solve transmission line and scattering problems. This paper presents a surface-based formulation to model skin effect in conductors of arbitrary cross section, and compute the per-unit-length impedance of a multiconductor transmission line. The proposed formulation is based on the Dirichlet-Neumann operator that relates the longitudinal electric field to the tangential magnetic field on the boundary of a conductor. We demonstrate how the surface operator can be obtained through the contour integral method for conductors of arbitrary shape. The proposed algorithm is simple to implement, efficient, and can handle arbitrary cross-sections, which is a main advantage over the existing approach based on eigenfunctions, which is available only for canonical conductor's shapes. The versatility of the method is illustrated through a diverse set of examples, which includes transmission lines with trapezoidal, curved, and V-shaped conductors. Numerical results demonstrate the accuracy, versatility, and efficiency of the proposed technique.
Matrix Theory for Minimal Trellises
Venue: arXiv cs.IT 2015
Year: 2015

Trellises provide a graphical representation for the row space of a matrix. The product construction of Kschischang and Sorokine builds minimal conventional trellises from matrices in minimal span form. Koetter and Vardy showed that minimal tail-biting trellises can be obtained by applying the product construction to submatrices of a characteristic matrix. We introduce the unique reduced minimal span form of a matrix and we obtain an expression for the unique reduced characteristic matrix. Among new properties of characteristic matrices we prove that characteristic matrices are in duality if and only if they have orthogonal column spaces, and that the transpose of a characteristic matrix is again a characteristic matrix if and only if the characteristic matrix is reduced. These properties have clear interpretations for the unwrapped unit memory convolutional code of a tail-biting trellis, they explain the duality for the class of Koetter and Vardy trellises, and they give a natural relation between the characteristic matrix based Koetter-Vardy construction and the displacement matrix based Nori-Shankar construction. For a pair of reduced characteristic matrices in duality, one is lexicographically first in a forward direction and the other is lexicographically first in the reverse direction. This confirms a conjecture by Koetter and Vardy after taking into account the different directions for the lexicographical ordering.
The more Product Complexity, the more Actual Effort? An Empirical Investigation into Software Developments
Venue: arXiv cs.SE 2015
Year: 2015

[Background:] Software effort prediction methods and models typically assume positive correlation between software product complexity and development effort. However, conflicting observations, i.e. negative correlation between product complexity and actual effort, have been witnessed from our experience with the COCOMO81 dataset. [Aim:] Given our doubt about whether the observed phenomenon is a coincidence, this study tries to investigate if an increase in product complexity can result in the abovementioned counter-intuitive trend in software development projects. [Method:] A modified association rule mining approach is applied to the transformed COCOMO81 dataset. To reduce noise of analysis, this approach uses a constant antecedent (Complexity increases while Effort decreases) to mine potential consequents with pruning. [Results:] The experiment has respectively mined four, five, and seven association rules from the general, embedded, and organic projects data. The consequents of the mined rules suggested two main aspects, namely human capability and product scale, to be particularly concerned in this study. [Conclusions:] The negative correlation between complexity and effort is not a coincidence under particular conditions. In a software project, interactions between product complexity and other factors, such as Programmer Capability and Analyst Capability, can inevitably play a "friction" role in weakening the practical influences of product complexity on actual development effort.
Learning dynamic Boltzmann machines with spike-timing dependent plasticity
Venue: arXiv cs.NE 2015
Year: 2015

We propose a particularly structured Boltzmann machine, which we refer to as a dynamic Boltzmann machine (DyBM), as a stochastic model of a multi-dimensional time-series. The DyBM can have infinitely many layers of units but allows exact and efficient inference and learning when its parameters have a proposed structure. This proposed structure is motivated by postulates and observations, from biological neural networks, that the synaptic weight is strengthened or weakened, depending on the timing of spikes (i.e., spike-timing dependent plasticity or STDP). We show that the learning rule of updating the parameters of the DyBM in the direction of maximizing the likelihood of given time-series can be interpreted as STDP with long term potentiation and long term depression. The learning rule has a guarantee of convergence and can be performed in a distributed matter (i.e., local in space) with limited memory (i.e., local in time).
Tuned and GPU-accelerated parallel data mining from comparable corpora
Venue: arXiv cs.CL 2015
Year: 2015

The multilingual nature of the world makes translation a crucial requirement today. Parallel dictionaries constructed by humans are a widely-available resource, but they are limited and do not provide enough coverage for good quality translation purposes, due to out-of-vocabulary words and neologisms. This motivates the use of statistical translation systems, which are unfortunately dependent on the quantity and quality of training data. Such has a very limited availability especially for some languages and very narrow text domains. Is this research we present our improvements to Yalign mining methodology by reimplementing the comparison algorithm, introducing a tuning scripts and by improving performance using GPU computing acceleration. The experiments are conducted on various text domains and bi-data is extracted from the Wikipedia dumps.
Data Hiding using Graphical Code based Steganography Technique
Venue: arXiv cs.IT 2015
Year: 2015

Data hiding has received much attention due to rapid development of internet and multimedia technologies where security of information is a very important concern. This is achieved by Steganography, which is the art or science of hiding data into another data, so that human eyes cannot catch the hidden information easily. There are many ways to hide information-like inside an image, text, audio/ video etc. Among them image steganography is a very attractive research area. The goal is to transmit a data within a modified image (called stego-image)by minimizing the number of bit flips. In this paper, a new steganography technique has been proposed using Graphical codes and also comparison with steganography technique using BCH codes has been studied.
Reasoning in Infinitely Valued G-IALCQ
Venue: arXiv cs.AI 2015
Year: 2015

Fuzzy Description Logics (FDLs) are logic-based formalisms used to represent and reason with vague or imprecise knowledge. It has been recently shown that reasoning in most FDLs using truth values from the interval [0,1] becomes undecidable in the presence of a negation constructor and general concept inclusion axioms. One exception to this negative result are FDLs whose semantics is based on the infinitely valued Gödel t-norm (G). In this paper, we extend previous decidability results for G-IALC to deal also with qualified number restrictions. Our novel approach is based on a combination of the known crispification technique for finitely valued FDLs and the automata-based procedure originally developed for reasoning in G-IALC. The proposed approach combines the advantages of these two methods, while removing their respective drawbacks.
Quadratic polynomials of small modulus cannot represent OR
Venue: arXiv cs.CC 2015
Year: 2015

An open problem in complexity theory is to find the minimal degree of a polynomial representing the $n$-bit OR function modulo composite $m$. This problem is related to understanding the power of circuits with $\text{MOD}_m$ gates where $m$ is composite. The OR function is of particular interest because it is the simplest function not amenable to bounds from communication complexity. Tardos and Barrington established a lower bound of $Ω((\log n)^{O_m(1)})$, and Barrington, Beigel, and Rudich established an upper bound of $n^{O_m(1)}$. No progress has been made on closing this gap for twenty years, and progress will likely require new techniques. We make progress on this question viewed from a different perspective: rather than fixing the modulus $m$ and bounding the minimum degree $d$ in terms of the number of variables $n$, we fix the degree $d$ and bound $n$ in terms of the modulus $m$. For degree $d=2$, we prove a quasipolynomial bound of $n\le m^{O(d)}\le m^{O(\log m)}$, improving the previous best bound of $2^{O(m)}$ implied by Tardos and Barrington's general bound. To understand the computational power of quadratic polynomials modulo $m$, we introduce a certain dichotomy which may be of independent interest. Namely, we define a notion of boolean rank of a quadratic polynomial $f$ and relate it to the notion of diagonal rigidity. Using additive combinatorics, we show that when the rank is low, $f(\mathbf x)=0$ must have many solutions. Using techniques from exponential sums, we show that when the rank of $f$ is high, $f$ is close to equidistributed. In either case, $f$ cannot represent the OR function in many variables.
Storing and Analyzing Historical Graph Data at Scale
Venue: arXiv cs.DB 2015
Year: 2015

The work on large-scale graph analytics to date has largely focused on the study of static properties of graph snapshots. However, a static view of interactions between entities is often an oversimplification of several complex phenomena like the spread of epidemics, information diffusion, formation of online communities}, and so on. Being able to find temporal interaction patterns, visualize the evolution of graph properties, or even simply compare them across time, adds significant value in reasoning over graphs. However, because of lack of underlying data management support, an analyst today has to manually navigate the added temporal complexity of dealing with large evolving graphs. In this paper, we present a system, called Historical Graph Store, that enables users to store large volumes of historical graph data and to express and run complex temporal graph analytical tasks against that data. It consists of two key components: a Temporal Graph Index (TGI), that compactly stores large volumes of historical graph evolution data in a partitioned and distributed fashion; it provides support for retrieving snapshots of the graph as of any timepoint in the past or evolution histories of individual nodes or neighborhoods; and a Spark-based Temporal Graph Analysis Framework (TAF), for expressing complex temporal analytical tasks and for executing them in an efficient and scalable manner. Our experiments demonstrate our system's efficient storage, retrieval and analytics across a wide variety of queries on large volumes of historical graph data.
The Cloud Needs a Reputation System
Venue: arXiv cs.NI 2015
Year: 2015

Today's cloud apps are built from many diverse services that are managed by different parties. At the same time, these parties, which consume and/or provide services, continue to rely on arcane static security and entitlements models. In this paper, we introduce Seit, an inter-tenant framework that manages the interactions between cloud services. Seit is a software-defined reputation-based framework. It consists of two primary components: (1) a set of integration and query interfaces that can be easily integrated into cloud and service providers' management stacks, and (2) a controller that maintains reputation information using a mechanism that is adaptive to the highly dynamic environment of the cloud. We have fully implemented Seit, and integrated it into an SDN controller, a load balancer, a cloud service broker, an intrusion detection system, and a monitoring framework. We evaluate the efficacy of Seit using both an analytical model and a Mininet-based emulated environment. Our analytical model validate the isolation and stability properties of Seit. Using our emulated environment, we show that Seit can provide improved security by isolating malicious tenants, reduced costs by adapting the infrastructure without compromising security, and increased revenues for high quality service providers by enabling reputation to impact discovery.
Knowledge-based system for collaborative process specification
Venue: arXiv cs.SE 2015
Year: 2015

This paper presents an ontology-based approach for the design of a collaborative business process model (CBP). This CBP is considered as a specification of needs in order to build a collaboration information system (CIS) for a network of organisations. The study is a part of a model driven engineering approach of the CIS in a specific enterprise interoperability framework that will be summarised. An adaptation of the Business Process Modeling Notation (BPMN) is used to represent the CBP model. We develop a knowledge-based system (KbS) which is composed of three main parts: knowledge gathering, knowledge representation and reasoning, and collaborative business process modelling. The first part starts from a high abstraction level where knowledge from business partners is captured. A collaboration ontology is defined in order to provide a structure to store and use the knowledge captured. In parallel, we try to reuse generic existing knowledge about business processes from the MIT Process Handbook repository. This results in a collaboration process ontology that is also described. A set of rules is defined in order to extract knowledge about fragments of the CBP model from the two previous ontologies. These fragments are finally assembled in the third part of the KbS. A prototype of the KbS has been developed in order to implement and support this approach. The prototype is a computer-aided design tool of the CBP. In this paper, we will present the theoretical aspects of each part of this KbS as well as the tools that we developed and used in order to support its functionalities.
Distributed Multi-task APA over Adaptive Networks Based on Partial Diffusion
Venue: arXiv cs.SY 2015
Year: 2015

Distributed multi-task adaptive strategies are useful to estimate multiple parameter vectors simultaneously in a collaborative manner. The existed distributed multi-task strategies use diffusion mode of cooperation in which during adaptation step each node gets the cooperation from it neighborhood nodes but not in the same cluster and during combining step each node combines the intermediate estimates of it neighboring nodes that belong to the same cluster. For this the nodes need to transmit the intermediate estimates to its neighborhood. In this paper we propose an extension to the multi-task diffusion affine projection algorithm by allowing partial sharing of the entries of the intermediate estimates among the neighbors. The proposed algorithm is termed as multi-task Partial diffusion Affine projection Algorithm (multi-task Pd-APA) which can provide the trade-off between the communication performance and the estimation performance. The performance analysis of the proposed multi-task partial diffusion APA algorithm is studied in mean and mean square sense. Simulations were conducted to verify the analytical results.
A spatial compositional model (SCM) for linear unmixing and endmember uncertainty estimation
Venue: arXiv cs.CV 2015
Year: 2015

The normal compositional model (NCM) has been extensively used in hyperspectral unmixing. However, most of the previous research has focused on estimation of endmembers and/or their variability. Also, little work has employed spatial information in NCM. In this paper, we show that NCM can be used for calculating the uncertainty of the estimated endmembers with spatial priors incorporated for better unmixing. This results in a spatial compositional model (SCM) which features (i) spatial priors that force neighboring abundances to be similar based on their pixel similarity and (ii) a posterior that is obtained from a likelihood model which does not assume pixel independence. The resulting algorithm turns out to be easy to implement and efficient to run. We compared SCM with current state-of-the-art algorithms on synthetic and real images. The results show that SCM can in the main provide more accurate endmembers and abundances. Moreover, the estimated uncertainty can serve as a prediction of endmember error under certain conditions.
Distributed Inference for Relay-Assisted Sensor Networks With Intermittent Measurements Over Fading Channels
Venue: arXiv cs.IT 2015
Year: 2015

In this paper, we consider a general distributed estimation problem in relay-assisted sensor networks by taking into account time-varying asymmetric communications, fading channels and intermittent measurements. Motivated by centralized filtering algorithms, we propose a distributed innovation-based estimation algorithm by combining the measurement innovation (assimilation of new measurement) and local data innovation (incorporation of neighboring data). Our algorithm is fully distributed which does not need a fusion center. We establish theoretical results regarding asymptotic unbiasedness and consistency of the proposed algorithm. Specifically, in order to cope with time-varying asymmetric communications, we utilize an ordering technique and the generalized Perron complement to manipulate the first and second moment analyses in a tractable framework. Furthermore, we present a performance-oriented design of the proposed algorithm for energy-constrained networks based on the theoretical results. Simulation results corroborate the theoretical findings, thus demonstrating the effectiveness of the proposed algorithm.
A High-Performance Parallel Algorithm for Nonnegative Matrix Factorization
Venue: arXiv cs.DC 2015
Year: 2015

Non-negative matrix factorization (NMF) is the problem of determining two non-negative low rank factors $W$ and $H$, for the given input matrix $A$, such that $A \approx W H$. NMF is a useful tool for many applications in different domains such as topic modeling in text mining, background separation in video analysis, and community detection in social networks. Despite its popularity in the data mining community, there is a lack of efficient parallel software to solve the problem for big datasets. Existing distributed-memory algorithms are limited in terms of performance and applicability, as they are implemented using Hadoop and are designed only for sparse matrices. We propose a distributed-memory parallel algorithm that computes the factorization by iteratively solving alternating non-negative least squares (NLS) subproblems for $W$ and $H$. To our knowledge, our algorithm is the first high-performance parallel algorithm for NMF. It maintains the data and factor matrices in memory (distributed across processors), uses MPI for interprocessor communication, and, in the dense case, provably minimizes communication costs (under mild assumptions). As opposed to previous implementations, our algorithm is also flexible: (1) it performs well for dense and sparse matrices, and (2) it allows the user to choose from among multiple algorithms for solving local NLS subproblems within the alternating iterations. We demonstrate the scalability of our algorithm and compare it with baseline implementations, showing significant performance improvements.