OpenRaiser/Intern-Atlas huggingface dataset:
Learning parametric dictionaries for graph signals
Venue: arXiv cs.LG 2014
Year: 2014

In sparse signal representation, the choice of a dictionary often involves a tradeoff between two desirable properties -- the ability to adapt to specific signal data and a fast implementation of the dictionary. To sparsely represent signals residing on weighted graphs, an additional design challenge is to incorporate the intrinsic geometric structure of the irregular data domain into the atoms of the dictionary. In this work, we propose a parametric dictionary learning algorithm to design data-adapted, structured dictionaries that sparsely represent graph signals. In particular, we model graph signals as combinations of overlapping local patterns. We impose the constraint that each dictionary is a concatenation of subdictionaries, with each subdictionary being a polynomial of the graph Laplacian matrix, representing a single pattern translated to different areas of the graph. The learning algorithm adapts the patterns to a training set of graph signals. Experimental results on both synthetic and real datasets demonstrate that the dictionaries learned by the proposed algorithm are competitive with and often better than unstructured dictionaries learned by state-of-the-art numerical learning algorithms in terms of sparse approximation of graph signals. In contrast to the unstructured dictionaries, however, the dictionaries learned by the proposed algorithm feature localized atoms and can be implemented in a computationally efficient manner in signal processing tasks such as compression, denoising, and classification.
Optimum Trade-offs Between the Error Exponent and the Excess-Rate Exponent of Variable-Rate Slepian-Wolf Coding
Venue: arXiv cs.IT 2014
Year: 2014

We analyze the optimal trade-off between the error exponent and the excess-rate exponent for variable-rate Slepian-Wolf codes. In particular, we first derive upper (converse) bounds on the optimal error and excess-rate exponents, and then lower (achievable) bounds, via a simple class of variable-rate codes which assign the same rate to all source blocks of the same type class. Then, using the exponent bounds, we derive bounds on the optimal rate functions, namely, the minimal rate assigned to each type class, needed in order to achieve a given target error exponent. The resulting excess-rate exponent is then evaluated. Iterative algorithms are provided for the computation of both bounds on the optimal rate functions and their excess-rate exponents. The resulting Slepian-Wolf codes bridge between the two extremes of fixed-rate coding, which has minimal error exponent and maximal excess-rate exponent, and average-rate coding, which has maximal error exponent and minimal excess-rate exponent.
Automated Reasoning over Deontic Action Logics with Finite Vocabularies
Venue: arXiv cs.LO 2014
Year: 2014

In this paper we investigate further the tableaux system for a deontic action logic we presented in previous work. This tableaux system uses atoms (of a given boolean algebra of action terms) as labels of formulae, this allows us to embrace parallel execution of actions and action complement, two action operators that may present difficulties in their treatment. One of the restrictions of this logic is that it uses vocabularies with a finite number of actions. In this article we prove that this restriction does not affect the coherence of the deduction system; in other words, we prove that the system is complete with respect to language extension. We also study the computational complexity of this extended deductive framework and we prove that the complexity of this system is in PSPACE, which is an improvement with respect to related systems.
The DynAlloy Visualizer
Venue: arXiv cs.SE 2014
Year: 2014

We present an extension to the DynAlloy tool to navigate DynAlloy counterexamples: the DynAlloy Visualizer. The user interface mimics the functionality of a programming language debugger. Without this tool, a DynAlloy user is forced to deal with the internals of the Alloy intermediate representation in order to debug a flaw in her model.
When Does Relay Transmission Give a More Secure Connection in Wireless Ad Hoc Networks?
Venue: arXiv cs.IT 2014
Year: 2014

Relay transmission can enhance coverage and throughput, while it can be vulnerable to eavesdropping attacks due to the additional transmission of the source message at the relay. Thus, whether or not one should use relay transmission for secure communication is an interesting and important problem. In this paper, we consider the transmission of a confidential message from a source to a destination in a decentralized wireless network in the presence of randomly distributed eavesdroppers. The source-destination pair can be potentially assisted by randomly distributed relays. For an arbitrary relay, we derive exact expressions of secure connection probability for both colluding and non-colluding eavesdroppers. We further obtain lower bound expressions on the secure connection probability, which are accurate when the eavesdropper density is small. By utilizing these lower bound expressions, we propose a relay selection strategy to improve the secure connection probability. By analytically comparing the secure connection probability for direct transmission and relay transmission, we address the important problem of whether or not to relay and discuss the condition for relay transmission in terms of the relay density and source-destination distance. These analytical results are accurate in the small eavesdropper density regime.
Outage Probability of Dual-Hop Multiple Antenna AF Systems with Linear Processing in the Presence of Co-Channel Interference
Venue: arXiv cs.IT 2014
Year: 2014

This paper considers a dual-hop amplify-and-forward (AF) relaying system where the relay is equipped with multiple antennas, while the source and the destination are equipped with a single antenna. Assuming that the relay is subjected to co-channel interference (CCI) and additive white Gaussian noise (AWGN) while the destination is corrupted by AWGN only, we propose three heuristic relay precoding schemes to combat the CCI, namely, 1) Maximum ratio combining/maximal ratio transmission (MRC/MRT), 2) Zero-forcing/MRT (ZF/MRT), 3) Minimum mean-square error/MRT (MMSE/MRT). We derive new exact outage expressions as well as simple high signal-to-noise ratio (SNR) outage approximations for all three schemes. Our findings suggest that both the MRC/MRT and the MMSE/MRT schemes achieve a full diversity of N, while the ZF/MRT scheme achieves a diversity order of N-M, where N is the number of relay antennas and M is the number of interferers. In addition, we show that the MMSE/MRT scheme always achieves the best outage performance, and the ZF/MRT scheme outperforms the MRC/MRT scheme in the low SNR regime, while becomes inferior to the MRC/MRT scheme in the high SNR regime. Finally, in the large N regime, we show that both the ZF/MRT and MMSE/MRT schemes are capable of completely eliminating the CCI, while perfect interference cancelation is not possible with the MRC/MRT scheme.
Terminal semantics for codata types in intensional Martin-Löf type theory
Venue: arXiv cs.LO 2014
Year: 2014

In this work, we study the notions of relative comonad and comodule over a relative comonad, and use these notions to give a terminal coalgebra semantics for the coinductive type families of streams and of infinite triangular matrices, respectively, in intensional Martin-Löf type theory. Our results are mechanized in the proof assistant Coq.
On the Communication Complexity of Secret Key Generation in the Multiterminal Source Model
Venue: arXiv cs.IT 2014
Year: 2014

Communication complexity refers to the minimum rate of public communication required for generating a maximal-rate secret key (SK) in the multiterminal source model of Csiszar and Narayan. Tyagi recently characterized this communication complexity for a two-terminal system. We extend the ideas in Tyagi's work to derive a lower bound on communication complexity in the general multiterminal setting. In the important special case of the complete graph pairwise independent network (PIN) model, our bound allows us to determine the exact linear communication complexity, i.e., the communication complexity when the communication and SK are restricted to be linear functions of the randomness available at the terminals.
Using Delta-Sigma Modulators in Visible Light OFDM Systems
Venue: arXiv cs.IT 2014
Year: 2014

Visible light communications (VLC) are motivated by the radio-frequency (RF) spectrum crunch and fast-growing solid-state lighting technology. VLC relies on white light emitting diodes (LEDs) to provide communication and illumination simultaneously. Simple two-level on-off keying (OOK) and pulse-position modulation (PPM) are supported in IEEE standard due to their compatibility with existing constant current LED drivers, but their low spectral efficiency have limited the achievable data rates of VLC. Orthogonal frequency division multiplexing (OFDM) has been applied to VLC due to its high spectral efficiency and ability to combat inter-symbol-interference (ISI). However, VLC-OFDM inherits the disadvantage of high peak-to-average power ratio (PAPR) from RF-OFDM. Besides, the continuous magnitude of OFDM signals requires complicated mixed-signal digital-to-analog converter (DAC) and modification of LED drivers. We propose the use of delta-sigma modulators in visible light OFDM systems to convert continuous magnitude OFDM symbols into LED driver signals. The proposed system has the communication theory advantages of OFDM along with the practical analog and optical advantages of simple two level driver signals. Simulation results are provided to illustrate the proposed system.
Selfishness as a Virtue in Mobile Ad Hoc Networks
Venue: arXiv cs.NI 2014
Year: 2014

Using Mobile Ad Hoc Networks as a way to break the dependency of mobile communications on permanent infrastructure has been an active area of research for several years, but only more recently has consideration been given to the economics of a distributed mobile service. In particular, the topic of handling nodes that act selfishly or maliciously has not yet been explored in detail. In this paper, we discuss the SAVMAN strategy for mobile offloading under the rules of the 2013 MANIAC Challenge.
Mobile Offloading in Wireless Ad Hoc Networks
Venue: arXiv cs.NI 2014
Year: 2014

This paper describes a strategy that was designed, implemented, and presented at the {\it Mobile Ad Hoc Networking Interoperability and Cooperation (MANIAC) Challenge 2013}. The theme of the MANIAC Challenge 2013 was ``Mobile Data Offloading,'' and consisted on developing and comparatively evaluating strategies to offload infrastructure access points via customer ad hoc forwarding using handheld devices (e.g., tablets and smartphones). According to the challenge rules, a hop-by-hop bidding contest (or ``auction'') should decide the path of each data packet towards its destination. Consequently, each team should rely on other teams' willingness to forward packets for them in order to get their traffic across the network. In this application scenario, the incentive for customers to join the ad hoc network is discounted monthly fees, while operators should benefit from decreased infrastructure costs. Following the rules of MANIAC Challenge 2013, this paper proposes a strategy that is based on the concept of how ``tight'' a node is to successfully deliver a packet to its destination within a given deadline. This ``tightness'' idea relies on a shortest-path analysis of the underlying network graph, and it is used to define three sub-strategies that specify a) how to participate in an auction; b) how to announce an auction; and c) how to decide who wins the announced auction. The proposed strategy seeks to minimize network resource utilization and to promote cooperative behavior among participant nodes.
A Recursive Algorithmic Approach to the Finding of Permutations for the Combination of Any Two Sets
Venue: arXiv cs.DS 2014
Year: 2014

In this paper I present a conjecture for a recursive algorithm that finds each permutation of combining two sets of objects (AKA the Shuffle Product). This algorithm provides an efficient way to navigate this problem, as each atomic operation yields a permutation of the union. The permutations of the union of the two sets are represented as binary integers which are then manipulated mathematically to find the next permutation. The routes taken to find each of the permutations then form a series of associations or adjacencies which can be represented in a tree graph which appears to possess some properties of a fractal. This algorithm was discovered while attempting to identify every possible end-state of a Tic-Tac-Toe (Naughts and Crosses) board. It was found to be a viable and efficient solution to the problem, and now---in its more generalized state---it is my belief that it may find applications among a wide range of theoretical and applied sciences. I hypothesize that, due to the fractal-like nature of the tree it traverses, this algorithm sheds light on a more generic principle of combinatorics and as such could be further generalized to perhaps be applied to the union of any number of sets.
Optimal Demand Response Using Device Based Reinforcement Learning
Venue: arXiv cs.LG 2014
Year: 2014

Demand response (DR) for residential and small commercial buildings is estimated to account for as much as 65% of the total energy savings potential of DR, and previous work shows that a fully automated Energy Management System (EMS) is a necessary prerequisite to DR in these areas. In this paper, we propose a novel EMS formulation for DR problems in these sectors. Specifically, we formulate a fully automated EMS's rescheduling problem as a reinforcement learning (RL) problem, and argue that this RL problem can be approximately solved by decomposing it over device clusters. Compared with existing formulations, our new formulation (1) does not require explicitly modeling the user's dissatisfaction on job rescheduling, (2) enables the EMS to self-initiate jobs, (3) allows the user to initiate more flexible requests and (4) has a computational complexity linear in the number of devices. We also demonstrate the simulation results of applying Q-learning, one of the most popular and classical RL algorithms, to a representative example.
Beyond One-Step-Ahead Forecasting: Evaluation of Alternative Multi-Step-Ahead Forecasting Models for Crude Oil Prices
Venue: arXiv cs.LG 2014
Year: 2014

An accurate prediction of crude oil prices over long future horizons is challenging and of great interest to governments, enterprises, and investors. This paper proposes a revised hybrid model built upon empirical mode decomposition (EMD) based on the feed-forward neural network (FNN) modeling framework incorporating the slope-based method (SBM), which is capable of capturing the complex dynamic of crude oil prices. Three commonly used multi-step-ahead prediction strategies proposed in the literature, including iterated strategy, direct strategy, and MIMO (multiple-input multiple-output) strategy, are examined and compared, and practical considerations for the selection of a prediction strategy for multi-step-ahead forecasting relating to crude oil prices are identified. The weekly data from the WTI (West Texas Intermediate) crude oil spot price are used to compare the performance of the alternative models under the EMD-SBM-FNN modeling framework with selected counterparts. The quantitative and comprehensive assessments are performed on the basis of prediction accuracy and computational cost. The results obtained in this study indicate that the proposed EMD-SBM-FNN model using the MIMO strategy is the best in terms of prediction accuracy with accredited computational load.
Pedestrian Route Choice by Iterated Equilibrium Search
Venue: arXiv cs.MA 2014
Year: 2014

In vehicular traffic planning it is a long standing problem how to assign demand such on the available model of a road network that an equilibrium with regard to travel time or generalized costs is realized. For pedestrian traffic this question can be asked as well. However, as the infrastructure of pedestrian dynamics is not a network (a graph), but two-dimensional, there is in principle an infinitely large set of routes. As a consequence none of the iterating assignment methods developed for road traffic can be applied for pedestrians. In this contribution a method to overcome this problem is briefly summarized and applied with an example geometry which as a result is enhanced with routes with intermediate destination areas of certain shape. The enhanced geometry is used in some exemplary assignment calculations.
Content Based Image Indexing and Retrieval
Venue: arXiv cs.CV 2014
Year: 2014

In this paper, we present the efficient content based image retrieval systems which employ the color, texture and shape information of images to facilitate the retrieval process. For efficient feature extraction, we extract the color, texture and shape feature of images automatically using edge detection which is widely used in signal processing and image compression. For facilitated the speedy retrieval we are implements the antipole-tree algorithm for indexing the images.
Speeding up SOR Solvers for Constraint-based GUIs with a Warm-Start Strategy
Venue: arXiv cs.HC 2014
Year: 2014

Many computer programs have graphical user interfaces (GUIs), which need good layout to make efficient use of the available screen real estate. Most GUIs do not have a fixed layout, but are resizable and able to adapt themselves. Constraints are a powerful tool for specifying adaptable GUI layouts: they are used to specify a layout in a general form, and a constraint solver is used to find a satisfying concrete layout, e.g.\ for a specific GUI size. The constraint solver has to calculate a new layout every time a GUI is resized or changed, so it needs to be efficient to ensure a good user experience. One approach for constraint solvers is based on the Gauss-Seidel algorithm and successive over-relaxation (SOR). Our observation is that a solution after resizing or changing is similar in structure to a previous solution. Thus, our hypothesis is that we can increase the computational performance of an SOR-based constraint solver if we reuse the solution of a previous layout to warm-start the solving of a new layout. In this paper we report on experiments to test this hypothesis experimentally for three common use cases: big-step resizing, small-step resizing and constraint change. In our experiments, we measured the solving time for randomly generated GUI layout specifications of various sizes. For all three cases we found that the performance is improved if an existing solution is used as a starting solution for a new layout.
Identification of $\cal K$ Most Vulnerable Nodes in Multi-layered Network Using a New Model of Interdependency
Venue: arXiv cs.NI 2014
Year: 2014

The critical infrastructures of the nation including the power grid and the communication network are highly interdependent. Recognizing the need for a deeper understanding of the interdependency in a multi-layered network, significant efforts have been made by the research community in the last few years to achieve this goal. Accordingly a number of models have been proposed and analyzed. Unfortunately, most of the models are over simplified and, as such, they fail to capture the complex interdependency that exists between entities of the power grid and the communication networks involving a combination of conjunctive and disjunctive relations. To overcome the limitations of existing models, we propose a new model that is able to capture such complex interdependency relations. Utilizing this model, we provide techniques to identify the $\cal K$ most vulnerable nodes of an interdependent network. We show that the problem can be solved in polynomial time in some special cases, whereas for some others, the problem is NP-complete. We establish that this problem is equivalent to computation of a {\em fixed point} of a multilayered network system and we provide a technique for its computation utilizing Integer Linear Programming. Finally, we evaluate the efficacy of our technique using real data collected from the power grid and the communication network that span the Maricopa County of Arizona.
Skew in Parallel Query Processing
Venue: arXiv cs.DB 2014
Year: 2014

We study the problem of computing a conjunctive query q in parallel, using p of servers, on a large database. We consider algorithms with one round of communication, and study the complexity of the communication. We are especially interested in the case where the data is skewed, which is a major challenge for scalable parallel query processing. We establish a tight connection between the fractional edge packings of the query and the amount of communication, in two cases. First, in the case when the only statistics on the database are the cardinalities of the input relations, and the data is skew-free, we provide matching upper and lower bounds (up to a poly log p factor) expressed in terms of fractional edge packings of the query q. Second, in the case when the relations are skewed and the heavy hitters and their frequencies are known, we provide upper and lower bounds (up to a poly log p factor) expressed in terms of packings of residual queries obtained by specializing the query to a heavy hitter. All our lower bounds are expressed in the strongest form, as number of bits needed to be communicated between processors with unlimited computational power. Our results generalizes some prior results on uniform databases (where each relation is a matching) [4], and other lower bounds for the MapReduce model [1].
Image reconstruction from few views by L0-norm optimization
Venue: arXiv cs.IT 2014
Year: 2014

The L1-norm of the gradient-magnitude images (GMI), which is the well-known total variation (TV) model, is widely used as regularization in the few views CT reconstruction. As the L1-norm TV regularization is tending to uniformly penalize the image gradient and the low-contrast structures are sometimes over smoothed, we proposed a new algorithm based on the L0-norm of the GMI to deal with the few views problem. To rise to the challenges introduced by the L0-norm DGT, the algorithm uses a pseudo-inverse transform of DGT and adapts an iterative hard thresholding (IHT) algorithm, whose convergence and effective efficiency have been theoretically proven. The simulation indicates that the algorithm proposed in this paper can obviously improve the reconstruction quality.
A Parameterized Complexity Analysis of Bi-level Optimisation with Evolutionary Algorithms
Venue: arXiv cs.NE 2014
Year: 2014

Bi-level optimisation problems have gained increasing interest in the field of combinatorial optimisation in recent years. With this paper, we start the runtime analysis of evolutionary algorithms for bi-level optimisation problems. We examine two NP-hard problems, the generalised minimum spanning tree problem (GMST), and the generalised travelling salesman problem (GTSP) in the context of parameterised complexity. For the generalised minimum spanning tree problem, we analyse the two approaches presented by Hu and Raidl (2012) with respect to the number of clusters that distinguish each other by the chosen representation of possible solutions. Our results show that a (1+1) EA working with the spanning nodes representation is not a fixed-parameter evolutionary algorithm for the problem, whereas the global structure representation enables to solve the problem in fixed-parameter time. We present hard instances for each approach and show that the two approaches are highly complementary by proving that they solve each other's hard instances very efficiently. For the generalised travelling salesman problem, we analyse the problem with respect to the number of clusters in the problem instance. Our results show that a (1+1) EA working with the global structure representation is a fixed-parameter evolutionary algorithm for the problem.