OpenRaiser/Intern-Atlas huggingface dataset:
Harnessing the Deep Net Object Models for Enhancing Human Action Recognition
Venue: arXiv cs.CV 2015
Year: 2015

In this study, the influence of objects is investigated in the scenario of human action recognition with large number of classes. We hypothesize that the objects the humans are interacting will have good say in determining the action being performed. Especially, if the objects are non-moving, such as objects appearing in the background, features such as spatio-temporal interest points, dense trajectories may fail to detect them. Hence we propose to detect objects using pre-trained object detectors in every frame statically. Trained Deep network models are used as object detectors. Information from different layers in conjunction with different encoding techniques is extensively studied to obtain the richest feature vectors. This technique is observed to yield state-of-the-art performance on HMDB51 and UCF101 datasets.
Sparse Multipath Channel Estimation and Decoding for Broadband Vector OFDM Systems
Venue: arXiv cs.IT 2015
Year: 2015

Vector orthogonal frequency division multiplexing (V-OFDM) is a general system that builds a bridge between OFDM and single-carrier frequency domain equalization in terms of intersymbol interference and receiver complexity. In this paper, we investigate the sparse multipath channel estimation and decoding for broadband V-OFDM systems. Unlike the non-sparse channel estimation, sparse channel estimation only needs to recover the nonzero taps with reduced complexity. Consider the pilot signals are transmitted through a sparse channel that has only a few nonzero taps with and without additive white Gaussian noise, respectively. The exactly and approximately sparse inverse fast Fourier transform (SIFFT) can be employed for these two cases. The SIFFT-based algorithm recovers the nonzero channel coefficients and their corresponding coordinates directly, which is significant to the proposed partial intersection sphere (PIS) decoding approach. Unlike the maximum likelihood (ML) decoding that enumerates symbol constellation and estimates the transmitted symbols with the minimum distance, the PIS decoding first generates the set of possible transmitted symbols and then chooses the transmitted symbols only from this set with the minimum distance. The diversity order of the PIS decoding is determined by not only the number of nonzero taps, but also the coordinates of nonzero taps, and the bit error rate (BER) is also influenced by vector block size to some extent but roughly independent of the maximum time delay. Simulation results indicate that by choosing appropriate sphere radius, the BER performance of the PIS decoding outperforms the conventional zero-forcing decoding and minimum mean square error decoding, and approximates to the ML decoding with the increase of signal-to-noise ratio, but reduces the computational complexity significantly.
Frequency hopping does not increase anti-jamming resilience of wireless channels
Venue: arXiv cs.IT 2015
Year: 2015

The effectiveness of frequency hopping for anti-jamming protection of wireless channels is analyzed from an information-theoretic perspective. The sender can input its symbols into one of several frequency subbands at a time. Each subband channel is modeled as an additive noise channel. No common randomness between sender and receiver is assumed. It is shown that capacity is positive, and then equals the common randomness assisted (CR) capacity, if and only if the sender power strictly exceeds the jammer power. Thus compared to transmission over any fixed frequency subband, frequency hopping is not more resilient towards jamming, but it does increase the capacity. Upper and lower bounds on the CR capacity are provided.
Spectral Analysis of Quasi-Cyclic Product Codes
Venue: arXiv cs.IT 2015
Year: 2015

This paper considers a linear quasi-cyclic product code of two given quasi-cyclic codes of relatively prime lengths over finite fields. We give the spectral analysis of a quasi-cyclic product code in terms of the spectral analysis of the row- and the column-code. Moreover, we provide a new lower bound on the minimum Hamming distance of a given quasi-cyclic code and present a new algebraic decoding algorithm.More specifically, we prove an explicit (unreduced) basis of an l\_a l\_b-quasi-cyclic product code in terms of the generator matrix in reduced Gr{ö}bner basis with respect to the position-over-term order (RGB/POT) form of the l\_a-quasi-cyclic row- and the l\_b-quasi-cyclic column-code, respectively. This generalizes the work of Burton and Weldon for the generator polynomial of a cyclic product code (where l\_a =l\_b=1). Furthermore, we derive the generator matrix in Pre-RGB/POT form of an l\_a l\_b-quasi-cyclic product code for two special cases: (i) for l\_a=2 and l\_b=1, and (ii) if the row-code is a 1-level l\_a-quasi-cyclic code (for arbitrary l\_a) and l\_b=1.For arbitrary l\_a and l\_b, the Pre-RGB/POT form of the generator matrix of an l\_a l\_b-quasi-cyclic product code is conjectured.The spectral analysis is applied to the generator matrix of the product of an l-quasi-cyclic and a cyclic code, and we propose a new lower bound on the minimum Hamming distance of a given l-quasi-cyclic code. In addition, we develop an efficient syndrome-based decoding algorithm for l-phased burst errors with guaranteed decoding radius.
Dissection with the Fewest Pieces is Hard, Even to Approximate
Venue: arXiv cs.CG 2015
Year: 2015

We prove that it is NP-hard to dissect one simple orthogonal polygon into another using a given number of pieces, as is approximating the fewest pieces to within a factor of $1+1/1080-\varepsilon$.
Multilinear Subspace Clustering
Venue: arXiv cs.IT 2015
Year: 2015

In this paper we present a new model and an algorithm for unsupervised clustering of 2-D data such as images. We assume that the data comes from a union of multilinear subspaces (UOMS) model, which is a specific structured case of the much studied union of subspaces (UOS) model. For segmentation under this model, we develop Multilinear Subspace Clustering (MSC) algorithm and evaluate its performance on the YaleB and Olivietti image data sets. We show that MSC is highly competitive with existing algorithms employing the UOS model in terms of clustering performance while enjoying improvement in computational complexity.
On Lagrangian Relaxation and Reoptimization Problems
Venue: arXiv cs.DS 2015
Year: 2015

We prove a general result demonstrating the power of Lagrangian relaxation in solving constrained maximization problems with arbitrary objective functions. This yields a unified approach for solving a wide class of {\em subset selection} problems with linear constraints. Given a problem in this class and some small $\eps \in (0,1)$, we show that if there exists an $r$-approximation algorithm for the Lagrangian relaxation of the problem, for some $r \in (0,1)$, then our technique achieves a ratio of $\frac{r}{r+1} -\! \eps$ to the optimal, and this ratio is tight. The number of calls to the $r$-approximation algorithm, used by our algorithms, is {\em linear} in the input size and in $\log (1 / \eps)$ for inputs with cardinality constraint, and polynomial in the input size and in $\log (1 / \eps)$ for inputs with arbitrary linear constraint. Using the technique we obtain (re)approximation algorithms for natural (reoptimization) variants of classic subset selection problems, including real-time scheduling, the {\em maximum generalized assignment problem (GAP)} and maximum weight independent set.
The Maximum Cardinality Cut Problem is Polynomial in Proper Interval Graphs
Venue: arXiv cs.DM 2015
Year: 2015

It is known that the maximum cardinality cut problem is NP-hard even in chordal graphs. In this paper, we consider the time complexity of the problem in proper interval graphs, a subclass of chordal graphs, and propose a dynamic programming algorithm which runs in polynomial-time.
Termination of canonical context-sensitive rewriting and productivity of rewrite systems
Venue: arXiv cs.PL 2015
Year: 2015

Termination of programs, i.e., the absence of infinite computations, ensures the existence of normal forms for all initial expressions, thus providing an essential ingredient for the definition of a normalization semantics for functional programs. In lazy functional languages, though, infinite data structures are often delivered as the outcome of computations. For instance, the list of all prime numbers can be returned as a neverending stream of numerical expressions or data structures. If such streams are allowed, requiring termination is hopeless. In this setting, the notion of productivity can be used to provide an account of computations with infinite data structures, as it "captures the idea of computability, of progress of infinite-list programs" (B.A. Sijtsma, On the Productivity of Recursive List Definitions, ACM Transactions on Programming Languages and Systems 11(4):633-649, 1989). However, in the realm of Term Rewriting Systems, which can be seen as (first-order, untyped, unconditional) functional programs, termination of Context-Sensitive Rewriting (CSR) has been showed equivalent to productivity of rewrite systems through appropriate transformations. In this way, tools for proving termination of CSR can be used to prove productivity. In term rewriting, CSR is the restriction of rewriting that arises when reductions are allowed on selected arguments of function symbols only. In this paper we show that well-known results about the computational power of CSR are useful to better understand the existing connections between productivity of rewrite systems and termination of CSR, and also to obtain more powerful techniques to prove productivity of rewrite systems.
Heuristic algorithms for finding distribution reducts in probabilistic rough set model
Venue: arXiv cs.AI 2015
Year: 2015

Attribute reduction is one of the most important topics in rough set theory. Heuristic attribute reduction algorithms have been presented to solve the attribute reduction problem. It is generally known that fitness functions play a key role in developing heuristic attribute reduction algorithms. The monotonicity of fitness functions can guarantee the validity of heuristic attribute reduction algorithms. In probabilistic rough set model, distribution reducts can ensure the decision rules derived from the reducts are compatible with those derived from the original decision table. However, there are few studies on developing heuristic attribute reduction algorithms for finding distribution reducts. This is partly due to the fact that there are no monotonic fitness functions that are used to design heuristic attribute reduction algorithms in probabilistic rough set model. The main objective of this paper is to develop heuristic attribute reduction algorithms for finding distribution reducts in probabilistic rough set model. For one thing, two monotonic fitness functions are constructed, from which equivalence definitions of distribution reducts can be obtained. For another, two modified monotonic fitness functions are proposed to evaluate the significance of attributes more effectively. On this basis, two heuristic attribute reduction algorithms for finding distribution reducts are developed based on addition-deletion method and deletion method. In particular, the monotonicity of fitness functions guarantees the rationality of the proposed heuristic attribute reduction algorithms. Results of experimental analysis are included to quantify the effectiveness of the proposed fitness functions and distribution reducts.
A Rate Splitting Strategy for Massive MIMO with Imperfect CSIT
Venue: arXiv cs.IT 2015
Year: 2015

In a multiuser MIMO broadcast channel, the rate performance is affected by the multiuser interference when the Channel State Information at the Transmitter (CSIT) is imperfect. To tackle the detrimental effect of the multiuser interference, a Rate-Splitting (RS) approach has been proposed recently, which splits one selected user's message into a common and a private part, and superimposes the common message on top of the private messages. The common message is drawn from a public codebook and should be decoded by all users. In this paper, we generalize the idea of RS into the large-scale array regime with imperfect CSIT. By further exploiting the channel second-order statistics, we propose a novel and general framework Hierarchical-Rate-Splitting (HRS) that is particularly suited to massive MIMO systems. HRS simultaneously transmits private messages intended to each user and two kinds of common messages that can be decoded by all users and by a subset of users, respectively. We analyse the asymptotic sum rate of RS and HRS and optimize the precoders of the common messages. A closed-form power allocation is derived which provides insights into the effects of system parameters. Finally, simulation results validate the significant sum rate gain of RS and HRS over various baselines.
Mechanizing a Process Algebra for Network Protocols
Venue: arXiv cs.LO 2015
Year: 2015

This paper presents the mechanization of a process algebra for Mobile Ad hoc Networks and Wireless Mesh Networks, and the development of a compositional framework for proving invariant properties. Mechanizing the core process algebra in Isabelle/HOL is relatively standard, but its layered structure necessitates special treatment. The control states of reactive processes, such as nodes in a network, are modelled by terms of the process algebra. We propose a technique based on these terms to streamline proofs of inductive invariance. This is not sufficient, however, to state and prove invariants that relate states across multiple processes (entire networks). To this end, we propose a novel compositional technique for lifting global invariants stated at the level of individual nodes to networks of nodes.
Mid-level Representation for Visual Recognition
Venue: arXiv cs.CV 2015
Year: 2015

Visual Recognition is one of the fundamental challenges in AI, where the goal is to understand the semantics of visual data. Employing mid-level representation, in particular, shifted the paradigm in visual recognition. The mid-level image/video representation involves discovering and training a set of mid-level visual patterns (e.g., parts and attributes) and represent a given image/video utilizing them. The mid-level patterns can be extracted from images and videos using the motion and appearance information of visual phenomenas. This thesis targets employing mid-level representations for different high-level visual recognition tasks, namely (i)image understanding and (ii)video understanding. In the case of image understanding, we focus on object detection/recognition task. We investigate on discovering and learning a set of mid-level patches to be used for representing the images of an object category. We specifically employ the discriminative patches in a subcategory-aware webly-supervised fashion. We, additionally, study the outcomes provided by employing the subcategory-based models for undoing dataset bias.
On Balanced k-coverage in Visual Sensor Network
Venue: arXiv cs.NI 2015
Year: 2015

Given a set of directional visual sensors, the $k$-coverage problem determines the orientation of minimal directional sensors so that each target is covered at least $k$ times. As the problem is NP-complete, a number of heuristics have been devised to tackle the issue. However, the existing heuristics provide imbalance coverage of the targets--some targets are covered $k$ times while others are left totally uncovered or singly covered. The coverage imbalance is more serious in under-provisioned networks where there do not exist enough sensors to cover all the targets $k$ times. Therefore, we address the problem of covering each target at least $k$ times in a balanced way using minimum number of sensors. We study the existing Integer Linear Programming (ILP) formulation for single coverage and extend the idea for $k$-coverage. However, the extension does not balance the coverage of the targets. We further propose Integer Quadratic Programming (IQP) and Integer Non-Linear Programming (INLP) formulations that are capable of addressing the coverage balancing. As the proposed formulations are computationally expensive, we devise a faster Centralized Greedy $k$-Coverage Algorithm (CGkCA) to approximate the formulations. Finally, through rigorous simulation experiments we show the efficacy of the proposed formulations and the CGkCA.
NPEFix: Automatic Runtime Repair of Null Pointer Exceptions in Java
Venue: arXiv cs.SE 2015
Year: 2015

Null pointer exceptions, also known as null dereferences are the number one exceptions in the field. In this paper, we propose 9 alternative execution semantics when a null pointer exception is about to happen. We implement those alternative execution strategies using code transformation in a tool called NPEfix. We evaluate our prototype implementation on 11 field null dereference bugs and 519 seeded failures and show that NPEfix is able to repair at runtime 10/11 and 318/519 failures.
The lateral transhipment problem with a-priori routes, and a lot sizing application
Venue: arXiv cs.DS 2015
Year: 2015

We propose exact solution approaches for a lateral transhipment problem which, given a pre-specified sequence of customers, seeks an optimal inventory redistribution plan considering travel costs and profits dependent on inventory levels. Trip-duration and vehicle-capacity constraints are also imposed. The same problem arises in some lot sizing applications, in the presence of setup costs and equipment re-qualifications. We introduce a pure dynamic programming approach and a branch-and-bound framework that combines dynamic programming with Lagrangian relaxation. Computational experiments are conducted to determine the most suitable solution approach for different instances, depending on their size, vehicle capacities and duration constraints. The branch-and-bound approach, in particular, solves problems with up to 50 delivery locations in less than ten seconds on a modern computer.
A Quadratic Assignment Formulation of the Graph Edit Distance
Venue: arXiv cs.DS 2015
Year: 2015

Computing efficiently a robust measure of similarity or dissimilarity between graphs is a major challenge in Pattern Recognition. The Graph Edit Distance (GED) is a flexible measure of dissimilarity between graphs which arises in error-tolerant graph matching. It is defined from an optimal sequence of edit operations (edit path) transforming one graph into an other. Unfortunately, the exact computation of this measure is NP-hard. In the last decade, several approaches have been proposed to approximate the GED in polynomial time, mainly by solving linear programming problems. Among them, the bipartite GED has received much attention. It is deduced from a linear sum assignment of the nodes of the two graphs, which can be efficiently computed by Hungarian-type algorithms. However, edit operations on nodes and edges are not handled simultaneously, which limits the accuracy of the approximation. To overcome this limitation, we propose to extend the linear assignment model to a quadratic one, for directed or undirected graphs having labelized nodes and edges. This is realized through the definition of a family of edit paths induced by assignments between nodes. We formally show that the GED, restricted to the paths in this family, is equivalent to a quadratic assignment problem. Since this problem is NP-hard, we propose to compute an approximate solution by an adaptation of the Integer Projected Fixed Point method. Experiments show that the proposed approach is generally able to reach a more accurate approximation of the optimal GED than the bipartite GED, with a computational cost that is still affordable for graphs of non trivial sizes.
On the Automated Synthesis of Enterprise Integration Patterns to Adapt Choreography-based Distributed Systems
Venue: arXiv cs.SE 2015
Year: 2015

The Future Internet is becoming a reality, providing a large-scale computing environments where a virtually infinite number of available services can be composed so to fit users' needs. Modern service-oriented applications will be more and more often built by reusing and assembling distributed services. A key enabler for this vision is then the ability to automatically compose and dynamically coordinate software services. Service choreographies are an emergent Service Engineering (SE) approach to compose together and coordinate services in a distributed way. When mismatching third-party services are to be composed, obtaining the distributed coordination and adaptation logic required to suitably realize a choreography is a non-trivial and error prone task. Automatic support is then needed. In this direction, this paper leverages previous work on the automatic synthesis of choreography-based systems, and describes our preliminary steps towards exploiting Enterprise Integration Patterns to deal with a form of choreography adaptation.
Efficient and Secure Routing Protocol for Wireless Sensor Networks through Optimal Power Control and Optimal Handoff-Based Recovery Mechanism
Venue: arXiv cs.NI 2015
Year: 2015

Advances in wireless sensor network (WSN) technology have provided the availability of small and low-cost sensor with capability of sensing various types of physical and environmental conditions, data processing, and wireless communication. In WSN, the sensor nodes have a limited transmission range, and their processing and storage capabilities as well as their energy resources are also limited. Modified triple umpiring system (MTUS) has already proved its better performance in Wireless Sensor Networks. In this paper, we extended the MTUS by incorporating optimal signal to noise ratio (SNR)-based power control mechanism and optimal handoff-based self-recovery features to form an efficient and secure routing for WSN. Extensive investigation studies using Glomosim-2.03 Simulator show that efficient and secure routing protocol (ESRP) with optimal power control mechanism, and handoff-based self-recovery can significantly reduce the power usage.
Cloud Radio Access Network: Virtualizing Wireless Access for Dense Heterogeneous Systems
Venue: arXiv cs.IT 2015
Year: 2015

Cloud Radio Access Network (C-RAN) refers to the virtualization of base station functionalities by means of cloud computing. This results in a novel cellular architecture in which low-cost wireless access points, known as radio units (RUs) or remote radio heads (RRHs), are centrally managed by a reconfigurable centralized "cloud", or central, unit (CU). C-RAN allows operators to reduce the capital and operating expenses needed to deploy and maintain dense heterogeneous networks. This critical advantage, along with spectral efficiency, statistical multiplexing and load balancing gains, make C-RAN well positioned to be one of the key technologies in the development of 5G systems. In this paper, a succinct overview is presented regarding the state of the art on the research on C-RAN with emphasis on fronthaul compression, baseband processing, medium access control, resource allocation, system-level considerations and standardization efforts.