OpenRaiser/Intern-Atlas huggingface dataset:
Low Complexity Delay-Constrained Beamforming for Multi-User MIMO Systems with Imperfect CSIT
Venue: arXiv cs.IT 2013
Year: 2013

In this paper, we consider the delay-constrained beamforming control for downlink multi-user MIMO (MU- MIMO) systems with imperfect channel state information at the transmitter (CSIT). The delay-constrained control problem is formulated as an infinite horizon average cost partially observed Markov decision process. To deal with the curse of dimensionality, we introduce a virtual continuous time system and derive a closed-form approximate value function using perturbation analysis w.r.t. the CSIT errors. To deal with the challenge of the conditional packet error rate (PER), we build a tractable closed- form approximation using a Bernstein-type inequality. Based on the closed-form approximations of the relative value function and the conditional PER, we propose a conservative formulation of the original beamforming control problem. The conservative problem is non-convex and we transform it into a convex problem using the semidefinite relaxation (SDR) technique. We then propose an alternating iterative algorithm to solve the SDR problem. Finally, the proposed scheme is compared with various baselines through simulations and it is shown that significant performance gain can be achieved.
Random Linear Network Codes for Secrecy over Wireless Broadcast Channels
Venue: arXiv cs.IT 2013
Year: 2013

We consider a set of $n$ messages and a group of $k$ clients. Each client is privileged for receiving an arbitrary subset of the messages over a broadcast erasure channel, which generalizes scenario of a previous work. We propose a method for secretly delivering each message to its privileged recipients in a way that each receiver can decode its own messages but not the others'. Our method is based on combining the messages using linear network coding and hiding the decoding coefficients from the unprivileged clients. We provide an information theoretic proof for the secrecy of the proposed method. In particular we show that an unprivileged client cannot obtain any meaningful information even if it holds the entire set of coded data packets transmitted over the channel. Moreover, in our method, the decoding complexity is desirably low at the receiver side.
How to find real-world applications for compressive sensing
Venue: arXiv cs.CV 2013
Year: 2013

The potential of compressive sensing (CS) has spurred great interest in the research community and is a fast growing area of research. However, research translating CS theory into practical hardware and demonstrating clear and significant benefits with this hardware over current, conventional imaging techniques has been limited. This article helps researchers to find those niche applications where the CS approach provides substantial gain over conventional approaches by articulating lessons learned in finding one such application; sea skimming missile detection. As a proof of concept, it is demonstrated that a simplified CS missile detection architecture and algorithm provides comparable results to the conventional imaging approach but using a smaller FPA. The primary message is that all of the excitement surrounding CS is necessary and appropriate for encouraging our creativity but we all must also take off our "rose colored glasses" and critically judge our ideas, methods and results relative to conventional imaging approaches.
Rate Distortion Function for a Class of Relative Entropy Sources
Venue: arXiv cs.IT 2013
Year: 2013

This paper deals with rate distortion or source coding with fidelity criterion, in measure spaces, for a class of source distributions. The class of source distributions is described by a relative entropy constraint set between the true and a nominal distribution. The rate distortion problem for the class is thus formulated and solved using minimax strategies, which result in robust source coding with fidelity criterion. It is shown that minimax and maxmin strategies can be computed explicitly, and they are generalizations of the classical solution. Finally, for discrete memoryless uncertain sources, the rate distortion theorem is stated for the class omitting the derivations while the converse is derived.
An Encryption Scheme with DNA Technology and JPEG Zigzag Coding for Secure Transmission of Images
Venue: arXiv cs.CR 2013
Year: 2013

The Internet is a ubiquitous and affordable communications network suited for e-commerce and medical image communications. Security has become a major issue as data communication channels can be intruded by intruders during transmission. Though, different methods have been proposed and used to protect the transmission of data from illegal and unauthorized access, code breakers have come up with various methods to crack them. DNA based Cryptography brings forward a new hope for unbreakable algorithms. This paper outlines an encryption scheme with DNA technology and JPEG Zigzag Coding for Secure Transmission of Images.
Parallel Chen-Han (PCH) Algorithm for Discrete Geodesics
Venue: arXiv cs.GR 2013
Year: 2013

In many graphics applications, the computation of exact geodesic distance is very important. However, the high computational cost of the existing geodesic algorithms means that they are not practical for large-scale models or time-critical applications. To tackle this challenge, we propose the parallel Chen-Han (or PCH) algorithm, which extends the classic Chen-Han (CH) discrete geodesic algorithm to the parallel setting. The original CH algorithm and its variant both lack a parallel solution because the windows (a key data structure that carries the shortest distance in the wavefront propagation) are maintained in a strict order or a tightly coupled manner, which means that only one window is processed at a time. We propose dividing the CH's sequential algorithm into four phases, window selection, window propagation, data organization, and events processing so that there is no data dependence or conflicts in each phase and the operations within each phase can be carried out in parallel. The proposed PCH algorithm is able to propagate a large number of windows simultaneously and independently. We also adopt a simple yet effective strategy to control the total number of windows. We implement the PCH algorithm on modern GPUs (such as Nvidia GTX 580) and analyze the performance in detail. The performance improvement (compared to the sequential algorithms) is highly consistent with GPU double-precision performance (GFLOPS). Extensive experiments on real-world models demonstrate an order of magnitude improvement in execution time compared to the state-of-the-art.
Tight Lower Bounds for Greedy Routing in Higher-Dimensional Small-World Grids
Venue: arXiv cs.DS 2013
Year: 2013

We consider Kleinberg's celebrated small world graph model (Kleinberg, 2000), in which a D-dimensional grid {0,...,n-1}^D is augmented with a constant number of additional unidirectional edges leaving each node. These long range edges are determined at random according to a probability distribution (the augmenting distribution), which is the same for each node. Kleinberg suggested using the inverse D-th power distribution, in which node v is the long range contact of node u with a probability proportional to ||u-v||^(-D). He showed that such an augmenting distribution allows to route a message efficiently in the resulting random graph: The greedy algorithm, where in each intermediate node the message travels over a link that brings the message closest to the target w.r.t. the Manhattan distance, finds a path of expected length O(log^2 n) between any two nodes. In this paper we prove that greedy routing does not perform asymptotically better for any uniform and isotropic augmenting distribution, i.e., the probability that node u has a particular long range contact v is independent of the labels of u and v and only a function of ||u-v||. In order to obtain the result, we introduce a novel proof technique: We define a budget game, in which a token travels over a game board, while the player manages a "probability budget". In each round, the player bets part of her remaining probability budget on step sizes. A step size is chosen at random according to a probability distribution of the player's bet. The token then makes progress as determined by the chosen step size, while some of the player's bet is removed from her probability budget. We prove a tight lower bound for such a budget game, and then obtain a lower bound for greedy routing in the D-dimensional grid by a reduction.
Optimal Noise Adding Mechanisms for Approximate Differential Privacy
Venue: arXiv cs.DS 2013
Year: 2013

We study the (nearly) optimal mechanisms in $(ε,δ)$-approximate differential privacy for integer-valued query functions and vector-valued (histogram-like) query functions under a utility-maximization/cost-minimization framework. We characterize the tradeoff between $ε$ and $δ$ in utility and privacy analysis for histogram-like query functions ($\ell^1$ sensitivity), and show that the $(ε,δ)$-differential privacy is a framework not much more general than the $(ε,0)$-differential privacy and $(0,δ)$-differential privacy in the context of $\ell^1$ and $\ell^2$ cost functions, i.e., minimum expected noise magnitude and noise power. In the same context of $\ell^1$ and $\ell^2$ cost functions, we show the near-optimality of uniform noise mechanism and discrete Laplacian mechanism in the high privacy regime (as $(ε,δ) \to (0,0)$). We conclude that in $(ε,δ)$-differential privacy, the optimal noise magnitude and noise power are $Θ(\min(\frac{1}ε,\frac{1}δ))$ and $Θ(\min(\frac{1}{ε^2},\frac{1}{δ^2}))$, respectively, in the high privacy regime.
Cold-start recommendation through granular association rules
Venue: arXiv cs.IR 2013
Year: 2013

Recommender systems are popular in e-commerce as they suggest items of interest to users. Researchers have addressed the cold-start problem where either the user or the item is new. However, the situation with both new user and new item has seldom been considered. In this paper, we propose a cold-start recommendation approach to this situation based on granular association rules. Specifically, we provide a means for describing users and items through information granules, a means for generating association rules between users and items, and a means for recommending items to users using these rules. Experiments are undertaken on a publicly available dataset MovieLens. Results indicate that rule sets perform similarly on the training and the testing sets, and the appropriate setting of granule is essential to the application of granular association rules.
How Many Queries Will Resolve Common Randomness?
Venue: arXiv cs.IT 2013
Year: 2013

A set of m terminals, observing correlated signals, communicate interactively to generate common randomness for a given subset of them. Knowing only the communication, how many direct queries of the value of the common randomness will resolve it? A general upper bound, valid for arbitrary signal alphabets, is developed for the number of such queries by using a query strategy that applies to all common randomness and associated communication. When the underlying signals are independent and identically distributed repetitions of m correlated random variables, the number of queries can be exponential in signal length. For this case, the mentioned upper bound is tight and leads to a single-letter formula for the largest query exponent, which coincides with the secret key capacity of a corresponding multiterminal source model. In fact, the upper bound constitutes a strong converse for the optimum query exponent, and implies also a new strong converse for secret key capacity. A key tool, estimating the size of a large probability set in terms of Renyi entropy, is interpreted separately, too, as a lossless block coding result for general sources. As a particularization, it yields the classic result for a discrete memoryless source.
Sharp control time for viscoelastic bodys
Venue: arXiv cs.SY 2013
Year: 2013

It is now well understood that equations of viscoelasticity can be seen as perturbation of wave type equations. This observation can be exploited in several different ways and it turns out that it is a usefull tool when studying controllability. Here we compare a viscoelastic system which fills a surface of a solid region (the string case has already been studied) with its memoryless counterpart (which is a generalized telegraph equation) in order to prove exact controllability of the viscoelastic body at precisely the same times at which the telegraph equation is controllable. The comparison is done using a moment method approach to controllability and we prove, using the perturbations theorems of Paley-Wiener and Bari, that a new sequence derived from the viscoelastic system is a Riesz sequence, a fact that implies controllability of the viscoelastic system. The results so obtained generalize existing controllability results and furthermore show that the ``sharp'' control time for the telegraph equation and the viscoelastic system coincide.
MC-curves and aesthetic measurements for pseudospiral curve segments
Venue: arXiv cs.GR 2013
Year: 2013

This article studies families of curves with monotonic curvature function (MC-curves) and their applications in geometric modelling and aesthetic design. Aesthetic analysis and assessment of the structure and plastic qualities of pseudospirals, which are curves with monotonic curvature function, are conducted for the first time in the field of geometric modelling from the position of technical aesthetics laws. The example of car body surface modelling with the use of aesthetics splines is given.
Using Dimensional Analysis to Assess Scalability and Accuracy in Molecular Communication
Venue: arXiv cs.IT 2013
Year: 2013

In this paper, we apply dimensional analysis to study a diffusive molecular communication system that uses diffusing enzymes in the propagation environment to mitigate intersymbol interference. The enzymes bind to information molecules and then degrade them so that they cannot interfere with the detection of future transmissions at the receiver. We determine when it is accurate to assume that the concentration of information molecules throughout the receiver is constant and equal to that expected at the center of the receiver. We show that a lower bound on the expected number of molecules observed at the receiver can be arbitrarily scaled over the environmental parameters, and generalize how the accuracy of the lower bound is qualitatively impacted by those parameters.
Performance Evaluation of Video Communications over 4G Network
Venue: arXiv cs.MM 2013
Year: 2013

With exponential increase in the volumes of video traffic in cellular net-works, there is an increasing need for optimizing the quality of video delivery. 4G networks (Long Term Evolution Advanced or LTE A) are being introduced in many countries worldwide, which allow a downlink speed of upto 1 Gbps and uplink of 100 Mbps over a single base station. In this paper, we characterize the performance of LTE A physical layer in terms of transmitted video quality when the channel condi-tions and LTE settings are varied. We test the performance achieved as the channel quality is changed and HARQ features are enabled in physical layer. Blocking and blurring metrics were used to model image quality.
On Advice Complexity of the k-server Problem under Sparse Metrics
Venue: arXiv cs.DS 2013
Year: 2013

We consider the k-server problem under the advice model of computation when the underlying metric space is sparse. On one side, we show that an advice of size Ω(n) is required to obtain a 1-competitive algorithm for sequences of size n, even for the 2-server problem on a path metric of size N >= 5. Through another lower bound argument, we show that at least (n/2)(log α - 1.22) bits of advice is required to obtain an optimal solution for metric spaces of treewidth α, where 4 <= α < 2k. On the other side, we introduce Θ(1)-competitive algorithms for a wide range of sparse graphs, which require advice of (almost) linear size. Namely, we show that for graphs of size N and treewidth α, there is an online algorithm which receives $O(n (log α + log log N))$ bits of advice and optimally serves a sequence of length n. With a different argument, we show that if a graph admits a system of μ collective tree (q,r)-spanners, then there is a (q+r)-competitive algorithm which receives O(n (log μ + log log N)) bits of advice. Among other results, this gives a 3-competitive algorithm for planar graphs, provided with O(n log log N) bits of advice.
Physical-Layer Multicasting by Stochastic Transmit Beamforming and Alamouti Space-Time Coding
Venue: arXiv cs.IT 2013
Year: 2013

Consider transceiver designs in a multiuser multi-input single-output (MISO) downlink channel, where the users are to receive the same data stream simultaneously. This problem, known as physical-layer multicasting, has drawn much interest. Presently, a popularized approach is transmit beamforming, in which the beamforming optimization is handled by a rank-one approximation method called semidefinite relaxation (SDR). SDR-based beamforming has been shown to be promising for a small or moderate number of users. This paper describes two new transceiver strategies for physical-layer multicasting. The first strategy, called stochastic beamforming (SBF), randomizes the beamformer in a per-symbol time-varying manner, so that the rank-one approximation in SDR can be bypassed. We propose several efficiently realizable SBF schemes, and prove that their multicast achievable rate gaps with respect to the MISO multicast capacity must be no worse than 0.8314 bits/s/Hz, irrespective of any other factors such as the number of users. The use of channel coding and the assumption of sufficiently long code lengths play a crucial role in achieving the above result. The second strategy combines transmit beamforming and the Alamouti space-time code. The result is a rank-two generalization of SDR-based beamforming. We show by analysis that this SDR-based beamformed Alamouti scheme has a better worst-case effective signal-to-noise ratio (SNR) scaling, and hence a better multicast rate scaling, than SDR-based beamforming. We further the work by combining SBF and the beamformed Alamouti scheme, wherein an improved constant rate gap of 0.39 bits/s/Hz is proven. Simulation results show that under a channel-coded, many-user setting, the proposed multicast transceiver schemes yield significant SNR gains over SDR-based beamforming at the same bit error rate level.
Linear Logic without Units
Venue: arXiv cs.LO 2013
Year: 2013

We study categorical models for the unitless fragment of multiplicative linear logic. We find that the appropriate notion of model is a special kind of promonoidal category. Since the theory of promonoidal categories has not been developed very thoroughly, at least in the published literature, we need to develop it here. The most natural way to do this - and the simplest, once the (substantial) groundwork has been laid - is to consider promonoidal categories as an instance of the general theory of pseudomonoids in a monoidal bicategory. Accordingly, we describe and explain the notions of monoidal bicategory and pseudomonoid therein. The higher-dimensional nature of monoidal bicategories presents serious notational difficulties, since to use the natural analogue of the commutative diagrams used in ordinary category theory would require the use of three-dimensional diagrams. We therefore introduce a novel technical device, which we dub the calculus of components, that simplifies the business of reasoning about a certain class of algebraic structure internal to a monoidal bicategory. When viewed through this simplifying lens, the theory of pseudomonoids turns out to be essentially formally identical to the ordinary theory of monoidal categories. We indicate how the calculus of components may be extended to cover structures that make use of the braiding in a braided monoidal bicategory, and use this to study braided pseudomonoids. A higher-dimensional analogue of Cayley's theorem is proved, and used to deduce a novel characterisation of the unit of a promonoidal category. This, and the other preceding work, is then used to give two characterisations of the categories that model the unitless fragment of intuitionistic multiplicative linear logic. Finally we consider the non-intuitionistic case, where the second characterisation in particular takes a surprisingly simple form.
Fast Collision Checking: From Single Robots to Multi-Robot Teams
Venue: arXiv cs.RO 2013
Year: 2013

We examine three different algorithms that enable the collision certificate method from [Bialkowski, et al.] to handle the case of a centralized multi-robot team. By taking advantage of symmetries in the configuration space of multi-robot teams, our methods can significantly reduce the number of collision checks vs. both [Bialkowski, et al.] and standard collision checking implementations.
Experiences of Using a Hybrid Cloud to Construct an Environmental Virtual Observatory
Venue: arXiv cs.DC 2013
Year: 2013

Environmental science is often fragmented: data is collected using mismatched formats and conventions, and models are misaligned and run in isolation. Cloud computing offers a lot of potential in the way of resolving such issues by supporting data from different sources and at various scales, by facilitating the integration of models to create more sophisticated software services, and by providing a sustainable source of suitable computational and storage resources. In this paper, we highlight some of our experiences in building the Environmental Virtual Observatory pilot (EVOp), a tailored cloud-based infrastructure and associated web-based tools designed to enable users from different backgrounds to access data concerning different environmental issues. We review our architecture design, the current deployment and prototypes. We also reflect on lessons learned. We believe that such experiences are of benefit to other scientific communities looking to assemble virtual observatories or similar virtual research environments.
Universally Truthful Secondary Spectrum Auctions
Venue: arXiv cs.GT 2013
Year: 2013

We present algorithms for implementing local spectrum redistribution in wireless networks using a mechanism design approach. For example, in single-hop request scheduling, secondary users are modeled as rational agents that have private utility when getting assigned a channel for successful transmission. We present a rather simple algorithmic technique that allows to turn existing and future approximation algorithms and heuristics into truthful mechanisms for a large variety of networking problems. In contrast to previous work, our approach works for virtually all known interference models in the literature, including the physical model of interference based on SINR. It allows to address single-hop and multi-hop scheduling, routing, and even more general assignment and allocation problems. Our mechanisms are randomized and represent the first universally-truthful mechanisms for these problems with rigorous worst-case guarantees on the solution quality. In this way, our mechanisms can be used to obtain guaranteed solution quality even with risk-averse or risk-seeking bidders, for which existing approaches fail.