Keywords:Learning and Inference, Data Analytics, Statistical Signal Processing Abstract: Cross–validation (CV) is a technique for evaluating the ability of statistical models/learning systems based on a given data set. Despite its wide applicability, the rather heavy computational cost can prevent its use as the system size grows. To resolve this difficulty in the case of Bayesian linear regression, we develop a formula for evaluating the leave-one-out CV error approximately without actually performing CV. The usefulness of the developed formula is tested by statistical mechanical analysis for a synthetic model. This is confirmed by application to a realworld supernova data set as well.

Keywords:Machine Learning and Learning Theory, Information Theory and Statistics, Detection and Estimation Abstract: We consider the problem of Gaussian mixture clustering in the high-dimensional limit where the data consists of m points in n dimensions, and n,m rightarrow infty and alpha = m/n stays finite. Using methods from statistical physics, we determine the critical value of alpha and the distance between the clusters at which it becomes information-theoretically possible to reconstruct the membership into clusters better than chance, and determine the accuracy achievable by the Bayes-optimal estimation algorithm. In particular, we find that when the number of clusters is sufficiently large, r > 4 + 2 sqrt{alpha}, there is a gap between the threshold for information-theoretically optimal performance and the threshold at which known algorithms succeed.

Keywords:Coding Theory, Data Analytics, Machine Learning and Learning Theory Abstract: Two important recent trends are the proliferation of learning algorithms along with the massive increase of data stored on unreliable storage mediums. These trends impact each other; noisy data can have an undesirable effect on the results provided by learning algorithms. Although traditional tools exist to improve the reliability of data storage devices, these tools operate at a different abstraction level and therefore ignore the data application, leading to an inefficient use of resources. In this paper we propose taking the operation of learning algorithms into account when deciding how to best protect data. Specifically, we examine several learning algorithms that operate on data that is stored on noisy mediums and protected by error-correcting codes with a limited budget of redundancy; we develop a principled way to allocate resources so that the harm on the output of the learning algorithm is minimized.

Keywords:Coding Theory, Data Storage, Coding Techniques and Applications Abstract: In distributed storage systems, multiple storage node failures are frequent and efficiently recovering them is crucial for high system performance. In this work, we consider the problem of repairing multiple failures in a centralized way, which can be desirable in many data storage configurations. We first establish the tradeoff between the repair bandwidth and the storage size for functional repair. Using a graph-theoretic approach, the optimal tradeoff is identified as the solution to an integer optimization problem, for which we derive a closed-form expression. When the number of erasures e satisfies e ge k, k being the minimum number of nodes needed to reconstruct the entire data, the tradeoff reduces to a single point, for which we provide an explicit code construction. Expressions of the extreme points, namely the minimum storage multi-node repair (MSMR) and minimum bandwidth multi-node repair (MBMR) points, are also derived. Furthermore, we prove that functional MBMR point is not achievable for linear exact repair codes. Finally, for emid k and e mid d, where d is the number of helper nodes during repair, we show that the functional repair tradeoff is not achievable under exact repair, except for maybe a small portion near the MSMR point, which parallels the results for single erasure repair by Shah et al.

Keywords:Information Theory and Statistics, Coding Theory, Learning and Inference Abstract: We consider the estimation of a signal from the knowledge of its noisy linear random Gaussian projections, a problem relevant in compressed sensing, sparse superposition codes or code division multiple access just to cite few. There has been a number of works considering the mutual information for this problem using the heuristic replica method from statistical physics. Here we put these considerations on a firm rigorous basis. First, we show, using a Guerra-type interpolation, that the replica formula yields an upper bound to the exact mutual information. Secondly, for many relevant practical cases, we present a converse lower bound via a method that uses spatial coupling, state evolution analysis and the I-MMSE theorem. This yields, in particular, a single letter formula for the mutual information and the minimal-mean-square error for random Gaussian linear estimation of all discrete bounded signals.

Keywords:Information Theory and Statistics, Information Theory, Learning and Inference Abstract: The spectral structure of conditional expectation operators underlies several useful notions in statistics and information theory. For instance, the second largest singular value of such an operator is known as maximal correlation, which has received considerable attention in the context of performing non-linear regression and analyzing contraction coefficients. Given source-channel pairs, we study the singular value decompositions of the corresponding conditional expectation operators, and derive necessary and sufficient conditions on the conditional moments that characterize when the conditional expectation operators have singular vectors that are orthogonal polynomials. Furthermore, we illustrate that conditional expectation operators constructed using well-known natural exponential families with quadratic variance functions and their conjugate priors have orthogonal polynomial singular vectors. In particular, the Gaussian source and Gaussian channel beget the Hermite case, the gamma source and Poisson channel beget the Laguerre case, and the beta source and binomial channel beget the Jacobi case.

Keywords:Information Theory and Statistics, Information Theory Abstract: Atypicality is a new concept that uses a codelength-based deviation from the norm to ﬁnd the interesting rare events. In a previous paper we have developed an information theoretic approach for discrete data. Then in the two other papers, we came up with an extension to the real-valued models for Gaussian and vector Gaussian cases. In the current paper we generalize our real-valued model to the class of exponential family. We include a comprehensive table that summarize the approximated atypicality criterion and bounds for common distributions in the exponential family model.

Keywords:Information Theory and Statistics Abstract: Binary hypothesis testing under the Neyman-Pearson formalism is a statistical inference framework for distinguishing data generated by two different source distributions. Privacy restrictions may require the curator of the data or the data respondents themselves to share data with the test only after applying a randomizing privacy mechanism. Using mutual information as the privacy metric and the relative entropy between the two distributions of the output (postrandomization) source classes as the utility metric (motivated by the Chernoff-Stein Lemma), this work focuses on finding an optimal mechanism that maximizes the chosen utility function while ensuring that the mutual information based leakage for both source distributions is bounded. Focusing on the high privacy regime, an Euclidean information-theoretic (E-IT) approximation to the tradeoff problem is presented. It is shown that the solution to the E-IT approximation is independent of the alphabet size and clarifies that a mutual information based privacy metric preserves the privacy of the source symbols in inverse proportion to their likelihood.

Keywords:Learning and Inference, Detection and Estimation, Information Theory and Statistics Abstract: Data clustering is a core problem in many fields of science and engineering. Community recovery in graphs is one popular approach to data clustering, and it has received significant attention due to its wide applicability to social network applications, protein complex detection, shape matching, image segmentation, etc. While the community recovery in graphs has been extensively studied in the literature, the problem of community recovery in hypergraphs has not been studied much. In this paper, we study the generalized Censored Block Model (CBM), where observations consist of randomly chosen hyperedges of size d, each of which is associated with the modulo-2 sum of the values of the nodes in the hyperedge, corrupted by Bernoulli noise. We characterize the information-theoretic limit of the community recovery in hypergraphs. Our results are for the general cases of arbitrarily scaling d.

Keywords:Network Information Theory, Wireless Communication Systems, Sensor Networks in Communications Abstract: We study the energy efficiency of wireless transmissions for a class of networks where a large number of proximal nodes co-operate over the wireless medium to reliably decode the message from a distant transmitter (the source). The objective is to minimize the sum total of energy expenditure (per bit) over all transmissions in the network. The wireless medium is assumed to be affected by Gaussian noise and symmetric fading with the channel state information known at the receivers but not at the transmitters. Furthermore, we assume the possibility of wideband communication and no delay constraints.

In a network with k proximal nodes, where the links amongst the nodes are much better than the link between the source and the nodes, the lower bound on the energy per bit could reduce by as much as k^{-1} (in k) up to a certain point. This suggests a large potential benefit in co-operating with proximal nodes. We first propose and analyze an estimate-and-forward transmission scheme inspired by the Gaussian CEO problem but show that it does not have such an asymptotic behavior (in k) under most conditions. Next, we propose a simple, uncoded aggregate-and-forward scheme and show that it has an almost optimal asymptotic behavior.

Keywords:Network Information Theory, Information Theory Abstract: Shannon determined that the zero-error capacity of a point-to-point channel whose channel p(y|x) has confusability matrix G_{X|Y} is positive if and only if there exist two inputs that are “non-adjacent”, which Massey rephrased as “non- confusable”. Equivalently, it is non-zero if and only if the independence number of GX|Y is strictly greater than 1. An expression for the capacity of the channel with confusability graph G is known (though it is generally multi-letter), and is given by the normalized limit (as the blocklength n → ∞) of the maximum independent set of the n-fold strong product of G. This is not generally computable with known methods. In this paper, we look at the zero-error capacity of four multi-user channels: the relay, the multiple-access (MAC), the broadcast (BC), and the interference (IC) channels. Before looking for expressions for the capacity (region) of such channels – which will be multi-letter until proven otherwise – we find necessary and sufficient conditions under which the zero-error capacity is strictly positive.

Keywords:Network Information Theory Abstract: This paper considers the two-user Gaussian interference channel in the presence of one or two adversarial jammers. Existing outer and inner bounds for the Gaussian interference channel are generalized in the presence of the jammer(s). We show that for certain problem parameters, precisely the same bounds hold, but with the noise variance increased by the received power of the jammer at each receiver. Thus, the jammers can do no better than to transmit Gaussian noise. For these problem parameters, this allows us to recover the half-bit theorem. Moreover, we show that, if the jammer has greater received power than the legitimate user, symmetrizability makes the capacity zero. The proof of the outer bound is straightforward, while the inner bound generalizes the Han-Kobayashi rate splitting scheme. As a novel aspect, the inner bound takes advantage of the common message acting as common randomness for the private message; hence, the jammer cannot symmetrize only the private codeword without being detected. We also prove a new version of a packing lemma for the Gaussian arbitrarily-varying channel.

Keywords:Network Information Theory, Information Theory Abstract: This paper investigates the joint source-channel coding problem of sending two correlated memoryless sources with common part over a memoryless multiple access channel (MAC). An inner bound and two outer bounds on the achievable distortion region are derived. In particular, they respectively recover the existing bounds for several special cases, such as communication without common part, lossless communication, and noiseless communication. When specialized to quadratic Gaussian communication case, the inner bound and outer bound are used to generate two new bounds. Numerical result shows that common part improves the performance of such distributed communication system.

Keywords:Network Information Theory Abstract: We consider the transmission of a common message from a transmitter to two receivers over a broadcast channel, also called a multicast channel in this case. The two receivers are allowed to cooperate with each other in full-duplex over non-orthogonal cooperation links. We investigate the information-theoretic upper and lower bounds on the broadcast rate. In particular, we propose a two-round cooperation scheme in which the receivers interactively perform compress-forward (CF) and then decode-forward (DF) to improve the achievable rate. Numerical results compare the proposed scheme to existing schemes and the cutset upper bound in the Gaussian case. We show that the proposed scheme outperforms the non-interactive DF and CF schemes as well as the noisy network coding scheme. The gain over the DF scheme becomes larger when the main channel becomes symmetric, while the gain over the CF scheme becomes larger when the main channel becomes asymmetric.

Keywords:Optimization, Data Analytics, Machine Learning and Learning Theory Abstract: Demand response is designed to motivate electricity customers to modify their loads at critical time periods. The accurate estimation of impact of demand response signals to customers' consumption is central to any successful program. In practice, learning these response is nontrivial because operators can only send a limited number of signals. In addition, customer behavior also depends on a large number of exogenous covariates. These two feature lead to a high dimensional inference problem with limited number of observations. In this paper, we formulate this problem using a multivariate linear model and adopt an experimental design approach to estimate the impact of demand response signals. We show that randomized assignment, which is widely used to estimate the average treatment effect, is not efficient in reducing the variance of the estimator when a large number of covariates is present. In contrast, we present a tractable algorithm that strategically assigns demand response signals to customers. This algorithm achieves the optimal reduction in estimation variance, independent of the number of covariates. The results are validated from simulations on synthetic data.

Keywords:Pricing and Congestion Control, Machine Learning and Learning Theory, Optimization Abstract: In this work, we address the profit maximization problem for a wireless network carrier and payment minimization for end-users with unknown demand profile. In particular, we address the exploration-exploitation tradeoff that faces the carrier who is unaware of users demand profiles and seeks to maximize its expected profit by applying smart pricing to incentivize users to apply proactive caching. We formulate the problem as a reinforcement learning problem where the carrier minimizes the regret defined as the difference between the profit obtained by a genie who knows the demand profile of all users and that obtained by the given policy over a finite horizon D. Users, on the other hand, harness their predictable demands in proactively caching peak time demand to minimize their expected payments. We show that the carrier needs only to know the distribution of users demand profile in order to converge to the same profit of the case when it has an access to the demand profile, hence preserving users privacy. An iterative gradient-based policy is proposed to minimize the regret. Numerical results are provided where the proposed policy is compared with the UCB1 algorithm.

Keywords:Optimization, Distributed and Large-Scale Systems, Computational Models and Representations Abstract: Minimum cost network flow problems appear in a wide range of applications including general network optimization problems, transportation systems, electricity networks and information networks. In these applications, the underlying physical layer of the systems can generate a very large graph resulting in an optimization problem with a large decision variable space. Various arc and node based cyber layer layouts have been proposed to solve this problem in a distributed manner. In this paper, for a physical layer network of n nodes and m arcs with biconnected graph topology, we take advantage of the cycle basis concept in the graph theory to reduce the search variables of an optimal network flow from m to m-n+1 variables. We show that our proposed new formulation of the optimal network flow problem is amenable to a distributed solution using alternating direction method of multipliers (ADMM) method via a cyber layer whose nodes are defined based on the fundamental cycles of a cycle basis of the physical layer graph. We demonstrate the performance of our algorithm through a numerical example.

Keywords:Optimization, Wireless Communication Systems, Pricing and Congestion Control Abstract: The increase in demand for spectrum-based services forms a bottleneck in wireless networks. Device-to-Device (D2D) caching networks tackle this problem by exploiting users behavior predictability and the possibility of sharing data between them to alleviate network congestion. Usually, network congestion occurs at certain times of the day and in some popular locations. Consequently, the information about user's demand alone is not enough. Capturing mobility statistics allows Service Providers (SPs) to enhance their caching strategies. In this work, we introduce a mobility-aware centralized D2D caching network where a SP harnesses users demand and mobility statistics to minimize the incurred service cost through an optimal caching policy. However, the complexity of the optimal caching policy grows exponentially with the number of users. Therefore, we discuss a greedy caching algorithm which has a polynomial order complexity. We also use this greedy algorithm to establish upper and lower bounds on the proactive service gain achieved by the optimal caching policy.

Keywords:Optimization, Adaptive Control and Automation, Performance Analysis Abstract: The problem of stochastic deadline scheduling is considered. A constrained Markov decision process model is introduced in which jobs arrive randomly at a service center with stochastic job sizes, rewards, and completion deadlines. The service provider faces random processing costs, convex non-completion penalties, and a capacity constraint that limits the simultaneous processing of jobs. Formulated as a restless multi-armed bandit problem, the stochastic deadline scheduling problem is shown to be indexable. A closed-form expression of the Whittle’s index is obtained for the case when the processing costs are constant. An upper bound on the gap-to-optimality of the Whittle’s index policy is established and the bound is shown to converge to zero as the job arrival rate and the the number of simultaneously available processors increase simultaneously.

Keywords:Information Theory Abstract: Given a set V of n nodes (or elements or points), consider the simple problem of clustering them into k clusters, where k is unknown. We rigorously study for the first time the classical query complexity of such clustering, where given elements u in V and vin V, a {em query} asks whether u,v belong to the same cluster or not, and the goal is to minimize the number of such queries to correctly reconstruct the clusters. When the answer to each query is correct, a simple lower and upper bound of Theta(nk) on query complexity can be shown. A major contribution of this paper is to show how only a mild side information (mutual information > 0) in the form of a similarity matrix lead to a {em great reduction} in query complexity to O(k^2). This remains true even when the answer of each query can be erroneous with certain probability and `resampling' is not allowed. Note that this bound can be significantly sublinear in n depending on the value of k. To show our lower bounds we introduce new general information theoretic methods; as well as use, in completely novel way, information theoretic inequalities to design efficient algorithms for clustering with near-optimal complexity. We believe our techniques both for the lower and upper bounds are of general interest.

Keywords:Network Games and Algorithms Abstract: A descending price algorithm based auction mech- anism in a two-sided matching market is proposed in this paper to determine market clearing prices. For general valuations with a intelligent choice of reverse constricted sets, we prove that the algorithm converges in a finite number of rounds. Then specializing to the rank one valuations in sponsored search markets, the proposed algorithm yields the element-wise maximum market clearing price.

If we know the time at which various nodes were infected, we can attempt to use this information in order to identify the source. However, maintaining observer nodes that can provide their infection time may be costly, and we may have a budget k on the number of observer nodes we can maintain.

Moreover, some nodes are more informative than others due to their location in the network.

Hence, a pertinent question arises: Which nodes should we select as observers in order to maximize the probability that we can accurately identify the source?

Inspired by the simple setting in which the node-to-node delays in the transmission of the epidemic are deterministic, we develop a principled approach for addressing the problem even when transmission delays are random. We show that the optimal observer-placement differs depending on the variance of the transmission delays and propose approaches in both low- and high-variance settings.

We validate our methods by comparing them against state-of-the-art observer-placements and show that, in both settings, our approach identifies the source with higher accuracy.

Keywords:Detection and Estimation, Statistical Signal Processing Abstract: Stochastic hybrid systems (SHS) represent a class of dynamical systems that involve the interaction of continuous and discrete dynamics with uncertainty. In SHS, the evolution of continuous states is described by stochastic differential equation (SDE), and discrete dynamics are modeled via a random process. In this paper, our focus is on a specific type of SHS in which the discrete state transitions depend on the continuous dynamics, referred to as guard conditions. Specifically, we develop and analyze state estimation strategies for SHS with guard conditions described via a quadratic form of continuous states. Approximate analytical results on the performance of the estimator are derived and validated using simulations. These results show that the proposed estimation strategy outperforms existing approaches in terms of estimation accuracy.

Keywords:Detection and Estimation, Coding Theory, Statistical Signal Processing Abstract: In this paper, we consider the compressive sensing (CS) problem in the presence of noise. The problem is to recover a K-sparse signal sin R^{n} from noisy linear measurements y = As+w. We propose a fast recovery algorithm that can reconstruct any K-sparse signal s with time complexity that grows linearly in K and sublinearly in n. Specifically, with high probability, our algorithm is able to recover an arbitrarily large fraction of the support of the sparse signal using Theta(Klog(n)loglog(n)) samples and Theta(Klog^{1+r}(n)) computational cost, where r>0 is an arbitrarily small constant. The sample and time complexities are near order-optimal. Further, our algorithm is able to recover the exact support with Theta(Klog(K)log(n)loglog(n)) measurements and time complexity of Theta(Klog(K)log^{1+r}(n)). With a mild technical assumption on the existence of a code with universal decoding algorithm and small decoding complexity, our algorithm can achieve Theta(Klog(n)) sample and time complexities for the large fraction recovery, and furthermore, Theta(Klog(K)log(n)) sample and time complexities for the full support recovery. The design of measurements and the recovery algorithm are based on sparse graph codes. We also justify our theoretical results with numerical experiments.

Keywords:Detection and Estimation, Statistical Signal Processing Abstract: Detection rules have traditionally been designed for rational agents that minimize the Bayes risk (average decision cost). With the advent of crowd-sensing systems, there is a need to redesign binary hypothesis testing rules for behavioral agents, whose cognitive behavior is not captured by traditional utility functions such as Bayes risk. In this paper, we adopt prospect theory based models for decision makers. We consider special agent models namely optimists and pessimists in this paper, and derive optimal detection rules under different scenarios. Using an illustrative example, we also show how the decision rule of a human agent deviates from the Bayesian decision rule under various behavioral models, considered in this paper.

Keywords:Detection and Estimation, Statistical Signal Processing, Data Analytics Abstract: Seismic event picking plays a key role in seismology studies. The goal of seismic event picking is to detect the onset of a seismic event, which typically causes an increase in the amplitude of the recorded signal. In this paper, we present a sequential change-point detection method for online seismic event detection, based on the generalized maximum likelihood statistic. We assume that the signals prior to the event are i.i.d. Gaussian random variables with zero mean and known variance, and after the event are i.i.d. Gaussian with zero mean and an {it increased} unknown variance. We form a generalized likelihood ratio (GLR) based statistic by replacing the unknown variance with its maximum likelihood estimate, which takes a simple form and has a recursive implementation. An event is detected whenever the statistic exceeds a prescribed threshold. We compare the performance of our GLR procedure relative to the commonly used short-term-average/long-term-average (STA/LTA) algorithm, which is the state-of-the-art for seismic event detection, using large-scale seismic dataset and demonstrate the benefits of our GLR statistic. We also present a joint detection method to utilize the capability of seismic sensors to record signals through three independent channels, to achieve much better detection performance. We also present a method to combine GLR procedure with P-wave and S-wave filtering.

Keywords:Detection and Estimation Abstract: The advent of emerging fields such as networked control systems and wireless sensor networks involving information flow over bandwidth-constrained digital channels has presented the control and information theory communities with a new set of challenges. One of these challenges is to accurately estimate the trajectory of (stochastic) nonlinear systems using sampled and quantized state measurements transmitted over a finite-bandwidth digital channel. This has led researchers to study these problems by combining notions from both control and communication domains, two fields which have been traditionally treated separately. A recent notion introduced in this context is called estimation entropy, which has been defined as the minimum bite rate required to estimate the trajectory of a deterministic nonlinear system with a given exponential convergence rate. In this paper, we show that this notion can be extended to continuous-time stochastic systems as well, particularly, a class of stochastic hybrid systems. We also provide an upper bound on the estimation entropy for this class of systems.

Keywords:Detection and Estimation, Signal Acquisition, Coding, and Retrieval Abstract: We pose the image reconstruction problem for pictures distorted by rolling shutter as an observability problem. In particular, we study the observability properties of linear systems of whom measurements are taken with a pixel-by-pixel evaluation. We do not concentrate on the technical process behind rolling shutter, but introduce and study it as a systems theoretic property. Assuming recurrences in the time series of pictures which we aim to reconstruct, we derive resonance-like conditions for observability.

Centre for Wireless Communications (CWC), Univ. of Oulu

Keywords:Network Games and Algorithms, Performance Analysis, Optimization Abstract: Abstract—To meet the ever growing need for wireless spectrum, the Federal Communication Commision (FCC) introduced the concept of 3-Tier Sharing Framework. In this model, underutilized federal spectrum will be released for shared use where the highest preference will be given to Tier-1 followed by Tier-2 and then Tier-3. In this paper, we contribute to the spectrum sharing literature by presenting a model where a wireless operator, who is interested in maximizing its profit, can operate as a Tier-2 and/or a Tier-3 user. Tier-2 is characterized by paid but “almost” guaranteed and interference free channel access while Tier-3 access is free but has lesser guarantee and also faces channel interference. So the operator has to optimally decide between paid but better channel quality and free but degraded channel quality. Also, the operator has to make these decisions without knowing future market parameters like customer demands or channel availability. We use tools from ski-rental literature to design a deterministic online algorithm for leasing channels which does not rely on the knowledge of market statistics. The efficiency of the online algorithm is analyzed by deriving its competitive ratio (CR) and by conducting simulations. The mathematical model for leasing channels is a novel generalization of the classical ski-rental problem. We therefore make fundamental contribution to ski-rental literature which has diverse applications beyond the problem considered in this paper.

Keywords:Network Coding, Network Information Theory, Coding Techniques and Applications Abstract: Universal security over a network with linear network coding has been intensively studied. However, previous linear codes used for this purpose were linear over a larger field than that used on the network. In this work, we introduce new parameters (relative dimension/rank support profile and relative generalized matrix weights) for linear codes that are linear over the field used in the network, measuring the universal security performance of these codes. The proposed new parameters enable us to use optimally universal secure linear codes on noiseless networks for all possible parameters, as opposed to previous works, and also enable us to add universal security to the recently proposed list-decodable rank-metric codes by Guruswami et al. We give several properties of the new parameters: monotonicity, Singleton-type lower and upper bounds, a duality theorem, and definitions and characterizations of equivalences of linear codes. Finally, we show that our parameters strictly extend relative dimension/length profile and relative generalized Hamming weights, respectively, and relative dimension/intersection profile and relative generalized rank weights, respectively. Moreover, we show that generalized matrix weights are larger than Delsarte generalized weights.

Keywords:Network Games and Algorithms, Sensor Networks, Optimization Abstract: We consider the problem of detecting security failures caused by a resource-constrained attacker using randomized sensing strategies. We propose a game-theoretic model in which the objective of the attacker (resp. defender) is to maximize the number of undetected attacks (resp. detections) on the network. Our game is strategically equivalent to a zero-sum game. Thus, the Nash Equilibria (NE) solution can be found by solving two linear programming (LP) problems. Still, characterization of equilibrium strategies is not tractable for large-scale networks. We assume that the defender's (resp. attacker's) detection (resp. attack) budget is limited relative to the size of the network. Under this assumption, we provide structural results on the equilibrium payoffs based on the players' resources and the size of the minimum set covers. We show that an equilibrium strategy of the defender is to choose a randomized sensing strategy that spans a minimum set cover. This result significantly improves the tractability of NE computation, and provides some practical insights on network sensing in adversarial environments.

Keywords:Network Games and Algorithms Abstract: Wireless networks implementing dynamic channel assignment mechanisms are vulnerable to stealthy decoy attacks that aim to disrupt natural network operation by creating cascading channel conflicts. This paper develops a game-theoretic defense strategy in which a network administrator makes judicious adjustments of the transmission footprint of the various nodes, thereby continuously adapting the underlying network topology. The defense strategy is a mixed-strategy Nash equilibrium of a formulated 2-player zero-sum game between the admin and the attacker. As the space of strategies of the admin grows exponentially with the size of the network, a scalable decomposition-based approach is developed yielding a defense strategy whose performance is shown to closely approach the Nash equilibrium of the non-decomposed game. Numerical results demonstrate the effectiveness of the proposed strategies against various attack policies under different attack costs and initial conflict sizes.

Keywords:Coding Theory Abstract: Quasi-Quadratic Residue Codes (QQR Codes) are a family of double circulant codes. They are important in at least two respects:

Firstly, they have very good minimum distances when p equiv 3 pmod 8, providing a critical test case for Goppa's Conjecture.

Secondly, they serve as a powerful tool for studying point distributions on hyperelliptic curves. We will use the result of their weight distributions to prove a variant on a result of Larsen cite{Larsen2008} on asymptotic normal distribution of numbers of points on hyperelliptic curves.

In this paper, we will show new results on QQR Codes from several perspectives. We will observe (and prove when p equiv 7 pmod 8) that the weight polynomial of a QQR Code is at least divisible by (x^2 + y^2)^{d-1}, where d is its minimum distance.

We also provide new results about their structures. When pequiv 7 pmod 8, it is the even weight subcode of the direct sum of the quadratic residue code with itself. Its automorphism group contains the invertible affine transformations on mathbb{F}_p.

We also answer a question of Joyner asking whether they satisfy the Riemann hypothesis.

Keywords:Coding Theory, Reliability, Security and Trust Abstract: We develop three new results regarding the second-order asymptotics of secure communication over wiretap channels. We first establish the optimal second-order asymptotics for a class of degraded wiretap channels without feedback under an effective secrecy criterion. We then derive the optimal second-order asymptotics for degraded wiretap channels with feedback. We finally develop a new converse bound for channel resolvability with non-capacity achieving distributions, which we use to develop useful converse bounds for asymmetric degraded wiretap channels. Our results are illustrated with several numerical examples, and suggest that known coding techniques already achieve their best performance.

Keywords:Decentralized Control Systems, Optimization, Distributed and Large-Scale Systems Abstract: We will review some recent results on existence and approximations in decentralized stochastic control and establish differences and connections with classical single-decision maker stochastic control problems. Towards this goal, we will introduce a strategic measures approach: These measures are the probability measures induced by admissible policies under a given decentralized information structure. Properties such as convexity of the sets of such measures will be studied; it will be shown that measures induced by deterministic policies form the extreme points of a properly expanded set of strategic measures, thus establishing the optimality of such policies. Conditions ensuring the compactness of sets of strategic measures will be established; here, two sets of results will be presented. These will lead to existence results for optimal solutions for both static and dynamic teams. Finally, through a proper approximation of these sets of strategic measures by those induced with quantization of measurement and action spaces, some recent approximation results will be reviewed.

Keywords:Wireless Communication Systems, Performance Analysis Abstract: We consider a wireless broadcast network where a base-station sends time sensitive information updates to users, over unreliable wireless channel. The freshness of the information is captured by the Age of Information (AoI) metric: Namely, the amount of time that elapsed since the most recent update was generated. We formulate a discrete-time decision problem to find the scheduling policy that minimizes the weighted sum AoI of the network, and show that a greedy policy, which transmits the packet with highest current age, is optimal for the case of symmetric channels. For the case of asymmetric channels, we establish that the problem is indexable and obtain Whittle`s Index in close form. Numerical results are presented to demonstrate the performance of the policies.

Keywords:Network Games and Algorithms, Complex Networked Systems, Computational Models and Representations Abstract: Personalized PageRank (PPR) is a measure of the importance of the nodes in a network from the perspective of a single node (called source). Due to the scale of today’s networks, precomputing each source’s PPR requires far too much storage, while computing PPR at query time using methods like power iteration is far too slow. To overcome these challenges, we consider two different approaches. Given the knowledge of the PPR vectors from a subset of source nodes (called seed nodes), the first approach uses a simpler random walk to obtain the PPR from other sources. Despite the simplifications, in the worst-case, this method does not afford an order improvement in complexity over running the power iteration from every source node. In our second approach we start by providing a new interpretation of the Approx-Contributions (AC) algorithm that forms the back-bone of the Bidrectional-PPR (BPPR) algorithm, which can be used to estimate the PPR of any given source-target pair. Using this interpretation, we develop algorithms for multiple-targets’ and multiple source-target pairs’ PPR queries that use a set of common simulated random walks. We show that these algorithms are faster than using BPPR, which runs AC for each target or source-target pair separately. Finally, we combine the two approaches to compute the PPR from a single source to many targets. Specifically, we pair faster random walks from a single source (knowing seed nodes) with our multiple-target algorithm.

Keywords:Optimization, Distributed and Large-Scale Systems Abstract: We present a fast bidirectional algorithm for estimating a single element of the product of a matrix power and vector. This is an important primitive in many applications; in particular, we describe how it can be used to estimate a single element in the solution of a linear system Ax=b, with sublinear average-case running time guarantees for sparse systems. Our work combines the von Neumann-Ulam MCMC scheme for matrix multiplication with recent developments in bidirectional algorithms for estimating random-walk metrics. In particular, given a target additive-error threshold, we show how to combine a reverse local-variational technique with forward MCMC sampling, such that the resulting algorithm is order-wise faster than each individual approach.

Keywords:Data Analytics, Performance Analysis Abstract: Data concerning the users and usage of Online Social Networks (OSNs) has become available externally, from public resources (e.g., user profiles), participation in OSNs (e.g., establishing relationships and recording transactions such as user updates) and APIs of the OSN provider (such as the Twitter API). APIs let OSN providers monetize the release of data while helping control measurement load, e.g. by providing samples with different cost-granularity tradeoffs. To date, this approach has been more suited to releasing transactional data, with graphical data still being obtained by resource intensive methods such a graph crawling. In this paper, we propose a method for OSNs to provide samples of the user graph of tunable size, in non-intersecting increments, with sample selection that can be weighted to enhance accuracy when estimating different features of the graph.

Keywords:Optimization, Learning and Inference, Distributed and Large-Scale Systems Abstract: We study a consensus-based distributed stochastic gradient method for distributed optimization in a setting common for machine learning applications. Nodes in the network hold disjoint data and seek to optimize a common objective which decomposes into a sum of convex functions of individual data points. We show that the rate of convergence for this method involves the spectral properties of two matrices: the standard spectral gap of a weight matrix from the network topology and a new term depending on the spectral norm of the sample covariance matrix of the data. This result shows the benefit of datasets with small spectral norm. Extensions of the method can identify the impact of limited communication, increasing the number of nodes, and scaling with data set size.

Keywords:Machine Learning and Learning Theory, Learning and Inference, Information Theory and Statistics Abstract: We explore the active top-K sorting problem, in which the goal is to recover the top-K items in order out of n items, from adaptive pairwise comparisons that are collected possibly in a sequential manner as per our design choice. Under a fairly general model which subsumes as special cases various models (e.g., Strong Stochastic Transitivity model, BTL model and uniform noise model), we characterize an upper bound on the sample size required for reliable top-K sorting. As a consequence, we demonstrate that active ranking can offer significant multiplicative gains in sample complexity over passive ranking. Depending on the underlying stochastic noise model, such gain varies from around log(n)/loglog(n) to n^2log(n)/loglog(n). We also present an algorithm that runs linearly in n and which achieves the sample complexity bound. Our theoretical findings are corroborated via numerical experiments.

Keywords:Data Analytics, Network Games and Algorithms, Complex Networked Systems Abstract: Many graph mining and network analysis problems rely on the availability of the full network over a set of nodes. But inferring a full network is sometimes non-trivial if the raw data is in the form of many small {em patches} or subgraphs, of the true network, and if there are ambiguities in the identities of nodes or edges in these patches. This may happen because of noise or because of the nature of data; for instance, in social networks, names are typically not unique. textit{Graph assembly} refers to the problem of reconstructing a graph from these many, possibly noisy, partial observations. Prior work suggests that graph assembly is essentially impossible in regimes of interest when the true graph is ErdH{o}s-R'{e}nyi . The purpose of the present paper is to show that a modest amount of clustering is sufficient to assemble even very large graphs.

We introduce the G(n,p;q) random graph model, which is the random closure over all open triangles of a G(n,p) ErdH{o}s-R'{e}nyi , and show that this model exhibits higher clustering than an equivalent ErdH{o}s-R'{e}nyi . We focus on an extreme case of graph assembly: the patches are small (1-hop egonets) and are unlabeled. We show that in realistic regimes, graph assembly is fundamentally feasible, because we can identify, for every edge e, a subgraph induced by its neighbors that is unique and present in every patch containing e. We also provide an achievability result for noisy patc

Keywords:Machine Learning and Learning Theory, Data Analytics Abstract: In this talk I will present data-driven algorithms for {em dense subgraph discovery} cite{mitzenmacher2015scalable,tsourakakis2015k}, and {em community detection} cite{tsourakakis2016scalable} respectively. The proposed algorithms leverage graph motifs to attack the large near-clique detection problem, and community detection respectively. In my talk, I will focus on triangles within graphs, but our techniques extend to other motifs as well. The intuition, that has been suggested but not formalized similarly in previous works, is that triangles are a better signature of community than edges. For both problems, we provide theoretical results, we design efficient algorithms, and then show the effectiveness of our methods to multiple applications in machine learning and graph mining.

Keywords:Information Theoretic Approaches in Wireless Communications, Network Information Theory, Information Theory Abstract: Two fundamental multi-user channel models: the multiple-input multiple-output (MIMO) wiretap channel with one helper (WTH) and the MIMO multiple access wiretap channel (MAC-WT) are considered. In each case, the eavesdropper has K antennas while the remaining terminals have N antennas. We consider a fast fading channel where the channel state information (CSI) of the legitimate receiver is available at the transmitters but no channel state information at the transmitters (CSIT) is available for the eavesdropper's channel. The optimal sum secure degrees of freedom (s.d.o.f.) for each channel model is determined for the regime K <= N, and we show that in this regime, the MAC-WT channel reduces to the WTH in the absence of eavesdropper CSIT. For the regime N < K < 2N, we obtain the optimal linear s.d.o.f., and show that the MAC-WT channel and the WTH have the same optimal s.d.o.f. when restricted to linear encoding strategies. In the absence of any such restrictions, we provide an upper bound for the sum s.d.o.f. of the MAC-WT chanel in the regime N < K < 2N. Our results show that unlike in the single-input single-output (SISO) case, there is loss of s.d.o.f. for even the WTH due to lack of eavesdropper CSIT, when K > N.

Keywords:Information Theoretic Approaches in Wireless Communications, Information Theory, Wireless Communication Systems Abstract: This paper investigates the capacity of a communications channel that, in addition to additive white Gaussian noise, also suffers the interference from a co-existing radar transmission. The radar interference (of short duty-cycle and of much wider bandwidth than the intended communication signal) is modeled as an additive term whose amplitude is known and constant, but whose phase is independent and identically uniformly distributed at each channel use. The capacity achieving input distribution, under the standard average power constraint, is shown to have independent modulo and phase. The phase is uniformly distributed in [0,2pi]. The modulo is discrete with countably infinite many mass points, but only finitely many in any bounded interval. From numerical evaluations, a proper-complex Gaussian input is seen to perform quite well for weak radar interference. Interestingly, for very large radar interference, a Gaussian input achieves frac{1}{2}logleft(1+snr right). Since a Gaussian input is optimal to within one~bit, it is concluded that the presence of the radar interference results in a loss of half degrees of freedom compared to an interference free channel.

Keywords:Wireless Communication Systems, Coding Theory, Information Theoretic Approaches in Wireless Communications Abstract: This paper takes a step towards making practical cooperative protocols for wireless low-latency high-reliability communication. We consider the effect of finite block-length error correction codes and the main message is that the demands on the error-correcting code are different in different phases of a diversity-seeking cooperative protocol: In the first hop where messages must reach potential relays, the code only has to achieve a moderate probability of error. The final hop from relays to the destination is where the code must be ultrareliable. The results are illustrated in the context of a simple concatenated Hamming+Reed Solomon code.

Keywords:Performance Analysis, Complex Networked Systems, Information Theoretic Approaches in Wireless Communications Abstract: We propose and study a novel continuous space-time model for wireless networks which takes into account the stochastic interactions in both space through interference and in time due to randomness in traffic. Our model consists of an interacting particle birth-death dynamics incorporating information-theoretic spectrum-sharing. Roughly speaking, particles (or more generally wireless links) arrive according to a Poisson Point Process on space-time, and stay for a duration governed by the local configuration of points present and then exit the network after completion of a file transfer. We analyze this particle dynamics to derive an explicit condition for time ergodicity (i.e. stability) which is tight. We also prove that when the dynamics is ergodic, the steady-state point process of links (or particles) exhibits a form statistical emph{clustering}. Based on the clustering, we propose a heuristic formula for mean delay and mean number of links in steady state which we observe from simulation to perform remarkably well.

Keywords:Wireless Communication Systems, Information Theory, Network Coding Abstract: Building on the recent coded-caching breakthrough by Maddah-Ali and Niesen, the work here considers the K-user cache-aided wireless multi-antenna (MISO) symmetric broadcast channel (BC) with random fading and imperfect feedback, and analyzes the throughput performance as a function of feedback statistics and cache size. In this setting, our work identifies the optimal cache-aided degrees-of-freedom (DoF) within a factor of 4, by identifying near-optimal schemes that exploit the new synergy between coded caching and delayed CSIT, as well as by exploiting the unexplored interplay between caching and feedback-quality.

The derived limits interestingly reveal that --- the combination of imperfect quality current CSIT, delayed CSIT, and coded caching, guarantees that --- the DoF gains have an initial offset defined by the quality of curren

Keywords:Performance Analysis Abstract: This paper studies resource allocation for data-parallel applications in a networked computing system with data locality. Data-parallel computing tasks have two components: data and computation. To support efficient data-processing in the system, the resource allocation algorithm should jointly consider load-balancing, data transmissions and processing scheduling. In this paper, we consider a general model of a computing system where the computing system is a network represented by a graph, with nodes being computing devices or switches and edges being communication links. The data chunks stored at the nodes can be processed locally or be transmitted to other computing nodes in the network to be processed. The throughput of such a system for processing data-parallel applications is determined jointly by the computing capacity of the nodes and the communication capacity of the network, and the resource allocation algorithm should strike a right balance between computing and communication. In this paper, we propose a throughput-optimal resource allocation algorithm, which is also able to control the tradeoff between the expected amount of data transmitted and the expected number of backlogged tasks in steady state through a parameter qth. We show that the gap between the expected data transmission rate under our algorithm and the optimal value is O(1/qth), while the expected number of total backlogged tasks is upper bounded by O(qth).

Keywords:Coding Techniques and Applications, Learning and Inference, Distributed and Large-Scale Systems Abstract: We consider the problem of computing distributed logistic regression using unreliable components. We consider both faults in the memory units and faults in the processing units. We show that using a real-number-coding technique, we can suppress errors during the computation and ensure that logistic regression converges with bounded error if the number of faults that happen during each iteration of the logistic regression is bounded, even when the faults happen in an adversarial manner. Moreover, since the coding technique is based on computation with real numbers, we show that the error-correction can be carried out at the algorithmic level (or block-level) based on the results from intermediate steps of logistic regression. Therefore, we only need to add redundant hardware at block-level, not the circuit level, for achieving fault- tolerance in the computation of logistic regression.

Keywords:Coding Techniques and Applications Abstract: Approximate computing, which sacrifices the accuracy during computation, is a promising technology to save energy. However, large number of computation errors may violate the accuracy requirement of certain applications and should be corrected. Consider a Graphical Processing Unit (GPU) with multiple Streaming Multiprocessors (SMs), where some of these SMs perform accurate computation while the others perform approximate computation. Provided the approximate outputs are correlated with other accurate outputs, we exploit this relation and model the approximate computation process as a communication process. Then the problem of error correction transforms to a problem of decoding and we want to solve it with certain error correction code. Different from the classical communications process, approximate computing raises additional constraints on the code design. In this paper, we propose a semi-regular LDPC code satisfying these constraints and prove this code can be perfectly decoded. Certain properties of the code are analyzed and simulations are provided to verify the statement.

Keywords:Coding Techniques and Applications, Performance Analysis Abstract: A novel coding scheme is proposed to speed up distributed computation through a form of approximate computing. It is known that task replication can greatly mitigate the “straggler effect” in cloud computing, wherein an overall computation can be significantly delayed by slowed processing nodes (or “stragglers”). It has also been demonstrated that, in certain contexts, ideas of error-correction coding can more efficiently deal with stragglers than pure replication. The approach proposed herein builds on these earlier observations through an “anytime” approach to approximate computing. In this paradigm, over time one can produces approximate solutions of increasing accuracy. To accomplish this we first decompose a computational job in to tasks of various priorities. Next, we apply linear error correction coding to produce subtasks that are assigned to different processors. The decomposition used has a big effect on the type of anytime performance we attain. We study this scheme in a general framework in terms of the expected cost of the approximate solution. We further explore the approach in the context of vector-matrix multiplication. The proposed construction is numerically studied and, in comparison to previous work, demonstrates a significant improvement in the accuracy/latency trade-off.

Keywords:Network Coding, Machine Learning and Learning Theory, Network Information Theory Abstract: Distributed learning platforms for processing large scale data-sets are becoming increasingly prevalent. In typical distributed implementations, a centralized master node breaks the data-set into smaller batches for parallel processing across distributed workers to achieve speed-up and efficiency. Several computational tasks are of sequential nature, and involve multiple passes over the data. At each iteration over the data, it is common practice to randomly re-shuffle the data at the master node, assigning different batches for each worker to process. This random re-shuffling operation comes at the cost of extra communication overhead, since at each shuffle, new data points need to be delivered to the distributed workers.

In this paper, we focus on characterizing the information theoretically optimal communication overhead for the distributed data shuffling problem. We propose a novel coded data delivery scheme for the case of no excess storage, where every worker can only store the assigned data batches under processing. Our scheme exploits a new type of coding opportunity and is applicable to any arbitrary shuffle, and for any number of workers. We also present information theoretic lower bounds on the minimum communication overhead for data shuffling, and show that the proposed scheme matches this lower bound for the worst-case communication overhead.

Keywords:Information Theory, Information Theoretic Approaches in Wireless Communications, Coding Techniques and Applications Abstract: We consider joint source-channel coding with bandwidth expansion, in a quadratic-Gaussian setting. We seek a scheme that will have favorable delay and robustness characteristics: it should be scalar (working on a single source sample), and closely follow the optimal curve of signal-to-distortion ratio (SDR) versus signal-to-noise ratio (SNR), asymptotically as the SNR grows. A natural candidate is bit interleaving, which was already proposed by Shannon in the context of bandwidth compression; however, in the case of expansion it suffers from severe noise amplification. A scheme proposed by Teherzadeh and Khandani introduces fixed bits in order to combat noise amplification, and has a multiplicative gap that is exponential the square root of the SNR from the ideal SDR-SNR curve. We propose an improved scheme that allocates the fixed bits in a source-dependent manner. This approach reduces the number of fixed bits needed, and thus has lower redundancy; we show that the multiplicative gap from the ideal curve is only linear in the SNR.

Keywords:Optimization Abstract: We consider the problem of minimizing a particular singular value of a matrix variable, which is then subject to some convex constraints. Convex heuristics for this problem are discussed, including some counter-intuitive results regarding which is best, which then provide upper bounds on the value of the problem. The use of polynomial optimization formulations is considered, particularly for obtaining lower bounds on the value of the problem.

We show that the main problem can also be formulated as an optimization problem with a bilinear matrix inequality (BMI), and discuss the use of this formulation.

Keywords:Information Theory Abstract: This paper formulates an abstract version of Shannon's lower bound that applies to abstract sources and arbitrary distortion measures and that recovers the classical Shannon lower bound as a special case. A necessary and sufficient condition for it to be attained exactly is presented. It is demonstrated that whenever that condition is met, the d-tilted information of the source adopts a simple, explicit representation that parallels Shannon's lower bound. That convenient representation simplifies the non-asymptotic analysis of achievable rate-distortion tradeoffs. In particular, if a memoryless source meets Shannon's lower bound with equality, then its rate-dispersion function is given simply by the varentropy of the source.

Keywords:Network Information Theory, Information Theoretic Approaches in Wireless Communications Abstract: Recent developments in network information theory, such as interference alignment and compute-and-forward, have highlighted connections to the branch of mathematics known as Diophantine approximation. At a high level, Diophantine approximation is concerned with how well the reals can be approximated by rationals. This paper surveys some classical and modern Diophantine results and demonstrates their applications in establishing degrees-of-freedom and capacity bounds.

Keywords:Distributed and Large-Scale Systems, Machine Learning and Learning Theory, Optimization Abstract: Asynchronous methods are widely used in deep learning, but have limited theoretical justification when applied to non-convex problems. We show that running stochastic gradient descent (SGD) in an asynchronous manner can be viewed as adding a momentum-like term to the SGD iteration. Our result does not assume convexity of the objective function, so it is applicable to deep learning systems. We observe that a standard queuing model of asynchrony results in a form of momentum that is commonly used by deep learning practitioners. This forges a link between queuing theory and asynchrony in deep learning systems, which could be useful for systems builders. For convolutional neural networks, we experimentally validate that the degree of asynchrony directly correlates with the momentum, confirming our main result. An important implication is that tuning the momentum parameter is important when considering different levels of asynchrony. Furthermore, our theory suggests ways of counter-acting the adverse effects of asynchrony. We see that a simple mechanism like using negative algorithmic momentum can be beneficial under high asynchrony. Since asynchronous methods have better hardware efficiency, this result may shed light on when asynchronous execution is more efficient for deep learning systems.

Keywords:Network Coding, Wireless Communication Systems, Network Games and Algorithms Abstract: We consider a data-exchange scenario in which each user initially has a subset of packets in the ground set X, and needs to retrieve all other packets in X. The users can exchange their packets by broadcasting coded or uncoded packets over a lossless broadcast channel. We refer to the set of all users as the grand coalition, and refer to any subset of users that collectively hold all packets in X as a minor coalition. A schedule and a scheme for transmissions satisfying all users in a coalition is called a solution for the coalition. The grand coalition is said to be stable under a solution if the following conditions hold: (i) there exists no other solution for any coalition S such that the transmission rate of some (or, respectively, any) member of S is strictly less (or, respectively, not greater) than that under the original solution; and (ii) there exists no other solution for any coalition S such that the sum-rate of S (i.e., the total transmission rate by all users in S) is strictly less (or, respectively, not greater) than the sum-rate of any coalition that includes some given (or, respectively, any arbitrary) member of S under the original solution. Our goal is to identify (if possible) a solution under which the grand coalition is stable. In this work, we propose an algorithm, referred to as cooperative data exchange with stable coalitions (CDESC), that, for any given instance, determines if there exists such a solution, and if so, it finds one such a solution.

Keywords:Network Coding, Network Information Theory, Coding Techniques and Applications Abstract: We study the problem of coded caching when the server has access to several libraries and each user makes independent requests from every library. The single-library scenario has been well studied and it has been proved that coded caching can significantly improve the delivery rate compared to uncoded caching. In this work we show that when all the libraries have the same number of files, memory-sharing is optimal and the delivery rate cannot be improved via coding across files from different libraries. In this setting, the optimal memory-sharing strategy is one that divides the cache of each user proportional to the size of the files in different libraries. As for the general case, when the number of files in different libraries are arbitrary, we propose an inner-bound based on memory-sharing and an outer-bound based on concatenation of files from different libraries.

Keywords:Coding Techniques and Applications, Coding Theory, Data Storage Abstract: Erasure-coded distributed storage systems can offer reliable storage services in a cost-effective manner. However, when disk failures occur in such systems, it is desirable to recreate the lost data with the help of surviving nodes to preserve the data redundancy. A key requirement during the recover process is to minimize the repair locality and computational complexity. We propose a simple framework for constructing storage codes that yield small repair locality and low repair complexity. The basic idea behind this framework is to take multiple instances of convolutional (tail-biting) codes, and then carefully arrange the coded symbols on storage nodes. The resultant codes enjoy the desirable repair-by-transfer property, and perform efficient repair by simple XOR operations. Moreover, we also evaluate the proposed codes atop an HDFS cluster testbed and compare the empirical performance with state-of-the-art repair-efficient storage codes.

Keywords:Coding Theory, Data Storage, Coding Techniques and Applications Abstract: When a node of a distributed storage system fails, it needs to be repaired quickly enough to maintain system integrity. While typical erasure codes can provide significant storage advantage over replication, they suffer from poor repair efficiency. Locally repairable codes (LRCs) tackle this issue by reducing the number of nodes participating in the repair process (locality), at the cost of reduced minimum distance. In this paper, we study the tradeoff characteristics between locality and minimum distance for LRCs, where the local codes have an arbitrary distance requirement. In our study, different from previous approaches, the localities specified are not necessarily the same for every symbol. Such property can be advantageous for distributed storage systems with non-homogeneous characteristics. We present a new Singleton-type minimum distance upper bound and also provide an optimal code construction with respect to this bound.

Keywords:Data Storage, Coding Theory, Coding Techniques and Applications Abstract: We construct "rank-metric codes" with local recoverability constraints. Our motivation stems from designing codes for efficient data recovery from correlated and/or mixed (i.e., complete and partial) failures in distributed storage systems. Specifically, the proposed local rank-metric codes can recover locally from "crisscross failures", which affect a limited number of rows and/or columns of the storage system. First, we prove a Singleton-like upper bound on the minimum rank-distance of linear codes with "rank-locality" constraints. Second, we construct a family of locally recoverable rank-metric codes that achieve this bound for a broad range of parameters. The proposed construction builds upon Tamo and Barg's method for constructing locally repairable codes with optimal minimum Hamming distance.

Keywords:Coding Theory, Data Storage Abstract: Locally repairable codes (LRC) have recently been a subject of intense research due to the theoretical appeal and their application in distributed storage systems. In an LRC, any coordinate of a codeword can be recovered by accessing only few other coordinates. For LRCs over small alphabet (such as binary), the optimal rate-distance trade-off is unknown. In this paper we provide the tightest known upper bound on the rate of linear LRCs of a given relative distance, an improvement over the best known bound by Cadambe and Mazumdar.

Keywords:Coding Theory, Coding Techniques and Applications, Information Theory Abstract: We study normal factor graph (NFG) representations of stabilizer quantum error-correction codes (QECCs), in particular NFG representations of the stabilizer label code and the normalizer label code associated with a stabilizer QECC. The structure of the NFGs we are using is such that the (symplectic) self-orthogonality constraint that stabilizer label codes have to satisfy can be proven rather straightforwardly by applying certain NFG reformulations. We show that a variety of well-known stabilizer QECCs can be expressed in this framework: (tail-biting) convolutional stabilizer QECCs, the toric stabilizer QECCs by Kitaev, and a class of stabilizer QECCs that was recently introduced by Tillich and Zemor. Our approach not only gives new insights into these stabilizer QECCs, but will ultimately help to formulate new classes of stabilizer QECCs and low-complexity (approximate) decoding algorithms.

Keywords:Decentralized Control Systems, Optimization, Robust and Nonlinear Control Abstract: This work considers the determination of non-binary measures of controllability or robustness with respect to decentralized controllers. A measure developed by Vaz and Davison in 1988 nicely captures the distance from a plant to the closest one with a fixed mode, and ties it to eigenvalue assignability; that is, how much effort is at most required to move the modes a given amount with the prescribed information structure. This metric is intractable to compute, but recent work has been very successful in finding close upper bounds. Finding lower bounds is not only important for providing guarantees on where the true metric lies, but is typically more important since determining whether the metric is bounded away from zero corresponds to whether the system can be controlled at all. This paper will address these lower bounds, in particular by using the Courant-Fischer formulation of singular values, we will formulate our problem as a polynomial optimization problem, for which we can then use Sum-of-Squares (SOS) techniques to find a lower bound.

Keywords:Optimization, Distributed and Large-Scale Systems, Decentralized Control Systems Abstract: This paper investigates the periodic time-triggered sparse Linear Quadratic Controller (LQC) design for the class of Linear Time Invariant (LTI) systems. Given a time period and keeping the control input fixed during such a time period, an optimization problem is formulated in which the objective function consists of a quadratic performance term along with an ell_0-regularization term. Recasting such an optimization problem as a rank-constrained optimization problem and utilizing the weighted ell_1-relaxation enable us to apply so-called bi-linear rank penalty technique to design periodic time-triggered sparse LQC. Employing the various test cases and running our proposed algorithm for different values of time period, performance/sparsity trade-off curves are visualized which suggest a helpful criterion to choose the time period in a way that the desired balance between controller sparsity and rate of periodic triggering is made.

Keywords:Optimization, Machine Learning and Learning Theory Abstract: We consider the problem of Nonnegative Matrix Factorization (NMF) which is a non-convex optimization problem with many applications in machine learning, computer vision, and topic modeling. General existing methods for finding a solution to the problem include additive or multiplicative update rules for doing alternate minimizations and ADMM, which find a locally optimal point for NMF. We propose a new method for finding a solution of NMF which considers transformations of initial factors derived from the singular value decomposition (SVD). This problem is shown to be equivalent to the NMF problem in a sense, and is then restricted to optimize over the set of orthonormal matrices known as the Stiefel manifold. We then utilize a method developed for optimization over this manifold to find solutions to the NMF problem. Application to synthetic data shows that the method exhibits promising characteristics, as it outperforms some traditional methods both in terms of reconstruction error and running time. Using the solution of this restriction as a starting point for the broader problem shows a further rapid decline in the error.

Keywords:Optimization, Machine Learning and Learning Theory Abstract: We consider the problem of handling binary constraints in optimization problems. We review methods for solving binary quadratic programs (BQPs), such as the spectral method and semidefinite programming relaxations. We then discuss two new methods for handling these constraints. The first involves the introduction of an extra unconstrained variable along with the alternating direction method of multipliers (ADMM), which has now also appeared in other recent literature. This allows the effect of the binary variables to be decoupled when they are minimized over. The second involves rewarding the one-norm while restricting the infinity-norm, based on a reformulation of the original problem. The piecewise linearity of the negative penalty results in the problem being convex until it hits a critical point, at which point the parameters of this linear term can be changed. These two methods can be applied to any problems which are convex except for binary constraints. In addition to testing them on BQPs, we show the efficacy of these approaches on point segmentation and image segmentation problems.

Keywords:Decentralized Control Systems, Optimization Abstract: We formulate a set of time-varying stochastic networked dynamical systems to model the evolution of tie strength among interacting agents. The dynamics of the strength of connections abide by local laws of reinforcement and penalization due to interactions among the agents. The proposed stochastic dynamical systems exhibit a strong attractor as a certain subset of the set of binary matrices. Moreover, the family of models adapts well to capture the phenomenon of emergence and downfall of leaders in social networks as it will be illustrated via numerical simulations.

Keywords:Distributed and Large-Scale Systems, Decentralized Control Systems, Detection and Estimation Abstract: We investigate the problem of distributed state estimation of a linear time-invariant (LTI) system by a network of sensors. We propose a new approach to designing distributed observers based on the following intuition: a given node (sensor) can reconstruct a certain portion of the state solely by using its own measurements together with an appropriate Luenberger observer. Hence it only needs to rely on information obtained from neighbors for estimating the portion of the state that is not locally detectable. We build on this intuition in this paper by extending the idea of the Kalman observable canonical decomposition to a setting with multiple sensors. We then construct local Luenberger observers at each node based on this decomposition, and use consensus dynamics to estimate the unobservable portions of the state at each node. This leads to an estimation scheme that achieves asymptotic state reconstruction at each node of the network for the most general class of LTI systems, sensor network topologies and sensor measurement structures.

Keywords:Decentralized Control Systems, Complex Networked Systems, Network Games and Algorithms Abstract: This work is a first step towards the study of open multi-agent systems: systems that agents can join and leave, and where arrivals and departures happen on a time-scale comparable to that of the process running on the system. We study the behavior of the average pairwise gossip algorithm on such open systems, and provide an exact characterization of its evolution in terms of three scale-independent quantities that are shown to be solutions of a 3-dimensional linear dynamical system. We then focus on two particular cases: one where each departure is immediately followed by an arrival, and one where agents keep arriving without ever leaving the system, so that the number of agents grows unbounded.

Keywords:Complex Networked Systems, Optimization, Distributed and Large-Scale Systems Abstract: In this paper, we adapt the Alternating Direction Method of Multipliers (ADMM) to develop a distributed algorithm for computing finite horizon optimal control for traffic flow over networks, where the cost is in terms of the density and flow vectors. The dynamics is described by the Cell Transmission Model. While the problem is non-convex in general, recent work has shown the existence of an equivalent convex relaxation, which we adopt in this paper. An equivalent finite dimensional representation for constraints is developed when the external inflows and control are piecewise constant. The auxiliary variables for ADMM implementation consist of a time shifted copy of the density vector, and two copies of the flow vector. A particular division of these variables into two blocks is provided which facilitates distributed implementation, as well as convergence of the ADMM iterates to an optimal solution, if the initial density on every link is strictly positive and strictly below the jam capacity, and the cost function is proper, closed, convex, and separable over density and flow variables, and over links. We also examine the necessary condition, as given by the maximum principle, to provide sufficient conditions under which the optimal control is unique for non-strict convex cost functions, and of bang-bang type, for a linear network.

Keywords:Complex Networked Systems, Decentralized Control Systems, Robust and Nonlinear Control Abstract: Investigation of synchronization phenomena in networks of coupled nonlinear oscillators plays a pivotal role in understanding the behavior of biological and mechanical systems with oscillatory properties. We derive a general sufficient condition for synchronization of a network of nonlinear oscillators using a non-smooth Lyapunov function, and we obtain conditions under which synchronization is guaranteed for a network of Fitzhugh-Nagumo (FN) oscillators in biologically relevant model parameter regimes. We incorporate two types of heterogeneity into our study of FN oscillators: 1) the network structure is arbitrary and 2) the oscillators have non-identical external inputs. Understanding the effects of heterogeneities on synchronization of oscillators with inputs provides a promising step toward control of key aspects of networked oscillatory systems.