OpenRaiser/Intern-Atlas huggingface dataset:
Payoff-based Inhomogeneous Partially Irrational Play for Potential Game Theoretic Cooperative Control of Multi-agent Systems
Venue: arXiv cs.SY 2011
Year: 2011

This paper handles a kind of strategic game called potential games and develops a novel learning algorithm Payoff-based Inhomogeneous Partially Irrational Play (PIPIP). The present algorithm is based on Distributed Inhomogeneous Synchronous Learning (DISL) presented in an existing work but, unlike DISL,PIPIP allows agents to make irrational decisions with a specified probability, i.e. agents can choose an action with a low utility from the past actions stored in the memory. Due to the irrational decisions, we can prove convergence in probability of collective actions to potential function maximizers. Finally, we demonstrate the effectiveness of the present algorithm through experiments on a sensor coverage problem. It is revealed through the demonstration that the present learning algorithm successfully leads agents to around potential function maximizers even in the presence of undesirable Nash equilibria. We also see through the experiment with a moving density function that PIPIP has adaptability to environmental changes.
Approximating minimum-power edge-multicovers
Venue: arXiv cs.DS 2011
Year: 2011

Given a graph with edge costs, the {\em power} of a node is themaximum cost of an edge incident to it, and the power of a graph is the sum of the powers of its nodes. Motivated by applications in wireless networks, we consider the following fundamental problem in wireless network design. Given a graph $G=(V,E)$ with edge costs and degree bounds $\{r(v):v \in V\}$, the {\sf Minimum-Power Edge-Multi-Cover} ({\sf MPEMC}) problem is to find a minimum-power subgraph $J$ of $G$ such that the degree of every node $v$ in $J$ is at least $r(v)$. We give two approximation algorithms for {\sf MPEMC}, with ratios $O(\log k)$ and $k+1/2$, where $k=\max_{v \in V} r(v)$ is the maximum degree bound. This improves the previous ratios $O(\log n)$ and $k+1$, and implies ratios $O(\log k)$ for the {\sf Minimum-Power $k$-Outconnected Subgraph} and $O(\log k \log \frac{n}{n-k})$ for the {\sf Minimum-Power $k$-Connected Subgraph} problems; the latter is the currently best known ratio for the min-cost version of the problem.
Threshold Improvement of Low-Density Lattice Codes via Spatial Coupling
Venue: arXiv cs.IT 2011
Year: 2011

Spatially-coupled low-density lattice codes (LDLC) are constructed using protographs. Using Monte Carlo density evolution using single-Gaussian messages, we observe that the threshold of the spatially-coupled LDLC is within 0.22 dB of capacity of the unconstrained power channel. This is in contrast with a 0.5 dB noise threshold for the conventional LDLC lattice construction.
On the Performance of Space Shift Keying (SSK) Modulation with Imperfect Channel Knowledge
Venue: arXiv cs.PF 2011
Year: 2011

In this paper, we study the sensitivity and robustness of Space Shift Keying (SSK) modulation to imperfect channel knowledge at the receiver. Unlike the common widespread belief, we show that SSK modulation is more robust to imperfect channel knowledge than other state-of-the-art transmission technologies, and only few training pilots are needed to get reliable enough channel estimates for data detection. More precisely, we focus our attention on the so-called Time-Orthogonal-Signal-Design (TOSD-) SSK modulation scheme, which is an improved version of SSK modulation offering transmit-diversity gains, and provide the following contributions: i) we develop a closed-form analytical framework to compute the Average Bit Error Probability (ABEP) of a mismatched detector for TOSD-SSK modulation, which can be used for arbitrary transmit-antenna, receive-antenna, channel fading, and training pilots; ii) we perform a comparative study of the performance of TOSD-SSK modulation and the Alamouti code under the same imperfect channel knowledge, and show that TOSD-SSK modulation is more robust to channel estimation errors; iii) we point out that only few pilot pulses are required to get performance very close to the perfect channel knowledge lower-bound; and iv) we verify that transmit- and receive-diversity gains of TOSD-SSK modulation are preserved even for a mismatched receiver.
A Logic for Strategy Updates
Venue: arXiv cs.GT 2011
Year: 2011

Notion of strategy in game theory is static and presumably constructed before the game play. The static, pre-determined notion of strategies falls short analyzing perfect information games. Because, we, people, do not strategize as such even in perfect information games - largely because we are not logically omniscient, and we have limited computational power and bounded memory. In this paper, we focus on what we call move updates where some moves become unavailable during the game. Our goal here is to present a formal framework for move based strategy restrictions extending strategy logic which was introduced by Ramanujam and Simon. In this paper, we present a dynamic version of strategy logic, prove its completeness and decidability along with the decidability of the strategy logic which was an open problem so far. We also present an analysis of centipede by using our logic.
Normative design using inductive learning
Venue: arXiv cs.LO 2011
Year: 2011

In this paper we propose a use-case-driven iterative design methodology for normative frameworks, also called virtual institutions, which are used to govern open systems. Our computational model represents the normative framework as a logic program under answer set semantics (ASP). By means of an inductive logic programming approach, implemented using ASP, it is possible to synthesise new rules and revise the existing ones. The learning mechanism is guided by the designer who describes the desired properties of the framework through use cases, comprising (i) event traces that capture possible scenarios, and (ii) a state that describes the desired outcome. The learning process then proposes additional rules, or changes to current rules, to satisfy the constraints expressed in the use cases. Thus, the contribution of this paper is a process for the elaboration and revision of a normative framework by means of a semi-automatic and iterative process driven from specifications of (un)desirable behaviour. The process integrates a novel and general methodology for theory revision based on ASP.
An end-to-end machine learning system for harmonic analysis of music
Venue: arXiv cs.SD 2011
Year: 2011

We present a new system for simultaneous estimation of keys, chords, and bass notes from music audio. It makes use of a novel chromagram representation of audio that takes perception of loudness into account. Furthermore, it is fully based on machine learning (instead of expert knowledge), such that it is potentially applicable to a wider range of genres as long as training data is available. As compared to other models, the proposed system is fast and memory efficient, while achieving state-of-the-art performance.
Distributed Planarization and Local Routing Strategies in Sensor Networks
Venue: arXiv cs.NI 2011
Year: 2011

We present an algorithm which computes a planar 2-spanner from an Unit Disk Graph when the node density is sufficient. The communication complexity in terms of number of node's identifier sent by the algorithm is $6n$, while the computational complexity is $O(nΔ)$, with $Δ$ the maximum degree of the communication graph. Furthermore, we present a simple and efficient routing algorithm dedicated to the computed graph. Last but not least, using traditional Euclidean coordinates, our algorithm needs the broadcast of as few as $3n$ node's identifiers. Under the hypothesis of sufficient node density, no broadcast at all is needed, reducing the previous best known complexity of an algorithm to compute a planar spanner of an Unit Disk Graph which was of $5n$ broadcasts.
Sparse approximation property and stable recovery of sparse signals from noisy measurements
Venue: arXiv cs.IT 2011
Year: 2011

In this paper, we introduce a sparse approximation property of order $s$ for a measurement matrix ${\bf A}$: $$\|{\bf x}_s\|_2\le D \|{\bf A}{\bf x}\|_2+ β\frac{σ_s({\bf x})}{\sqrt{s}} \quad {\rm for\ all} \ {\bf x},$$ where ${\bf x}_s$ is the best $s$-sparse approximation of the vector ${\bf x}$ in $\ell^2$, $σ_s({\bf x})$ is the $s$-sparse approximation error of the vector ${\bf x}$ in $\ell^1$, and $D$ and $β$ are positive constants. The sparse approximation property for a measurement matrix can be thought of as a weaker version of its restricted isometry property and a stronger version of its null space property. In this paper, we show that the sparse approximation property is an appropriate condition on a measurement matrix to consider stable recovery of any compressible signal from its noisy measurements. In particular, we show that any compressible signalcan be stably recovered from its noisy measurements via solving an $\ell^1$-minimization problem if the measurement matrix has the sparse approximation property with $β\in (0,1)$, and conversely the measurement matrix has the sparse approximation property with $β\in (0,\infty)$ if any compressible signal can be stably recovered from its noisy measurements via solving an $\ell^1$-minimization problem.
Competitive Auctions for Markets with Positive Externalities
Venue: arXiv cs.GT 2011
Year: 2011

In digital goods auctions, there is an auctioneer who sells an item with unlimited supply to a set of potential buyers, and the objective is to design truthful auction to maximize the total profit of the auctioneer. Motivated from an observation that the values of buyers for the item could be interconnected through social networks, we study digital goods auctions with positive externalities among the buyers. This defines a multi-parameter auction design problem where the private valuation of every buyer is a function of other winning buyers. The main contribution of this paper is a truthful competitive mechanism for subadditive valuations. Our competitive result is with respect to a new solution benchmark $\mathcal{F}^{(3)}$; on the other hand, we show a surprising impossibility result if comparing to the benchmark $\mathcal{F}^{(2)}$, where the latter has been used quite successfully in digital goods auctions without extenalities \cite{Goldberg2006}. Our results from $\mathcal{F}^{(2)}$ to $\mathcal{F}^{(3)}$ could be considered as the loss of optimal profit at the cost of externalities.
Non-Uniform Cellular Automata: classes, dynamics, and decidability
Venue: arXiv cs.FL 2011
Year: 2011

The dynamical behavior of non-uniform cellular automata is compared with the one of classical cellular automata. Several differences and similarities are pointed out by a series of examples. Decidability of basic properties like surjectivity and injectivity is also established. The final part studies a strong form of equicontinuity property specially suited for non-uniform cellular automata.
Multi Layer Analysis
Venue: arXiv cs.CV 2011
Year: 2011

This thesis presents a new methodology to analyze one-dimensional signals trough a new approach called Multi Layer Analysis, for short MLA. It also provides some new insights on the relationship between one-dimensional signals processed by MLA and tree kernels, test of randomness and signal processing techniques. The MLA approach has a wide range of application to the fields of pattern discovery and matching, computational biology and many other areas of computer science and signal processing. This thesis includes also some applications of this approach to real problems in biology and seismology.
Replicator Dynamics of Co-Evolving Networks
Venue: arXiv cs.GT 2011
Year: 2011

We propose a simple model of network co-evolution in a game-dynamical system of interacting agents that play repeated games with their neighbors, and adapt their behaviors and network links based on the outcome of those games. The adaptation is achieved through a simple reinforcement learning scheme. We show that the collective evolution of such a system can be described by appropriately defined replicator dynamics equations. In particular, we suggest an appropriate factorization of the agents' strategies that results in a coupled system of equations characterizing the evolution of both strategies and network structure, and illustrate the framework on two simple examples.
TDMA Achieves the Optimal Diversity Gain in Relay-Assisted Cellular Networks
Venue: arXiv cs.NI 2011
Year: 2011

In multi-access wireless networks, transmission scheduling is a key component that determines the efficiency and fairness of wireless spectrum allocation. At one extreme, greedy opportunistic scheduling that allocates airtime to the user with the largest instantaneous channel gain achieves the optimal spectrum efficiency and transmission reliability but the poorest user-level fairness. At the other extreme, fixed TDMA scheduling achieves the fairest airtime allocation but the lowest spectrum efficiency and transmission reliability. To balance the two competing objectives, extensive research efforts have been spent on designing opportunistic scheduling schemes that reach certain tradeoff points between the two extremes. In this paper and in contrast to the conventional wisdom, we find that in relay-assisted cellular networks, fixed TDMA achieves the same optimal diversity gain as greedy opportunistic scheduling. In addition, by incorporating very limited opportunism, a simple relaxed-TDMA scheme asymptotically achieves the same optimal system reliability in terms of outage probability as greedy opportunistic scheduling. This reveals a surprising fact: transmission reliability and user fairness are no longer contradicting each other in relay-assisted systems. They can be both achieved by the simple TDMA schemes. For practical implementations, we further propose a fully distributed algorithm to implement the relaxed-TDMA scheme. Our results here may find applications in the design of next-generation wireless communication systems with relay architectures such as LTE-advanced and WiMAX.
Deterministic Construction of an Approximate M-Ellipsoid and its Application to Derandomizing Lattice Algorithms
Venue: arXiv cs.CC 2011
Year: 2011

We give a deterministic O(log n)^n algorithm for the {\em Shortest Vector Problem (SVP)} of a lattice under {\em any} norm, improving on the previous best deterministic bound of n^O(n) for general norms and nearly matching the bound of 2^O(n) for the standard Euclidean norm established by Micciancio and Voulgaris (STOC 2010). Our algorithm can be viewed as a derandomization of the AKS randomized sieve algorithm, which can be used to solve SVP for any norm in 2^O(n) time with high probability. We use the technique of covering a convex body by ellipsoids, as introduced for lattice problems in (Dadush et al., FOCS 2011). Our main contribution is a deterministic approximation of an M-ellipsoid of any convex body. We achieve this via a convex programming formulation of the optimal ellipsoid with the objective function being an n-dimensional integral that we show can be approximated deterministically, a technique that appears to be of independent interest.
Iterative methods for solving the pressure problem at multiphase filtration
Venue: arXiv cs.NA 2011
Year: 2011

Applied problems of oil and gas recovery are studied numerically using the mathematical models of multiphase fluid flows in porous media. The basic model includes the continuity equations and the Darcy laws for each phase, as well as the algebraic expression for the sum of saturations. Primary computational algorithms are implemented for such problems using the pressure equation. In this paper, we highlight the basic properties of the pressure problem and discuss the necessity of their fulfillment at the discrete level. The resulting elliptic problem for the pressure equation is characterized by a non-selfadjoint operator. Possibilities of approximate solving the elliptic problem are considered using the iterative methods. Special attention is given to the numerical algorithms for calculating the pressure on parallel computers.
Application of Gammachirp Auditory Filter as a Continuous Wavelet Analysis
Venue: arXiv cs.SD 2011
Year: 2011

This paper presents a new method on the use of the gammachirp auditory filter based on a continuous wavelet analysis. The gammachirp auditory filter is designed to provide a spectrum reflecting the spectral properties of the cochlea, which is responsible for frequency analysis in the human auditory system. The impulse response of the theoretical gammachirp auditory filter that has been developed by Irino and Patterson can be used as the kernel for wavelet transform which approximates the frequency response of the cochlea. This study implements the gammachirp auditory filter described by Irino as an analytical wavelet and examines its application to a different speech signals. The obtained results will be compared with those obtained by two other predefined wavelet families that are Morlet and Mexican Hat. The results show that the gammachirp wavelet family gives results that are comparable to ones obtained by Morlet and Mexican Hat wavelet family.
Universal Prediction of Selected Bits
Venue: arXiv cs.LG 2011
Year: 2011

Many learning tasks can be viewed as sequence prediction problems. For example, online classification can be converted to sequence prediction with the sequence being pairs of input/target data and where the goal is to correctly predict the target data given input data and previous input/target pairs. Solomonoff induction is known to solve the general sequence prediction problem, but only if the entire sequence is sampled from a computable distribution. In the case of classification and discriminative learning though, only the targets need be structured (given the inputs). We show that the normalised version of Solomonoff induction can still be used in this case, and more generally that it can detect any recursive sub-pattern (regularity) within an otherwise completely unstructured sequence. It is also shown that the unnormalised version can fail to predict very simple recursive sub-patterns.
Asymptotically Optimal Agents
Venue: arXiv cs.AI 2011
Year: 2011

Artificial general intelligence aims to create agents capable of learning to solve arbitrary interesting problems. We define two versions of asymptotic optimality and prove that no agent can satisfy the strong version while in some cases, depending on discounting, there does exist a non-computable weak asymptotically optimal agent.
Closed Form Secrecy Capacity of MIMO Wiretap Channels with Two Transmit Antennas
Venue: arXiv cs.IT 2011
Year: 2011

A Gaussian multiple-input multiple-output (MIMO) wiretap channel model is considered. The input is a two-antenna transmitter, while the outputs are the legitimate receiver and an eavesdropper, both equipped with multiple antennas. All channels are assumed to be known. The problem of obtaining the optimal input covariance matrix that achieves secrecy capacity subject to a power constraint is addressed, and a closed-form expression for the secrecy capacity is obtained.
Minimization of Storage Cost in Distributed Storage Systems with Repair Consideration
Venue: arXiv cs.IT 2011
Year: 2011

In a distributed storage system, the storage costs of different storage nodes, in general, can be different. How to store a file in a given set of storage nodes so as to minimize the total storage cost is investigated. By analyzing the min-cut constraints of the information flow graph, the feasible region of the storage capacities of the nodes can be determined. The storage cost minimization can then be reduced to a linear programming problem, which can be readily solved. Moreover, the tradeoff between storage cost and repair-bandwidth is established.
Image Deblurring Using Derivative Compressed Sensing for Optical Imaging Application
Venue: arXiv cs.NA 2011
Year: 2011

Reconstruction of multidimensional signals from the samples of their partial derivatives is known to be a standard problem in inverse theory. Such and similar problems routinely arise in numerous areas of applied sciences, including optical imaging, laser interferometry, computer vision, remote sensing and control. Though being ill-posed in nature, the above problem can be solved in a unique and stable manner, provided proper regularization and relevant boundary conditions. In this paper, however, a more challenging setup is addressed, in which one has to recover an image of interest from its noisy and blurry version, while the only information available about the imaging system at hand is the amplitude of the generalized pupil function (GPF) along with partial observations of the gradient of GPF's phase. In this case, the phase-related information is collected using a simplified version of the Shack-Hartmann interferometer, followed by recovering the entire phase by means of derivative compressed sensing. Subsequently, the estimated phase can be combined with the amplitude of the GPF to produce an estimate of the point spread function (PSF), whose knowledge is essential for subsequent image deconvolution. In summary, the principal contribution of this work is twofold. First, we demonstrate how to simplify the construction of the Shack-Hartmann interferometer so as to make it less expensive and hence more accessible. Second, it is shown by means of numerical experiments that the above simplification and its associated solution scheme produce image reconstructions of the quality comparable to those obtained using dense sampling of the GPF phase.
Evolutionary Dynamics of Scientific Collaboration Networks: Multi-Levels and Cross-time Analysis
Venue: arXiv cs.SI 2011
Year: 2011

Several studies exist which use scientific literature for comparing scientific activities (e.g., productivity, and collaboration). In this study, using co-authorship data over the last 40 years, we present the evolutionary dynamics of multi level (i.e., individual, institutional and national) collaboration networks for exploring the emergence of collaborations in the research field of "steel structures". The collaboration network of scientists in the field has been analyzed using author affiliations extracted from Scopus between 1970 and 2009. We have studied collaboration distribution networks at the micro-, meso- and macro-levels for the 40 years. We compared and analyzed a number of properties of these networks (i.e., density, centrality measures, the giant component and clustering coefficient) for presenting a longitudinal analysis and statistical validation of the evolutionary dynamics of "steel structures" collaboration networks. At all levels, the scientific collaborations network structures were central considering the closeness centralization while betweenness and degree centralization were much lower. In general networks density, connectedness, centralization and clustering coefficient were highest in marco-level and decreasing as the network size grow to the lowest in micro-level. We also find that the average distance between countries about two and institutes five and for authors eight meaning that only about eight steps are necessary to get from one randomly chosen author to another.
Generating a Diverse Set of High-Quality Clusterings
Venue: arXiv cs.LG 2011
Year: 2011

We provide a new framework for generating multiple good quality partitions (clusterings) of a single data set. Our approach decomposes this problem into two components, generating many high-quality partitions, and then grouping these partitions to obtain k representatives. The decomposition makes the approach extremely modular and allows us to optimize various criteria that control the choice of representative partitions.