NME 130

From Murray Wiki
Revision as of 02:17, 12 July 2009 by Murray (talk | contribs) (→‎Optimization and algorithms)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigationJump to search

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
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 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/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 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 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