Lecturer : Justin Romberg (Georgia Institute of Technology, Atlanta)
Outline of the school :
“The dogma of signal processing maintains that a signal must be sampled at a rate at least twice its highest frequency in order to be represented without error. However, in practice, we often compress the data soon after sensing, trading off signal representation complexity (bits) for some error (consider JPEG image compression in digital cameras, for example). Clearly, this is wasteful of valuable sensing resources. Over the past few years, a new theory of “compressive sensing” has begun to emerge, in which the signal is sampled (and simultaneously compressed) at a greatly reduced rate.
Compressive sensing is also referred to in the literature by the terms: compressed sensing, compressive sampling, and sketching/heavy-hitters.” [by courtesy of: http://dsp.rice.edu/cs]
- Basis decompositions and frames (3-4 hours)
- fundamentals of basis and frame decompositions
- the discrete cosine transform and applications to image/video compression
- the lapped orthogonal transform
- thresholding for noise reduction
- Sparsest decomposition from a dictionary (3-4 hours)
- omp and basis pursuit for selecting atoms
- uncertainty principles and sparsest decomposition
- the “spikes+sines” dictionary
- general unions of orthobases
- Introduction to compressive sampling and applications (2 hours)
- Recovering sparse vectors from linear measurements (6 hours/ 1 day)
- review of classical least-squares theory: the svd, pseudo-inverse, stability analysis, regularization
- sparse recovery conditions: l1 duality, sparsest decomposition revisited (with random support)
- the restricted isometry property and sparse recovery : l1 for perfect recovery from noise-free measurements,
l1 stability, l2 stability
- Random matrices are restricted isometries (2 hours)
- Optimization (6 hours / 1 day)
- conjugate gradients
- log-barrier methods
- first-order l1 solvers
- greedy algorithms and iterative thresholding
- recursive least-squares
- the Kalman filter
- dynamic l1 updating
- Low-rank recovery (2 hours)
Dates : 9-13/01/2012
Correspondant local : Paulo Goncalves
Intervenant : François Baccelli (http://www.di.ens.fr/~baccelli/)
The lecture will be taught in English.
Dates : 10 – 14 janvier 2011 – ENS Lyon
lundi : 10h30 : 12h30 – 14h00 : 17h00
mardi : 10h00 : 12h00 – 14h00 : 17h00
mercredi : 10h00 : 12h00 – 14h00 : 17h00
jeudi : 10h00 : 12h00 – 14h00 : 17h00
vendredi : 10h00 : 12h00 – 14h00 : 16h00
Objectif: Introduction à la géométrie stochastique et application à la modélisation des communications dans les réseaux sans fil.
Part I – Classical Stochastic Geometry
1. Poisson Point Process
2. Marked Point Processes and Shot-Noise Fields
3. Boolean Model
4. Voronoi Tessellation
Part II – Signal-to-Interference Ratio Stochastic Geometry
5. Signal-to-Interference Ratio Cells
6. Interacting Signal-to-Interference Ratio Cells
7. Signal-to-Interference Ratio Coverage
8. Signal-to-Interference Ratio Connectivity
Part III – Medium Access Control
9. Spatial Aloha: the Bipole Model
10. Receiver Selection in Spatial Aloha
11. Carrier Sense Multiple Access
12. Code Division Multiple Access in Cellular Networks
Part IV – Multihop Routing in Mobile ad Hoc Networks
13. Optimal Routing
14. Greedy Routing
15. Time-Space Routing
Prérequis : Probabilités (à cet effet, les étudiants de M1 sont vivement invités à suivre le cours de L3 “Probabilités – Statistiques“)
Documents de support : monographie “Stochastic Geometry and Wireless Networks” (2009), by F. Baccelli and B. Blaszczyszyn (available on-line at http://www.di.ens.fr/~baccelli/)
Correspondant local : P. Gonçalves.
Sponsor : Pôle ResCom du GDR CNRS ASR
du 25 au 29 janvier 2010 — ENS Lyon
Location and schedule
All the lectures will take place in amphitheater B, at the 3rd floor of the GN1 building (main building of the “exact sciences” part of ENS Lyon).
- Monday 25/01/2010 Morning: Eitan Altman 11:00 – 13
Zero-sum Games: these are the most elementary game where there are two players, one playing against the other. These games are useful for modeling malicious users, denial of service attacks, jamming etc. We introduce the notions of upper and lower values as well as the notion of value of a zero-sum game. We present some minimax theorems which are used to establish the existence of a value. We end with an LP solution for Zero sum matrix games. We present examples of games with and without a value. Solution of 2 by 2 matrix games.
Non-zero sum games. We present the notion of Nash equilibrium as well as epsilon Nash equilibrium. We then introduce Coordination Games and present their properties. We then study Lemke’s algorithm for computing the equilibrium in non-zero sum games with two players. We present examples of channel selection games. We end this part with the concept of Correlated equilibrium
Afternoon: Corinne Touati 14h30 – 17h00
Notions from cooperative game theory: Bargaining and fairness.
Le but de cette partie est de comprendre comment appréhender les qualités d’une allocation (équilibre de Nash ou valeur optimisant une fonction par exemple). Nous commençons par la définition de la propriété d’optimalité. Parmi l’ensemble des points optimaux, un ensemble de critères permet de choisir un point dit équitable. Nous présentons des techniques numériques permettant d’approcher la frontière de Pareto et de calculer les points équitables. Enfin, nous verrons dans une dernière partie des méthodes d’évaluations des performances d’allocations, en terme à la fois d’équité et d’optimalité.
a. Définition de Pareto et notions liées
b. Propriétés des ensembles de Pareto (par ex. compacité)
c. Epsilon-approximation et méthodes de résolutions
d. Introduction à l’optimisation multi-critères, exemple d’un problème d’ordonnancement.
- Tuesday 26/01/10 Morning: Corinne Touati 10:30 – 12:30
2. Fairness and Nash bargaining.
a. Axiomatic definitions: Thomson, Raiffa-Kalai-Smorodinsky, Nash)
b. Equivalent optimizations and properties
c. Alpha fairness
d. Algorithmic solutions.
e. Application to flow control and TCP.
3. Performance evaluation of the resource allocation:
a. The Gain index,
b. Price of anarchy
c. Selfish Degradation Factor
d. Pareto equilibrium
Afternoon: Eitan Altman 14:00 – 16:30
Convex games. These are games with a convex compact space. We shall study Rosen’s theory for the existence of an equilibria, The strict diagonal concavity property (which extends concavity to a game context). This notion is used to establish uniqueness of equilibrium in convex games.
We then introduce games with coupled constraints as in Rosen, as well as the related notion of generalized Equilibrium. These are equilibria in which the space of actions of each player are not independent: the actions available to a player may depend on those already chosen by others (for example, if there are capacity constraints over links then the amount of flow that a player can send over a link depends on how much other players send over that link). In the presence of such constrained there is in general no uniqueness of equilibrium. We thus introduce the problem of equilibrium selection. We introduce in particular the notion of normalized Nash equilibrium which and and relate it to scalable pricing.
- Wednesday 27/01/10Morning Rachid El-Azouzi 9h30 – 12h30
Energy-efficient power control games Non-cooperative games where terminals want to maximize the number of information bits per joule are analyzed. The solution of this game is shown to be inefficient.
Medium access games: the aloha game.
Afternoon Rachid El-Azouzi 14:00 – 17:00
Super-modular Games and Potential Games. These are two classes of games in which not only do we know that equilibria exists, but we also know that sequence of best responses of players convenrge to the equilibrium. In particular, we show how potential games can be transformed into a global optimization problem whose optimum corresponds to the equilibrium of the original game.
Routing games Wardrop equilibrium: the players are modeled as infinitesimally small, which means that we have a continuum of players. computation of the equilibrium of the game
Definitions. Price of anarchy, price of stability, variational inequalities. Link between Nash and Wardrop equilibria.
- Thursday 28/01/10Morning: Corinne Touati 10:30 – 12:30
Evolutionary game theory and population games. (games are related to infinite number of players). We introduce the concept of equilibrium is Evolutionary Stable Strategy, which is more general than a Nash equilibrium in a given sense.
Replicator Dynamics and evolutionary dynamics: Methods for convergence to equilibria, cases of non-convergence and oscillations. Based on the idea that higher fitness will be adopted by a growing number of individuals. Other evolutionary dynamics: Brown-von Neumann-Nash, Best response dynamics, Fictitious play, Logit response dynamics. We will discuss about the main difference of those dynamics and present a generalization which is called the revision protocols.
Afternoon: Corinne Touati 14:00 – 17:00
Learning in games. All the previous evolutionary dynamics are related to learning process. The theory of learning in games explains the dynamic behavior of each player or agents depending on its own experience. Those learning processes related to the evolutionary dynamics, are used in order to construct distributed algorithms converging to equilibrium (Nash or ESS). We will introduce an example of distributed algorithm proposed in the literature which has been widely used in the networking community for power control, pricing, resource sharing and routing protocol. We will present other reinforcement learning algorithms: the Erev-Roth algorithm, and the Arthur algorithm for a variant of the last one with renormalization. Those distributed algorithms have interesting properties of implementation as they are totally distributed but they suffer from stability problems at the boundary of the state space. We will investigate how feedback delays and errors affect convergence
- Friday 29/01/10Morning: Eitan Altman 11:00 – 13:00
The Braess paradox. Routing games with finitely many users: Uniqueness of the equilibrium. Parallel links. Load balancing problems. Relation to Ad-hoc networks.
Afternoon: Eitan Altman 14:30 – 17:00
Introduction to Repeated Games. Threats and punishments. Credibility of threats and refinements of equilibria. Stochastic games and Dynamic programming approach for stochastic games. The discouted cost and the average cost games. Product stochastic games. Anonymous sequential games, Markov Decision Evoluationary Games.
- Paulo Goncalves