OpenRaiser/Intern-Atlas huggingface dataset:
Phase Retrieval via Wirtinger Flow: Theory and Algorithms
Venue: arXiv cs.IT 2015
Year: 2015

We study the problem of recovering the phase from magnitude measurements; specifically, we wish to reconstruct a complex-valued signal x of C^n about which we have phaseless samples of the form y_r = |< a_r,x >|^2, r = 1,2,...,m (knowledge of the phase of these samples would yield a linear system). This paper develops a non-convex formulation of the phase retrieval problem as well as a concrete solution algorithm. In a nutshell, this algorithm starts with a careful initialization obtained by means of a spectral method, and then refines this initial estimate by iteratively applying novel update rules, which have low computational complexity, much like in a gradient descent scheme. The main contribution is that this algorithm is shown to rigorously allow the exact retrieval of phase information from a nearly minimal number of random measurements. Indeed, the sequence of successive iterates provably converges to the solution at a geometric rate so that the proposed scheme is efficient both in terms of computational and data resources. In theory, a variation on this scheme leads to a near-linear time algorithm for a physically realizable model based on coded diffraction patterns. We illustrate the effectiveness of our methods with various experiments on image data. Underlying our analysis are insights for the analysis of non-convex optimization schemes that may have implications for computational problems beyond phase retrieval.
Private Multiplicative Weights Beyond Linear Queries
Venue: arXiv cs.DS 2015
Year: 2015

A wide variety of fundamental data analyses in machine learning, such as linear and logistic regression, require minimizing a convex function defined by the data. Since the data may contain sensitive information about individuals, and these analyses can leak that sensitive information, it is important to be able to solve convex minimization in a privacy-preserving way. A series of recent results show how to accurately solve a single convex minimization problem in a differentially private manner. However, the same data is often analyzed repeatedly, and little is known about solving multiple convex minimization problems with differential privacy. For simpler data analyses, such as linear queries, there are remarkable differentially private algorithms such as the private multiplicative weights mechanism (Hardt and Rothblum, FOCS 2010) that accurately answer exponentially many distinct queries. In this work, we extend these results to the case of convex minimization and show how to give accurate and differentially private solutions to *exponentially many* convex minimization problems on a sensitive dataset.
Training Sequence Design for Feedback Assisted Hybrid Beamforming in Massive MIMO Systems
Venue: arXiv cs.IT 2015
Year: 2015

The use of large-scale antenna systems in future commercial wireless communications is an emerging technology that uses an excess of transmit antennas to realize high spectral efficiency. Achieving potential gains with large-scale antenna arrays in practice hinges on sufficient channel estimation accuracy. Much prior work focuses on TDD based networks, relying on reciprocity between the uplink and downlink channels. However, most currently deployed commercial wireless systems are FDD based, making it difficult to exploit channel reciprocity. In massive MIMO FDD systems, the problem of channel estimation becomes even more challenging due to the attendant substantial training resources and feedback requirements which scale with the number of antennas. In this paper, we consider the problem of training sequence design that employs a set of training signals and its mapping to the training periods. We focus on reduced-dimension training sequence designs, along with transmit precoder designs, aimed at reducing both hardware complexity and power consumption. The resulting designs are extended to hybrid analog-digital beamforming systems, which employ a limited number of active RF chains for transmit precoding, by applying the Toeplitz distribution theorem to large-scale linear antenna systems. A practical guideline for training sequence parameter selection is presented along with performance analysis.
An Analytical Framework for Device-to-Device Communication in Cellular Networks
Venue: arXiv cs.IT 2015
Year: 2015

This paper presents a framework that enables characterizing analytically the spectral efficiency achievable by D2D (device-to-device) communication integrated with a cellular network. This framework is based on a stochastic geometry formulation with a novel approach to the modeling of interference and with the added possibility of incorporating exclusion regions to protect cellular receivers from excessive interference from active D2D transmitters. To illustrate the potential of the framework, a number of examples are provided. These examples confirm the potential of D2D communication in situations of strong traffic locality as well as the effectiveness of properly sized exclusion regions.
Efficient Steered-Response Power Methods for Sound Source Localization Using Microphone Arrays
Venue: arXiv cs.SD 2015
Year: 2015

This paper proposes an efficient method based on the steered-response power (SRP) technique for sound source localization using microphone arrays: the volumetric SRP (V-SRP). As compared to the SRP, by deploying a sparser volumetric grid, the V-SRP achieves a significant reduction of the computational complexity without sacrificing the accuracy of the location estimates. By appending a fine search step to the V-SRP, its refined version (RV-SRP) improves on the compromise between complexity and accuracy. Experiments conducted in both simulated- and real-data scenarios demonstrate the benefits of the proposed approaches. Specifically, the RV-SRP is shown to outperform the SRP in accuracy at a computational cost of about ten times lower.
Strong Converse Theorems for Classes of Multimessage Multicast Networks: A Rényi Divergence Approach
Venue: arXiv cs.IT 2015
Year: 2015

This paper establishes that the strong converse holds for some classes of discrete memoryless multimessage multicast networks (DM-MMNs) whose corresponding cut-set bounds are tight, i.e., coincide with the set of achievable rate tuples. The strong converse for these classes of DM-MMNs implies that all sequences of codes with rate tuples belonging to the exterior of the cut-set bound have average error probabilities that necessarily tend to one (and are not simply bounded away from zero). Examples in the classes of DM-MMNs include wireless erasure networks, DM-MMNs consisting of independent discrete memoryless channels (DMCs) as well as single-destination DM-MMNs consisting of independent DMCs with destination feedback. Our elementary proof technique leverages properties of the Rényi divergence.
Private Pareto Optimal Exchange
Venue: arXiv cs.GT 2015
Year: 2015

We consider the problem of implementing an individually rational, asymptotically Pareto optimal allocation in a barter-exchange economy where agents are endowed with goods and have preferences over the goods of others, but may not use money as a medium of exchange. Because one of the most important instantiations of such economies is kidney exchange -- where the "input"to the problem consists of sensitive patient medical records -- we ask to what extent such exchanges can be carried out while providing formal privacy guarantees to the participants. We show that individually rational allocations cannot achieve any non-trivial approximation to Pareto optimality if carried out under the constraint of differential privacy -- or even the relaxation of \emph{joint} differential privacy, under which it is known that asymptotically optimal allocations can be computed in two-sided markets, where there is a distinction between buyers and sellers and we are concerned only with privacy of the buyers~\citep{Matching}. We therefore consider a further relaxation that we call \emph{marginal} differential privacy -- which promises, informally, that the privacy of every agent $i$ is protected from every other agent $j \neq i$ so long as $j$ does not collude or share allocation information with other agents. We show that, under marginal differential privacy, it is possible to compute an individually rational and asymptotically Pareto optimal allocation in such exchange economies.
Joint Power Control and Fronthaul Rate Allocation for Throughput Maximization in OFDMA-based Cloud Radio Access Network
Venue: arXiv cs.IT 2015
Year: 2015

The performance of cloud radio access network (C-RAN) is constrained by the limited fronthaul link capacity under future heavy data traffic. To tackle this problem, extensive efforts have been devoted to design efficient signal quantization/compression techniques in the fronthaul to maximize the network throughput. However, most of the previous results are based on information-theoretical quantization methods, which are hard to implement due to the extremely high complexity. In this paper, we consider using practical uniform scalar quantization in the uplink communication of an orthogonal frequency division multiple access (OFDMA) based C-RAN system, where the mobile users are assigned with orthogonal sub-carriers for multiple access. In particular, we consider joint wireless power control and fronthaul quantization design over the sub-carriers to maximize the system end-to-end throughput. Efficient algorithms are proposed to solve the joint optimization problem when either information-theoretical or practical fronthaul quantization method is applied. Interestingly, we find that the fronthaul capacity constraints have significant impact to the optimal wireless power control policy. As a result, the joint optimization shows significant performance gain compared with either optimizing wireless power control or fronthaul quantization alone. Besides, we also show that the proposed simple uniform quantization scheme performs very close to the throughput performance upper bound, and in fact overlaps with the upper bound when the fronthaul capacity is sufficiently large. Overall, our results would help reveal practically achievable throughput performance of C-RAN, and lead to more efficient deployment of C-RAN in the next-generation wireless communication systems.
An Alloy Verification Model for Consensus-Based Auction Protocols
Venue: arXiv cs.SE 2015
Year: 2015

Max Consensus-based Auction (MCA) protocols are an elegant approach to establish conflict-free distributed allocations in a wide range of network utility maximization problems. A set of agents independently bid on a set of items, and exchange their bids with their first hop-neighbors for a distributed (max-consensus) winner determination. The use of MCA protocols was proposed, $e.g.$, to solve the task allocation problem for a fleet of unmanned aerial vehicles, in smart grids, or in distributed virtual network management applications. Misconfigured or malicious agents participating in a MCA, or an incorrect instantiation of policies can lead to oscillations of the protocol, causing, $e.g.$, Service Level Agreement (SLA) violations. In this paper, we propose a formal, machine-readable, Max-Consensus Auction model, encoded in the Alloy lightweight modeling language. The model consists of a network of agents applying the MCA mechanisms, instantiated with potentially different policies, and a set of predicates to analyze its convergence properties. We were able to verify that MCA is not resilient against rebidding attacks, and that the protocol fails (to achieve a conflict-free resource allocation) for some specific combinations of policies. Our model can be used to verify, with a "push-button" analysis, the convergence of the MCA mechanism to a conflict-free allocation of a wide range of policy instantiations.
Tractable Model for Rate in Self-Backhauled Millimeter Wave Cellular Networks
Venue: arXiv cs.IT 2015
Year: 2015

Millimeter wave (mmW) cellular systems will require high gain directional antennas and dense base station (BS) deployments to overcome high near field path loss and poor diffraction. As a desirable side effect, high gain antennas provide interference isolation, providing an opportunity to incorporate self-backhauling--BSs backhauling among themselves in a mesh architecture without significant loss in throughput--to enable the requisite large BS densities. The use of directional antennas and resource sharing between access and backhaul links leads to coverage and rate trends that differ significantly from conventional microwave ($μ$W) cellular systems. In this paper, we propose a general and tractable mmW cellular model capturing these key trends and characterize the associated rate distribution. The developed model and analysis is validated using actual building locations from dense urban settings and empirically-derived path loss models. The analysis shows that in sharp contrast to the interference limited nature of $μ$W cellular networks, the spectral efficiency of mmW networks (besides total rate) also increases with BS density particularly at the cell edge. Increasing the system bandwidth, although boosting median and peak rates, does not significantly influence the cell edge rate. With self-backhauling, different combinations of the wired backhaul fraction (i.e. the faction of BSs with a wired connection) and BS density are shown to guarantee the same median rate (QoS).
Weihrauch degrees of finding equilibria in sequential games
Venue: arXiv cs.LO 2015
Year: 2015

We consider the degrees of non-computability (Weihrauch degrees) of finding winning strategies (or more generally, Nash equilibria) in infinite sequential games with certain winning sets (or more generally, outcome sets). In particular, we show that as the complexity of the winning sets increases in the difference hierarchy, the complexity of constructing winning strategies increases in the effective Borel hierarchy.
Optimal User-Cell Association for Massive MIMO Wireless Networks
Venue: arXiv cs.NI 2015
Year: 2015

The use of a very large number of antennas at each base station site (referred to as "Massive MIMO") is one of the most promising approaches to cope with the predicted wireless data traffic explosion. In combination with Time Division Duplex and with simple per-cell processing, it achieves large throughput per cell, low latency, and attractive power efficiency performance. Following the current wireless technology trend of moving to higher frequency bands and denser small cell deployments, a large number of antennas can be implemented within a small form factor even in small cell base stations. In a heterogeneous network formed by large (macro) and small cell BSs, a key system optimization problem consists of "load balancing", that is, associating users to BSs in order to avoid congested hot-spots and/or under-utilized infrastructure. In this paper, we consider the user-BS association problem for a massive MIMO heterogeneous network. We formulate the problem as a network utility maximization, and provide a centralized solution in terms of the fraction of transmission resources (time-frequency slots) over which each user is served by a given BS. Furthermore, we show that such a solution is physically realizable, i.e., there exists a sequence of integer scheduling configurations realizing (by time-sharing) the optimal fractions. While this solution is optimal, it requires centralized computation. Then, we also consider decentralized user-centric schemes, formulated as non-cooperative games where each user makes individual selfish association decisions based only on its local information. We identify a class of schemes such that their Nash equilibrium is very close to the global centralized optimum. Hence, these user-centric algorithms are attractive not only for their simplicity and fully decentralized implementation, but also because they operate near the system "social" optimum.
Data granulation by the principles of uncertainty
Venue: arXiv cs.AI 2015
Year: 2015

Researches in granular modeling produced a variety of mathematical models, such as intervals, (higher-order) fuzzy sets, rough sets, and shadowed sets, which are all suitable to characterize the so-called information granules. Modeling of the input data uncertainty is recognized as a crucial aspect in information granulation. Moreover, the uncertainty is a well-studied concept in many mathematical settings, such as those of probability theory, fuzzy set theory, and possibility theory. This fact suggests that an appropriate quantification of the uncertainty expressed by the information granule model could be used to define an invariant property, to be exploited in practical situations of information granulation. In this perspective, a procedure of information granulation is effective if the uncertainty conveyed by the synthesized information granule is in a monotonically increasing relation with the uncertainty of the input data. In this paper, we present a data granulation framework that elaborates over the principles of uncertainty introduced by Klir. Being the uncertainty a mesoscopic descriptor of systems and data, it is possible to apply such principles regardless of the input data type and the specific mathematical setting adopted for the information granules. The proposed framework is conceived (i) to offer a guideline for the synthesis of information granules and (ii) to build a groundwork to compare and quantitatively judge over different data granulation procedures. To provide a suitable case study, we introduce a new data granulation technique based on the minimum sum of distances, which is designed to generate type-2 fuzzy sets. We analyze the procedure by performing different experiments on two distinct data types: feature vectors and labeled graphs. Results show that the uncertainty of the input data is suitably conveyed by the generated type-2 fuzzy set models.
Robust analysis $\ell_1$-recovery from Gaussian measurements and total variation minimization
Venue: arXiv cs.IT 2015
Year: 2015

Analysis $\ell_1$-recovery refers to a technique of recovering a signal that is sparse in some transform domain from incomplete corrupted measurements. This includes total variation minimization as an important special case when the transform domain is generated by a difference operator. In the present paper we provide a bound on the number of Gaussian measurements required for successful recovery for total variation and for the case that the analysis operator is a frame. The bounds are particularly suitable when the sparsity of the analysis representation of the signal is not very small.
Privacy and Truthful Equilibrium Selection for Aggregative Games
Venue: arXiv cs.DS 2015
Year: 2015

We study a very general class of games --- multi-dimensional aggregative games --- which in particular generalize both anonymous games and weighted congestion games. For any such game that is also large, we solve the equilibrium selection problem in a strong sense. In particular, we give an efficient weak mediator: a mechanism which has only the power to listen to reported types and provide non-binding suggested actions, such that (a) it is an asymptotic Nash equilibrium for every player to truthfully report their type to the mediator, and then follow its suggested action; and (b) that when players do so, they end up coordinating on a particular asymptotic pure strategy Nash equilibrium of the induced complete information game. In fact, truthful reporting is an ex-post Nash equilibrium of the mediated game, so our solution applies even in settings of incomplete information, and even when player types are arbitrary or worst-case (i.e. not drawn from a common prior). We achieve this by giving an efficient differentially private algorithm for computing a Nash equilibrium in such games. The rates of convergence to equilibrium in all of our results are inverse polynomial in the number of players $n$. We also apply our main results to a multi-dimensional market game. Our results can be viewed as giving, for a rich class of games, a more robust version of the Revelation Principle, in that we work with weaker informational assumptions (no common prior), yet provide a stronger solution concept (ex-post Nash versus Bayes Nash equilibrium). In comparison to previous work, our main conceptual contribution is showing that weak mediators are a game theoretic object that exist in a wide variety of games -- previously, they were only known to exist in traffic routing games.
An Approximate Inner Bound to the QoS Aware Throughput Region of a Tree Network under IEEE 802.15.4 CSMA/CA and Application to Wireless Sensor Network Design
Venue: arXiv cs.NI 2015
Year: 2015

We consider a tree network spanning a set of source nodes that generate measurement packets, a set of additional relay nodes that only forward packets from the sources, and a data sink. We assume that the paths from the sources to the sink have bounded hop count. We assume that the nodes use the IEEE 802.15.4 CSMA/CA for medium access control, and that there are no hidden terminals. In this setting, starting with a set of simple fixed point equations, we derive sufficient conditions for the tree network to approximately satisfy certain given QoS targets such as end-to-end delivery probability and delay under a given rate of generation of measurement packets at the sources (arrival rates vector). The structures of our sufficient conditions provide insight on the dependence of the network performance on the arrival rate vector, and the topological properties of the network. Furthermore, for the special case of equal arrival rates, default backoff parameters, and for a range of values of target QoS, we show that among all path-length-bounded trees (spanning a given set of sources and BS) that meet the sufficient conditions, a shortest path tree achieves the maximum throughput.
On Practical Regular Expressions
Venue: arXiv cs.FL 2015
Year: 2015

We report on simulation, hierarchy, and decidability results for Practical Regular Expressions (PRE), which may include back references in addition to the standard operations union, concatenation, and star. The following results are obtained: PRE can be simulated by the classical model of nondeterministic finite automata with sensing one-way heads. The number of heads depends on the number of different variables in the expressions. A space bound O(n log m) for matching a text of length m with a PRE with n variables based on the previous simulation. This improves the bound O(nm) from (Câmpeanu and Santean 2009). PRE cannot be simulated by deterministic finite automata with at most three sensing one-way heads or deterministic finite automata with any number of non-sensing one-way heads. PRE with a bounded number of occurrences of variables in any match can be simulated by nondeterministic finite automata with one-way heads. There is a tight hierarchy of PRE with a growing number of non-nested variables over a fixed alphabet. A previously known hierarchy was based on nested variables and growing alphabets (Larsen 1998). Matching of PRE without star over a single-letter alphabet is NP-complete. This strengthens the corresponding result for expressions over larger alphabets and with star (Aho 1990). Inequivalence of PRE without closure operators is Sigma^P_2-complete. The decidability of universality of PRE over a single letter alphabet is linked to the existence of Fermat Primes. Greibach's Theorem applies to languages characterized by PRE.