OpenRaiser/Intern-Atlas huggingface dataset:
Discrete-Valued Control by Sum-of-Absolute-Values Optimization
Venue: arXiv cs.SY 2015
Year: 2015

In this paper, we propose a new design method of discrete-valued control for continuous-time linear time-invariant systems based on sum-of-absolute-values (SOAV) optimization. We first formulate the discrete-valued control design as a finite-horizon SOAV optimal control, which is an extended version of L1 optimal control. We then give simple conditions that guarantee the existence, discreteness, and uniqueness of the SOAV optimal control. Also, we give the continuity property of the value function, by which we prove the stability of infinite-horizon model predictive SOAV control systems. We provide a fast algorithm for the SOAV optimization based on the alternating direction method of multipliers (ADMM), which has an important advantage in real-time control computation. A simulation result shows the effectiveness of the proposed method.
Cognitive Access-Transmission Policies under a Primary ARQ process via Chain Decoding
Venue: arXiv cs.IT 2015
Year: 2015

This paper introduces a novel technique that enables access by a cognitive secondary user (SU) to a spectrum occupied by an incumbent primary user (PU) that employs Type-I Hybrid ARQ. The technique allows the SU to perform selective retransmissions of SU data packets that have not been successfully decoded in the previous attempts. The temporal redundancy introduced by the PU ARQ protocol and by the selective retransmission process of the SU can be exploited by the SU receiver to perform interference cancellation (IC) over multiple transmission slots, thus creating a "clean" channel for the decoding of the concurrent SU or PU packets. The chain decoding technique is initiated by a successful decoding operation of a SU or PU packet and proceeds by an iterative application of IC in order to decode the buffered signals that represent packets that could not be decoded before. Based on this scheme, an optimal policy is designed that maximizes the SU throughput under a constraint on the average long-term PU performance. The optimality of the chain decoding protocol is proved, which determines which packet the SU should send at a given time. Moreover, a decoupling principle is proved, which establishes the optimality of decoupling the secondary access strategy from the chain decoding protocol. Specifically, first, the SU access policy, optimized via dynamic programming, specifies whether the SU should access the channel or not, based on a compact state representation of the protocol; and second, the chain decoding protocol embeds four basic rules that are used to determine which packet should be transmitted by the SU. Chain decoding provably yields the maximum improvement that can be achieved by any scheme under our assumptions, and thus it is the ultimate scheme, which completely closes the gap between previous schemes and optimality.
Approximation and Heuristic Algorithms for Probabilistic Physical Search on General Graphs
Venue: arXiv cs.MA 2015
Year: 2015

We consider an agent seeking to obtain an item, potentially available at different locations in a physical environment. The traveling costs between locations are known in advance, but there is only probabilistic knowledge regarding the possible prices of the item at any given location. Given such a setting, the problem is to find a plan that maximizes the probability of acquiring the good while minimizing both travel and purchase costs. Sample applications include agents in search-and-rescue or exploration missions, e.g., a rover on Mars seeking to mine a specific mineral. These probabilistic physical search problems have been previously studied, but we present the first approximation and heuristic algorithms for solving such problems on general graphs. We establish an interesting connection between these problems and classical graph-search problems, which led us to provide the approximation algorithms and hardness of approximation results for our settings. We further suggest several heuristics for practical use, and demonstrate their effectiveness with simulation on real graph structure and synthetic graphs.
Transcoder Migration For Real Time Video Streaming Systems
Venue: arXiv cs.NI 2015
Year: 2015

The increase in real time ultra-high definition video services presents a challenging issue to current network infrastructures, because of its high bandwidth usage, which saturate network links. The required bandwidth is related to strict QoS requirements for digital media. There are systems in place currently to help reduce these problems, such as transcoders and application layer multicasting. However, these approaches are limited because they are usually implemented as static resources. In contrast, by using the OpenFlow based system presented in this paper, it is possible to provide a more effective approach using dynamic resources - by both optimally placing transcoders in the network, as well as by migrating them to different locations while the streaming is taking place. This migration mechanism provides a near seamless switchover with minimal interruption to the clients.
Compressive phase retrieval of sparse bandlimited signals
Venue: arXiv cs.IT 2015
Year: 2015

This contribution proposes a two stage strategy to allow for phase retrieval in state of the art sub-Nyquist sampling schemes for sparse multiband signals. The proposed strategy is based on data acquisition via modulated wideband converters known from sub-Nyquist sampling. This paper describes how the modulators have to be modified such that signal recovery from sub-Nyquist amplitude samples becomes possible and a corresponding recovery algorithm is given which is computational efficient. In addition, the proposed strategy is fairly general, allowing for several constructions and recovery algorithms.
Fast Non-local Stereo Matching based on Hierarchical Disparity Prediction
Venue: arXiv cs.CV 2015
Year: 2015

Stereo matching is the key step in estimating depth from two or more images. Recently, some tree-based non-local stereo matching methods have been proposed, which achieved state-of-the-art performance. The algorithms employed some tree structures to aggregate cost and thus improved the performance and reduced the coputation load of the stereo matching. However, the computational complexity of these tree-based algorithms is still high because they search over the entire disparity range. In addition, the extreme greediness of the minimum spanning tree (MST) causes the poor performance in large areas with similar colors but varying disparities. In this paper, we propose an efficient stereo matching method using a hierarchical disparity prediction (HDP) framework to dramatically reduce the disparity search range so as to speed up the tree-based non-local stereo methods. Our disparity prediction scheme works on a graph pyramid derived from an image whose disparity to be estimated. We utilize the disparity of a upper graph to predict a small disparity range for the lower graph. Some independent disparity trees (DT) are generated to form a disparity prediction forest (HDPF) over which the cost aggregation is made. When combined with the state-of-the-art tree-based methods, our scheme not only dramatically speeds up the original methods but also improves their performance by alleviating the second drawback of the tree-based methods. This is partially because our DTs overcome the extreme greediness of the MST. Extensive experimental results on some benchmark datasets demonstrate the effectiveness and efficiency of our framework. For example, the segment-tree based stereo matching becomes about 25.57 times faster and 2.2% more accurate over the Middlebury 2006 full-size dataset.
Detecting global bridges in networks
Venue: arXiv cs.SI 2015
Year: 2015

The identification of nodes occupying important positions in a network structure is crucial for the understanding of the associated real-world system. Usually, betweenness centrality is used to evaluate a node capacity to connect different graph regions. However, we argue here that this measure is not adapted for that task, as it gives equal weight to "local" centers (i.e. nodes of high degree central to a single region) and to "global" bridges, which connect different communities. This distinction is important as the roles of such nodes are different in terms of the local and global organisation of the network structure. In this paper we propose a decomposition of betweenness centrality into two terms, one highlighting the local contributions and the other the global ones. We call the latter bridgeness centrality and show that it is capable to specifically spot out global bridges. In addition, we introduce an effective algorithmic implementation of this measure and demonstrate its capability to identify global bridges in air transportation and scientific collaboration networks.
A Simple Multipath OpenFlow Controller using topology-based algorithm for Multipath TCP
Venue: arXiv cs.NI 2015
Year: 2015

Multipath TCP, or MPTCP, is a widely-researched mechanism that allows a single application-level connection to be split to more than one TCP stream, and consequently more than one network interface, as opposed to the traditional TCP/IP model. Being a transport layer protocol, MPTCP can easily interact between the application using it and the network supporting it. However, MPTCP does not have control of its own route. Default IP routing behavior generally takes all traffic through the shortest or best-metric path. However, this behavior may actually cause paths to collide with each other, creating contention for bandwidth in a number of edges. This can result in a bottleneck which limits the throughput of the network. Therefore, a multipath routing mechanism is necessary to ensure smooth operation of MPTCP. We created smoc, a Simple Multipath OpenFlow Controller, that uses only topology information of the network to avoid collision where possible. Evaluation of smoc in a virtual local-area and a physical wide-area SDNs showed favorable results as smoc provided better performance than simple or spanning-tree routing mechanisms.
Recoverability of Group Sparse Signals from Corrupted Measurements via Robust Group Lasso
Venue: arXiv cs.IT 2015
Year: 2015

This paper considers the problem of recovering a group sparse signal matrix $\mathbf{Y} = [\mathbf{y}_1, \cdots, \mathbf{y}_L]$ from sparsely corrupted measurements $\mathbf{M} = [\mathbf{A}_{(1)}\mathbf{y}_{1}, \cdots, \mathbf{A}_{(L)}\mathbf{y}_{L}] + \mathbf{S}$, where $\mathbf{A}_{(i)}$'s are known sensing matrices and $\mathbf{S}$ is an unknown sparse error matrix. A robust group lasso (RGL) model is proposed to recover $\mathbf{Y}$ and $\mathbf{S}$ through simultaneously minimizing the $\ell_{2,1}$-norm of $\mathbf{Y}$ and the $\ell_1$-norm of $\mathbf{S}$ under the measurement constraints. We prove that $\mathbf{Y}$ and $\mathbf{S}$ can be exactly recovered from the RGL model with a high probability for a very general class of $\mathbf{A}_{(i)}$'s.
Optimal Auction Design with Quantized Bids
Venue: arXiv cs.GT 2015
Year: 2015

This letter considers the design of an auction mechanism to sell the object of a seller when the buyers quantize their private value estimates regarding the object prior to communicating them to the seller. The designed auction mechanism maximizes the utility of the seller (i.e., the auction is optimal), prevents buyers from communicating falsified quantized bids (i.e., the auction is incentive-compatible), and ensures that buyers will participate in the auction (i.e., the auction is individually-rational). The letter also investigates the design of the optimal quantization thresholds using which buyers quantize their private value estimates. Numerical results provide insights regarding the influence of the quantization thresholds on the auction mechanism.
Quantitative Information Flow for Scheduler-Dependent Systems
Venue: arXiv cs.CR 2015
Year: 2015

Quantitative information flow analyses measure how much information on secrets is leaked by publicly observable outputs. One area of interest is to quantify and estimate the information leakage of composed systems. Prior work has focused on running disjoint component systems in parallel and reasoning about the leakage compositionally, but has not explored how the component systems are run in parallel or how the leakage of composed systems can be minimised. In this paper we consider the manner in which parallel systems can be combined or scheduled. This considers the effects of scheduling channels where resources may be shared, or whether the outputs may be incrementally observed. We also generalise the attacker's capability, of observing outputs of the system, to consider attackers who may be imperfect in their observations, e.g. when outputs may be confused with one another, or when assessing the time taken for an output to appear. Our main contribution is to present how scheduling and observation effect information leakage properties. In particular, that scheduling can hide some leaked information from perfect observers, while some scheduling may reveal secret information that is hidden to imperfect observers. In addition we present an algorithm to construct a scheduler that minimises the min-entropy leakage and min-capacity in the presence of any observer.
A Novel Scattered Pilot Design for FBMC/OQAM Systems
Venue: arXiv cs.IT 2015
Year: 2015

Filter bank multi-carrier with offset quadrature amplitude modulation (FBMC/OQAM) has been heavily studied as an alternative waveform for 5G systems. Its advantages of higher spectrum efficiency, localized frequency response and insensitivity to synchronization errors may enable promising performance when orthogonal frequency division multiplexing (OFDM) fails. However, performing channel estimation under the intrinsic interference has been a fundamental obstacle towards adopting FBMC/OQMA in a practical system. Several schemes are available but the performance is far from satisfaction. In this paper, we will show the existing methods are trapped by the paradigm that a clean pilot is mandatory so as to explicitly carry a reference symbol to the receiver for the purpose of channel estimation. By breaking this paradigm, a novel dual dependent pilot scheme is proposed, which gives up the independent pilot and derives dual pilots from the imposed interference. By doing this, the interference between pilots can be fully utilized. Consequentially, the new scheme significantly outperforms existing solutions and the simulation results show FBMC/OQAM can achieve close-to-OFDM performance in a practical system even with the presence of strong intrinsic interference.
Semantics, Representations and Grammars for Deep Learning
Venue: arXiv cs.LG 2015
Year: 2015

Deep learning is currently the subject of intensive study. However, fundamental concepts such as representations are not formally defined -- researchers "know them when they see them" -- and there is no common language for describing and analyzing algorithms. This essay proposes an abstract framework that identifies the essential features of current practice and may provide a foundation for future developments. The backbone of almost all deep learning algorithms is backpropagation, which is simply a gradient computation distributed over a neural network. The main ingredients of the framework are thus, unsurprisingly: (i) game theory, to formalize distributed optimization; and (ii) communication protocols, to track the flow of zeroth and first-order information. The framework allows natural definitions of semantics (as the meaning encoded in functions), representations (as functions whose semantics is chosen to optimized a criterion) and grammars (as communication protocols equipped with first-order convergence guarantees). Much of the essay is spent discussing examples taken from the literature. The ultimate aim is to develop a graphical language for describing the structure of deep learning algorithms that backgrounds the details of the optimization procedure and foregrounds how the components interact. Inspiration is taken from probabilistic graphical models and factor graphs, which capture the essential structural features of multivariate distributions.
Improving the Performance of Trickle-Based Data Dissemination in Low-Power Networks
Venue: arXiv cs.NI 2015
Year: 2015

Trickle is a polite gossip algorithm for managing communication traffic. It is of particular interest in low-power wireless networks for reducing the amount of control traffic, as in routing protocols (RPL), or reducing network congestion, as in multicast protocols (MPL). Trickle is used at the network or application level, and relies on up-to-date information on the activity of neighbors. This makes it vulnerable to interference from the media access control layer, which we explore in this paper. We present several scenarios how the MAC layer in low-power radios violates Trickle timing. As a case study, we analyze the impact of CSMA/CA with ContikiMAC on Trickle's performance. Additionally, we propose a solution called Cleansing that resolves these issues.
An intelligent extension of Variable Neighbourhood Search for labelling graph problems
Venue: arXiv cs.AI 2015
Year: 2015

In this paper we describe an extension of the Variable Neighbourhood Search (VNS) which integrates the basic VNS with other complementary approaches from machine learning, statistics and experimental algorithmic, in order to produce high-quality performance and to completely automate the resulting optimization strategy. The resulting intelligent VNS has been successfully applied to a couple of optimization problems where the solution space consists of the subsets of a finite reference set. These problems are the labelled spanning tree and forest problems that are formulated on an undirected labelled graph; a graph where each edge has a label in a finite set of labels L. The problems consist on selecting the subset of labels such that the subgraph generated by these labels has an optimal spanning tree or forest, respectively. These problems have several applications in the real-world, where one aims to ensure connectivity by means of homogeneous connections.
Subverting Massive MIMO by Smart Jamming
Venue: arXiv cs.IT 2015
Year: 2015

We consider uplink transmission of a massive multi-user multiple-input multiple-output (MU-MIMO) system in the presence of a smart jammer. The jammer aims to degrade the sum spectral efficiency of the legitimate system by attacking both the training and data transmission phases. First, we derive a closed-form expression for the sum spectral efficiency by taking into account the presence of a smart jammer. Then, we determine how a jammer with a given energy budget should attack the training and data transmission phases to induce the maximum loss to the sum spectral efficiency. Numerical results illustrate the impact of optimal jamming specifically in the large limit of the number of base station (BS) antennas.
Computing Marginals Using MapReduce
Venue: arXiv cs.DB 2015
Year: 2015

We consider the problem of computing the data-cube marginals of a fixed order $k$ (i.e., all marginals that aggregate over $k$ dimensions), using a single round of MapReduce. The focus is on the relationship between the reducer size (number of inputs allowed at a single reducer) and the replication rate (number of reducers to which an input is sent). We show that the replication rate is minimized when the reducers receive all the inputs necessary to compute one marginal of higher order. That observation lets us view the problem as one of covering sets of $k$ dimensions with sets of a larger size $m$, a problem that has been studied under the name "covering numbers." We offer a number of constructions that, for different values of $k$ and $m$ meet or come close to yielding the minimum possible replication rate for a given reducer size.
Stats-Calculus Pose Descriptor Feeding A Discrete HMM Low-latency Detection and Recognition System For 3D Skeletal Actions
Venue: arXiv cs.CV 2015
Year: 2015

Recognition of human actions, under low observational latency, is a growing interest topic, nowadays. Many approaches have been represented based on a provided set of 3D Cartesian coordinates system originated at a certain specific point located on a root joint. In this paper, We will present a statistical detection and recognition system using Hidden Markov Model using 7 types of pose descriptors. * Cartesian Calculus Pose descriptor. * Angular Calculus Pose descriptor. * Mixed-mode Stats-Calculus Pose descriptor. * Centro-Stats-Calculus Pose descriptor. * Rela-Centro-Stats-Calculus Pose descriptor. * Rela-Centro-Stats-Calculus DCT Pose descriptor. * Rela-Centro-Stats-Calculus DCT-AMDF Pose descriptor. Stats-Calculus is a feature extracting technique, that is developed on Moving Pose descriptor , but using a combination of Statistics measures and Calculus measures.
Distributed Weighted Parameter Averaging for SVM Training on Big Data
Venue: arXiv cs.LG 2015
Year: 2015

Two popular approaches for distributed training of SVMs on big data are parameter averaging and ADMM. Parameter averaging is efficient but suffers from loss of accuracy with increase in number of partitions, while ADMM in the feature space is accurate but suffers from slow convergence. In this paper, we report a hybrid approach called weighted parameter averaging (WPA), which optimizes the regularized hinge loss with respect to weights on parameters. The problem is shown to be same as solving SVM in a projected space. We also demonstrate an $O(\frac{1}{N})$ stability bound on final hypothesis given by WPA, using novel proof techniques. Experimental results on a variety of toy and real world datasets show that our approach is significantly more accurate than parameter averaging for high number of partitions. It is also seen the proposed method enjoys much faster convergence compared to ADMM in features space.
Multi-objective Differential Evolution with Helper Functions for Constrained Optimization
Venue: arXiv cs.NE 2015
Year: 2015

Solving constrained optimization problems by multi-objective evolutionary algorithms has scored tremendous achievements in the last decade. Standard multi-objective schemes usually aim at minimizing the objective function and also the degree of constraint violation simultaneously. This paper proposes a new multi-objective method for solving constrained optimization problems. The new method keeps two standard objectives: the original objective function and the sum of degrees of constraint violation. But besides them, four more objectives are added. One is based on the feasible rule. The other three come from the penalty functions. This paper conducts an initial experimental study on thirteen benchmark functions. A simplified version of CMODE is applied to solving multi-objective optimization problems. Our initial experimental results confirm our expectation that adding more helper functions could be useful. The performance of SMODE with more helper functions (four or six) is better than that with only two helper functions.
Processing of acoustical signals via a wavelet-based analysis
Venue: arXiv cs.SD 2015
Year: 2015

In the present paper, details are given on the implementation of a wavelet-based analysis tailored to the processing of acoustical signals. The family of the suitable wavelets (`Reimann wavelets') are obtained in the time domain from a Fourier transform, extracted in Ref.~\cite{r1} after invoking theoretical principles and time-frequency localisation constraints. A scheme is set forth to determine the optimal values of the parameters of this type of wavelet on the basis of the goodness of the reproduction of a $30$-s audio file containing harmonic signals corresponding to six successive $A$ notes of the chromatic musical scale, from $A_2$ to $A_7$. The quality of the reproduction over about six and a half octaves is investigated. Finally, details are given on the incorporation of the re-assignment method in the analysis framework, as the means a) to determine the important contributions of the wavelet transforms and b) to suppress noise present in the signal.