NME 130

NME 130 is a new class on "information systems" that we are planning. This web page collects together some of the information from discussions during the spring term 2009 between faculty, postdocs and students about what might be part of this course.

Participants: John Doyle (CDS/BE/EE), Steven Low (CS/EE), Michelle Effros (EE), Tracey Ho (EE/CS), Joel Tropp (ACM), Andreas Krause (CS), Pablo Parrilo (MIT), Richard Murray (CDS/BE).

Background information

(The information below is pulled from a planning document put together by Emmanuel Candes, John Doyle, Steven Low, Richard Murray and Pablo Parrilo, based on discussions in 2008-09.)

Many cutting edge problems in the natural sciences involve understanding aggregate behavior in complex large-scale systems. This behavior "emerges" from the interaction of multitudinous simpler systems, with intricate patterns of information flow. Representative examples can be found in fields ranging from embryology to seismology to global climate change. Key features of these new challenges include the (sometimes bewildering) complexity of the underlying phenomena of interest, the increasing ability to collect large amounts of data from sophisticated instruments, and the desire to develop principles that aid in our understanding and allow us to predict future behavior and/or design systems that behave reliably in the presence of large amounts of uncertainty.

While sophisticated theories have been developed by domain experts for the analysis of various complex systems, the development of rigorous methodology that can discover and exploit common features and essential mathematical structure remains a major challenge to the research community; we need new approaches and techniques.

To address this opportunity, we believe that a new PhD program in Network Mathematics and Engineering (working title) is timely and would keep Caltech in a leadership position in fundamental research on complex, networked systems across several areas of applied science and mathematics in which Caltech is already active, as well as enable potentially new thrusts within the sciences. The long term goals of this PhD program are:

• Develop new approaches for understanding and building complex systems, with an emphasis on the underlying theory and application across a broad variety of the sciences and engineering.

• Recruit students, postdocs and faculty to Caltech who will serve as leaders in their respective fields around the world, and who will help develop the theoretical frameworks required to tackle new problems in complex, networked systems.

• Develop a curriculum and educational culture that supports the education of broadly-trained scientists, applied mathematician and engineers who work in and across multiple disciplines over the course of their careers. careers and

A key theme of the program is to help facilitate interaction between a broad variety of application areas in which in a common set of mathematical problems arise. This will be accomplished in part by keeping the program very open and encouraging students to work with faculty from around the campus.

The following nominal course sequences will make up the core courses in the PhD program (taken by all students):

• NME 110ab. Stochastic systems} (2 quarters) - random processes, Markov chains
• NME 120. Optimization} (1 quarter) - convex optimization
• NME 121. Algorithms} (1 quarter) - TBD. Could range from numerical algorithms to computational complexity.
• NME 130ab. Information systems} 9 units (3-0-6); first and second terms. Prerequisites: CS 21 (or equivalent), EE 111 (or equivalent), Ma 2, \phdabbv 110 (may be taken concurrently). This course covers the fundamental mathematics of information systems, including key concepts and theories from communications, computer science, control theory, information theory and networking. Topics include: mathematical representations of information, signals and systems, computational complexity, fundamental limits of feedforward and feedback systems (Bode/Shannon), applications of graph theory to distributed systems.
• NME 140ab. Data-driven modeling and analysis} (2 quarters) - statistics, machine learning, model reduction

Discussion sessions

To help understand the contents of the courses and the interactions between the different topics, a series of discussions sections were held. The focus of these sessions was on topics related to the "information systems" course (NME 130). The links for each topic contain notes for the discussion.

Date	Topics	Discussion leaders	Unavailable
15 May (Fri) @ 3 pm, 110 Steele	Optimization Linear programming/duality Optimization and lower bounds, with applications in control Computational complexity? Convex analysis	John, Ben	Nader, Michelle, Tracy, Pablo, Ufuk
20 May (Wed) @ 12 pm	Distributed/networked systems Graph theory Distributed optimization and computation (large scale) Network algorithms (optimization; exploit networked structure) Graphical models	Steven, Javad	Richard (phone?), Nader
28 May (Thu) @ 12 pm	Information theory Method of types, large numbers, AEP Source/channel coding theorem Coding/network coding	Tracey, Michelle	Richard, Ufuk, Nader
3 Jun (Wed) @ 12 pm	Uncertainty Robustness and uncertainty (controls-ish) Bayesian theory, belief propogation Hypothesis testing, inference, decision making	Ufuk, Nader	Richard
16 Jun (Tue) @ 3 pm	Dynamical Systems Stability (including Lyapunov and Nyquist) Specifications (control versus CS) Equivalence and abstraction (simulation, bisimulation, model reduction?) Hybrid systems, automata theory Time delay, time-varying systems	Nader, Andy	Michelle, John, Tracey
19 Jun (Fri) @ 11 am	Graphical models	Andreas	John (phone?)
24 Jun (Wed) @ 4 pm	Synthesis theory Synthesis theory and hardbounds (Bode, Shannon, Carnot, Turing) Bayesian theory, belief propogation Hypothesis testing, inference, decision making Computational complexity Estimation and detection Coding/network coding	TBD
26 Jun (Fri) @ 11 am	Course planning	Richard

2009-10 course plan

Based on the discussions over the term, the following rough curriculum was sketched out as a possible starting point for the program. This curriculum attempts to make maximal use of courses that are already taught, so that we don't have to create too many new courses at once. The top set of courses are the core program, followed by a list of courses offered through the various options whose students faculty might eventually participate in the program:

Track	Fall	Winter	Spring
Stochastic systems	ACM/EE 116 (Owhadi) Introduction to Stochastic Processes and Modeling	ACM 216 (Tropp) Markov Chains, Discrete Stochastic Processes and Applications	NME 130 Discrete systems Graphs and optimization (shortest distance, max cut, etc) Temporal logic, automata, SAT Algorithm complexity (build on CS/EE/Ma 129) Dynamics and stability Nonlinear discrete time systems, hybrid systems Stability and stability certificates (Lyapunov, SOS) Feedback systems, small gain theorems Uncertainty and robustness Representation of uncertainty Operator bounds; links to small gain Robust performance: discrete time, NL? Need to say all of this in a non-control specific way Fundamental limits: Bode, Shannon, Bode/Shannon Case studies Internet: layering as optimization One more (not the cell)
Optimization and algorithms	Note: ACM 104/CDS 201 is a possibility for students who need more linear algebra and applied analysis Perhaps rename this row "Linear algebra and optimization" Similar course at MIT	ACM 113/CDS 203 (Owhadi) Convex analysis Linear programming/duality Note: create CDS 203 as alternative to CDS 202?
Information systems	CS/EE/Ma 129a (Winfree) Information and complexity Information theory and coding Finite state automata, Turing machines, computability Data compression Note: EE 126 is an alternative to this course for people who have already seen automata, computability, etc	CS/EE/Ma 129b (Winfree) Information and complexity Channel coding, capacity and rate theorem Time complexity of algorithms; P vs NP Formal logic and provability
Data-driven modeling	CS/CNS/EE 156 (Abu-Mostafa) Learning systems CS 155 (Krause) Graphical models Will eventually move to second term
ACM	ACM 104/CDS 201 (Beck) - Linear Algebra and Applied Operator Theory ACM 118 (Tropp) - Methods in Applied Statistics and Data Analysis	ACM 105 (???) - Applied Real and Functional Analysis	ACM 217 (???) - Advanced Topics in Stochastic Analysis
CS	CS/EE 143 - Communication Networks (Low)	CS/EE 146 - Advanced Networking (Low) CS/EE 144 -- The ideas behind the web (Wierman) the structure of the web/internet/social network web search, sponsored search, data center design spam & bot protection, network economics, and content aggregation	CS/EE 145 - Projects in Networking CS/EE 147 -- Network performance analysis (Wierman) some stochastic processes & Markov chains queueing, heavy-tailed distributions, large deviations, and scheduling
CDS	CDS 210a - Control theory (MacMynowski) State space models, Lyapunov stability Reachability, observability, state space design Frequency domain techniques Fundamental limits and robustness	CDS 110b - Optimization-based control (MacMynowski) Optimal control theory Trajectory generation, receding horizon control Kalman filtering CDS 212- Modern control theory (Doyle) Robust control of nonlinear systems Fundamental limits of performance	CDS 104 - Introduction to Dynamical Systems CDS 142 (Beck) - Stochastic System Analysis and Bayesian Updating
EE	EE 126a - Information Theory (Effros)	EE 126b - Information Theory (Effros) EE 163a - Communications Theory (Quirk?)	EE 163b - Communications Theory (Quirk?) EE 164 - Stochastic and Adaptive Signal Processing