 
Last updated on September 22, 2017. This conference program is tentative and subject to change
Technical Program for Thursday October 2, 2014

ThA1 
Library 
Controlled Sensing and Information Processing in Networks II 
Invited Session 
Chair: Veeravalli, Venugopal  Univ. of Illinois 

08:3008:50, Paper ThA1.1  
Towards Cloud Sensing Enabled Target Localization (I) 
Cao, Nianxia  Syracuse Univ 
Brahma, Swastik  Syracuse Univ 
Varshney, Pramod  Syracuse Univ 
Keywords: Network Games and Algorithms, Sensor Networks, Statistical Signal Processing
Abstract: In this paper, we introduce ``cloud sensing" as a paradigm for enabling sensingasaservice in the context of target localization in wireless sensor networks (WSNs). We present a bilateral trading mechanism consisting of a sensing service provider (fusion center) that ``sells'' information regarding the target through sensor management, and a user who seeks to ``buy'' information regarding the target. Our mechanism, aware of resource costs involved in service provisioning, maximizes the expected total gain from the trade while assuring individual rationality and incentive compatibility. The impossibility of achieving ex post efficiency is also shown in the paper. Design of the mechanism enables the study of the tradeoff between information gain and the costs of the WSN for sensor management. Simulation results provide insights into the dynamics of the proposed model.


08:5009:10, Paper ThA1.2  
Controlled Sensing and Event Based Communication for Remote Estimation (I) 
Akyol, Emrah  USC 
Mitra, Urbashi  Univ. of Southern California 
Nayyar, Ashutosh  Univ. of Southern California 
Keywords: Detection and Estimation, Stochastic Systems and Control, Sensor Networks
Abstract: We consider a setup where a sensor is observing a stochastic process of interest which must be communicated to a remote estimator. In addition to the distortion cost, the system incurs costs associated with sensing and communication. The overall cost is to be optimized by jointly designing strategies for controlled sensing, event based communication and remote estimation. Instead of continuously sensing the environment, the sensor is activated only when the remote estimator issues an activation command. Further, when the sensor makes the observation, it can choose not to communicate (and hence reduce communication cost) if the observation is not too informative. We consider the joint optimization of the sensor activation, communication and remote estimation strategies. The resulting optimization problem is a decentralized sequential decision making problem. Unlike prior work, we consider both the controlled sensing and the event based communication aspects of the problem. We extend the analytical approach of [1] to characterize optimal strategies.


09:1009:30, Paper ThA1.3  
Thermodynamic Costs in Implementing KalmanBucy Filters (I) 
Sandberg, Henrik  KTH Royal Inst. of Tech 
Delvenne, JeanCharles  Univ. Catholique De Louvain 
Newton, Nigel  Univ. of Essex 
Mitter, Sanjoy  MIT 
Keywords: Stochastic Systems and Control, CyberPhysical Systems
Abstract: In this paper, we investigate fundamental limits for physical implementations of the KalmanBucy filter for state estimation of a class of linear portHamiltonian systems. In particular, for the studied class of systems we show the KalmanBucy filter itself is a portHamiltonian systems and by invoking the second law of thermodynamics, we can characterize the external power supply needed to generate an optimal state estimate. We also show how the required external power supply can be decreased by allowing the filter to perturb the measured system to a larger extent. Hence, it is possible to decrease the socalled back action of the filter by spending more energy. We illustrate our results using passive electric circuits.


09:3009:50, Paper ThA1.4  
Eminence Grise Coalitions in Opinion Dynamics (I) 
Bolouki, Sadegh  Lehigh Univ 
Malhame, Roland  École Pol. De Montréal 
Siami, Milad  Lehigh Univ 
Motee, Nader  Lehigh Univ 
Keywords: Decentralized and Distributed Control, MultiAgent Systems and Robot Control
Abstract: In this paper, we consider linear continuoustime models of evolution of opinions in largescale dynamical networks. Our focus is on dynamical networks that are defined on general exogenously given timevarying graphs, where the nodes of the underlying graph model individuals (or agents) with firstorder linear opinion dynamics. In such a network, for an arbitrary fixed initial time, a subset of individuals is said to form an eminence grise coalition (EGC) if its members are capable of leading the entire network to agreeing on any desired value through a cooperative choice of their own initial opinions. The coalition members are assumed to have access to full profile of the underlying graph of the network as well as the initial opinions of all other individuals. While the complete coalition of individuals in an opinion network trivially qualifies as an EGC, we establish the existence of a minimum size EGC for an arbitrary timevarying network and develop a nontrivial set of upper and lower bounds on that size. As a result, we show that even when the underlying graph does not guarantee convergence to a single or multiple consensus, a generally restricted coalition of agents can steer public opinion towards a desired consensus without affecting any of the predefined graph interactions by having its members collectively adjust their own initial opinions. Geometric insights into the structure of EGC's are also developed.


09:5010:10, Paper ThA1.5  
Towards Lower Bounds for Distributed Convex Optimization (I) 
Rabbat, Michael  McGill Univ. 

ThA2 
Solarium 
Topics in Coding Theory 
Invited Session 
Chair: Gabrys, Ryan  UCLA 

08:3008:50, Paper ThA2.1  
NonMalleable Coding and Applications (I) 
Cheraghchi, Mahdi  MIT 

08:5009:10, Paper ThA2.2  
Isn't Hybrid ARQ Sufficient? (I) 
Heindlmaier, Michael  Tech. Univ. Muenchen 
Soljanin, Emina  Bell Labs 
Keywords: Network Coding in Communication, Coding for Wireless Communications, Coding Techniques and Applications
Abstract: In practical systems, reliable communication is often accomplished by coding at different network layers. We question the necessity of this approach and examine when it can be beneficial. Through conceptually simple probabilistic models (based on coin tossing), we argue that multicast scenarios and protocol restrictions may make concatenated multilayer coding preferable to physical layer coding alone, which is mostly not the case in pointtopoint communications.


09:1009:30, Paper ThA2.3  
On MultiVersion Coding for Distributed Storage (I) 
Wang, Zhiying  Stanford Univ 
Cadambe, Viveck  Pennsylvania State Univ 
Keywords: Data Storage, Coding Theory, Distributed Computation on Networks
Abstract: The multiversion coding problem described previously by Wang and Cadambe is motivated by applications to distributed storage and computing. Here, we consider a modification to the previously described multiversion coding problem that retains the essence of the earlier definition, and show that our modification leads to a reduced storage cost. We consider a setting where there are n servers that aim to store nu versions of a message, where there is a total ordering on the from the earliest to the latest. We assume that each message version has size log_{2}M bits. Each server can receive any subset of the nu versions and stores over an alphabet of size q a function of the message versions it receives. The (n,c,nu,M,q) multiversion code we consider ensures that, a decoder that connects to any c of the n servers can recover the message corresponding to the latest common version stored among those servers, or a message corresponding to a version that is later than the latest common version. Unlike our earlier paper, we allow for the message version that is decoded to be one that is later than the latest common version. Through an achievable scheme and a tight converse, we describe the optimal multiversion code for nu=2 versions from the perspective of the storage cost frac{log_{2}q}{log_{2}M}. In particular, we show that for nu=2, the optimal multiversion code has a storage cost of 2 log_2 M/(c+1) when c is odd and frac{2 log_2 M(c+1)}{c(c+2)} when c is even. We also present achievable code constructions for arbitrary values of the parameter nu.


09:3009:50, Paper ThA2.4  
Use of Erasure Code for Low Latency Cloud Storage (I) 
Liang, Guanfeng  DOCOMO Innovations Inc 
Kozat, Ulas  DOCOMO Innovations Inc 
Keywords: Data Storage, Queuing Theory and Analysis, Coding Techniques and Applications
Abstract: Recent literature including our past work provide analysis and solutions for using (i) erasure coding, (ii) parallelism, or (iii) variable slicing/chunking (i.e., dividing an object of a specific size into a variable number of smaller chunks) in speeding up the I/O performance of storage clouds. Generally, such systems can be characterized by the tuple of parameters (n,k,L): each data file is represented by k equally sized “data chunks” and encoded into at least n coded chunks; there are L parallel/independent servers/connections in total, each of which can download 1 coded chunk at a time; retrieval of a file is carried out by downloading n coded chunks in parallel and considered finished upon completion of any k downloading jobs. Bounds have been developed for very restricted special cases (n=k and n=L) with exponential service time, and very little is known when k


09:5010:10, Paper ThA2.5  
GilbertVarshamovLike Lower Bounds for DeletionCorrecting Codes (I) 
Gabrys, Ryan  UCLA 

ThA3 
Butternut 
Decentralized and Distributed Control 
Regular Session 
Chair: Li, Na  Harvard Univ 
CoChair: Lavaei, Javad  Columbia Univ 

08:3008:50, Paper ThA3.1  
RealTime Decentralized Voltage Control in Distribution Networks 
Li, Na  Harvard Univ 
Qu, Guannan  Harvard Univ 
Dahleh, Munther  MIT 
Keywords: Decentralized and Distributed Control, Optimization, Control Applications
Abstract: Voltage control plays an important role in the operation of electricity distribution networks, especially when there is a large penetration of renewable energy resources. In this paper, we focus on voltage control through reactive power compensation and study how different information structures affect the control performance. In particular, we first show that only using voltage measurements to determine reactive power compensation is insufficient to maintain voltage in the acceptable range. Then we proposes two fully decentralized algorithms by slightly adding additional information into the control design. The two algorithms are guaranteed to stabilize the voltage in the acceptable range regardless of the system operating condition. The one with higher complexity can further minimize a cost of reactive power compensation in a particular form. Both of the two algorithms use only local measurements and local variables and require no communication.


08:5009:10, Paper ThA3.2  
Power FlowBased Adaptive Generator Controls 
Garcia, Manuel  Los Alamos National Lab. 
Backhaus, Scott  Los Alamos National Lab. 
Bent, Russell  Los Alamos National Lab. 

09:1009:30, Paper ThA3.3  
Efficient Convex Relaxation for Stochastic Optimal Distributed Control Problem 
Kalbat, Abdulrahman  Columbia Univ 
Madani, Ramtin  Columbia Univ 
Fazelnia, Ghazal  Columbia Univ 
Lavaei, Javad  Columbia Univ 
Keywords: Decentralized and Distributed Control, Optimization, Control Applications
Abstract: This paper is concerned with the design of an efficient convex relaxation for the notorious problem of stochastic optimal distributed control (SODC). The objective is to find an optimal structured controller for a dynamical system subject to input disturbance and measurement noise. With no loss of generality, this paper focuses on the design of a static controller for a discretetime system. First, it is shown that there is a semidefinite programming (SDP) relaxation for this problem with the property that its SDP matrix solution is guaranteed to have rank at most 3. This result is due to the extreme sparsity of the SODC problem. Since this SDP relaxation is computationally expensive, an efficient twostage algorithm is proposed. A computationallycheap SDP relaxation is solved in the first stage. The solution is then fed into a second SDP problem to recover a nearglobal controller with an enforced sparsity pattern. The proposed technique is always exact for the classical H_2 optimal control problem (i.e., in the centralized case). The efficacy of our technique is demonstrated on the IEEE 39bus New England power network, a massspring system, and highlyunstable random systems, for which nearoptimal stabilizing controllers with global optimality degrees above 90% are designed under a wide range of noise levels.


09:3009:50, Paper ThA3.4  
Control Configuration Design for a Class of Structural Bilinear Systems 
Ghosh, Supratim  Singapore Univ. of Tech. and Design 
Ruths, Justin  Singapore Univ. of Tech. & Design 
Keywords: Networked Control Systems, Nonlinear Control
Abstract: Analysis of structured systems has opened up the potential to understand the control properties of large scale systems modeled as networks. Networks present novel questions to control theory because the interchangeability of nodes means that any subset could be controlled. In contrast, classic control systems have prescribed connections between controls and states. We present an algorithm to determine the structure of the input connectivity for singleinput rankone structured bilinear systems, which is analogous to designing the control configuration, or placement, of controls on edges in the network. In particular, we develop the control configuration with a minimum number of new interconnections (with respect to a cacti representation of the graph). These controls become the weights of certain edges in the network representation of the bilinear system.


09:5010:10, Paper ThA3.5  
Localized Distributed Optimal Control with Output Feedback and Communication Delays 
Wang, YuhShyang  California Inst. of Tech 
Matni, Nikolai  California Inst. of Tech 
Keywords: Decentralized and Distributed Control, CyberPhysical Systems, Optimization
Abstract: This paper presents an output feedback control scheme for localizable distributed systems subject to delay, that is to say systems for which the effect of both process noise and sensor noise can be localized in closed loop despite communications delays between controllers. By reformulating the distributed optimal control problem in terms of the closed loop transfer matrices from sensor and process noise to controlled output, we cast the optimal localized distributed control problem as a finite dimensional affinely constrained convex program. We additionally show how to synthesize the controller achieving the desired closed loop response, and that the controller can be implemented in a localized and thus scalable manner, which is essential when applying the scheme to large scale systems. Simulation shows that for certain systems, our optimal controller, with its constraints on locality, settling time, and communication delay, can achieve similar performance to a centralized optimal one.


ThA4 
Pine 
Pricing Congestion Control and Resilient Systems 
Regular Session 
Chair: Berry, Randall  Northwestern Univ 

08:3008:50, Paper ThA4.1  
Existence and Controllability Results for Fractional Impulsive Integrodifferential Systems with Nonlocal Initial Conditions in Banach Spaces 
Qin, Haiyong  China Univ. of Petroleum(Beijing) 
Liu, Jianwei  China Univ. of Petroleum, Beijing 
Zuo, Xin  China Univ. of Petroleum, Beijing 
Guo, Longchuan  China Univ. of Petroleum Beijing 
Keywords: Nonlinear Control, Control Applications
Abstract: This paper is concerned with existence results of nonlocal problems for fractional impulsive integrodifferential equations in Banach spaces. Moreover, we define a piecewise continuous control function to obtain the results on the controllability of the corresponding fractional impulsive integrodifferential systems. The results are obtained by means of fixed point methods. An example to illustrate the applications of our main results is also given.


08:5009:10, Paper ThA4.2  
Demand Shaping in Cellular Networks 
Zhou, Xinyang  Univ. of Colorado at Boulder 
Chen, Lijun  California Inst. of Tech 
Keywords: Pricing and Congestion Control, Decentralized and Distributed Control, Wireless Communication Systems
Abstract: Demand shaping is a promising way to mitigate the wireless cellular capacity shortfall in the presence of ever increasing wireless data demand. In this paper, we formulate demand shaping as an optimization problem that minimizes the variation in aggregate traffic. We design a distributed and randomized offline demand shaping algorithm under complete traffic information and prove its almost surely convergence. We further consider a more realistic setting where the traffic information is incomplete but future traffic can be predicted to a certain accuracy. We design an online demand shaping algorithm that updates the schedules of deferrable applications each time when new information is available, based on solving at each timeslot an optimization problem over a shrinking horizon from the current time to the end of the day. We compare the performance of the online algorithm against the optimal offline algorithm, and provide numerical examples.


09:1009:30, Paper ThA4.3  
A Priority Queue Model for Competition with Shared Spectrum 
Liu, Chang  Northwestern Univ 
Berry, Randall A.  Northwestern Univ 
Keywords: Pricing and Congestion Control
Abstract: Spectrum sharing has been put forward as a way to more efficiently use limited spectrum and thus increase wireless network capacity. This paper considers a scenario where a primary Service Provider (SP) shares spectrum with secondary SPs and competes for a common pool of customers. We study such a scenario using a model for price competition in which customers select a SP based on the sum of the SP's announced service price and the congestion incurred when using their service. Here, we assume that the primary has strict priority over the secondary and model the resulting congestion via a preemptive priority queue. We characterize the equilibrium of the resulting pricing game. In particular we find that when the service time has a small variance, secondary users can be excluded from the system, while the primary has to offer a lower price than it would if it were a monopolist due to the threat of entry. As the amount of available bandwidth increases, the primary SP's profit will decrease asymptotically to zero. In addition, for some scenarios, we show that social welfare may decrease with additional bandwidth and be less than that obtained without sharing.


09:3009:50, Paper ThA4.4  
Combating Curse of Dimensionality in Resilient Plant Monitoring Systems: Overlapping Decomposition and Knowledge Fusion 
Garcia, Humberto E.  Idaho National Lab 
Meerkov, Semyon  Univ. of Michigan, Ann Arbor 
Ravichandran, Maruthi  Univ. of Michigan, Ann Arbor 
Keywords: Resilient Systems, CyberPhysical Systems, Decentralized and Distributed Control
Abstract: Resilient plant monitoring systems (RPMS) are sensor networks that degrade gracefully under cyberphysical attacks. In the previous work, we have developed an adaptive fourlayer RPMS architecture and evaluated its performance under various attack scenarios. While the steady state performance of this system has been shown to be satisfactory, the transients have not: adaptation time grows exponentially as a function of the number of states in the network. The current paper is intended to provide a method for combating this curse of dimensionality. The approach is based on the idea of overlapping plant decomposition and subsequent fusion of knowledge derived in the overlapping subnetworks. In this paper such a monitoring system is developed (fivelayer architecture), analyzed, and shown to have desirable steady state and, to a certain extent, transient characteristics.


09:5010:10, Paper ThA4.5  
An Experts Learning Approach to Mobile Service Offloading 
Tekin, Cem  Univ. of California, Los Angeles 
van der Schaar, Mihaela  Univ. of California Los Angeles 
Keywords: Machine Learning and Approximate Dynamic Programming, Distributed Computation on Networks, Decentralized and Distributed Control
Abstract: Mobile devices are more and more often called on to perform services which require too much computation power and battery energy. If delay is an important consideration, offloading to the cloud may be too slow and a better approach is to offload to a resourcerich machine in the proximity of the device. This paper develops a new approach to this problem in which the machines are viewed as a collection of experts  but experts that are coupled in space and in time: the current action at a given machine affects the future state of the given machine and of other machines to which the given machine is connected. At any time, given the state and unknown dynamics of the system, the experts available at that time should cooperatively pick the best available actions. Within this framework, we propose online learning algorithms that results in substantial savings in energy consumption.


ThA5 
Lower Level 
Network Coding and Information Theory 
Regular Session 
Chair: Shakkottai, Sanjay  The Univ. of Texas at Austin 
CoChair: Kar, Soummya  Carnegie Mellon Univ 

08:3008:50, Paper ThA5.1  
SumNetworks from Undirected Graphs: Construction and Capacity Analysis 
Tripathy, Ardhendu S.  Iowa State Univ 
Ramamoorthy, Aditya  Iowa State Univ 
Keywords: Network Coding in Communication, Network Coding
Abstract: We consider a directed acyclic network with multiple sources and multiple terminals where each terminal is interested in decoding the sum of independent sources generated at the source nodes. We describe a procedure whereby a simple undirected graph can be used to construct such a textit{sumnetwork} and demonstrate an upper bound on its computation rate. Furthermore, we show sufficient conditions for the construction of a linear network code that achieves this upper bound. Our procedure allows us to construct sumnetworks that have any arbitrary computation rate frac{p}{q} (where p,q are nonnegative integers). Our work significantly generalizes a previous approach for constructing sumnetworks with arbitrary capacities. Specifically, we answer an open question in prior work by demonstrating sumnetworks with significantly fewer number of sources and terminals.


08:5009:10, Paper ThA5.2  
Can a Noisy Encoder Be Used to Communicate Reliably? 
Yang, Yaoqing  Carnegie Mellon Univ 
Grover, Pulkit  Carnegie Mellon Univ 
Kar, Soummya  Carnegie Mellon Univ 
Keywords: Coding Theory, Information Theory, Coding Techniques and Applications
Abstract: In this paper the problem of reliable communication with a noisy encoder is examined. We explicitly provided the construction of the encoder and show that even when all logic gates that constitute the encoder are noisy, reliable communication with a positive rate is still possible. The encoding complexity is shown to be O((log 1/ptar)/(log 1/ϵ)) per bit to achieve a target bit error rate ptar, where ϵ denotes the error probability of each noisy gate. This complexity upper bound is shown to coincide with a lower bound in order sense, and is hence tight. The key technique in the proposed construction is to embed noisy decoders inside the noisy encoder, which are utilized repeatedly to prevent the bit error rate from escalating. The proposed noisy encoder has a direct application in noisy computing of a linear transform.


09:1009:30, Paper ThA5.3  
Asymmetric ComputeAndForward: Going Beyond One Hop 
Tan, Yihua  The Chinese Univ. of Hong Kong 
Yuan, Xiaojun  ShanghaiTech Univ 
Liew, Soung Chang  The Chinese Univ. of Hong Kong 
Kavcic, Aleksandar  Univ. of Hawaii 
Keywords: Network Coding in Communication, Information Theoretic Approaches in Wireless Communications, Wireless Communication Systems
Abstract: We consider a twohop relay model in which multiple sources communicate with a single destination via multiple distributed relays. We propose an asymmetric ComputeandForward (CoF) scheme that allows lattice coding with different coarse and fine lattices at the sources. The proposed scheme is motivated by the observation that, in an asymmetric CoF system, a higher transmission power at a source does not necessarily translate to a higher achievable information rate. We show that significant performance enhancement can be achieved by optimizing the transmission powers of the sources below their respective budgets. Further, the asymmetric construction of lattice coding allows the relays to conduct different modulo operations to reduce their forwarding rates, thereby supporting higher rates at the sources. However, modulo operations in general incur information loss, and so need to be carefully designed to ensure that the destination can successfully recover the source messages. As such, we propose a novel succesive recovering algorithm for decoding at the destination, and establish sufficient conditions to guarantee successful recovery. Numerical results are provided to verify the superiority of our proposed scheme over other schemes.


09:3009:50, Paper ThA5.4  
SignComputeResolve for Random Access 
Goseling, Jasper  Univ. of Twente 
Stefanovic, Cedomir  Aalborg Univ 
Popovski, Petar  Aalborg Univ 
Keywords: Wireless Communication Systems, Network Coding in Communication
Abstract: We present an approach to random access that is based on three elements: physicallayer network coding, signature codes and tree splitting. In presence of a collision physicallayer network coding enables the receiver to decode the sum of the information that was transmitted by the individual users. For each user this information consists of the data that the user wants to communicate as well as the user's signature. As long as no more than K users collide, their identities can be recovered from the sum of their signatures. A splitting protocol is used to deal with the case that more than K users collide. We demonstrate that compared to, for instance coded random access, our approach is significantly increasing the performance of the system, both in terms of user resolution rate as well as overall throughput of the system.


09:5010:10, Paper ThA5.5  
Scheduling in Densified Networks: Algorithms and Performance 
Moharir, Sharayu Arun  Univ. of Texas at Austin 
Krishnasamy, Subhashini  The Univ. of Texas at Austin 
Shakkottai, Sanjay  The Univ. of Texas at Austin 
Keywords: Wireless Communication Systems, Queuing Theory and Analysis, Performance Analysis
Abstract: With increasing data demand, wireless networks are evolving to a hierarchical architecture where coverage is provided by both widearea basestations (BS) and dense deployments of shortrange access nodes (AN) (e.g., small cells). The dense scale and mobility of users provide new challenges for schedul ing: (i) High flux in mobiletoAN associations, where mobile nodes quickly change associations with access nodes (timescale of seconds) due to their small footprint, and (ii) multipoint connectivity, where mobile nodes are simultaneously connected to several access nodes at any time. We study such a densified scenario with multichannel wireless links (e.g., multichannel OFDM) between nodes (BS/AN/mobile). We first show that traditional algorithms that forward each packet at most once, either to a single access node or a mobile user, do not have good delay performance. We argue that the fast association dynamics between access nodes and mobile users necessitate a multipoint relaying strategy, where multiple access nodes have duplicate copies of the data, and coordinate to deliver data to the mobile user. Surprisingly, despite data replication and no coordination between ANs, we show that our algorithm (a distributed scheduler – DIST) can approximately stabilize the system in largescale instantiations of this setting, and further, performs well from a queuelength/delay perspective (shown via large deviation bounds).


ThB1 
Library 
Applications of Information Theory 
Invited Session 
Chair: Viswanath, Pramod  Univ. of Illinois 

10:3010:50, Paper ThB1.1  
A Deterministic View on the Capacity of Bandlimited Functions (I) 
Lim, Taehyung Jayel  Univ. of California at San Diego 
Franceschetti, Massimo  Univ. of California at San Diego 
Keywords: Information Theory
Abstract: In this paper, the relationship between Kolmogorov's capacity and Shannon's capacity in the context of communication with squareintgrable, bandlimited signals subject to additive noise is illustrated. Upper and lower bounds on the Kolmogorov capacity are derived, that improve upon previous results. The functional form of these bounds is analogous to the one of the capacity of the additive white Gaussian noise channel, showing an essential similarity between the deterministic and the stochastic approaches, and suggesting that communication limits are a fundamental physical concept that transcends the details of the specific mathematical description chosen for their representation.


10:5011:10, Paper ThB1.2  
PointToPoint Codes for Interference Channels: A Journey Toward High Performance at Low Complexity (I) 
Kim, YoungHan  UCSD 

11:1011:30, Paper ThB1.3  
Efficient Statistics: Extracting Information from IID Observations (I) 
Huang, ShaoLun  MIT 
Makur, Anuran  Massachusetts Inst. of Tech 
Kozynski, Fabián  Massachusetts Inst. of Tech 
Zheng, Lizhong  MIT 
Keywords: Statistical Signal Processing, Source Coding and Compression
Abstract: In this paper, we study how information can be conveyed through a noisy channel and extracted efficiently, under the scenarios and applications, where the observing order of the symbols does not carry any useful information. In such cases, the informationcarrying objects are the empirical distributions of the transmitted and received symbol sequences. We develop a local geometric structure and a new coordinate system for the space of distributions. With this approach, we can decompose the computation of the posterior distribution of the data into a sequence of score functions, with decreasing information volumes. Thus, when our goal is not to recover the entire data, but only to detect certain features of the data, we only need to compute the first few scores, which greatly simplifies the problem. We demonstrate the use of our technique with some image processing examples based on graphical models.


11:3011:50, Paper ThB1.4  
Refraction and Optimal Focusing at a Planar Interface (I) 
Ho, John  Stanford Univ. 
Poon, Ada  Stanford Univ. 

11:5012:10, Paper ThB1.5  
Fundamental Limits of DNA Variant Calling (I) 
Mohajer, Soheil  Univ. of Minnesota 
Kannan, Sreeram  Univ. of Washington Seattle 
Tse, David  UC Berkeley 

12:1012:30, Paper ThB1.6  
Must One Learn the Channel to Communicate at Capacity? (I) 
Gao, Yuguang  Cornell Univ 
Wagner, Aaron  Cornell Univ 
Keywords: Information Theory, Information Theoretic Approaches in Wireless Communications
Abstract: We consider a large alphabet channel model with noiseless feedback in which the channel is not known to the encoder or the decoder, and we provide several results to the effect that universal communication at capacity is possible only if it is possible for the encoder and decoder to completely learn the channel prior to the end of transmission.


ThB2 
Solarium 
Control and Optimization in Electrical Energy Systems: Smart Grid
Applications and Beyond I 
Invited Session 
Chair: DominguezGarcia, Alejandro  Univ. of Illinois at UrbanaChampaign 

10:3010:50, Paper ThB2.1  
Feasibility of Power System Structure Preserving Linear Transformations for the Optimal Power Flow Problem (I) 
Wu, Dan  Univ. of WisconsinMadison 
Lesieutre, Bernard  Univ. of Wisconsin 
Ramanathan, Parmesh  Univ. of WisconsinMadison 
Keywords: CyberPhysical Systems, Optimization
Abstract: This paper introduces a method to construct a linear transformation on extended coordinates between two AC optimal power flow (OPF) problems. Furthermore, the paper also presents the optimality preserving conditions to map any local extremum of one problem to any local extremum of the other.


10:5011:10, Paper ThB2.2  
Toward a Scalable ChanceConstrained Formulation for Unit Commitment to Manage High Penetration of Variable Generation (I) 
Martinez, Gabriela  Cornell Univ 
Anderson, C. Lindsay  Cornell Univ 
Keywords: Optimization, Stochastic Systems and Control
Abstract: In this work, a riskaverse optimization model is applied to the security constrained unit commitment problem. The optimal dayahead scheduling of the system generators is formulated as a chanceconstrained optimiza tion model in which the load balance constraint is satisfied with a userdefined probability level. The assumption of a specific underlying distribution is avoided and a flexible datadriven uncertainty set is used to obtain a feasible riskaverse scheduling of the system. Results on a test scale system show the flexible and effective nature of this approach and indicate significant potential for application to large scale instances.


11:1011:30, Paper ThB2.3  
Optimal LoadSide Control for Frequency Regulation in Smart Grids (I) 
Mallada, Enrique  California Inst. of Tech 
Zhao, Changhong  California Inst. of Tech 
Low, Steven  California Inst. of Tech 
Keywords: Networked Control Systems, CyberPhysical Systems, Decentralized and Distributed Control
Abstract: Frequency control rebalances supply and demand while maintaining the network state within operational margins. It is implemented using fast ramping reserves that are expensive and wasteful, and which are expected to grow with the increasing penetration of renewables. The most promising solution to this problem is the use of demand response, i.e. load participation in frequency control. Yet it is still unclear how to efficiently integrate load participation without introducing instabilities and violating operational constraints. In this paper we present a comprehensive loadside frequency control mechanism that can maintain the grid within operational constraints. Our controllers can rebalance supply and demand after disturbances, restore the frequency to its nominal value and preserve interarea power flows. Furthermore, our controllers are distributed (unlike generationside), can allocate load updates optimally, and can maintain line flows within thermal limits. We prove that such a distributed loadside control is globally asymptotically stable and illustrate its convergence with simulation.


11:3011:50, Paper ThB2.4  
Unifying Concepts Underlying Low Dimensional Behavior in Phasor Measurement Data for Both Voltage and Small Signal Stability (I) 
DeMarco, Christopher L.  Univ. of WisconsinMadison 
Lim, Jong Min  Univ. of Wisconsin  Madison 

11:5012:10, Paper ThB2.5  
Distributed Stopping for Average Consensus Using Double Linear Iterative Strategies (I) 
Manitara, Nicolaos  Univ. of Cyprus 
Hadjicostis, Christoforos  Univ. of Cyprus 
Keywords: Decentralized and Distributed Control, Distributed Computation on Networks, Sensor Networks
Abstract: We consider how double linear iterative strategies for asymptotic average consensus can be adapted so that the nodes can determine, in a distributed fashion, a stopping criterion that allows them to terminate (in finite time) the execution of the iterations when approximate average consensus has been reached. The nodes are said to have reached approximate average consensus when each of them has a value that is close to the desirable average (in a way that we precisely define). We consider both undirected and directed graphs, and compare the number of iterations and transmissions required by the proposed protocols against previously proposed stopping protocols for approximate average consensus.


ThB3 
Butternut 
Information Theory I 
Regular Session 
Chair: Bloch, Matthieu  Georgia Inst. of Tech 

10:3010:50, Paper ThB3.1  
Information Spectrum Approach to Strong Converse Theorems for Degraded Wiretap Channels 
Tan, Vincent  National Univ. of Singapore 
Bloch, Matthieu  Georgia Inst. of Tech 
Keywords: Information Theory, Security and Trust
Abstract: We consider block codes for degraded wiretap channels in which the legitimate receiver decodes the message with an asymptotic error probability varepsilon but the leakage to the eavesdropper vanishes. For discrete memoryless and Gaussian wiretap channels, we show that the maximum rate of transmission does not depend on varepsilon in [0,1), i.e., such channels possess the partial strong converse property. Furthermore, we derive sufficient conditions for the partial strong converse property to hold for memoryless but nonstationary symmetric and degraded wiretap channels. Our proof techniques leverage the information spectrum method, which allows us to establish a necessary and sufficient condition for the partial strong converse to hold for general wiretap channels without any information stability assumptions.


10:5011:10, Paper ThB3.2  
A RateDistortion Based Secrecy System with Side Information at Decoders 
Song, Chen  Princeton Univ 
Cuff, Paul  Princeton Univ 
Poor, H. Vincent  Princeton Univ 
Keywords: Information Theory, Security and Trust, Information Theoretic Approaches in Wireless Communications
Abstract: A secrecy system with side information at the decoders is studied in the context of lossy source compression over a noiseless broadcast channel. The decoders have access to different side information sequences that are correlated with the source. The fidelity of the communication to the legitimate receiver is measured by a distortion metric, as is traditionally done in the WynerZiv problem. The secrecy performance of the system is also evaluated under a distortion metric. An achievable ratedistortion region is derived for the general case of arbitrarily correlated side information. Exact bounds are obtained for several special cases in which the side information satisfies certain constraints. An example is considered in which the side information sequences come from a binary erasure channel and a binary symmetric channel.


11:1011:30, Paper ThB3.3  
An Extremal Inequality for Long Markov Chains 
Courtade, Thomas  Univ. of California, Berkeley 
Jiao, Jiantao  Stanford Univ 
Keywords: Information Theory
Abstract: Let X,Y be jointly Gaussian vectors, and consider random variables U,V that satisfy the Markov constraint UXYV. We prove an extremal inequality relating the mutual informations between all {4 choose 2} pairs of random variables from the set (U,X,Y,V). As a first application, we show that the rate region for the twoencoder quadratic Gaussian source coding problem follows as an immediate corollary of the the extremal inequality. In a second application, we establish the rate region for a vectorGaussian source coding problem where LöwnerJohn ellipsoids are approximated based on rateconstrained descriptions of the data.


11:3011:50, Paper ThB3.4  
Asymptotic Capacity of a Random Channel 
Sutter, Tobias  ETH Zurich 
Sutter, David  ETH Zurich 
Lygeros, John  ETH Zurich 
Keywords: Information Theory, Optimization
Abstract: We consider discrete memoryless channels with input and output alphabet size n whose channel transition matrix consists of entries that are independent and identically distributed according to some probability distribution nu on R_+ before being normalized, where nu is such that E[(X log X)^2]


11:5012:10, Paper ThB3.5  
Ergodic Capacity under Channel Distribution Uncertainty 
Loyka, Sergey  Univ. of Ottawa 
Charalambous, Charalambos  Univ. of Cyprus 
Keywords: Information Theory, Information Theoretic Approaches in Wireless Communications, Wireless Communication Systems
Abstract: The impact of channel distribution uncertainty on the performance of fading channels is studied. The compound capacity of a class of ergodic fading channels subject to channel distribution uncertainty is obtained, for arbitrary noise and nominal channel distribution. The saddlepoint property is established, so that the compound capacity equals to the worstcase channel capacity, which is characterized as 1D convex optimization problem. The properties of worstcase mutual information and channel distribution are studied. Closedform solutions are obtained in the asymptotic regimes of small and large uncertainty, and an error floor effect is established in the latter case. The known results for the ergodic capacity of the Gaussian MIMO channel under i.i.d. Rayleigh fading are shown to hold under the channel distribution uncertainty as well.


12:1012:30, Paper ThB3.6  
Partial Decode–Forward Relaying for the Gaussian TwoHop Relay Network 
Li, Jing  Xidian Univ 
Kim, YoungHan  UCSD 
Keywords: Network Coding in Communication, Information Theory, Coding for Wireless Communications
Abstract: The multicast capacity of the Gaussian twohop relay network with one source, N relays, and L destinations is studied. It is shown that a careful modification of the partial decodeforward coding scheme, in which the relays cooperate through degraded sets of message parts, achieves the cutset upper bound within log N bits regardless of the channel gains and power constraints. This scheme improves upon a previous scheme by Chern and "Ozg"ur, which is also based on partial decodeforward yet has an unbounded gap from the cutset bound for L ge 2 destinations. As an added benefit, the achievable rate of the proposed scheme involves evaluating rate for L(N+1) cuts out of the total L 2^N possible cuts.


ThB4 
Pine 
Polar and LP Coding 
Regular Session 
Chair: Mondelli, Marco  EPFL 

10:3010:50, Paper ThB4.1  
How to Achieve the Capacity of Asymmetric Channels 
Mondelli, Marco  EPFL 
Hassani, Seyed Hamed  ETHZ 
Urbanke, Rudiger  EPFL 
Keywords: Coding Techniques and Applications, Coding Theory
Abstract: We describe coding techniques that achieve the capacity of a discrete memoryless asymmetric channel. To do so, we discuss how recent advances in coding for symmetric channels yield more efficient solutions also for the asymmetric case. In more detail, we consider three basic approaches. The first one is Gallager's scheme that concatenates a linear code with a nonlinear mapper, in order to bias the input distribution. We explicitly show that both polar codes and spatially coupled codes can be employed in this scenario. Further, we derive a scaling law between the gap to capacity, the cardinality of channel input and output alphabets, and the required size of the mapper. The second one is an integrated approach in which the coding scheme is used both for source coding, in order to create codewords with the capacityachieving distribution, and for channel coding, in order to provide error protection. Such a technique has been recently introduced by Honda and Yamamoto in the context of polar codes, and we show how to apply it also to the design of sparse graph codes. The third approach is based on an idea due to Bocherer and Mathar and separates completely the two tasks of source coding and channel coding by "chaining" together several codewords. We prove that we can combine any suitable source code with any suitable channel code in order to provide optimal schemes for asymmetric channels. In particular, polar codes and spatially coupled codes fulfill the required conditions.


10:5011:10, Paper ThB4.2  
On the Scaling Exponent of Binary Polarization Kernels 
Fazeli, Arman  Univ. of California, San Diego 
Vardy, Alexander  Univ. of California San Diego 
Keywords: Coding Theory, Coding Techniques and Applications, Coding for Wireless Communications
Abstract: A given l times l polarization kernel K transforms l copies of the underlying channel W into l bitchannels W_1,W_2,ldots,W_l. Notably, if W is a BEC with erasure probability z, then each of W_1,W_2,ldots,W_l is also a BEC. The erasure probabilities of W_1,W_2,ldots,W_l are polynomials in z with integer coefficients. We refer to the corresponding set of polynomials {p_1(z),p_2(z),ldots,p_l(z)} as the polarization behavior of K; the scaling exponent of K is completely determined by its polarization behavior. We show that the polarization behavior can be characterized in terms of a nested chain of linear codes, and use this fact to prove that computing the polarization behavior is NPhard. We further prove that an arbitrary l times l polarization kernel K can be transformed into a lowertriangular form without altering its polarization behavior. We then use this result to answer the following question: what is the smallest value of l for which Arikan's scaling exponent mu(G) = 3.627 can be improved? We show that mu(K) ge 3.627 for all l times l kernels with l le 7. On the other hand, we explicitly construct an 8times8 matrix K_8 with mu(K_8) = 3.577. We extend our construction of K_8 into a general heuristic design method. Guided by this design method, we employ the coset structure of ReedMuller codes and bent functions in order to construct a 16times16 kernel K_{16} with mu(K_{16}) = 3.356.


11:1011:30, Paper ThB4.3  
Universal Source Polarization and an Application to a MultiUser Problem 
Ye, Min  Univ. of Maryland 
Barg, Alexander  Univ. of Maryland 
Keywords: Coding Theory, Information Theory
Abstract: We propose a scheme that universally achieves the smallest possible compression rate for a class of sources with side information, and develop an application of this result for a joint source channel coding problem over a broadcast channel.


11:3011:50, Paper ThB4.4  
Concatenations of Polar Codes with Outer BCH Codes and Convolutional Codes 
Wang, Ying  Texas A&M Univ 
Narayanan, Krishna  Texas A&M Univ 
Keywords: Coding Theory, Coding Techniques and Applications, Coding for Wireless Communications
Abstract: We analyze concatenation schemes of polar codes with outer binary BCH codes and convolutional codes. We show that both BCHpolar and Convolutionalpolar (Convpolar) codes can have frame error rate that decays exponentially with the frame length, which is a substantial improvement over standalone polar codes. With the increase in the cutoff rate of the channel after polarization, long constraintlength convolutional codes with sequential decoding suffice to achieve a frame error rate that decays exponentially with the frame length, whereas the average decoding complexity is low. Numerical results show that both BCHpolar codes and Convpolar codes can outperform standalone polar codes for some lengths and choice of decoding algorithms used to decode the outer codes. For the additive white Gaussian noise channel, Convpolar codes substantially outperform concatenated Reed Solomonpolar codes with a careful choice of the lengths of inner and outer codes.


11:5012:10, Paper ThB4.5  
Interactive Function Computation Via Polar Coding 
Gulcu, Talha Cihad  Univ. of Maryland, Coll. Park 
Barg, Alexander  Univ. of Maryland 
Keywords: Information Theory, Coding Theory, Network Coding in Communication
Abstract: In a series of papers N. Ma and P. Ishwar (201113) considered a range of distributed source coding problems that arise in the context of iterative computation of functions, characterizing the region of achievable communication rates. We consider the problems of interactive computation of functions by two terminals and interactive computation in a collocated network, showing that the rate regions for both these problems can be achieved using several rounds of polarcoded transmissions.


12:1012:30, Paper ThB4.6  
LPDecodable Multipermutation Codes 
Liu, Xishuo  Univ. of WisconsinMadison 
Draper, Stark  Univ. of Toronto 
Keywords: Coding Techniques and Applications, Data Storage, Optimization
Abstract: In this paper, we introduce a new way of constructing and decoding multipermutation codes. Multipermutations are permutations of a multiset that may consist of duplicate entries. We first introduce a new class of matrices called multipermutation matrices. We characterize the convex hull of multipermutation matrices. Based on this characterization, we propose a new class of codes that we term LPdecodable multipermutation codes. Then, we derive two LP decoding algorithms. We first formulate an LP decoding problem for memoryless channels. We then derive an LP algorithm that minimizes the Chebyshev distance. Finally, we show a numerical example of our algorithm.


ThB5 
Lower Level 
Signal Processing for Big Data 
Invited Session 
Chair: Moulin, Pierre  Univ. of Illinois 
Organizer: Moulin, Pierre  Univ. of Illinois 
Organizer: Veeravalli, Venugopal  Univ. of Illinois 

10:3010:50, Paper ThB5.1  
Dictionary Recovery with (Almost) Proportional Sparsity (I) 
Wright, John  Columbia Univ. 

10:5011:10, Paper ThB5.2  
Unsupervised Nonparametric Anomaly Detection: A Kernel Method (I) 
Zou, Shaofeng  Syracuse Univ 
Liang, Yingbin  Syracuse Univ 
Poor, H. Vincent  Princeton Univ 
Shi, Xinghua  Univ. of North Carolina at Charlotte 
Keywords: Intrusion/Anomaly Detection and Diagnosis, Detection and Estimation
Abstract: An anomaly detection problem is investigated, in which s out of n sequences are anomalous and need to be detected. Each sequence consists of m independent and identically distributed (i.i.d.) samples drawn either from a nominal distribution p or from an anomalous distribution q that is distinct from p. Neither p nor q is known a priori. Two scenarios respectively with s known and unknown are studied. Distributionfree tests are constructed based on the metric of the maximum mean discrepancy (MMD). It is shown that if the value of s is known, as n goes to infinity, the number m of samples in each sequence should be of order O(log n) or larger to guarantee that the constructed test is exponentially consistent. On the other hand, if the value of s is unknown, the number m of samples in each sequence should be of the order strictly greater than O(log n) to guarantee the constructed test is consistent. The computational complexity of all tests are shown to be polynomial. Numerical results are provided to confirm the theoretic characterization of the performance. Further numerical results on both synthetic data sets and real data sets demonstrate that the MMDbased tests outperform or perform as well as other approaches.


11:1011:30, Paper ThB5.3  
Distributed Dimension Reduction for Topological Data Analysis (I) 
Krim, Hamid  North Carolina State Univ. 

11:3011:50, Paper ThB5.4  
Fast and Efficient Compressive PhaseRetrieval Based on SparseGraph Codes (I) 
Pedarsani, Ramtin  UC Berkeley 
Lee, Kangwook  Uc Berkeley 
Ramchandran, Kannan  UC Berkeley 
Keywords: Sparse Data Analysis, Coding Techniques and Applications, Coding Theory
Abstract: We consider the problem of recovering a complex signal x in mathbb{C}^n from m intensity measurements of the form a_i x, ~1 leq i leq m, where a_i is a measurement row vector. Our main focus is on the case where the measurement vectors are unconstrained, and where x is exactly Ksparse, or the socalled general compressive phaseretrieval problem. We introduce PhaseCode, a novel family of fast and efficient algorithms (that includes Unicolor PhaseCode and Multicolor PhaseCode) that are based on a sparsegraph coding framework. As one instance, our Unicolor PhaseCode algorithm can provably recover, with high probability, all but a tiny 10^{7} fraction of the significant signal components, using at most m=14K measurements, which is a small constant factor from the fundamental limit, with an optimal mathcal{O}(K) decoding time and an optimal mathcal{O}(K) memory complexity. We provide extensive simulation results that validate the practical power of our proposed algorithms. A key contribution of our work is the novel use of codingtheoretic tools like density evolution methods for the design and analysis of fast and efficient algorithms for compressive phaseretrieval problems. This contrasts and complements popular approaches to the phase retrieval problem based on alternatingminimization, convexrelaxation, and semidefinite programming.


11:5012:10, Paper ThB5.5  
Signal Detection on Graphs (I) 
Saligrama, Venkatesh  Boston Univ. 

12:1012:30, Paper ThB5.6  
Distributed Stochastic Optimization and Learning (I) 
Srebro, Nathan  Toyota Tech. Inst. at Chicago 
Shamir, Ohad  Weizmann Inst. of Science 
Keywords: Signal Processing for big data
Abstract: We consider the problem of distributed stochastic optimization, where each of several machines has access to samples from the same source distribution, and the goal is to jointly optimize the expected objective w.r.t. the source distribution, minimizing: (1) overall runtime; (2) communication costs; (3) number of samples used. We study this problem systematically, highlighting fundamental limitations, and differences versus distributed consensus problems where each machine has a different, independent, objective. We show how the best known guarantees are obtained by a minibatched SGD approach, and contrast the runtime and sample costs of the approach with those of other distributed optimization algorithms.


ThB6 
Visitor Center 
Compressive Sensing 
Regular Session 
Chair: Baron, Dror  North Carolina State Univ 

10:3010:50, Paper ThB6.1  
Compressed Sensing Via Universal Denoising and Approximate Message Passing 
Ma, Yanting  North Carolina State Univ. 
Zhu, Junan  North Carolina State Univ. 
Baron, Dror  North Carolina State Univ. 

10:5011:10, Paper ThB6.2  
InfoGreedy Sequential Adaptive Compressed Sensing 
Gabor, Braun  Georgia Inst. of Tech 
Pokutta, Sebastian  Georgia Inst. of Tech 
Xie, Yao  Georgia Inst. of Tech 
Keywords: Statistical Signal Processing, Sparse Data Analysis, Detection and Estimation
Abstract: We present an informationtheoretic framework for sequential adaptive compressed sensing, InfoGreedy Sensing, where measurements are chosen to maximize the extracted information conditioned on the previous measurements. We lower bound the expected number of measurements for a given accuracy, and derive various forms of InfoGreedy Sensing algorithms under different signal and noise models, as well as under the sparse measurement vector constraint. We also show the InfoGreedy optimality of the bisection algorithm for ksparse signals, as well as that of the iterative algorithm which measures using the maximum eigenvector of the posterior Gaussian signals. Numerical examples demonstrate the good performance of the proposed algorithms using simulated and real data.


11:1011:30, Paper ThB6.3  
Estimating Structured Signals in Sparse Noise: A Precise Noise Sensitivity Analysis 
Thrampoulidis, Christos  California Inst. of Tech 
Hassibi, Babak  California Inst. of Tech 
Keywords: Sparse Data Analysis, Optimization
Abstract: We consider the problem of estimating a structured signal x_0 from linear, underdetermined and noisy measurements y=Ax_0+z, in the presence of emph{sparse} noise z. A natural approach to recovering x_0, that takes advantage of both the structure of x_0 and the sparsity of z is solving: hat x=argmin_x yAx_1 text{ subject to } f(x)leq f(x_0) (constrained LAD estimator). Here, f is a convex function aiming to promote the structure of x_0, say ell_1norm to promote sparsity or nuclear norm to promote lowrankness. We assume that the entries of A and the nonzero entries of z are i.i.d normal with variances 1 and sigma^2, respectively. Our analysis precisely characterizes the asymptotic noise sensitivity hat xx_0_2^2/sigma^2 in the limit sigma^2rightarrow 0. We show analytically that the LAD method outperforms the more popular LASSO method when the noise is sparse. At the same time its performance is no more than pi/2 times worse in the presence of nonsparse noise. Our simulation results verify the validity of our theoretical predictions.


11:3011:50, Paper ThB6.4  
Gaussian DistortionRate Function under SubNyquist Nonuniform Sampling 
Kipnis, Alon  Stanford Univ 
Goldsmith, Andrea  Stanford Univ 
Eldar, Yonina  Tech. Israel Inst. of Tech 
Keywords: Source Coding and Compression, Information Theory, Detection and Estimation
Abstract: A bound on the amount of distortion in the reconstruction of a stationary Gaussian process from its ratelimited samples is derived. The bound is based on a combined sampling and source coding problem in which a Gaussian stationary process is described from a compressed version of its values on an infinite discrete set. We show that the distortion in reconstruction cannot be lower than the distortionrate function based on optimal uniform filterbank sampling using a sufficient number of sampling branches. This can be seen as an extension of Landau's theorem on a necessary condition for optimal recovery of a signal from its samples, in the sense that it describes both the error as a result of subsampling and the error incurred due to lossy compression of the samples.


11:5012:10, Paper ThB6.5  
Sensitivity Analysis in RIPless Compressed Sensing 
Abdolhosseini Moghadam, Abdolreza  Michigan State Univ 
Aghagolzadeh, Mohammad  Michigan State Univ 
Radha, Hayder  Michigan State Univ 
Keywords: Sparse Data Analysis, Universal Algorithms and Machine Learning, Optimization
Abstract: Sensitivity analysis in optimization theory explores how the solution to a particular optimization problem changes as the objective function or constraints of such optimization problem perturb. A recent and yet important class of optimization problems is the framework of compressed sensing where the objective is to find the sparsest solution to an underdetermined and possibly noisy system of linear equations. In this paper, we show that by utilizing some tools in sensitivity analysis, namely Invariant Support Sets (ISS), one can improve certain developed results in the field of compressed sensing. More specifically, we show that in a noiseless and RIPless setting, the recovery process of a compressed sensing framework is a binary event in the sense that either all vectors with the same support and sign pattern can be recovered from their compressive samples or none can be estimated correctly. However, in a noisy and RIPless setting, recovering only one signal from its limited noisy samples guarantees that there exist signals (possibly even with different supports and sign patterns) and noise vectors that shall be recovered with good accuracies by using Lasso.


12:1012:30, Paper ThB6.6  
Optimal Tuning of Approximate Message Passing 
Mousavi, Ali  Rice Univ. 
Maleki, Arian  Columbia Univ. 
Baraniuk, Richard  Rice Univ. 

ThC1 
Library 
Security 
Invited Session 
Chair: Kiyavash, Negar  Univ. of Illinois 

13:3013:50, Paper ThC1.1  
On Private Learning and Optimization (I) 
Bassily, Raef  Pennsylvania State Univ 
Thakurta, Abhradeep Guha  Microsoft Res 
Smith, Adam  Pennsylvania State Univ 

13:5014:10, Paper ThC1.2  
On InformationTheoretic Metrics for SymmetricKey Encryption and Privacy (I) 
Calmon, Flavio  Massachusetts Inst. of Tech 
Médard, Muriel  MIT 
Varia, Mayank  Lincoln Labs, Massachusetts Inst. of Tech 
Keywords: Security and Trust, Information Theory, Coding Techniques and Applications
Abstract: Most practical security systems do not achieve perfect secrecy, i.e. the information observed by a computationally unbounded eavesdropper is not independent of the plaintext message. Nevertheless, there may still be properties of the plaintext that the eavesdropper cannot reliably infer. In this paper, we build on previous work by the authors and introduce new bounds that are used to quantify how well an adversary can estimate certain functions of the plaintext in the nonperfect secrecy regime. In particular, we present lower bounds for the minimummeansquarederror of estimating a target function of the plaintext given that a certain class of functions of the plaintext is known to be hard (or easy) to infer, either by design of the security system or by restrictions imposed on the adversary. We demonstrate how these bounds can be applied to characterize fundamental security properties of symmetrickey encryption schemes. Our results also shed light on the fundamental privacyutility tradeoff that exists in privacypreserving systems.


14:1014:30, Paper ThC1.3  
MultiTerminal Networks with an Untrusted Relay (I) 
Zewail, Ahmed  The Pennsylvania State Univ 
Nafea, Mohamed  The Pennsylvania State Univ 
Yener, Aylin  The Pennsylvania State Univ 
Keywords: Information Theoretic Approaches in Wireless Communications, Security and Trust, Information Theory
Abstract: This paper investigates the impact of cooperation with an untrusted relay in multisource multidestination networks.The set up considered is one where the relay is the only means of communications due to the absence of direct links between the sources and the destinations. Since the relay is untrusted, all messages from the sources need to be kept secret from the relay. Furthermore, the destinations are assumed to have different levels of security clearance, i.e., some private messages should only be decoded by their intended receiver and should be kept secret from other destinations. An achievable secure rate region is found by using random binning at the sources, cooperative jamming from the destinations, and compressandforward at the relay. Additionally, a genie aided outer bound on the secure rate region is derived. Comparison of inner and outer bounds are provided.


14:3014:50, Paper ThC1.4  
A RateDisortion Perspective on Local Differential Privacy (I) 
Sarwate, Anand  Rutgers Univ 
Sankar, Lalitha  Arizona State Univ 
Keywords: Information Theory, Security and Trust
Abstract: Local differential privacy is a model for privacy in which an untrusted statistician collects data from individuals who mask their data before revealing it. While randomized response has shown to be a good strategy when the statistician's goal is to estimate a parameter of the population, we consider instead the problem of locally private data publishing, in which the data collector must publish a version of the data it has collected. We model utility by a distortion measure and consider privacy mechanisms that act via a memoryless channnel operating on the data. If we consider a the source distribution to be unknown but in a class of distributions, we arrive at a robustrate distortion model for the privacydistortion tradeoff. We show that under Hamming distortions, the differential privacy risk is lower bounded for all nontrivial distortions, and that the lower bound grows logarithmically in the alphabet size.


14:5015:10, Paper ThC1.5  
Link Privacy in Social Networks (I) 
Mittal, Prateek  Princeton Univ. 

ThC2 
Solarium 
Bounds and Duality in Network Coding 
Invited Session 
Chair: El Rouayheb, Salim  IIT Chicago 

13:3013:50, Paper ThC2.1  
Achievable Schemes and Limits for Local Recovery on a Graph (I) 
Mazumdar, Arya  Univ. of MinnesotaTwin Cities 
Keywords: Coding Theory, Data Storage, Network Coding
Abstract: Recently, a graphtheoretic model for a singlefailurerecoverable distributed storage system was proposed. Unlike the usual local recovery model of codes for distributed storage, this model accounts for the fact that each server or storage node in a network is connectible to only some, and not all other, nodes. Here we provide bounds and constructive schemes for data storage in such networks. We also impose an additional requirement on the codes for such model  a minimum distance guarantee. The model is further generalized for multiple node failures and cooperative repairs.


13:5014:10, Paper ThC2.2  
On the Average Entropy Regions (I) 
Salimi, Amir  Texas A&M Univ. 
Liu, Tie  Texas A&M Univ. 
Cui, Shuguang  Texas A&M Univ. 
Tian, Chao  Texas A&M Univ. 
Chen, Jun  McMaster Univ. 

14:1014:30, Paper ThC2.3  
Finite Length Analysis of CachingAided Coded Multicasting (I) 
Shanmugam, Karthikeyan  Univ. of Texas at Austin 
Ji, Mingyue  Univ. of Southern California 
Tulino, Antonia  Bell Lab. (AlcatelLucent) 
Llorca, Jaime  Bell Labs 
Dimakis, Alex  UT Austin 
Keywords: Data Storage, Coding Theory
Abstract: In this work we study a noiseless broadcast link serving K users whose requests arise from a library of N files. Every user is equipped with a cache of size M files each. It has been shown that by splitting all the files into packets and placing individual packets in a random independent manner across all the caches, it requires at most N/M file transmissions for any set of demands from the library. The achievable delivery scheme involves linearly combining packets of different files following a greedy clique cover solution to the underlying index coding problem. This remarkable multiplicative gain of decentralized random caching has been established in the asymptotic regime when the number of packets per file F, scales to infinity. In this work, we initiate the finitelength analysis of random caching schemes when the number of packets F is a function of the system parameters M,N,K. Specifically, we show that existing random placement and greedy clique cover delivery schemes, while providing large gains in the asymptotic regime, can have at most a multiplicative gain of 2 if the number of packets is subexponential. Further, for any clique cover based coded delivery and a large class of random caching schemes, that includes the existing ones, we show that the number of packets required to get a multiplicative gain of 2g is at least O((N/M )g ). We exhibit a caching and an efficient clique cover based coded delivery scheme that approximately achieves this lower bound. We also provide tight concentration results that show that the average (over the random caching involved) number of transmissions concentrates very well with only polynomial number of packets in the rest of the parameters.


14:3014:50, Paper ThC2.4  
Chop and Roll: Improving the Cutset Bound (I) 
Kamath, Sudeep  Princeton Univ 
Kim, YoungHan  UCSD 
Keywords: Network Coding, Information Theory
Abstract: A new outer bound on the capacity region of a general noisy network with multiple messages is established. The bound considers an ordered partition of the nodes in the network, and has an intuitive interpretation as the directed information between inputs and outputs across these subsets of the partition. The standard cutset bound is recovered as a special case when the partition has two subsets. The new bound extends several existing bounds to the general network that were obtained for special classes of networks. Examples include the generalized network sharing (GNS) bound for wireline networks by Kamath, Tse, and Anantharam, the GNS bound for Gaussian networks by Kamath, Kannan, and Viswanath, and the generalized cutset bound for deterministic networks by Shomorony and Avestimehr. It is demonstrated by a few simple examples that the improvement over the cutset bound can be significant.


14:5015:10, Paper ThC2.5  
An Algorithm for Simultaneous Partial Inverses 
Yu, JiunHung  ETH Zurich 
Loeliger, HansAndrea  ETH Zurich 
Keywords: Coding Techniques and Applications
Abstract: The Simultaneous partialinverse problem is similar to the multisequence shiftregister synthesis problem. The paper introduces the problem and proposes a new algorithm for its solution. An application to decoding interleaved ReedSolomon codes, beyond half the minimum distance, is also demonstrated.


ThC3 
Butternut 
Topics in Network Theory 
Regular Session 
Chair: Silva, Alonso  AlcatelLucent Bell Labs France 
CoChair: Taha, Ahmad  Purdue Univ. School of Electrical and Computer Engineering 

13:3013:50, Paper ThC3.1  
Stability Analysis of Networked Control Systems with Unknown Inputs 
Taha, Ahmad  Purdue Univ. School of Electrical and Computer Engineering 
Elmahdi, Ahmed  Purdue Univ. School of Electrical and ComputerEngineering 
Panchal, Jitesh  Assistant Professor, School of Mechanical Engineering, Purdue Un 
Sun, Dengfeng  Assistant Professor, Purdue Univ 
Keywords: Networked Control Systems
Abstract: Unknown Input Observers (UIO) use the known plant's inputs and outputs to generate state estimates for plants with unknown inputs. In many cases, the UIO's inputs are transmitted through a communication network, which is a key component in modern Networked Control Systems (NCS). Most of the developed UIOs in the literature are designed for nonnetworked systems. In this paper, the objective is to study the effect of unknown inputs and network perturbations on state observation and stability using UIOs. Given an UIO design for any nonnetworked system, we derive the dynamics of the UIObased NCS, also referred to as Networked Unknown Input Observer (NetUIO). The stability of the NetUIO is analyzed by deriving a stabilityguaranteeing bound on the networkedinduced perturbation. Numerical simulations are provided to highlight the applicability of the obtained bounds.


13:5014:10, Paper ThC3.2  
Dynamic Economic Dispatch among Strategic Generators with Storage Systems 
Tang, Wenyuan  Univ. of Southern California 
Jain, Rahul  Univ. of Southern California 
Keywords: Network Games and Algorithms, Networked Control Systems, Dynamic Games and Decision Theory
Abstract: We consider a dynamic economic dispatch problem in wholesale electricity markets. The key feature is that each generator has its own energy storage system, which makes the problem coupled across the time horizon. To implement the optimal dispatch among strategic generators, one major challenge is that the independent system operator is unaware of the operation of the storages. Nevertheless, we show that under certain conditions, the locational marginal pricing mechanism, defined on the static economic dispatch problem, can still induce an efficient Nash equilibrium in the dynamic setting. We also present an alternative pricing mechanism that can induce an efficient Nash equilibrium in a wider range of scenarios.


14:1014:30, Paper ThC3.3  
Strategic Resource Allocation for Competitive Influence in Social Networks 
Masucci, Antonia Maria  INRIA 
Silva, Alonso  Bell Labs, AlcatelLucent, France 
Keywords: Social Networks, Network Games and Algorithms, Optimization
Abstract: One of the main objectives of data mining is to help companies determine to which potential customers to market and how many resources to allocate to these potential customers. Most previous works on competitive influence in social networks focus on the first issue. In this work, our focus is on the second issue, i.e., we are interested on the competitive influence of marketing campaigns who need to simultaneously decide how many resources to allocate to their potential customers to advertise their products. Using results from game theory, we are able to completely characterize the optimal strategic resource allocation for the voter model of social networks and prove that the price of competition of this game is unbounded. This work is a step towards providing a solid foundation for marketing advertising in more general scenarios.


14:3014:50, Paper ThC3.4  
A Convex Approach to Consensus on SO(n) 
Matni, Nikolai  California Inst. of Tech 
Horowitz, Matanya  California Inst. of Tech 
Keywords: Distributed Computation on Networks, Optimization, Decentralized and Distributed Control
Abstract: This paper introduces several new algorithms for consensus over the special orthogonal group. By relying on a convex relaxation of the space of rotation matrices, consensus over rotation elements is reduced to solving a convex problem with a unique global solution. The consensus protocol is then implemented as a distributed optimization using (i) dual decomposition, and (ii) both semi and fully distributed variants of the alternating direction method of multipliers technique  all with strong convergence guarantees. The convex relaxation is shown to be exact at all iterations of the dual decomposition based method, and exact once consensus is reached in the case of the alternating direction method of multipliers. Further, analytic and/or efficient solutions are provided for each iteration of these distributed computation schemes, allowing consensus to be reached without any online optimization. Examples in satellite attitude alignment with up to 100 agents, an estimation problem from computer vision, and a rotation averaging problem on SO(6) validate the approach.


14:5015:10, Paper ThC3.5  
Optimizing the Service Policy of a Wireless Access Point on the Move with Renewable Energy 
Ceran, Elif Tugce  METU 
Erkilic, Tugce  ASELSAN 
UysalBiyikoglu, Elif  METU 
Girici, Tolga  Tobb Etu 
Leblebicioglu, Kemal  METU 
Keywords: Wireless Communication Systems, Stochastic Systems and Control, Optimization
Abstract: Inspired by recent industry efforts toward providing Internet access to the areas devoid of regular telecommunications infrastructure, an online resource allocation problem of a mobile access point (AP) is studied throughout this paper. While prudently managing its available energy, AP judiciously allocates its resources to maximize the total utility (reward) provided to the users demanding service. The problem is formulated as a 0/1 knapsack problem with growing dynamic capacity in a finite time horizon, solution of which is still quite open in the literature. Dynamic suboptimal policies are proposed considering the scenarios of both stochastic and deterministic behavior of environment and users. A threshold based policy using dynamic programming approach is shown to be optimal under some conditions. We also propose several online heuristics presenting an instantaneous threshold that can adapt to shorttimescale dynamics, including one which has an optimal competitive ratio under a certain condition, and study their performances and competitive ratios with respect to the optimal solution.


ThC4 
Pine 
Broadcast and Relay Channels 
Regular Session 
CoChair: Loyka, Sergey  Univ. of Ottawa 

13:3013:50, Paper ThC4.1  
TwoUser Degraded Broadcast Channel with Channel State Information at Transmitter and Message Side Information at Receivers 
Song, Lin  The Chinese Univ. of Hong Kong 
Xin, Haiyang  The Chinese Univ. of Hong Kong 
Yuan, Xiaojun  ShanghaiTech Univ 
Liu, Tie  Texas A&M Univ 
Keywords: Information Theory, Coding Theory, Wireless Communication Systems
Abstract: This paper investigates the twouser degraded broadcast channel with states where the channel state information is known at transmitter noncausally and the receivers know the message intended to the other as message side information. We characterize the capacity region by introducing two auxiliary random variables which can be viewed as an extension of Gel'fan and Pinsker coding. For the Gaussian case, we further show that within Gaussian input distributions the achievable rate region can be expressed using only one auxiliary random variable. We also provide the capacity region for twouser broadcast channel with noncausal state information at transmitter and message side information at weak receiver only.


13:5014:10, Paper ThC4.2  
Linear Relaying for Gaussian Diamond Networks 
Xu, Yi  Cornell Univ 
Kim, YoungHan  UCSD 
Keywords: Information Theory, Coding Theory
Abstract: Linear relaying for the Gaussian diamond network is studied as a natural extension of the amplify–forward relaying strategy by Schein and Gallager. A singleletter optimal rate is characterized, which is shown to be achieved by time sharing between four amplify–forward strategies at different power levels. This linear relaying capacity has a bounded gap from the cutset bound when the network is symmetric, but in general has an unbounded gap. The main idea of the proof is to transform a multiletter rate expression into an infinitedimensional optimization problem, the relaxation of which matches the performance of timeshared amplify–forward. A similar proof technique can be applied to other relay networks with layered structure such as the Nrelay Gaussian diamond network and the receiver frequencydivision Gaussian relay channel.


14:1014:30, Paper ThC4.3  
ColourAndForward: Relaying "what the Destination Needs" in the ZeroError Primitive Relay Channel 
Chen, Yanying  Univ. of Illinois at Chicago 
Shahi, Sara  Univ. of Illinois at Chicago 
Devroye, Natasha  Univ. of Illinois at Chicago 
Keywords: Information Theory, Coding Techniques and Applications, Information Theoretic Approaches in Wireless Communications
Abstract: Zeroerror communication over a primitive relay channel is for the first time proposed and studied. This model is used to highlight how one may exploit the channel structure to design a relaying strategy that explicitly provides "what destination needs". We propose the ColourandForward relaying scheme which constructs a graph G_R of relay outputs based on the joint conditional distribution of the relay and destination outputs given the channel input. The colours of this graph G_R are sent over the outofband link in the primitive relay channel and are shown to be information lossless in the zeroerror sense; they result in the same confusability graph as if the destination had the relay's received signal. This allows us to obtain an achievable zeroerror communication rate for the primitive relay channel, which may be shown to be capacity for a class of channels.


14:3014:50, Paper ThC4.4  
Dependence Balance Outer Bounds for the Discrete Memoryless TwoWay Multiple Access Broadcast Channel 
Hajizadeh, Saeed  Univ. of Illinois at Chicago 
Devroye, Natasha  Univ. of Illinois at Chicago 
Keywords: Information Theory
Abstract: We present an outer bound for the discrete memoryless twoway multiple access broadcast channel (TWMAC/BC) using the dependence balance idea. The cutset outer bound for multiuser channels allows arbitrarily correlated input distributions while the dependence balance idea limits the set of arbitrarily correlated input distributions to those satisfying a specific constraint known as dependence balance bound, which is particularly useful in channels with feedback or adaptation, as in twoway channels. We obtain a general dependencebalancebased outer bound for the discrete memoryless TWMAC/BC, and a parallel channel extension for the singleoutput channel. We then show that for the singleoutput binary additive noisy TWMAC/BC Y=X_1+X_2+X_3+Z (Z Bernoulli(0.5)), an outer bound to the symmetric sumrate of our outer bound is strictly smaller than that of the cutset outer bound. This is shown using the composite function technique introduced by Willems and used by Tandon and Ulukus in the context of multipleaccess channels with feedback.


14:5015:10, Paper ThC4.5  
The Compound Secrecy Capacity of a Class of NonDegraded MIMO Gaussian Channels 
Schaefer, Rafael F.  Princeton Univ 
Loyka, Sergey  Univ. of Ottawa 
Keywords: Information Theory, MIMO Systems
Abstract: Secrecy capacity of a class of nondegraded compound MIMO Gaussian channels is obtained. Earlier results established for isotropic uncertainty sets are extended to broader class of (nonisotropic) sets, which bound not only the gain but also the eigendirections of the eavesdropper channel. When a maximum element exists in the uncertainty set, a saddlepoint exists so that the compound and worstcase channel capacities coincide and signaling on the worstcase channel also works for the whole class of channels. The case of additive uncertainty in the legitimate channel, in addition to the unknown eavesdropper channel of a bounded spectral norm, is also studied. Its compound secrecy capacity and the optimal signaling are established in a closedform, revealing the saddlepoint property. The optimal signaling is Gaussian and on the eigenvectors of the legitimate channel and the worstcase eavesdropper is isotropic. The eigenmode power allocation somewhat resembles the standard waterfilling but is not identical to it.


ThC5 
Lower Level 
Control Applications and Nonlinear Control 
Regular Session 
CoChair: Sojoudi, Somayeh  NYU Langone Medical Center 

13:3013:50, Paper ThC5.1  
Social Game for Building Energy Efficiency: Incentive Design 
Ratliff, Lillian  Univ. of California, Berkeley 
Jin, Ming  Univ. of California, Berkeley 
Konstantakopoulos, Ioannis  Univ. of California, Berkeley 
Spanos, Costas  Univ. of California, Berkeley 
Sastry, Shankar  UC Berkeley 
Keywords: Control Applications, Dynamic Games and Decision Theory
Abstract: We present analysis and results of a social game encouraging energy efficient behavior in occupants by distributing points which determine the likelihood of winning in a lottery. We estimate occupants utilities and formulate the interaction between the building manager and the occupants as a reversed Stackelberg game in which there are multiple followers that play in a noncooperative game. The estimated utilities are used for determining the occupant behavior in the noncooperative game. Due to nonconvexities and complexity of the problem, in particular the size of the joint distribution across the states of the occupants, we solve the resulting the bi level optimization problem using a particle swarm optimization method. Drawing from the distribution across player states, we compute the Nash equilibrium of the game using the resulting leader choice. We show that the behavior of the agents under the leader choice results in greater utility for the leader.


13:5014:10, Paper ThC5.2  
Equivalence of Graphical Lasso and Thresholding for Sparse Graphs 
Sojoudi, Somayeh  NYU Langone Medical Center 
Keywords: Control Applications, Optimization, Sparse Data Analysis
Abstract: This paper is concerned with the problem of finding a sparse graph capturing the conditional dependence between the entries of a Gaussian random vector, where the only available information is a sample correlation matrix. A popular approach is to solve a graphical lasso problem with a sparsitypromoting regularization term. This paper derives a simple condition under which the computationallyexpensive graphical lasso behaves the same as the simple heuristic method of thresholding. This condition depends only on the solution of graphical lasso and makes no direct use of the sample correlation matrix or the regularization coefficient. It is also proved that this condition is always satisfied if the solution of graphical lasso is replaced by its firstorder Taylor approximation. The condition is tested on several random problems and it is shown that graphical lasso and the thresholding method (based on the correlation matrix) lead to a similar result (if not equivalent), provided the regularization term is high enough to seek a sparse graph.


14:1014:30, Paper ThC5.3  
Optimal Kinodynamic Motion Planning in Environments with Unexpected Obstacles 
Boardman, Beth  Univ. of California, San Diego 
Harden, Troy  Los Alamos National Lab 
Martinez, Sonia  Univ. of California, San Diego 
Keywords: Control Applications, Optimization
Abstract: This paper presents and analyzes a new algorithm, the Goal Tree (GT) algorithm, for motion planning in dynamic environments where new unexpected obstacles appear sporadically. The GT builds on the RRT* algorithm by employing an initial RRT* tree rooted at the goal. When finding new obstacle information, O, the GT quickly constructs a new tree rooted at the current location of the robot, xI , by sampling in a strict subset of the free space. The new tree then reuses branches from the original tree so that it can produce paths to the goal. Compared to running the RRT*, the GT reduces, on average, the time needed to produce a path of equal cost. We prove that, generically, there exists a region, which is a strict subset of the free space, which can be used with the GT algorithm to produce a asymptotically globally optimal path. This region is theoretically characterized for planning problems in d dimensional environments. An alternative region is provided for robot with Dubins’ vehicle dynamics and a vehicle with no dynamics both under a Euclidean distance cost function. Simulations for a Dubins’ vehicle robot verify our results.


14:3014:50, Paper ThC5.4  
Multivariable Algebraic Loops with Complementarity Constraints Enforcing Some KKT Conditions 
Adegbege, Ambrose Adebayo  The Coll. of New Jersey 
Heath, William Paul  The Univ. of Manchester 
Keywords: Nonlinear Control, Reliable and Robust Control, Optimization
Abstract: In this paper, we address the wellposedness and online resolution of algebraic loop arising from the feedback interconnection of a linear time invariant system having a feedthrough term and a static nonlinearity whose inputoutput characteristics enforce some KKT optimality conditions. We establish sufficient conditions for the wellposedness of such algebraic loops using the theory of linear complementarity problems. In particular, we show that wellposedness is equivalent to the existence and uniqueness of solution of a convex optimization problem for which efficient solution algorithms are well established. The application of the results to constrained control problem is illustrated using a multivariable antiwindup design.


14:5015:10, Paper ThC5.5  
NonHamiltonian Spectral Conditions for Strict Positive Realness of Descriptor Systems 
Bajcinca, Naim  TU Kaiserslautern 

ThD1 
Library 
Control and Optimization in Electrical Energy Systems: Smart Grid
Applications and Beyond II 
Invited Session 
Chair: DominguezGarcia, Alejandro  Univ. of Illinois at UrbanaChampaign 

15:3015:50, Paper ThD1.1  
Identification of Faults Using Sparse Optimization (I) 
Feng, Guangyu  NORTHEASTERN Univ 
Abur, Ali  NORTHEASTERN Univ 
Keywords: Optimization, Sparse Data Analysis, Detection and Estimation
Abstract: This paper describes a fault identification method based on the equivalence between the fault current drawn at an arbitrary point along a given line section and a pair of virtual superimposed current injections at the terminal nodes of the same line section. Therefore a fault can be located by estimating the pair of terminal current injections that would cause the recorded changes in bus voltages. One nice feature of this approach is that it is independent of fault type and fault resistance. Assuming the availability of an accurate threephase network model and a sufficient set of synchronized voltage sensors, the fault identification problem can be formulated as a sparse linear estimation problem with m equations representing the measured buses and n (n>m) unknowns representing the changes in current injections, which are all null except for the ones corresponding to the terminal nodes of the faulted line section. The practical implementation of this approach relies on the efficient solution of an L1 regularization problem and the proper placement of a sufficient number of measurements satisfying the conditions for a unique solution.


15:5016:10, Paper ThD1.2  
Decentralized Control of DCSegmented Power Systems (I) 
Taylor, Joshua  Univ. of Toronto 
Scardovi, Luca  Univ. of Toronto 
Keywords: Control Applications, Decentralized and Distributed Control
Abstract: Direct current (DC) transmission is highly regarded for its ability to dynamically decouple AC power systems by segmenting them into disjoint networks. Such configurations lead to more efficient power transfers and better oscillation damping, but necessitate controllers with seemingly heavy communication requirements that rely on widearea measurement systems. This paper shows that DCsegmented power systems are posetcausal, making them amenable to powerful decentralized control techniques that can substantially reduce their communication needs. Specifically, optimal decentralized control is attainable with communication only between AC subsystems that are directly connected by a DC line. The approach explicitly leverages the implied graph structure of power systems with AC and DC lines. Numerical results demonstrate that the decentralized controller achieves nearly the same performance as the optimal centralized controller.


16:1016:30, Paper ThD1.3  
On Market Dynamics of Electric Vehicle Diffusion (I) 
Yu, Zhe  Cornell Univ 
Li, Shanjun  Cornell Univ 
Tong, Lang  Cornell Univ 
Keywords: Dynamic Games and Decision Theory, Machine Learning and Approximate Dynamic Programming, Stochastic Systems and Control
Abstract: A sequential game model is proposed to analyze a twosided market and indirect network effects involving electrical vehicles (EV) and electric vehicle charging stations (EVCS). The investor maximizes his profit by choosing a set of locations to build charging stations or deferring his investment and earning interest at a fixed rate. The investor also decides the optimal pricing of charging. The consumer, on the other hand, decides whether to purchase an EV or a gasoline vehicle (GV) based on the price of EV, the cost of charging, and the availability of charging stations. The solution of the game provides a closedform expression of the EV market share as a function of EV price, the price of charging, and the density of charging stations. An asymptotically optimal algorithm is proposed for solving the optimization of the investor's decision.


16:3016:50, Paper ThD1.4  
Synchronization of a Class of Nonlinear Circuits in Connected Electrical Networks (I) 
Dhople, Sairaj  Univ. of Minnesota 
Dorfler, Florian  ETH Zurich 
Johnson, Brian B.  National Renewable Energy Lab. 
Hamadeh, Abdullah O.  Rutgers Univ. 

16:5017:10, Paper ThD1.5  
Direct Load Control for Financial Risk Management in Electricity Markets Via RiskLimiting Dynamic Contracts (I) 
Yang, Insoon  Univ. of California, Berkeley 
Callaway, Duncan  Univ. of California, Berkeley 
Tomlin, Claire  Univ. of California, Berkeley 
Keywords: Stochastic Systems and Control, CyberPhysical Systems, Control Applications
Abstract: This paper proposes a new direct load control framework that provides financial risk management solutions for realtime electricity markets. In this program, a loadserving entity makes risklimiting dynamic contracts with its customers to optimally manage its revenue and risk. This risk is generated by both price volatility and demand uncertainty regarding distributed renewable generation as negative load. The key feature of our contract method is its risklimiting capability: the amount of risk transferred to each customer is less than or equal to a prespecified threshold. This is achieved by formulating the contract design problem as meanvariance constrained risksensitive control. We develop a dynamic programmingbased solution approach. We demonstrate the performance of the proposed contracts by using locational marginal price (LMP) data from the Electricity Reliability Council of Texas and data on the electric energy consumption of customers in Austin, Texas. The numerical experiments suggest that the proposed direct load control program efficiently manages the loadserving entity's and its customers' risks even when the loadserving entity passes the wholesale electricity price to the customers.


17:1017:30, Paper ThD1.6  
Promises of Conic Relaxation for ContingencyConstrained Optimal Power Flow Problem (I) 
Madani, Ramtin  Columbia Univ 
Ashraphijuo, Morteza  Sharif Univ. of Tech 
Lavaei, Javad  Columbia Univ 
Keywords: Control Applications, Optimization, CyberPhysical Systems
Abstract: This paper is concerned with the securityconstrained optimal power flow (SCOPF) problem, where each contingency corresponds to the outage of an arbitrary number of lines and generators. The problem is studied by means of a convex relaxation, named semidefinite program (SDP). The existence of a rank1 SDP solution guarantees the recovery of a global solution of SCOPF. We prove that the rank of the SDP solution is upper bounded by the treewidth of the power network, which is perceived to be small in practice. We then propose a decomposition method to reduce the computational complexity of the relaxation. In the case where the relaxation is not exact, we develop a graphtheoretic convex program to identify the problematic lines of the network and penalize their loss in the SDP problem, leading to a penalized SDP problem. We perform several simulations on largescale benchmark systems and verify that the penalized relaxation is able to find feasible solutions that are at most 1% away from the unknown global minima.


ThD3 
Butternut 
Security, Secrecy and Trust 
Regular Session 
Chair: Atia, George  Univ. of Central Florida 
CoChair: Liu, Mingyan  Univ. of Michigan 

15:3015:50, Paper ThD3.1  
On the Secrecy Capacity Region of a Class of Parallel Wiretap Broadcast Channel 
Benammar, Meryem  Supelec 
Piantanida, Pablo  SUPELEC 
Keywords: Network Coding in Communication, Information Theoretic Approaches in Wireless Communications, Information Theory
Abstract: This work investigates the secrecy capacity region of a class of Wiretap Broadcast Channel (WBC) where a source wishes to send two independent messages to two receivers in the presence of an external eavesdropper. We focus on the class of parallel WBC and more precisely on the product of two reversely lessnoisy BC with a more noisy eavesdropper. We fully characterize the capacity region of such a setting through a novel powerful outer bound that relies on a careful single letter expression, followed by a nontrivial equivalent formulation of the resulting rate region. This outer bound turns out to be tight with the inner bound we derive for the setting under study.


15:5016:10, Paper ThD3.2  
Covert SingleHop Communication in a Wireless Network with Distributed Artificial Noise Generation 
Soltani, Ramin  Univ. of Massachusetts Amherst 
Bash, Boulat  Univ. of Massachusetts, Amherst 
Goeckel, Dennis  Univ. of Massachusetts Amherst 
Guha, Saikat  BBN 
Towsley, Don  Univ. of Massachusetts 
Keywords: Security and Trust, Information Theoretic Approaches in Wireless Communications, Sensor Networks in Communications
Abstract: Covert communication, also known as low probability of detection (LPD) communication, prevents the adversary from knowing that a communication is taking place. Recent work has demonstrated that, in a threeparty scenario with a transmitter (Alice), intended recipient (Bob), and adversary (Warden Willie), the maximum number of bits that can be transmitted reliably from Alice to Bob without detection by Willie, when additive white Gaussian noise (AWGN) channels exist between all parties, is on the order of the square root of the number of channel uses. In this paper, we begin consideration of network scenarios by studying the case where there are additional “friendly” nodes present in the environment that can produce artificial noise to aid in hiding the communication. We establish achievability results by considering constructions where the system node closest to the warden produces artificial noise and demonstrate a significant improvement in the throughput achieved covertly, without requiring close coordination between Alice and the noisegenerating node. Conversely, under mild restrictions on the communication strategy, we demonstrate no higher covert throughput is possible. Extensions to the consideration of the achievable covert throughput when multiple wardens randomly located in the environment collaborate to attempt detection of the transmitter are also considered.


16:1016:30, Paper ThD3.3  
On the Relation between Identifiability, Differential Privacy and MutualInformation Privacy 
Wang, Weina  Arizona State Univ 
Ying, Lei  Arizona State Univ 
Zhang, Junshan  Arizona State Univ 
Keywords: Security and Trust, Information Theory
Abstract: This paper investigates the relation between three different notions of privacy: identifiability, differential privacy and mutualinformation privacy. Under a privacydistortion framework, where the distortion is defined to be the expected Hamming distance between the input and output databases, we establish some fundamental connections between these three privacy notions. Given a maximum distortion D, let 𝜖 _{i}*( D) denote the smallest (best) identifiability level, and 𝜖 _{d}*( D) the smallest differential privacy level. Then we characterize 𝜖 _{i}*( D) and 𝜖 _{d}*( D), and prove that 𝜖 _{i}*( D) − 𝜖 _{X} ≤ 𝜖 _{d}*( D) ≤ 𝜖 _{i}*( D) for D in some range, where 𝜖 _{X} is a constant depending on the distribution of the original database X, and diminishes to zero when the distribution of X is uniform. Furthermore, we show that identifiability and mutualinformation privacy are consistent in the sense that given a maximum distortion D in some range, there is a mechanism that optimizes the identifiability level and also achieves the best mutualinformation privacy.


16:3016:50, Paper ThD3.4  
A Unifying Approach for the Identification of ApplicationDriven Stealthy Attacks on Mobile CPS 
Nguyen, Vu  Texas State Univ 
Guirguis, Mina  Texas State Univ 
Atia, George  Univ. of Central Florida 
Keywords: Security and Trust, CyberPhysical Systems, Machine Learning and Approximate Dynamic Programming
Abstract: CyberPhysical Systems (CPS) employing mobile nodes rely on wireless communication in many critical applications. Due to interference and intentional jamming by adversaries, mobile nodes may fail to communicate with each other causing severe performance consequences. In this paper, we present a unifying approach for identifying attacks that target Mobile CPS applications. The attack policies are obtained as solutions to Markov Decision Process (MDP) problems, in which a decision to interfere with a signal on a given link is based on the current state of the system. Through applying approximate policy iteration methods, efficient attack policies that only interfere with a selective set of signals between the mobile nodes are derived to maximize damage while minimizing exposure and detection. The proposed approach is instantiated on pheromonebased coordination methods that are used in reconnaissance, surveillance, and search missions in military operations. The identified attack policies are shown to be more potent than other attack policies, including myopic, heuristic, and Denial of Service (DoS) policies.


16:5017:10, Paper ThD3.5  
Budget Balance or Voluntary Participation? Incentivizing Investments in Interdependent Security Games 
Naghizadeh Ardabili, Parinaz  Univ. of Michigan 
Liu, Mingyan  Univ. of Michigan 
Keywords: Network Games and Algorithms, Security and Trust
Abstract: In a system of interdependent users, all entities are affected by the security decisions of one another. These users benefit from the improved health of the system when their neighbors invest in security measures; an effect known as positive externality. The externality of these decisions make security a public good, the optimal provision of which in a system of selfinterested users requires regulation/incentives through an external mechanism. In this paper we first show that due to the nonexcludable nature of security, no mechanism can achieve social optimality and ensure voluntary participation, while maintaining a balanced budget, for all instances of a security game. We then compare two incentive mechanisms in this context for improving security investment among users, namely the Pivotal mechanism and the Externality mechanism. We show that even though both mechanisms incentivize socially optimal investments, they differ in terms of budget require ments and participation. The Pivotal mechanism guarantees users’ participation; however, although (weakly) budget bal anced in many game environments, it runs a budget deficit in security games. The Externality mechanism on the other hand is a budget balanced mechanism, but fails to incentivize voluntary participation. We further study the effects of the information available to the mechanism designer on the budget deficit of the Pivotal mechanism.


ThD4 
Pine 
Performance Analysis 
Regular Session 
Chair: Beirami, Ahmad  Duke Univ 
CoChair: Sun, Jun  MIT Lincoln Lab 

15:3015:50, Paper ThD4.1  
Data Locality in MapReduce: A Network Perspective 
Wang, Weina  Arizona State Univ 
Ying, Lei  Arizona State Univ 
Keywords: Performance Analysis, Queuing Theory and Analysis
Abstract: The data locality problem is crucial to the performance of MapReduce systems and has been studied in the literature. In this paper, we view the data locality problem from a network perspective. The key observation is that if we make appropriate use of the network to route the data chunk to the machine where it will be processed in advance, then processing a remote task is the same as processing a local task. However, to benefit from such a strategy, we must (i) balance the tasks assigned to local machines and those assigned to remote machines, and (ii) design the routing algorithm to avoid network congestion. Taking these challenges into consideration, we propose a scheduling/routing algorithm, named the Joint Scheduler, which utilizes both the computing resources and the communication network efficiently. To show that the Joint Scheduler has superior performance, we first prove that the Join Scheduler can support any load that can be supported by some other algorithm, i.e., achieve the maximum capacity region. Simulation results demonstrate that with popularity skew, the Joint Scheduler improves the throughput significantly (more than 30% in our simulations) compared to the Hadoop Fair Scheduler with delay scheduling, which is the de facto industry standard. The delay performance is also evaluated through simulations, where we can see a significant delay reduce under the Joint Scheduler with moderate to heavy load.


15:5016:10, Paper ThD4.2  
An Analytical Approach to Study Cascading Failures in FiniteSize Random Geometric Networks 
Eslami, Ali  Texas A&M Univ 
Huang, Chuan  Texas A&M Univ 
Zhang, Junshan  Arizona State Univ 
Cui, Shuguang  Texas A&M Univ 
Keywords: CyberPhysical Systems, Resilient Systems, Social Networks
Abstract: The problem of cascading failures in cyberphysical networks is garnering much attention for different network models underlining various applications. While a variety of analytic results has been reported for the case of large networks, very few of them are readily applicable to finitesize networks. This paper studies cascading failures in finitesize geometric networks where the number of nodes is on the order of tens or hundreds as in many reallife networks. First, the impact of the tolerance parameter on network resiliency is investigated. We quantify the network reaction to initial disturbances of different sizes by measuring the damage imposed on the network. Lower and upper bounds on the number of failures are derived to characterize such damages. In addition to the finite analysis, an asymptotic analysis of both bounds is carried out, discovering a threshold behavior of the network as the tolerance parameter changes. The critical value of the tolerance parameter in the asymptotic regime is further derived. Findings of this paper, in particular, shed light on how to choose the tolerance parameter appropriately such that a cascade of failures could be avoided.


16:1016:30, Paper ThD4.3  
Fundamental Performance Limits of ChaoticMap Random Number Generators 
Beirami, Ahmad  Duke Univ 
Nejati, Hamid  Univ. of Michigan 
Callegari, Sergio  Univ. of Bologna 
Keywords: Stochastic Systems and Control, Security and Trust, Statistical Signal Processing
Abstract: A chaoticmap random number generator (RNG) is defined using a chaotic map and a bitgeneration function. When the map function is exactly known, for a given bitgeneration function, the entropyrate of the generated output bit sequence is asymptotically the highest rate at which truly random bits can be generated from the map. The supremum of the entropyrate amongst all bitgeneration functions is called the binary metric entropy, which is the highest rate at which information can be extracted from any given map using the optimal bitgeneration function. In this paper, we provide converse and achievable bounds on the binary metric entropy. The achievability is based on a sequence of *universal* bitgeneration functions in the sense that the bitgeneration function is not dependent on the specific map. The proposed sequence of bitgeneration functions offers a fairly simple implementation which can easily be realized on hardware for practical purposes.


16:3016:50, Paper ThD4.4  
Right Buffer Sizing Matters: Stability, Queuing Delay and Traffic Burstiness in Compound TCP 
Ghosh, Debayani  Indian Inst. of Tech. Madras 
Jagannathan, Krishna  IIT Madras 
Raina, Gaurav  Indian Inst. of Tech. Madras 
Keywords: Performance Analysis, Control Applications, Pricing and Congestion Control
Abstract: Motivated by recent concerns that queuing delays in the Internet are on the rise, we conduct a performance evaluation of Compound TCP in two topologies. The first topology consists of a single bottleneck, and the second consists of two distinct sets of flows, regulated by two edge routers, feeding into a core router. We consider longlived flows, and a combination of long and short flows. For these models, we derive necessary and sufficient conditions for stability and prove that the dynamical system undergoes a Hopf bifurcation as the stability condition gets violated. Using a combination of analysis and packetlevel simulations, we emphasise that larger buffers, in addition to increasing delay, are prone to inducing limit cycles. These limit cycles in turn induce synchronisation among TCP flows and tend to make the downstream traffic bursty.


16:5017:10, Paper ThD4.5  
Bounds on Wireless Network Capacity through SparsestCut 
Sun, Jun  MIT Lincoln Lab. 
NarulaTam, Aradhana  MIT Lincoln Lab. 
Kuperman, Greg  MIT Lincoln Lab. 
Gremban, Keith  Shavano Systems, LLC 

ThD5 
Lower Level 
Allerton Class 2014 
Invited Session 
Chair: Nedich, Angelia  Univ. of Illinois 

15:3015:50, Paper ThD5.1  
Estimating R'enyi Entropy of Discrete Distributions (I) 
Acharya, Jayadev  Cornell Univ. 
Orlitsky, Alon  UCSD 
Suresh, Ananda Theertha  Univ. of CaliforniaSan Diego 
Tyagi, Himanshu  UC San Diego 

15:5016:10, Paper ThD5.2  
On SourceChannel Coding Over Gaussian Sensor Networks for Path Planning (I) 
Akyol, Emrah  USC 
Mitra, Urbashi  Univ. of Southern California 
Keywords: Information Theory, Sensor Networks in Communications, Detection and Estimation
Abstract: Path planning is an important component of mobile sensor and autonomous mobile systems. This paper studies inner and outer bounds for joint sourcechannel coding over Gaussian sensor networks, to drive powerdistortion metrics for path planning problems for sensor data gathering. The Gaussian multiple access channel is considered for two source models. In the first setting, the underlying source is estimated with minimum mean squared error (MSE), while in the second, reconstruction of a random field is considered. The second problem simplifies to weighted MSE minimization over the sensor measurements. For both cases, we identify conditions for optimality of uncoded communication, beyond the known optimality results. For both problem settings, we derive inner and outer bounds of sensor powerdistortion curve. Next, we consider optimal power allocation among sensors under a total weighted sum power constraint and obtain closed form characterizations of optimal total power versus distortion tradeoff. We numerically analyze the gap between outer and inner bounds for both total power and individual power constrained settings.


16:1016:30, Paper ThD5.3  
Learning Graphical Models from the Glauber Dynamics (I) 
Bresler, Guy  MIT 
Gamarnik, David  MIT 
Shah, Devavrat  MIT 
Keywords: Universal Algorithms and Machine Learning, Information Theory, Sparse Data Analysis
Abstract: In this paper we consider the problem of learning undirected graphical models from data generated according to the Glauber dynamics. The Glauber dynamics is a Markov chain that sequentially updates individual nodes (variables) in a graphical model and it is frequently used to sample from the stationary distribution (to which it converges given sufficient time). Additionally, the Glauber dynamics is a natural dynamical model in a variety of settings. This work deviates from the standard formulation of graphical model learning in the literature, where one assumes access to i.i.d. samples from the distribution. Much of the research on graphical model learning has been directed towards finding algorithms with low computational cost. As the main result of this work, we establish that the problem of reconstructing binary pairwise graphical models is computationally tractable when we observe the Glauber dynamics. Specifically, we show that a binary pairwise graphical model on p nodes with maximum degree d can be learned in time f(d)p^{3} log p, for a function f(d), using nearly the informationtheoretic minimum possible number of samples. There is no known algorithm of comparable efficiency for learning arbitrary binary pairwise models from i.i.d. samples.


16:3016:50, Paper ThD5.4  
Controlling Epidemics on Networks (I) 
Drakopoulos, Kimon  MIT 
Ozdaglar, Asu  MIT 
Tsitsiklis, John  Massachusetts Inst. of Tech. 

16:5017:10, Paper ThD5.5  
Joint Control and Compressed Sensing for Dynamic Spectrum Access in Agile Wireless Networks (I) 
Michelusi, Nicolo  Univ. of Southern California 
Mitra, Urbashi  Univ. of Southern California 
Keywords: Decentralized and Distributed Control, Stochastic Systems and Control, Detection and Estimation
Abstract: In this paper, a crosslayer framework for joint distributed sensing, estimation and control in agile wireless networks is presented. A network of secondary users (SUs) opportunistically accesses portions of the spectrum left unused by a licensed network of primary users (PUs). A central controller (CC) schedules the spectrum bands detected as idle for access by the SUs, based on compressed measurements acquired by the SUs. The sparsity in the spectrum occupancy dynamics is exploited: leveraging the spectrum occupancy estimate in the previous slot, the CC needs to estimate only a sparse residual uncertainty vector via sparse recovery techniques, so that only few measurements suffice. The sensing probability of the SUs and the spectrum scheduling are adapted over time by the CC, based on the current spectrum occupancy estimate, and jointly optimized so as to maximize the SU throughput, under constraints on the PU throughput degradation and the sensing cost incurred by the SUs. A compact state space representation and decoupling of the state estimator from the CC are proposed: the estimator provides a maximumaposteriori spectrum estimate, as well as falsealarm and misdetection error probabilities for the bins detected as busy and idle, respectively, based on which the CC performs scheduling and sensing decisions. Simulation results demonstrate improvements up to 11% in the SU throughput over a static sensing scheme.


17:1017:30, Paper ThD5.6  
Learning to Optimize Via InformationDirected Sampling (I) 
Russo, Daniel  Stanford Univ. 
Van Roy, Benjamin  Stanford Univ. 

17:3017:50, Paper ThD5.7  
Network Evolution with Incomplete Information and Learning (I) 
Xu, Jie  Univ. of California, Los Angeles 
Zhang, Simpson  Univ. of California, Los Angeles 
van der Schaar, Mihaela  Univ. of California Los Angeles 
Keywords: Dynamic Games and Decision Theory, Social Networks, Network Games and Algorithms
Abstract: We analyze networks that feature reputational learning: how links are initially formed by agents under incomplete information, how agents learn about their neighbors through these links, and how links may ultimately become broken. We show that the type of information agents have access to, and the speed at which agents learn about each other, can have tremendous repercussions for the network evolution and the overall network social welfare. Specifically, faster learning can often be harmful for networks as a whole if agents are myopic, because agents fail to fully internalize the benefits of experimentation and break off links too quickly. As a result, preventing two agents from linking with each other can be socially beneficial, even if the two agents are initially believed to be of high quality. This is due to the fact that having fewer connections slows the rate of learning about these agents, which can be socially beneficial. Another method of solving the informational problem is to impose costs for breaking links, in order to incentivize agents to experiment more carefully.

 