OpenRaiser/Intern-Atlas huggingface dataset:
D2D Enhanced Heterogeneous Cellular Networks with Dynamic TDD
Venue: arXiv cs.NI 2015
Year: 2015

Over the last decade, the growing amount of UL and DL mobile data traffic has been characterized by substantial asymmetry and time variations. Dynamic time-division duplex (TDD) has the capability to accommodate to the traffic asymmetry by adapting the UL/DL configuration to the current traffic demands. In this work, we study a two-tier heterogeneous cellular network (HCN) where the macro tier and small cell tier operate according to a dynamic TDD scheme on orthogonal frequency bands. To offload the network infrastructure, mobile users in proximity can engage in D2D communications, whose activity is determined by a carrier sensing multiple access (CSMA) scheme to protect the ongoing infrastructure-based and D2D transmissions. We present an analytical framework to evaluate the network performance in terms of load-aware coverage probability and network throughput. The proposed framework allows to quantify the effect on the coverage probability of the most important TDD system parameters, such as the UL/DL configuration, the base station density, and the bias factor. In addition, we evaluate how the bandwidth partition and the D2D network access scheme affect the total network throughput. Through the study of the tradeoff between coverage probability and D2D user activity, we provide guidelines for the optimal design of D2D network access.
Deterministic polynomial factoring under the assumption of the Extended Riemann Hypothesis (ERH)
Venue: arXiv cs.DM 2015
Year: 2015

We consider the problem of deterministically factoring a univariate polynomial over a finite field under the assumption of the Extended Riemann Hypothesis (ERH). This work builds upon the line of approach first explored by Gao in $2001$. The general approach has been to implicitly construct a graph with the roots as vertices and the edges formed by some polynomial time computable relation. The algorithm then fails to factor a polynomial if this associated graph turns out to be \emph{regular}. In the first part of our work we strengthen the edge relation so that the resulting set of graphs we obtain are subgraphs of Gao's graphs, all of which must be \emph{regular}. In the second part of our work we strengthen the regularity condition of these graphs. This is accomplished by finding a parallel between their algorithms and the $1$-dimensional Weisfeiler-Leman algorithm for solving the Graph Isomorphism problem. We observe that the general principle behind their algorithms is to separate the roots by computing the $1$-dimensional Weisfeiler-Leman approximation to the orbits of this graph. This leads us to the natural question of whether this approximation may be improved. We then go on to show how to implicitly compute the $2$-dimensional Weisfeiler-Leman approximation of the orbits of these graphs. The polynomials that our algorithm fails to factor form graphs that are \emph{strongly regular} and their set of adjacency matrices forms a combinatorial structure called an \emph{Association scheme}.
Dynamic Routing for Flying Ad Hoc Networks
Venue: arXiv cs.NI 2015
Year: 2015

This paper reports experimental results on self-organizing wireless networks carried by small flying robots. Flying ad hoc networks (FANETs) composed of small unmanned aerial vehicles (UAVs) are flexible, inexpensive and fast to deploy. This makes them a very attractive technology for many civilian and military applications. Due to the high mobility of the nodes, maintaining a communication link between the UAVs is a challenging task. The topology of these networks is more dynamic than that of typical mobile ad hoc networks (MANETs) and of typical vehicle ad hoc networks (VANETs). As a consequence, the existing routing protocols designed for MANETs partly fail in tracking network topology changes. In this work, we compare two different routing algorithms for ad hoc networks: optimized link-state routing (OLSR), and predictive-OLSR (P-OLSR). The latter is an OLSR extension that we designed for FANETs; it takes advantage of the GPS information available on board. To the best of our knowledge, P-OLSR is currently the only FANET-specific routing technique that has an available Linux implementation. We present results obtained by both Media Access Control (MAC) layer emulations and real-world experiments. In the experiments, we used a testbed composed of two autonomous fixed-wing UAVs and a node on the ground. Our experiments evaluate the link performance and the communication range, as well as the routing performance. Our emulation and experimental results show that P-OLSR significantly outperforms OLSR in routing in the presence of frequent network topology changes.
Multi-stage Multi-task feature learning via adaptive threshold
Venue: arXiv cs.LG 2015
Year: 2015

Multi-task feature learning aims to identity the shared features among tasks to improve generalization. It has been shown that by minimizing non-convex learning models, a better solution than the convex alternatives can be obtained. Therefore, a non-convex model based on the capped-$\ell_{1},\ell_{1}$ regularization was proposed in \cite{Gong2013}, and a corresponding efficient multi-stage multi-task feature learning algorithm (MSMTFL) was presented. However, this algorithm harnesses a prescribed fixed threshold in the definition of the capped-$\ell_{1},\ell_{1}$ regularization and the lack of adaptivity might result in suboptimal performance. In this paper we propose to employ an adaptive threshold in the capped-$\ell_{1},\ell_{1}$ regularized formulation, where the corresponding variant of MSMTFL will incorporate an additional component to adaptively determine the threshold value. This variant is expected to achieve a better feature selection performance over the original MSMTFL algorithm. In particular, the embedded adaptive threshold component comes from our previously proposed iterative support detection (ISD) method \cite{Wang2010}. Empirical studies on both synthetic and real-world data sets demonstrate the effectiveness of this new variant over the original MSMTFL.
Technical Report: Performance of the Expected Force on AS-level Inernet topologies
Venue: arXiv cs.NI 2015
Year: 2015

Many concepts in network science are based on idealized network models. Infrastructure networks, however, are strongly constrained by specific engineering and economic constraints which do not appear in such models. One result is that concepts which are assumed to be fundamental by theoriticians severely underperform in real world situations. This motivated us to test if the Expected Force (ExF) metric, which was developed in the context of more theoretical network models, would continue to be predictive of epidemic outcomes on the highly structured topology of the internet at the autonomous systems (AS) level router connectivity. Results suggest that the ExF performs extremely well on these topologies, perhaps reflecting their design constraint of easing the diffusion of information.
Homotopy based algorithms for $\ell_0$-regularized least-squares
Venue: arXiv cs.NA 2015
Year: 2015

Sparse signal restoration is usually formulated as the minimization of a quadratic cost function $\|y-Ax\|_2^2$, where A is a dictionary and x is an unknown sparse vector. It is well-known that imposing an $\ell_0$ constraint leads to an NP-hard minimization problem. The convex relaxation approach has received considerable attention, where the $\ell_0$-norm is replaced by the $\ell_1$-norm. Among the many efficient $\ell_1$ solvers, the homotopy algorithm minimizes $\|y-Ax\|_2^2+λ\|x\|_1$ with respect to x for a continuum of $λ$'s. It is inspired by the piecewise regularity of the $\ell_1$-regularization path, also referred to as the homotopy path. In this paper, we address the minimization problem $\|y-Ax\|_2^2+λ\|x\|_0$ for a continuum of $λ$'s and propose two heuristic search algorithms for $\ell_0$-homotopy. Continuation Single Best Replacement is a forward-backward greedy strategy extending the Single Best Replacement algorithm, previously proposed for $\ell_0$-minimization at a given $λ$. The adaptive search of the $λ$-values is inspired by $\ell_1$-homotopy. $\ell_0$ Regularization Path Descent is a more complex algorithm exploiting the structural properties of the $\ell_0$-regularization path, which is piecewise constant with respect to $λ$. Both algorithms are empirically evaluated for difficult inverse problems involving ill-conditioned dictionaries. Finally, we show that they can be easily coupled with usual methods of model order selection.
Eigenvalue Dynamics of a Central Wishart Matrix with Application to MIMO Systems
Venue: arXiv cs.IT 2015
Year: 2015

We investigate the dynamic behavior of the stationary random process defined by a central complex Wishart (CW) matrix ${\bf{W}}(t)$ as it varies along a certain dimension $t$. We characterize the second-order joint cdf of the largest eigenvalue, and the second-order joint cdf of the smallest eigenvalue of this matrix. We show that both cdfs can be expressed in exact closed-form in terms of a finite number of well-known special functions in the context of communication theory. As a direct application, we investigate the dynamic behavior of the parallel channels associated with multiple-input multiple-output (MIMO) systems in the presence of Rayleigh fading. Studying the complex random matrix that defines the MIMO channel, we characterize the second-order joint cdf of the signal-to-noise ratio (SNR) for the best and worst channels. We use these results to study the rate of change of MIMO parallel channels, using different performance metrics. For a given value of the MIMO channel correlation coefficient, we observe how the SNR associated with the best parallel channel changes slower than the SNR of the worst channel. This different dynamic behavior is much more appreciable when the number of transmit ($N_T$) and receive ($N_R$) antennas is similar. However, as $N_T$ is increased while keeping $N_R$ fixed, we see how the best and worst channels tend to have a similar rate of change.
Early Recognition of Human Activities from First-Person Videos Using Onset Representations
Venue: arXiv cs.CV 2015
Year: 2015

In this paper, we propose a methodology for early recognition of human activities from videos taken with a first-person viewpoint. Early recognition, which is also known as activity prediction, is an ability to infer an ongoing activity at its early stage. We present an algorithm to perform recognition of activities targeted at the camera from streaming videos, making the system to predict intended activities of the interacting person and avoid harmful events before they actually happen. We introduce the novel concept of 'onset' that efficiently summarizes pre-activity observations, and design an approach to consider event history in addition to ongoing video observation for early first-person recognition of activities. We propose to represent onset using cascade histograms of time series gradients, and we describe a novel algorithmic setup to take advantage of onset for early recognition of activities. The experimental results clearly illustrate that the proposed concept of onset enables better/earlier recognition of human activities from first-person videos.
Learning computationally efficient dictionaries and their implementation as fast transforms
Venue: arXiv cs.LG 2015
Year: 2015

Dictionary learning is a branch of signal processing and machine learning that aims at finding a frame (called dictionary) in which some training data admits a sparse representation. The sparser the representation, the better the dictionary. The resulting dictionary is in general a dense matrix, and its manipulation can be computationally costly both at the learning stage and later in the usage of this dictionary, for tasks such as sparse coding. Dictionary learning is thus limited to relatively small-scale problems. In this paper, inspired by usual fast transforms, we consider a general dictionary structure that allows cheaper manipulation, and propose an algorithm to learn such dictionaries --and their fast implementation-- over training data. The approach is demonstrated experimentally with the factorization of the Hadamard matrix and with synthetic dictionary learning experiments.
Optimum Power Control at Finite Blocklength
Venue: arXiv cs.IT 2015
Year: 2015

This paper investigates the maximal channel coding rate achievable at a given blocklength $n$ and error probability $ε$, when the codewords are subject to a long-term (i.e., averaged-over-all-codeword) power constraint. The second-order term in the large-$n$ expansion of the maximal channel coding rate is characterized both for additive white Gaussian noise (AWGN) channels and for quasi-static fading channels with perfect channel state information available at both the transmitter and the receiver. It is shown that in both cases the second-order term is proportional to $\sqrt{n^{-1}\ln n}$. For the quasi-static fading case, this second-order term is achieved by truncated channel inversion, namely, by concatenating a dispersion-optimal code for an AWGN channel subject to a short-term power constraint, with a power controller that inverts the channel whenever the fading gain is above a certain threshold. Easy-to-evaluate approximations of the maximal channel coding rate are developed for both the AWGN and the quasi-static fading case.
Network-Level Performance Evaluation of a Two-Relay Cooperative Random Access Wireless System
Venue: arXiv cs.NI 2015
Year: 2015

In wireless networks relay nodes can be used to assist the users' transmissions to reach their destination. Work on relay cooperation, from a physical layer perspective, has up to now yielded well-known results. This paper takes a different stance focusing on network-level cooperation. Extending previous results for a single relay, we investigate here the benefits from the deployment of a second one. We assume that the two relays do not generate packets of their own and the system employs random access to the medium; we further consider slotted time and that the users have saturated queues. We obtain analytical expressions for the arrival and service rates of the queues of the two relays and the stability conditions. We investigate a model of the system, in which the users are divided into clusters, each being served by one relay, and show its advantages in terms of aggregate and throughput per user. We quantify the above, analytically for the case of the collision channel and through simulations for the case of Multi-Packet Reception (MPR), and we provide insight on when the deployment of a second relay in the system can yield significant advantages.
Constrained Expressions and their Derivatives
Venue: arXiv cs.FL 2015
Year: 2015

This paper proposes an extension to classical regular expressions by the addition of two operators allowing the inclusion of boolean formulae from the zeroth order logic. These expressions are called constrained expressions. The associated language is defined thanks to the notion of interpretation and of realization. We show that the language associated when both interpretation and realization are fixed is stricly regular and can be not regular otherwise. Furthermore, we use an extension of Antimirov partial derivatives in order to solve the membership test in the general case. Finally, we show that once the interpretation is fixed, the membership test of a word in the language denoted by a constrained expression can be undecidable whereas it is always decidable when the interpretation is not fixed.
Dynamic Model of a Pumping Kite Power System
Venue: arXiv cs.SY 2015
Year: 2015

Converting the traction power of kites into electricity can be a low cost solution for wind energy. Reliable control of both trajectory and tether reeling is crucial. The present study proposes a modelling framework describing the dynamic behaviour of the interconnected system components, suitable for design and optimization of the control systems. The wing, bridle, airborne control unit and tether are represented as a particle system using spring-damper elements to describe their mechanical properties. Two kite models are proposed: a point mass model and a four point model. Reeling of the tether is modelled by varying the lengths of constituent tether elements. Dynamic behaviour of the ground station is included. The framework is validated by combining it with the automatic control system used for the operation of a kite power system demonstrator. The simulation results show that the point mass model can be adjusted to match the measured behaviour during a pumping cycle. The four point model can better predict the influence of gravity and inertia on the steering response and remains stable also at low tether forces. Compared to simple one point models, the proposed framework is more accurate and robust while allowing real-time simulations of the complete system.
Bounding Clique-Width via Perfect Graphs
Venue: arXiv cs.DM 2015
Year: 2015

Given two graphs $H_1$ and $H_2$, a graph $G$ is $(H_1,H_2)$-free if it contains no subgraph isomorphic to $H_1$ or $H_2$. We continue a recent study into the clique-width of $(H_1,H_2)$-free graphs and present three new classes of $(H_1,H_2)$-free graphs of bounded clique-width and one of unbounded clique-width. The four new graph classes have in common that one of their two forbidden induced subgraphs is the diamond (the graph obtained from a clique on four vertices by deleting one edge). To prove boundedness of clique-width for the first three cases we develop a technique based on bounding clique covering number in combination with reduction to subclasses of perfect graphs. We extend our proof of unboundedness for the fourth case to show that Graph Isomorphism is Graph Isomorphism-complete on the same graph class. We also show the implications of our results for the computational complexity of the Colouring problem restricted to $(H_1,H_2)$-free graphs.
Robust Layered Transmission in Secure MISO Multiuser Unicast Cognitive Radio Systems
Venue: arXiv cs.IT 2015
Year: 2015

This paper studies robust resource allocation algorithm design for a multiuser multiple-input single-output (MISO) cognitive radio (CR) downlink communication network. We focus on a secondary system which provides unicast secure wireless layered video information to multiple single-antenna secondary receivers. The resource allocation algorithm design is formulated as a non-convex optimization problem for minimization of the total transmit power at the secondary transmitter. The proposed framework takes into account a quality of service (QoS) requirement regarding video communication secrecy in the secondary system, the imperfection of the channel state information (CSI) of potential eavesdroppers (primary receivers) at the secondary transmitter, and a limit for the maximum tolerable received interference power at the primary receivers. Thereby, the proposed problem formulation exploits the self-protecting architecture of layered transmission and artificial noise generation to ensure communication secrecy. Semidefinite programming (SDP) relaxation is employed to derive a resource allocation algorithm which finds the global optimal solution to the formulated problem. Simulation results demonstrate significant transmit power savings and robustness against CSI imperfection for the proposed resource allocation algorithm for layered transmission compared to baseline schemes with traditional single-layer transmission.
Parameterized Synthesis Case Study: AMBA AHB (extended version)
Venue: arXiv cs.SE 2015
Year: 2015

We revisit the AMBA AHB case study that has been used as a benchmark for several reactive syn- thesis tools. Synthesizing AMBA AHB implementations that can serve a large number of masters is still a difficult problem. We demonstrate how to use parameterized synthesis in token rings to obtain an implementation for a component that serves a single master, and can be arranged in a ring of arbitrarily many components. We describe new tricks -- property decompositional synthesis, and direct encoding of simple GR(1) -- that together with previously described optimizations allowed us to synthesize the model with 14 states in 30 minutes.
Gossip-based Signaling Dissemination Extension for Next Steps In Signaling
Venue: arXiv cs.NI 2015
Year: 2015

In this paper, we propose a new gossip-based signaling dissemination method for the Next Steps in Signaling protocol family. In more detail, we propose to extend the General Internet Signaling Transport (GIST) protocol, so as to leverage these new dissemination capabilities from all NSIS Signaling Layer Protocol applications using its transport capabilities. The new GIST extension consists of two main procedures: a bootstrap procedure, during which new GIST-enabled nodes discover each other, and a service dissemination procedure, which is used to effectively disseminate signaling messages within an Autonomous System. To this aim, we defined three dissemination models, bubble, balloon, and hose, so as to fulfill requirements of different network and/or service management scenarios. An experimental campaign carried out on the GENI testbed shows the effectiveness of the proposed solution.
Pixel-wise Orthogonal Decomposition for Color Illumination Invariant and Shadow-free Image
Venue: arXiv cs.CV 2015
Year: 2015

In this paper, we propose a novel, effective and fast method to obtain a color illumination invariant and shadow-free image from a single outdoor image. Different from state-of-the-art methods for shadow-free image that either need shadow detection or statistical learning, we set up a linear equation set for each pixel value vector based on physically-based shadow invariants, deduce a pixel-wise orthogonal decomposition for its solutions, and then get an illumination invariant vector for each pixel value vector on an image. The illumination invariant vector is the unique particular solution of the linear equation set, which is orthogonal to its free solutions. With this illumination invariant vector and Lab color space, we propose an algorithm to generate a shadow-free image which well preserves the texture and color information of the original image. A series of experiments on a diverse set of outdoor images and the comparisons with the state-of-the-art methods validate our method.
Branching Bisimilarity of Normed BPA Processes is in NEXPTIME
Venue: arXiv cs.LO 2015
Year: 2015

Branching bisimilarity on normed BPA processes was recently shown to be decidable by Yuxi Fu (ICALP 2013) but his proof has not provided any upper complexity bound. We present a simpler approach based on relative prime decompositions that leads to a nondeterministic exponential-time algorithm; this is close to the known exponential-time lower bound.
Info-Greedy sequential adaptive compressed sensing
Venue: arXiv cs.IT 2015
Year: 2015

We present an information-theoretic framework for sequential adaptive compressed sensing, Info-Greedy Sensing, where measurements are chosen to maximize the extracted information conditioned on the previous measurements. We show that the widely used bisection approach is Info-Greedy for a family of $k$-sparse signals by connecting compressed sensing and blackbox complexity of sequential query algorithms, and present Info-Greedy algorithms for Gaussian and Gaussian Mixture Model (GMM) signals, as well as ways to design sparse Info-Greedy measurements. Numerical examples demonstrate the good performance of the proposed algorithms using simulated and real data: Info-Greedy Sensing shows significant improvement over random projection for signals with sparse and low-rank covariance matrices, and adaptivity brings robustness when there is a mismatch between the assumed and the true distributions.