OpenRaiser/Intern-Atlas huggingface dataset:
Energy-Efficient Symbol-Level Precoding in Multiuser MISO Based on Relaxed Detection Region
Venue: arXiv cs.IT 2015
Year: 2015

This paper addresses the problem of exploiting interference among simultaneous multiuser transmissions in the downlink of multiple-antenna systems. Using symbol-level precoding, a new approach towards addressing the multiuser interference is discussed through jointly utilizing the channel state information (CSI) and data information (DI). The interference among the data streams is transformed under certain conditions to a useful signal that can improve the signal-to-interference noise ratio (SINR) of the downlink transmissions and as a result the system's energy efficiency. In this context, new constructive interference precoding techniques that tackle the transmit power minimization (min power) with individual SINR constraints at each user's receiver have been proposed. In this paper, we generalize the CI precoding design under the assumption that the received MPSK symbol can reside in a relaxed region in order to be correctly detected. Moreover, a weighted maximization of the minimum SNR among all users is studied taking into account the relaxed detection region. Symbol error rate analysis (SER) for the proposed precoding is discussed to characterize the tradeoff between transmit power reduction and SER increase due to the relaxation. Based on this tradeoff, the energy efficiency performance of the proposed technique is analyzed. Finally, extensive numerical results show that the proposed schemes outperform other state-of-the-art techniques.
Structural Properties of Index Coding Capacity Using Fractional Graph Theory
Venue: arXiv cs.IT 2015
Year: 2015

The capacity region of the index coding problem is characterized through the notion of confusion graph and its fractional chromatic number. Based on this multiletter characterization, several structural properties of the capacity region are established, some of which are already noted by Tahmasbi, Shahrasbi, and Gohari, but proved here with simple and more direct graph-theoretic arguments. In particular, the capacity region of a given index coding problem is shown to be simple functionals of the capacity regions of smaller subproblems when the interaction between the subproblems is none, one-way, or complete.
Complete Dictionary Recovery over the Sphere
Venue: arXiv cs.IT 2015
Year: 2015

We consider the problem of recovering a complete (i.e., square and invertible) matrix $\mathbf A_0$, from $\mathbf Y \in \mathbb R^{n \times p}$ with $\mathbf Y = \mathbf A_0 \mathbf X_0$, provided $\mathbf X_0$ is sufficiently sparse. This recovery problem is central to the theoretical understanding of dictionary learning, which seeks a sparse representation for a collection of input signals, and finds numerous applications in modern signal processing and machine learning. We give the first efficient algorithm that provably recovers $\mathbf A_0$ when $\mathbf X_0$ has $O(n)$ nonzeros per column, under suitable probability model for $\mathbf X_0$. In contrast, prior results based on efficient algorithms provide recovery guarantees when $\mathbf X_0$ has only $O(n^{1-δ})$ nonzeros per column for any constant $δ\in (0, 1)$. Our algorithmic pipeline centers around solving a certain nonconvex optimization problem with a spherical constraint, and hence is naturally phrased in the language of manifold optimization. To show this apparently hard problem is tractable, we first provide a geometric characterization of the high-dimensional objective landscape, which shows that with high probability there are no "spurious" local minima. This particular geometric structure allows us to design a Riemannian trust region algorithm over the sphere that provably converges to one local minimizer with an arbitrary initialization, despite the presence of saddle points. The geometric approach we develop here may also shed light on other problems arising from nonconvex recovery of structured signals.
Deviation Based Pooling Strategies For Full Reference Image Quality Assessment
Venue: arXiv cs.MM 2015
Year: 2015

The state-of-the-art pooling strategies for perceptual image quality assessment (IQA) are based on the mean and the weighted mean. They are robust pooling strategies which usually provide a moderate to high performance for different IQAs. Recently, standard deviation (SD) pooling was also proposed. Although, this deviation pooling provides a very high performance for a few IQAs, its performance is lower than mean poolings for many other IQAs. In this paper, we propose to use the mean absolute deviation (MAD) and show that it is a more robust and accurate pooling strategy for a wider range of IQAs. In fact, MAD pooling has the advantages of both mean pooling and SD pooling. The joint computation and use of the MAD and SD pooling strategies is also considered in this paper. Experimental results provide useful information on the choice of the proper deviation pooling strategy for different IQA models.
Information Complexity and the Quest for Interactive Compression (A Survey)
Venue: arXiv cs.CC 2015
Year: 2015

Information complexity is the interactive analogue of Shannon's classical information theory. In recent years this field has emerged as a powerful tool for proving strong communication lower bounds, and for addressing some of the major open problems in communication complexity and circuit complexity. A notable achievement of information complexity is the breakthrough in understanding of the fundamental direct sum and direct product conjectures, which aim to quantify the power of parallel computation. This survey provides a brief introduction to information complexity, and overviews some of the recent progress on these conjectures and their tight relationship with the fascinating problem of compressing interactive protocols.
Stable Delaunay Graphs
Venue: arXiv cs.CG 2015
Year: 2015

Let $P$ be a set of $n$ points in $\mathrm{R}^2$, and let $\mathrm{DT}(P)$ denote its Euclidean Delaunay triangulation. We introduce the notion of an edge of $\mathrm{DT}(P)$ being {\it stable}. Defined in terms of a parameter $α>0$, a Delaunay edge $pq$ is called $α$-stable, if the (equal) angles at which $p$ and $q$ see the corresponding Voronoi edge $e_{pq}$ are at least $α$. A subgraph $G$ of $\mathrm{DT}(P)$ is called {\it $(cα, α)$-stable Delaunay graph} ($\mathrm{SDG}$ in short), for some constant $c \ge 1$, if every edge in $G$ is $α$-stable and every $cα$-stable of $\mathrm{DT}(P)$ is in $G$. We show that if an edge is stable in the Euclidean Delaunay triangulation of $P$, then it is also a stable edge, though for a different value of $α$, in the Delaunay triangulation of $P$ under any convex distance function that is sufficiently close to the Euclidean norm, and vice-versa. In particular, a $6α$-stable edge in $\mathrm{DT}(P)$ is $α$-stable in the Delaunay triangulation under the distance function induced by a regular $k$-gon for $k \ge 2π/α$, and vice-versa. Exploiting this relationship and the analysis in~\cite{polydel}, we present a linear-size kinetic data structure (KDS) for maintaining an $(8α,α)$-$\mathrm{SDG}$ as the points of $P$ move. If the points move along algebraic trajectories of bounded degree, the KDS processes nearly quadratic events during the motion, each of which can processed in $O(\log n)$ time. Finally, we show that a number of useful properties of $\mathrm{DT}(P)$ are retained by $\mathrm{SDG}$ of $P$.
Optimal Detection of Random Walks on Graphs: Performance Analysis via Statistical Physics
Venue: arXiv cs.IT 2015
Year: 2015

We study the problem of detecting a random walk on a graph from a sequence of noisy measurements at every node. There are two hypotheses: either every observation is just meaningless zero-mean Gaussian noise, or at each time step exactly one node has an elevated mean, with its location following a random walk on the graph over time. We want to exploit knowledge of the graph structure and random walk parameters (specified by a Markov chain transition matrix) to detect a possibly very weak signal. The optimal detector is easily derived, and we focus on the harder problem of characterizing its performance through the (type-II) error exponent: the decay rate of the miss probability under a false alarm constraint. The expression for the error exponent resembles the free energy of a spin glass in statistical physics, and we borrow techniques from that field to develop a lower bound. Our fully rigorous analysis uses large deviations theory to show that the lower bound exhibits a phase transition: strong performance is only guaranteed when the signal-to-noise ratio exceeds twice the entropy rate of the random walk. Monte Carlo simulations show that the lower bound fully captures the behavior of the true exponent.
A symbolic calculus for a class of quantum computing circuits
Venue: arXiv cs.ET 2015
Year: 2015

This paper introduces a symbolic calculus to evaluate the output signals at the target line(s) of quantum computing subcircuits using controlled negations and controlled-Q gates, where Q represents the k-th root of [0 1; 1 0], the unitary matrix of NOT, and k is a power of two. The controlling signals are GF(2) expressions possibly including Boolean expressions. The method does not require operating with complex-valued matrices. The method may be used to verify the functionality and to check for possible minimization of a given quantum computing circuit using target lines. The method does not apply for a whole circuit if there are interactions among target lines. In this case the method applies for the independent subcircuits.
Proof Theory of a Multi-Lane Spatial Logic
Venue: arXiv cs.LO 2015
Year: 2015

We extend the Multi-lane Spatial Logic MLSL, introduced in previous work for proving the safety (collision freedom) of traffic maneuvers on a multi-lane highway, by length measurement and dynamic modalities. We investigate the proof theory of this extension, called EMLSL. To this end, we prove the undecidability of EMLSL but nevertheless present a sound proof system which allows for reasoning about the safety of traffic situations. We illustrate the latter by giving a formal proof for the reservation lemma we could only prove informally before. Furthermore we prove a basic theorem showing that the length measurement is independent from the number of lanes on the highway.
SegSALSA-STR: A convex formulation to supervised hyperspectral image segmentation using hidden fields and structure tensor regularization
Venue: arXiv cs.CV 2015
Year: 2015

We present a supervised hyperspectral image segmentation algorithm based on a convex formulation of a marginal maximum a posteriori segmentation with hidden fields and structure tensor regularization: Segmentation via the Constraint Split Augmented Lagrangian Shrinkage by Structure Tensor Regularization (SegSALSA-STR). This formulation avoids the generally discrete nature of segmentation problems and the inherent NP-hardness of the integer optimization associated. We extend the Segmentation via the Constraint Split Augmented Lagrangian Shrinkage (SegSALSA) algorithm by generalizing the vectorial total variation prior using a structure tensor prior constructed from a patch-based Jacobian. The resulting algorithm is convex, time-efficient and highly parallelizable. This shows the potential of combining hidden fields with convex optimization through the inclusion of different regularizers. The SegSALSA-STR algorithm is validated in the segmentation of real hyperspectral images.
Performance evaluation of the Mojette erasure code for fault-tolerant distributed hot data storage
Venue: arXiv cs.IT 2015
Year: 2015

Packet erasure codes are today a real alternative to replication in fault tolerant distributed storage systems. In this paper, we propose the Mojette erasure code based on the Mojette transform, a formerly tomographic tool. The performance of coding and decoding are compared to the Reed-Solomon code implementations of the two open-source reference libraries namely ISA-L and Jerasure 2.0. Results clearly show better performances for our discrete geometric code compared to the classical algebraic approaches. A gain factor up to $2$ is measured in comparison with the ISA-L Intel . Those very good performances allow to deploy Mojette erasure code for hot data distributed storage and I/O intensive applications.
On the Verification of SCOOP Programs
Venue: arXiv cs.SE 2015
Year: 2015

In this paper we focus on the development of a toolbox for the verification of programs in the context of SCOOP -- an elegant concurrency model, recently formalized based on Rewriting Logic (RL) and Maude. SCOOP is implemented in Eiffel and its applicability is demonstrated also from a practical perspective, in the area of robotics programming. Our contribution consists in devising and integrating an alias analyzer and a Coffman deadlock detector under the roof of the same RL-based semantic framework of SCOOP. This enables using the Maude rewriting engine and its LTL model-checker "for free", in order to perform the analyses of interest. We discuss the limitations of our approach for model-checking deadlocks and provide solutions to the state explosion problem. The latter is mainly caused by the size of the SCOOP formalization which incorporates all the aspects of a real concurrency model. On the aliasing side, we propose an extension of a previously introduced alias calculus based on program expressions, to the setting of unbounded program executions such as infinite loops and recursive calls. Moreover, we devise a corresponding executable specification easily implementable on top of the SCOOP formalization. An important property of our extension is that, in non-concurrent settings, the corresponding alias expressions can be over-approximated in terms of a notion of regular expressions. This further enables us to derive an algorithm that always stops and provides a sound over-approximation of the "may aliasing" information, where soundness stands for the lack of false negatives.
Effectiveness of Structural Restrictions for Hybrid CSPs
Venue: arXiv cs.CC 2015
Year: 2015

Constraint Satisfaction Problem (CSP) is a fundamental algorithmic problem that appears in many areas of Computer Science. It can be equivalently stated as computing a homomorphism $\mbox{$\bR \rightarrow \bGamma$}$ between two relational structures, e.g.\ between two directed graphs. Analyzing its complexity has been a prominent research direction, especially for {\em fixed template CSPs} in which the right side $\bGamma$ is fixed and the left side $\bR$ is unconstrained. Far fewer results are known for the {\em hybrid} setting that restricts both sides simultaneously. It assumes that $\bR$ belongs to a certain class of relational structures (called a {\em structural restriction} in this paper). We study which structural restrictions are {\em effective}, i.e.\ there exists a fixed template $\bGamma$ (from a certain class of languages) for which the problem is tractable when $\bR$ is restricted, and NP-hard otherwise. We provide a characterization for structural restrictions that are {\em closed under inverse homomorphisms}. The criterion is based on the {\em chromatic number} of a relational structure defined in this paper; it generalizes the standard chromatic number of a graph. As our main tool, we use the algebraic machinery developed for fixed template CSPs. To apply it to our case, we introduce a new construction called a "lifted language." We also give a characterization for structural restrictions corresponding to minor-closed families of graphs, extend results to certain Valued CSPs (namely conservative valued languages), and state implications for CSPs with ordered variables, (valued) CSPs on structures with large girth, and for the maximum weight independent set problem on some restricted families of graphs including graphs with large girth.
Optimal Shuffle Code with Permutation Instructions
Venue: arXiv cs.DS 2015
Year: 2015

During compilation of a program, register allocation is the task of mapping program variables to machine registers. During register allocation, the compiler may introduce shuffle code, consisting of copy and swap operations, that transfers data between the registers. Three common sources of shuffle code are conflicting register mappings at joins in the control flow of the program, e.g, due to if-statements or loops; the calling convention for procedures, which often dictates that input arguments or results must be placed in certain registers; and machine instructions that only allow a subset of registers to occur as operands. Recently, Mohr et al. proposed to speed up shuffle code with special hardware instructions that arbitrarily permute the contents of up to five registers and gave a heuristic for computing such shuffle codes. In this paper, we give an efficient algorithm for generating optimal shuffle code in the setting of Mohr et al. An interesting special case occurs when no register has to be transferred to more than one destination, i.e., it suffices to permute the contents of the registers. This case is equivalent to factoring a permutation into a minimal product of permutations, each of which permutes up to five elements.
Fully-dynamic Approximation of Betweenness Centrality
Venue: arXiv cs.DS 2015
Year: 2015

Betweenness is a well-known centrality measure that ranks the nodes of a network according to their participation in shortest paths. Since an exact computation is prohibitive in large networks, several approximation algorithms have been proposed. Besides that, recent years have seen the publication of dynamic algorithms for efficient recomputation of betweenness in evolving networks. In previous work we proposed the first semi-dynamic algorithms that recompute an approximation of betweenness in connected graphs after batches of edge insertions. In this paper we propose the first fully-dynamic approximation algorithms (for weighted and unweighted undirected graphs that need not to be connected) with a provable guarantee on the maximum approximation error. The transfer to fully-dynamic and disconnected graphs implies additional algorithmic problems that could be of independent interest. In particular, we propose a new upper bound on the vertex diameter for weighted undirected graphs. For both weighted and unweighted graphs, we also propose the first fully-dynamic algorithms that keep track of such upper bound. In addition, we extend our former algorithm for semi-dynamic BFS to batches of both edge insertions and deletions. Using approximation, our algorithms are the first to make in-memory computation of betweenness in fully-dynamic networks with millions of edges feasible. Our experiments show that they can achieve substantial speedups compared to recomputation, up to several orders of magnitude.
Secure Zones: An Attribute-Based Encryption advisory system for safe firearms
Venue: arXiv cs.CR 2015
Year: 2015

This work presents an application of the highly expressive Attribute-Based Encryption to implement Secure Zones for firearms. Within these zones, radio-transmitted local policies based on attributes of the user and the firearm are received by embedded hardware in the firearms, which then advises the user about safe operations. The Secure Zones utilize Attribute-Based Encryption to encode the policies and user attributes, and providing privacy and security through it cryptography. We describe a holistic approach to evolving the firearm to a cyber-physical system to aid in augmenting safety. We introduce a conceptual model for a firearm equipped with sensors and a context-aware software agent. Based on the information from the sensors, the agent can access the context and inform the user of potential unsafe operations. To support Secure Zones and the cyber-physical firearm model, we propose a Key Infrastructure Scheme for key generation, distribution, and management, and a Context-Aware Software Agent Framework for Firearms.
Convolutional Channel Features
Venue: arXiv cs.CV 2015
Year: 2015

Deep learning methods are powerful tools but often suffer from expensive computation and limited flexibility. An alternative is to combine light-weight models with deep representations. As successful cases exist in several visual problems, a unified framework is absent. In this paper, we revisit two widely used approaches in computer vision, namely filtered channel features and Convolutional Neural Networks (CNN), and absorb merits from both by proposing an integrated method called Convolutional Channel Features (CCF). CCF transfers low-level features from pre-trained CNN models to feed the boosting forest model. With the combination of CNN features and boosting forest, CCF benefits from the richer capacity in feature representation compared with channel features, as well as lower cost in computation and storage compared with end-to-end CNN methods. We show that CCF serves as a good way of tailoring pre-trained CNN models to diverse tasks without fine-tuning the whole network to each task by achieving state-of-the-art performances in pedestrian detection, face detection, edge detection and object proposal generation.
Distributed inference over directed networks: Performance limits and optimal design
Venue: arXiv cs.IT 2015
Year: 2015

We find large deviations rates for consensus-based distributed inference for directed networks. When the topology is deterministic, we establish the large deviations principle and find exactly the corresponding rate function, equal at all nodes. We show that the dependence of the rate function on the stochastic weight matrix associated with the network is fully captured by its left eigenvector corresponding to the unit eigenvalue. Further, when the sensors' observations are Gaussian, the rate function admits a closed form expression. Motivated by these observations, we formulate the optimal network design problem of finding the left eigenvector which achieves the highest value of the rate function, for a given target accuracy. This eigenvector therefore minimizes the time that the inference algorithm needs to reach the desired accuracy. For Gaussian observations, we show that the network design problem can be formulated as a semidefinite (convex) program, and hence can be solved efficiently. When observations are identically distributed across agents, the system exhibits an interesting property: the graph of the rate function always lies between the graphs of the rate function of an isolated node and the rate function of a fusion center that has access to all observations. We prove that this fundamental property holds even when the topology and the associated system matrices change randomly over time, with arbitrary distribution. Due to generality of its assumptions, the latter result requires more subtle techniques than the standard large deviations tools, contributing to the general theory of large deviations.
TACTICS: TACTICal Service Oriented Architecture
Venue: arXiv cs.SE 2015
Year: 2015

Due to the increasing complexity and heterogeneity of contemporary Command, Control, Communications, Computers, & Intelligence systems at all levels within military organizations, the adoption of the Service Oriented Architectures (SOA) principles and concepts is becoming essential. SOA provides flexibility and interoperability of services enabling the realization of efficient and modular information infrastructure for command and control systems. However, within a tactical domain, the presence of potentially highly mobile actors equipped with constrained communications media (i.e., unreliable radio networks with limited bandwidth) limits the applicability of traditional SOA technologies. The TACTICS project aims at the definition and experimental demonstration of a Tactical Services Infrastructure enabling tactical radio networks (without any modifications of the radio part of those networks) to participate in SOA infrastructures and provide, as well as consume, services to and from the strategic domain independently of the user's location.