Murat Arcak, UC Berkeley, Pattern Formation by Lateral Inhibition: A Case Study in Networked Dynamical Systems
A common pattern formation mechanism in multi-cellular organisms is lateral inhibition where the cells inhibit their immediate neighbors through a contact signaling mechanism. We will present a broad dynamical model to represent this mechanism and reveal the key properties of the model that are necessary for patterning. The model consists of subsystems representing the biochemical reactions in individual cells, interconnected according to an undirected graph describing which cells are in contact. By making use of input-output properties of the subsystems and the spectral properties of the adjacency matrix for the contact graph, we will present verifiable conditions that determine when the spatially homogeneous steady-state loses its stability and what types of patterns emerge. In particular, we will classify types of graphs using special symmetries and exhibit the associated patterns. Above all, this talk will showcase the merger of a control-theoretic input-output approach with graph-theoretic concepts to infer global behavior of a large-scale and nonlinear networked system.
Murat Arcak is an associate professor of Electrical Engineering and Computer Sciences at the University of California, Berkeley. He received his Ph.D. from the University of California, Santa Barbara, in 2000 and was a faculty member at the Rensselaer Polytechnic Institute prior to joining Berkeley. He received a CAREER Award from the National Science Foundation in 2003, the Donald P. Eckman Award from the American Automatic Control Council in 2006, and the SIAG CST Prize from the Society for Industrial and Applied Mathematics in 2007. He is a member of SIAM and a fellow of IEEE.
Bassam Bamieh, UC Santa Barbara, Coherence and Disorder in Large Dynamical Networks: Role of Network Connectivity versus Node Complexity
Networks of interconnected dynamical systems subject to stochastic disturbances exhibit scaling phenomena that are not present in deterministic networks. We argue that standard notions of stability as a binary property (i.e. a system is either stable or not) may fail to predict the behavior of large networks. This motivates the study of such networks using system norms as performance measures. This talk will specifically address the notion of network coherence under stochastic disturbances, and its dependence on network topology and various notions of network dimension. Regular lattices and fractal networks provide case studies with both integer and fractional dimension. We give asymptotic lower bounds on network disorder and show its dependence on both the complexity of individual node dynamics, as well as network dimension. It turns out that higher connectivity (network dimension) improves coherence, while more complex node dynamics can hinder it. However, in all cases there is a critical network dimension above which purely local interactions can lead to the emergence of global order. We outline the connections between these results and those on the statistical mechanics of harmonic solids. We also present some implications to the distributed control of vehicular formations and platoons, as well as phase synchronization in power networks with highly-distributed generation.
Bassam Bamieh is Professor of Mechanical Engineering at the University of California at Santa Barbara. He received his PhD degree in Electrical and Computer Engineering from Rice University in 1992. Prior to joining UCSB in 1998, he was an Assistant Professor in the Department of Electrical and Computer Engineering and the Coordinated Science Laboratory at the University of Illinois at Urbana-Champaign. His research interests are in the fundamentals of Control and Dynamical Systems, as well as the applications of systems and feedback techniques in physical and engineering systems such as shear flow transition and turbulence, and the use of feedback in thermoacoustic energy conversion devices. He has co-authored over 100 refereed publications in Systems and Controls and allied fields, and received several awards and honors for his research, including an IEEE Control Systems Society G. S. Axelby Outstanding Paper Award, an AACC Hugo Schuck Best Paper Award, and a National Science Foundation CAREER award. He is a Distinguished Lecturer of the IEEE Control Systems Society, a Fellow of the International Federation of Automatic Control (IFAC) , and a Fellow of the IEEE.
Christina Fragouli, École Polytechnique Fédérale de Lausanne, Bringing Network Coding Closer to Practice
The paradigm of network coding allows intermediate nodes in a network to not only forward but also combine their incoming information flows. This modern application of coding to the theory and practice of communication networks raises novel and exciting research problems, and is promising to have an impact in diverse areas of network communications that include multicasting, network monitoring, resource sharing, network security, among other areas.
However, one of the main challenges is to realize the benefits of network coding functionalities with implementable computational complexity. We illustrate through two examples how algorithmic and combinatorial tools can be applied to make progress on this challenging question.
One of the challenges in the deployment of network coding is the fact that network nodes may need to perform operations over relatively large finite fields. We propose instead to use vector network coding, where nodes process and combine binary packets by multiplying them with binary coding matrices, as opposed to scalar coefficients over a field. We introduce an algebraic framework for vector network coding, and provide a polynomial time algorithm for the design of coding matrices, that aims to minimize the size of the employed matrices, and thus reduce the encoding complexity. Our algorithm reduces the problem of finding small size matrices to the problem of finding a small degree coprime factor of an algebraic polynomial, and leads to solutions not possible with using scalar network coding.
We then consider a specific application. Our scenario is that a group of wireless nodes want to exchange a secret key, such that no eavesdropper can guess the key. Using network coding techniques, we develop a protocol that enables the group of nodes to agree on secret bits at a rate depending on the properties of the wireless network that interconnects them. Our protocol uses simple, polynomial-time operations and does not require any changes to the physical or MAC-layer of network devices. We formally prove and experimentally demonstrate that our protocol can generate information-theoretically secret keys in a realistic setting.
Christina Fragouli is a tenure track Professor in the School of Computer and Communication Sciences, EPFL, Switzerland. She received the B.S. degree in Electrical Engineering from the National Technical University of Athens, Athens, Greece, and the M.Sc. and Ph.D. degrees in electrical engineering from the University of California, Los Angeles. She has worked at the Information Sciences Center, AT&T Labs, Florham Park New Jersey, and the National University of Athens. She also visited Bell Laboratories, Murray Hill, NJ, and DIMACS, Rutgers University. From 2006 to 2007, she was an FNS Professor in the School of Computer and Communication Sciences, EPFL, Switzerland. Her research interests are in network information flow theory and algorithms, network coding, wireless networks, and connections between communications, networking and computer science. She received the Fulbright Fellowship for her graduate studies, the Outstanding Ph.D. Student Award 2000-2001, UCLA, Electrical Engineering Department, the Zonta award 2008 in Switzerland, and the Young Investigator ERC grant award in 2009. She served as an editor for IEEE Communications Letters, IEEE Transactions on Communications and Elsevier Computer Communications, and is currently serving as an editor for IEEE Transactions on Information Theory and IEEE Transactions on Mobile Computing. She is also serving as a Distinguished Lecturer for the IEEE Information Theory Society.
Massimo Franceschetti, UC San Diego,
A Journey Through Data-Rate Theorems for Communication and Control
In this talk, we address the problem of mean-square stabilization of a discrete-time linear dynamical system where the estimated state is transmitted for control over a digital communication channel. This arises in several emerging applications including remote robot control, automated highway navigation using wireless sensor systems, and automatic control for pursuit evasion games. In this context, a data-rate theorem refers to the minimum information rate required to guarantee the stability of the system over a given communication channel. Loosely speaking, it states that the information rate to be supported by the channel must be large enough compared to the unstable modes of the system, so that it can compensate for the expansion of the state during the communication process. Since its first rigorous formulation about a decade ago, and driven by technological advancements of embedded systems for control, there has been a growing interest in stating data rate theorems for the most general communication models. We will review a series of contributions by different groups (including ours), sketching mathematical arguments based on a blend of information-theoretic and control-theoretic tools. We will also try to draw a connection between results in control and some recent advancements in communications with feedback and will conclude mentioning some open problems in the field.
Massimo Franceschetti is associate professor in the Department of Electrical and Computer Engineering of University of California at San Diego. He received the Laurea degree, magna cum laude, in Computer Engineering from the University of Naples in 1997, and the M.S. and Ph.D. degrees in Electrical Engineering from the California Institute of Technology in 1999, and 2003. Before joining UCSD, he was a post-doctoral scholar at University of California at Berkeley for two years. Prof. Franceschetti was awarded the C. H. Wilts Prize in 2003 for best doctoral thesis in Electrical Engineering at Caltech; the S. A. Schelkunoff award in 2005 for best paper in the IEEE Transactions on Antennas and Propagation; an NSF CAREER award in 2006, an ONR Young Investigator award in 2007; and the IEEE Communications society best tutorial paper award in 2010. He has held visiting positions at at the Vrije Universiteit Amsterdam in the Netherlands, the Ecole Polytechnique Federale de Lausanne in Switzerland, and the University of Trento in Italy. He is associate editor for communication networks of the IEEE Transactions on Information Theory and has served as guest editor for two issues of the IEEE Journal on Selected Areas in Communication. His research interests are in communication systems theory and include random networks, wave propagation in random media, wireless communication, and control over networks.
Georgios B. Giannakis, University of Minnesota, In-network Rank Minimization and Sparsity Regularization: Algorithms and Application to Unveiling Traffic Anomalies
Given a limited number of entries from the superposition of a low-rank matrix plus the product of a known fat compression matrix times a sparse matrix, recovery of the low-rank and sparse components is a fundamental task subsuming compressed sensing, matrix completion, and principal components pursuit. This talk presents algorithms for distributed sparsity-regularized rank minimization over networks, when the nuclear- and l1-norms are used as surrogates to the rank and nonzero entry counts of the sought matrices, respectively. While nuclear-norm minimization has well-documented merits when centralized processing is viable, non-separability of the singular-value sum challenges its distributed minimization. To overcome this limitation, an alternative characterization of the nuclear norm is advocated which leads to a separable, yet non-convex cost minimized via the alternating-direction method of multipliers. The resultant per-node iterations incur affordable complexity and message passing among single-hop neighbors to approach the (centrally attainable) global optimum regardless of initialization. Possible applications presented will include unveiling traffic anomalies in backbone networks, predicting network-wide path latencies, and mapping the RF ambiance using wireless cognitive radios.
G. B. Giannakis (IEEE Fellow’97) received his Diploma in Electrical Engr. from the Ntl. Tech. Univ. of Athens, Greece, 1981. From 1982 to 1986 he was with the Univ. of Southern California (USC), where he received his MSc. in Electrical Engineering, 1983, MSc. in Mathematics, 1986, and Ph.D. in Electrical Engr., 1986. Since 1999 he has been a professor with the Univ. of Minnesota, where he now holds an ADC Chair in Wireless Telecommunications in the ECE Department, and serves as director of the Digital Technology Center. His general interests span the areas of communications, networking and statistical signal processing - subjects on which he has published more than 300 journal papers, 500 conference papers, 20 book chapters, two edited books and two research monographs. Current research focuses on compressive sensing, cognitive radios, cross-layer designs, wireless sensors, social and power grid networks. He is the (co-) inventor of 21 patents issued, and the (co-) recipient of 8 best paper awards from the IEEE Signal Processing (SP) and Communications Societies, including the G. Marconi Prize Paper Award in Wireless Communications. He also received Technical Achievement Awards from the SP Society (2000), from EURASIP (2005), a Young Faculty Teaching Award, and the G. W. Taylor Award for Distinguished Research from the University of Minnesota. He is a Fellow of EURASIP, and has served the IEEE in a number of posts, including that of a Distinguished Lecturer for the IEEE-SP Society.
Ian A. Hiskens, University of Michigan, Enhanced Power System Responsiveness Through Distributed
Control of Loads
Responsive load control offers a particularly effective approach to compensating for the variability inherent in large-scale renewable generation. Furthermore, as plug-in electric vehicles grow in popularity, scheduling their charging load will become vitally important to prevent local overloads, and to ensure optimal use of generation resources. Fortunately expansive communications networks and advances in distributed control algorithms facilitate precise, non-disruptive forms of load control. The presentation will discuss various approaches to coordinated control of large numbers of highly distributed and diverse loads. At the local distribution level, we will consider distributed model predictive control (MPC) and consensus algorithms. We will show that game-based strategies provide an effective mechanism for optimally scheduling electric vehicle charging, and that hysteretic controls enable precise tracking of variations in renewable energy production. The technology underpinning ubiquitous load control will be examined, and technical challenges will be considered. A range of applications will be presented.
Ian A. Hiskens is the Vennema Professor of Engineering in the Department of Electrical Engineering and Computer Science at the University of Michigan in Ann Arbor. He has held prior appointments in the electricity supply industry (for ten years), and various universities in Australia and the United States. Dr Hiskens’ research focuses on power system analysis, in particular the modelling, dynamics and control of large-scale, networked, nonlinear systems. His recent activities include integration of renewable generation and new forms of load. He is actively involved in various IEEE societies, and is the VP for Finance of the IEEE Systems Council. He is a Fellow of the IEEE, a Fellow of Engineers Australia, and a Chartered Professional Engineer in Australia.
Sonia Martínez, UC San Diego, Attack-Resilient Control Algorithms for Remotely-Operated Vehicles
Recent advances in communications, sensing and computation have made possible the development of highly sophisticated unmanned vehicles in a wide range of scenarios. More recently, the use of unmanned vehicles remotely controlled by human operators has been proposed to enhance information sharing and maintain situational awareness among the group. However this capability comes at the price of an increased vulnerability to the cyber and communication systems needed to deploy them. In this talk, we discuss our recent progress in the analysis and design of resilient control policies for vehicle-operator groups. We consider a class of adversaries who can corrupt the control commands sent from operators to vehicles. We then present conditions under which system stabilization is possible by means of backup commands and/or learning mechanisms in operators and adversaries.
Sonia Martínez received her Ph.D. degree in Engineering Mathematics from the Universidad Carlos III de Madrid, Spain, in May 2002. Following a year as a Visiting Assistant Professor of Applied Mathematics at the Technical University of Catalonia, Spain, she obtained a Postdoctoral Fulbright Fellowship and held appointments at the Coordinated Science Laboratory of the University of Illinois, Urbana-Champaign during 2004, and at the Center for Control, Dynamical systems and Computation (CCDC) of the University of California, Santa Barbara during 2005. From January 2006 to July 2010, she was an Assistant Professor with the department of Mechanical and Aerospace Engineering at the University of California, San Diego.
In a broad sense, Dr Martínez’ main reseach interests include networked control systems, multi-agent systems, nonlinear control theory and robotics. In particular, she has focused on the modeling and control of robotic sensor networks, the development of distributed coordination algorithms for groups of autonomous vehicles, and the geometric control of mechanical systems. For her work on the control of underactuated mechanical systems she received the Best Student Paper award at the 2002 IEEE Conference on Decision and Control. She was the recipient of a NSF CAREER Award in 2007. For the paper “Motion coordination with Distributed Information,” co-authored with Jorge Cortés and Francesco Bullo, she received the 2008 Control Systems Magazine Outstanding Paper Award.
Prashant Mehta, University of Illinois at Urbana-Champaign, Recent Advances in Nonlinear Filtering with Applications to Neuroscience
The subject of my talk is a new formulation of nonlinear filter that is based on concepts from optimal control and mean-field game theory. Nonlinear filtering is critical to many applications in engineering, biology, economics, and atmospheric sciences. It is also an important paradigm in neuroscience. The Bayesian model of sensory (e.g., visual) signal processing suggests that the cortical networks in the brain encode a probabilistic ‘belief’ about reality. The belief state is updated based on comparison between the novel stimuli (from senses) and the internal prediction. In my talk, I will introduce the feedback particle filter and show how it admits an innovations error-based feedback control structure. The control is chosen so that the posterior distribution of any particle matches the posterior distribution of the true state given the observations. Applying these results to neuroscience, I will address the question of implementing Bayes rule at the level of neurophysiologically plausible spiking elements, my qualified approach to the problem being based on a coupled oscillator feedback particle filter model. A single oscillator is a simplified model of a single spiking neuron, and the coupled oscillator model solves an inference problem. The methodology will be described with the aid of a model problem involving estimation of a “walking gait cycle.” This work is the result of collaboration with several students and colleagues at the University of Illinois.
Prashant Mehta is an Associate Professor in the Department of Mechanical Science and Engineering, University of Illinois at Urbana-Champaign. He received his Ph.D. in Applied Mathematics from Cornell University in 2004. Prior to joining Illinois, he was a Research Engineer at the United Technologies Research Center (UTRC). His research interests are at the intersection of dynamical systems and control theory, including mean-field games, model reduction, and nonlinear control. He has received several awards including an Outstanding Achievement Award for his research contributions at UTRC, several Best Paper awards with his students at Illinois, and numerous teaching and advising honors at Illinois.
Andrea Montanari, Stanford University, Collaborative Filtering: Models and Algorithms
Modern online services aggregate information from millions of users about their interests and preferences. On the basis of this information, they provide to users ‘intelligent’ ways to navigate through a universe of items. Obvious examples include e-commerce companies (e.g. Amazon, Netflix, etc), that recommend products to buy or rent on the basis of the user’s past choices. A very similar function is implemented in online social networks (e.g. Facebook or Twitter) that recommend new connections on the basis of past ones.
Collaborative filtering broadly requires to a collection of problems and methods whereby information is aggregated and processed jointly across multiple users to provide feedback to any one of them. In the first part of this talk I will overview some simple mathematical models of collaborative filtering. Such models allow to formulate and answer questions of the type: How much information about a specific user can be gained from other users’ behavior? In the second part of the talk, I will discuss a few variants of the basic setting involving privacy protection and long term performance optimization.
Andrea Montanari received a Laurea degree in Physics in 1997, and a Ph. D. in Theoretical Physics in 2001 (both from Scuola Normale Superiore in Pisa, Italy). He has been post-doctoral fellow at Laboratoire de Physique Théorique de l’Ecole Normale Supérieure (LPTENS), Paris, France, and the Mathematical Sciences Research Institute, Berkeley, USA. Since 2002 he is Chargé de Recherche (with Centre National de la Recherche Scientifique, CNRS) at LPTENS. In September 2006 he joined Stanford University as a faculty, and since 2010 he is Associate Professor in the Departments of Electrical Engineering and Statistics.
He was co-awarded the ACM SIGMETRICS best paper award in 2008. He received the CNRS bronze medal for theoretical physics in 2006 and the National Science Foundation CAREER award in 2008.
Asu Ozdaglar, Massachusetts Institute of Technology, Network Security and Contagion
This paper develops a theoretical model of investments in security in a network of interconnected agents. The network connections introduce the possibility of cascading failures depending on exogenous or endogenous attacks and the profile of security investments by the agents. The general presumption in the literature, based on intuitive arguments or analysis of symmetric networks, is that because security investments create positive externalities on other agents, there will be underinvestment in security. We show that this reasoning is incomplete because of a first-order economic force: security investments are also strategic substitutes. In a general (non-symmetric) network, this implies that underinvestment by some agents will encourage overinvestment by others. We demonstrate by means of examples that not only there will be overinvestment by some agents but also aggregate probabilities of infection can be lower in equilibrium than in the social optimum. We then provide sufficient conditions for underinvestment. This requires both sufficiently convex cost functions (just convexity is not enough) and networks that are either symmetric or locally tree-like (i.e., either trees or in the case of stochastic networks, without local cycles with high probability). We also characterize the impact of network structure on equilibrium and optimal investments. Finally, we show that when the attack location is endogenized (by assuming that the attacker chooses a probability distribution over the location of the attack in order to maximize damage), there is another reason for overinvestment: greater investment by an agent shifts the attack to other parts of the network.
Asu Ozdaglar received the B.S. degree in electrical engineering from the Middle East Technical University, Ankara, Turkey, in 1996, and the S.M. and the Ph.D. degrees in electrical engineering and computer science from the Massachusetts Institute of Technology, Cambridge, in 1998 and 2003, respectively. Since 2003, she has been a member of the faculty of the Electrical Engineering and Computer Science Department at the Massachusetts Institute of Technology, where she is currently the Class of 1943 Associate Professor. She is also a member of the Laboratory for Information and Decision Systems and the Operations Research Center. Her research interests include optimization theory, with emphasis on nonlinear programming and convex analysis, game theory, with applications in communication, social, and economic networks, and distributed optimization and control. She is the co-author of the book entitled “Convex Analysis and Optimization” (Athena Scientific, 2003). Professor Ozdaglar is the recipient of a Microsoft fellowship, the MIT Graduate Student Council Teaching award, the NSF Career award, the 2008 Donald P. Eckman award of the American Automatic Control Council, and is a 2011 Kavli Fellow of the National Academy of Sciences. She served on the Board of Governors of the Control System Society in 2010. She is currently the area co-editor for a new area for the journal Operations Research, entitled “Games, Information and Networks”, an associate editor for IEEE Transactions on Automatic Control, and the chair of the Control System Society Technical Committee “Networks and Communications Systems”.