OpenRaiser/Intern-Atlas huggingface dataset:
Adaptive and Iterative Multi-Branch MMSE Decision Feedback Detection Algorithms for MIMO Systems
Venue: arXiv cs.IT 2013
Year: 2013

In this work, decision feedback (DF) detection algorithms based on multiple processing branches for multi-input multi-output (MIMO) spatial multiplexing systems are proposed. The proposed detector employs multiple cancellation branches with receive filters that are obtained from a common matrix inverse and achieves a performance close to the maximum likelihood detector (MLD). Constrained minimum mean-squared error (MMSE) receive filters designed with constraints on the shape and magnitude of the feedback filters for the multi-branch MMSE DF (MB-MMSE-DF) receivers are presented. An adaptive implementation of the proposed MB-MMSE-DF detector is developed along with a recursive least squares-type algorithm for estimating the parameters of the receive filters when the channel is time-varying. A soft-output version of the MB-MMSE-DF detector is also proposed as a component of an iterative detection and decoding receiver structure. A computational complexity analysis shows that the MB-MMSE-DF detector does not require a significant additional complexity over the conventional MMSE-DF detector, whereas a diversity analysis discusses the diversity order achieved by the MB-MMSE-DF detector. Simulation results show that the MB-MMSE-DF detector achieves a performance superior to existing suboptimal detectors and close to the MLD, while requiring significantly lower complexity.
A (7/2)-Approximation Algorithm for Guarding Orthogonal Art Galleries with Sliding Cameras
Venue: arXiv cs.CG 2013
Year: 2013

Consider a sliding camera that travels back and forth along an orthogonal line segment $s$ inside an orthogonal polygon $P$ with $n$ vertices. The camera can see a point $p$ inside $P$ if and only if there exists a line segment containing $p$ that crosses $s$ at a right angle and is completely contained in $P$. In the minimum sliding cameras (MSC) problem, the objective is to guard $P$ with the minimum number of sliding cameras. In this paper, we give an $O(n^{5/2})$-time $(7/2)$-approximation algorithm to the MSC problem on any simple orthogonal polygon with $n$ vertices, answering a question posed by Katz and Morgenstern (2011). To the best of our knowledge, this is the first constant-factor approximation algorithm for this problem.
Accelerating R-based Analytics on the Cloud
Venue: arXiv cs.DC 2013
Year: 2013

This paper addresses how the benefits of cloud-based infrastructure can be harnessed for analytical workloads. Often the software handling analytical workloads is not developed by a professional programmer, but on an ad hoc basis by Analysts in high-level programming environments such as R or Matlab. The goal of this research is to allow Analysts to take an analytical job that executes on their personal workstations, and with minimum effort execute it on cloud infrastructure and manage both the resources and the data required by the job. If this can be facilitated gracefully, then the Analyst benefits from on-demand resources, low maintenance cost and scalability of computing resources, all of which are offered by the cloud. In this paper, a Platform for Parallel R-based Analytics on the Cloud (P2RAC) that is placed between an Analyst and a cloud infrastructure is proposed and implemented. P2RAC offers a set of command-line tools for managing the resources, such as instances and clusters, the data and the execution of the software on the Amazon Elastic Computing Cloud infrastructure. Experimental studies are pursued using two parallel problems and the results obtained confirm the feasibility of employing P2RAC for solving large-scale analytical problems on the cloud.
Parameterized Algorithms for Modular-Width
Venue: arXiv cs.DS 2013
Year: 2013

It is known that a number of natural graph problems which are FPT parameterized by treewidth become W-hard when parameterized by clique-width. It is therefore desirable to find a different structural graph parameter which is as general as possible, covers dense graphs but does not incur such a heavy algorithmic penalty. The main contribution of this paper is to consider a parameter called modular-width, defined using the well-known notion of modular decompositions. Using a combination of ILPs and dynamic programming we manage to design FPT algorithms for Coloring and Partitioning into paths (and hence Hamiltonian path and Hamiltonian cycle), which are W-hard for both clique-width and its recently introduced restriction, shrub-depth. We thus argue that modular-width occupies a sweet spot as a graph parameter, generalizing several simpler notions on dense graphs but still evading the "price of generality" paid by clique-width.
Opacity of Memory Management in Software Transactional Memory
Venue: arXiv cs.DC 2013
Year: 2013

Opacity of Transactional Memory is proposed to be established by incremental validation. Quiescence in terms of epoch-based memory reclamation is applied to deal with doomed transactions causing memory access violations. This method unfortunately involves increased memory consumption and does not cover reclamations outside of transactions. This paper introduces a different method which combines incremental validation with elements of sandboxing to solve these issues.
Gradient Magnitude Similarity Deviation: A Highly Efficient Perceptual Image Quality Index
Venue: arXiv cs.CV 2013
Year: 2013

It is an important task to faithfully evaluate the perceptual quality of output images in many applications such as image compression, image restoration and multimedia streaming. A good image quality assessment (IQA) model should not only deliver high quality prediction accuracy but also be computationally efficient. The efficiency of IQA metrics is becoming particularly important due to the increasing proliferation of high-volume visual data in high-speed networks. We present a new effective and efficient IQA model, called gradient magnitude similarity deviation (GMSD). The image gradients are sensitive to image distortions, while different local structures in a distorted image suffer different degrees of degradations. This motivates us to explore the use of global variation of gradient based local quality map for overall image quality prediction. We find that the pixel-wise gradient magnitude similarity (GMS) between the reference and distorted images combined with a novel pooling strategy the standard deviation of the GMS map can predict accurately perceptual image quality. The resulting GMSD algorithm is much faster than most state-of-the-art IQA methods, and delivers highly competitive prediction accuracy.
Communication Network Design: Balancing Modularity and Mixing via Optimal Graph Spectra
Venue: arXiv cs.SI 2013
Year: 2013

By leveraging information technologies, organizations now have the ability to design their communication networks and crowdsourcing platforms to pursue various performance goals, but existing research on network design does not account for the specific features of social networks, such as the notion of teams. We fill this gap by demonstrating how desirable aspects of organizational structure can be mapped parsimoniously onto the spectrum of the graph Laplacian allowing the specification of structural objectives and build on recent advances in non-convex programming to optimize them. This design framework is general, but we focus here on the problem of creating graphs that balance high modularity and low mixing time, and show how "liaisons" rather than brokers maximize this objective.
Detecting Data Races on OpenCL Kernels with Symbolic Execution
Venue: arXiv cs.PL 2013
Year: 2013

We present an automatic analysis technique for checking data races on OpenCL kernels. Our method defines symbolic execution techniques based on separation logic with suitable abstractions to automatically detect non-benign racy behaviours on kernel
Space-Time Interference Alignment and Degrees of Freedom Regions for the MISO Broadcast Channel with Periodic CSI Feedback
Venue: arXiv cs.IT 2013
Year: 2013

This paper characterizes the degrees of freedom (DoF) regions for the multi-user vector broadcast channel with periodic channel state information (CSI) feedback. As a part of the characterization, a new transmission method called space-time interference alignment is proposed, which exploits both the current and past CSI jointly. Using the proposed alignment technique, an inner bound of the sum-DoF region is characterized as a function of a normalized CSI feedback frequency, which measures CSI feedback speed compared to the speed of user's channel variations. One consequence of the result is that the achievable sum-DoF gain is improved significantly when a user sends back both current and outdated CSI compared to the case where the user sends back current CSI only. Then, a trade-off between CSI feedback delay and the sum-DoF gain is characterized for the multi-user vector broadcast channel in terms of a normalized CSI feedback delay that measures CSI obsoleteness compared to channel coherence time. A crucial insight is that it is possible to achieve the optimal DoF gain if the feedback delay is less than a derived fraction of the channel coherence time. This precisely characterizes the intuition that a small delay should be negligible.
Improving the Testability of Object-oriented Software during Testing and Debugging Processes
Venue: arXiv cs.SE 2013
Year: 2013

Testability is the probability whether tests will detect a fault, given that a fault in the program exists. How efficiently the faults will be uncovered depends upon the testability of the software. Various researchers have proposed qualitative and quantitative techniques to improve and measure the testability of software. In literature, a plethora of reliability growth models have been used to assess and measure the quantitative quality assessment of software during testing and operational phase. The knowledge about failure distribution and their complexity can improve the testability of software. Testing effort allocation can be made easy by knowing the failure distribution and complexity of faults, and this will ease the process of revealing faults from the software. As a result, the testability of the software will be improved. The parameters of the model along with the proportion of faults of different complexity to be removed from the software have been presented in the paper .We have used failure data of two object oriented software developed under open source environment namely MySQL for python and Squirrel SQL Client for estimation purpose
Sorted Range Reporting Revisited
Venue: arXiv cs.DS 2013
Year: 2013

We consider the two-dimensional sorted range reporting problem. Our data structure requires O(n lglg n) words of space and O(lglg n + k lglg n) query time, where k is the number of points in the query range. This data structure improves a recent result of Nekrich and Navarro [8] by a factor of O(lglg n) in query time, and matches the state of the art for unsorted range reporting [1].
On Some Recent MAX SAT Approximation Algorithms
Venue: arXiv cs.DS 2013
Year: 2013

Recently a number of randomized 3/4-approximation algorithms for MAX SAT have been proposed that all work in the same way: given a fixed ordering of the variables, the algorithm makes a random assignment to each variable in sequence, in which the probability of assigning each variable true or false depends on the current set of satisfied (or unsatisfied) clauses. To our knowledge, the first such algorithm was proposed by Poloczek and Schnitger; Van Zuylen subsequently gave an algorithm that set the probabilities differently and had a simpler analysis. She also set up a framework for deriving such algorithms. Buchbinder, Feldman, Naor, and Schwartz, as a special case of their work on maximizing submodular functions, also give a randomized 3/4-approximation algorithm for MAX SAT with the same structure as these previous algorithms. In this note we give a gloss on the Buchbinder et al. algorithm that makes it even simpler, and show that in fact it is equivalent to the previous algorithm of Van Zuylen. We also show how it extends to a deterministic LP rounding algorithm; such an algorithm was also given by Van Zuylen.
Security Type Systems as Recursive Predicates
Venue: arXiv cs.CR 2013
Year: 2013

We show how security type systems from the literature of language-based noninterference can be represented more directly as predicates defined by structural recursion on the programs. In this context, we show how our uniform syntactic criteria from previous work cover several previous type-system soundness results.
xTras: a field-theory inspired xAct package for Mathematica
Venue: arXiv cs.SC 2013
Year: 2013

We present the tensor computer algebra package xTras, which provides functions and methods frequently needed when doing (classical) field theory. Amongst others, it can compute contractions, make Ansätze, and solve tensorial equations. It is built upon the tensor computer algebra system xAct, a collection of packages for Mathematica.
Innovative Second-Generation Wavelets Construction With Recurrent Neural Networks for Solar Radiation Forecasting
Venue: arXiv cs.NE 2013
Year: 2013

Solar radiation prediction is an important challenge for the electrical engineer because it is used to estimate the power developed by commercial photovoltaic modules. This paper deals with the problem of solar radiation prediction based on observed meteorological data. A 2-day forecast is obtained by using novel wavelet recurrent neural networks (WRNNs). In fact, these WRNNS are used to exploit the correlation between solar radiation and timescale-related variations of wind speed, humidity, and temperature. The input to the selected WRNN is provided by timescale-related bands of wavelet coefficients obtained from meteorological time series. The experimental setup available at the University of Catania, Italy, provided this information. The novelty of this approach is that the proposed WRNN performs the prediction in the wavelet domain and, in addition, also performs the inverse wavelet transform, giving the predicted signal as output. The obtained simulation results show a very low root-mean-square error compared to the results of the solar radiation prediction approaches obtained by hybrid neural networks reported in the recent literature.
Distributed Ranging and Localization for Wireless Networks via Compressed Sensing
Venue: arXiv cs.NI 2013
Year: 2013

Location-based services in a wireless network require nodes to know their locations accurately. Conventional solutions rely on contention-based medium access, where only one node can successfully transmit at any time in any neighborhood. In this paper, a novel, complete, distributed ranging and localization solution is proposed, which let all nodes in the network broadcast their location estimates and measure distances to all neighbors simultaneously. An on-off signaling is designed to overcome the physical half-duplex constraint. In each iteration, all nodes transmit simultaneously, each broadcasting codewords describing the current location estimate. From the superposed signals from all neighbors, each node decodes their neighbors' locations and also estimates their distances using the signal strengths. The node then broadcasts its improved location estimates in the subsequent iteration. Simulations demonstrate accurate localization throughout a large network over a few thousand symbol intervals, suggesting much higher efficiency than conventional schemes based on ALOHA or CSMA.
Application of Analog Network Coding to MIMO Two-Way Relay Channel in Cellular Systems
Venue: arXiv cs.IT 2013
Year: 2013

An efficient analog network coding transmission protocol is proposed in this letter for a MIMO two way cellular network. Block signal alignment is first proposed to null the inter-user interference for multi-antenna users, which makes the dimensions of aligned space larger compared with the existing signal alignment. Two algorithms are developed to jointly design the precoding matrices at the relay and BS for outage optimization. Especially, the last algorithm is designed to maximize the effective channel gain to the effective noise gain ratio. The performance of this transmission protocol is also verified by simulations.
ZigBee Based Wireless Data Acquisition Using LabVIEW for Implementing Smart Driving Skill Evaluation System
Venue: arXiv cs.CY 2013
Year: 2013

The Smart Driving Skill Evaluation (SDSE) System presented in this paper expedite the testing of candidates aspiring for a driving license in a more efficient and transparent manner, as compared to the present manual testing procedure existing in most parts of Asia and Pacific region. The manual test procedure is also subjected to multiple limitations like time consuming, costly and heavily controlled by the experience of examiner in conducting the test. This technological solution is developed by customizing 8051 controller based embedded system and LabVIEW based virtual instrument. The controller module senses the motion of the test vehicle on the test track referred to as zero rpm measurement and the LabVIEW based virtual instrument provides a Graphical User Interface for remote end monitoring of the sensors embedded on the test track. The proposed technological solution for the automation of existing manual test process enables the elimination of human intervention and improves the driving test accuracy while going paperless with Driving Skill Evaluation System. As a contribution to the society this technological solution can reduce the number of road accidents because most accidents results from lack of planning, anticipation and control which are highly dependent on driving skill.
Computational Properties of Fiction Writing and Collaborative Work
Venue: arXiv cs.HC 2013
Year: 2013

From the earliest days of computing, there have been tools to help shape narrative. Spell-checking, word counts, and readability analysis, give today's novelists tools that Dickens, Austen, and Shakespeare could only have dreamt of. However, such tools have focused on the word, or phrase levels. In the last decade, research focus has shifted to support for collaborative editing of documents. This work considers more sophisticated attempts to visualise the semantics, pace and rhythm within a narrative through data mining. We describe real life applications in two related domains.
Comment on "robustness and regularization of support vector machines" by H. Xu, et al., (Journal of Machine Learning Research, vol. 10, pp. 1485-1510, 2009, arXiv:0803.3490)
Venue: arXiv cs.LG 2013
Year: 2013

This paper comments on the published work dealing with robustness and regularization of support vector machines (Journal of Machine Learning Research, vol. 10, pp. 1485-1510, 2009) [arXiv:0803.3490] by H. Xu, etc. They proposed a theorem to show that it is possible to relate robustness in the feature space and robustness in the sample space directly. In this paper, we propose a counter example that rejects their theorem.
Joint Phase Noise Estimation and Data Detection in Coded MIMO Systems
Venue: arXiv cs.IT 2013
Year: 2013

In this paper, the problem of joint oscillator phase noise (PHN) estimation and data detection for multi-input multi-output (MIMO) systems using bit-interleaved coded modulation (BICM) is analyzed. A new MIMO receiver that iterates between the estimator and the detector, based on the expectation-maximization (EM) framework, is proposed. It is shown that at high signal-to-noise ratios, a maximum a posteriori estimator (MAP) can be used to carry out the maximization step of the EM algorithm. Moreover, to reduce the computational complexity of the proposed EM algorithm, a soft decision-directed extended Kalman filter-smoother (EKFS) is applied instead of the MAP estimator to track the PHN parameters. Numerical results show that by combining the proposed EKFS based approach with an iterative detector that employs low density parity check (LDPC) codes, PHN can be accurately tracked. Simulations also demonstrate that compared to existing algorithms, the proposed iterative receiver can significantly enhance the performance of MIMO systems in the presence of PHN.
Reference Distance Estimator
Venue: arXiv cs.LG 2013
Year: 2013

A theoretical study is presented for a simple linear classifier called reference distance estimator (RDE), which assigns the weight of each feature j as P(r|j)-P(r), where r is a reference feature relevant to the target class y. The analysis shows that if r performs better than random guess in predicting y and is conditionally independent with each feature j, the RDE will have the same classification performance as that from P(y|j)-P(y), a classifier trained with the gold standard y. Since the estimation of P(r|j)-P(r) does not require labeled data, under the assumption above, RDE trained with a large number of unlabeled examples would be close to that trained with infinite labeled examples. For the case the assumption does not hold, we theoretically analyze the factors that influence the closeness of the RDE to the perfect one under the assumption, and present an algorithm to select reference features and combine multiple RDEs from different reference features using both labeled and unlabeled data. The experimental results on 10 text classification tasks show that the semi-supervised learning method improves supervised methods using 5,000 labeled examples and 13 million unlabeled ones, and in many tasks, its performance is even close to a classifier trained with 13 million labeled examples. In addition, the bounds in the theorems provide good estimation of the classification performance and can be useful for new algorithm design.
Natural Language Web Interface for Database (NLWIDB)
Venue: arXiv cs.CL 2013
Year: 2013

It is a long term desire of the computer users to minimize the communication gap between the computer and a human. On the other hand, almost all ICT applications store information in to databases and retrieve from them. Retrieving information from the database requires knowledge of technical languages such as Structured Query Language. However majority of the computer users who interact with the databases do not have a technical background and are intimidated by the idea of using languages such as SQL. For above reasons, a Natural Language Web Interface for Database (NLWIDB) has been developed. The NLWIDB allows the user to query the database in a language more like English, through a convenient interface over the Internet.
Compiling Finite Domain Constraints to SAT with BEE: the Director's Cut
Venue: arXiv cs.PL 2013
Year: 2013

BEE is a compiler which facilitates solving finite domain constraints by encoding them to CNF and applying an underlying SAT solver. In BEE constraints are modeled as Boolean functions which propagate information about equalities between Boolean literals. This information is then applied to simplify the CNF encoding of the constraints. We term this process equi-propagation. A key factor is that considering only a small fragment of a constraint model at one time enables to apply stronger, and even complete reasoning to detect equivalent literals in that fragment. Once detected, equivalences propagate to simplify the entire constraint model and facilitate further reasoning on other fragments. BEE is described in several recent papers. In this paper, after a quick review of BEE, we elaborate on two undocumented details of the implementation: the hybrid encoding of cardinality constraints and complete equi-propagation. We thendescribe on-going work aimed to extend BEE to consider binary representation of numbers.
Remarks on criteria for achieving the optimal diversity-multiplexing gain trade-off
Venue: arXiv cs.IT 2013
Year: 2013

In this short note we will prove that non-vanishing determinant (NVD) criterion is not enough for an asymmetric space-time block code (STBC) to achieve the optimal diversity-multiplexing gain trade-off (DMT). This result is in contrast to the recent result made by Srinath and Rajan. In order to clarify the issue further the approximately universality criterion by Tavildar and Viswanath is translated into language of lattice theory and some conjectures are given.