École Normale Supérieure

Département de Mathématiques et Applications

Mémoire de Magistère MMFAI

Lacunarité et incohérence

Yohann de Castro

19 octobre 2007
Table des matières

1 Un modèle déterministe comme première approche . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

1.1 Un problème de reconstruction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2 Le vecteur dual π . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.3 Stabilité en norme `1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.4 Le modèle de Bernoulli . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

2 L’incohérence, levier de la reconstruction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

2.1 Principe d’incertitude et géométrie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.2 Une inégalité de Rudelson . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.3 Un théorème de Talagrand . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.4 Preuve du théorème de Candès-Romberg . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

Références . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
1
Un modèle déterministe comme première approche

Au début du vingt et unième siècle, E. Candès, J. Romberg et T. Tao ont résolu un problème tomographique
classique en imagerie médicale : Reconstruire une image 2D à partir de la connaissance de sa transformée de Fourier
sur un domaine étoilé Ω. Dans ce problème on connaît un petit nombre de valeurs de la transformée de Fourier,
et on cherche à reconstruire exactement le signal échantillonné. Dans le cas de signaux lacunaires, c’est-à-dire
avec un grand nombre de coefficients nuls, E. Candès, J. Romberg et T. Tao se sont aperçus que l’on avait
reconstruction exacte en considérant le signal qui minimise la norme `1 sous la contrainte imposée par
l’échantillonnage. Cette approche est basée sur un algorithme bien établi, le Basis Pursuit, de minimisation
de la norme `1 d’un signal sous une contrainte linéaire.

1.1 Un problème de reconstruction

On suppose que le signal que l’on cherche à reconstruire est lacunaire, c’est-à-dire qu’il a un grand
nombre de coefficients nuls. Cette hypothèse est primordiale ; elle est la seule et unique hypothèse faite dans
ce chapitre. Fixer cette hypothèse amène à considérer la classe des signaux ayant soit une représentation
lacunaire dans une base donnée (base d’ondelettes par exemple), soit un gradient lacunaire dans une base
donnée (signaux BV par exemple). Le théorème qui suit s’applique donc à une large classe de signaux.

Enoncé du problème

On s’intéresse au problème suivant :

Est-il possible de reconstruire un signal x connaissant seulement ses coefficients de Fourier sur un ensemble
aléatoire Ω ?
On considère un signal x appartenant à CN que l’on représente comme une fonction de l’ensemble des
indices NN := {0, 1, . . . , N − 1} à valeurs dans C. On désigne par T := {t ∈ NN , x(t) 6= 0} le support du
signal x, et par S le cardinal de cet ensemble. On définit la transformée de Fourier discrète à la fréquence Ω de
x par
1 X
b(ω) = √
x x(t)e−i2πωt/N .
N t∈NN
On cherche à savoir s’il est possible de reconstruire le signal x connaissant K de ses coefficients de Fourier.
Dans ce chapitre on note U la matrice de Fourier. Soit Ω un sous-ensemble aléatoire choisi de manière
uniforme parmi les sous-ensembles de cardinal K. On note UΩ la matrice de Fourier dont on n’a gardé que
les colonnes d’indice appartenant à l’ensemble Ω.

UΩ x = (b
x(ω))ω∈Ω .

Enoncé du théorème

Dans leur article [4], Emmanuel Candès, Justin Romberg et Terence Tao ont montré qu’un signal suffisam-
ment lacunaire peut être reconstruit exactement, avec grande probabilité, comme la solution du problème
(P1 ) de minimisation convexe
min kgk`1 sachant que UΩ x = UΩ g,
g∈CN
P
où la norme kgk`1 vaut t∈NN |g(t)|.
4 1 Un modèle déterministe comme première approche

Théorème 1.1 (Théorème de reconstruction de Candès-Romberg-Tao). Soit Ω un sous-ensemble aléatoire de

taille K choisi de manière uniforme parmi les sous-ensembles de taille K. Soit un paramètre de fiabilité M donné.
Alors tout signal x ∈ RN dont on ne connaît qu’une borne sur la taille de son support :

S ≤ CM (K/ log N ), (1)

où CM est une constante qui ne dépend que de M , peut être reconstruit exactement comme l’unique solution du
problème (P1 ) :
min kgk`1 sachant que UΩ x = UΩ g ,
g∈CN

avec une probabilité d’au moins 1 − O(N −M ).

La suite de ce chapitre apportera les principales étapes de la démonstration de ce théorème.
Remarque 1.2. — La constante implicite dans la notation O( . ) peut dépendre de M . Le paramètre M dépend
de la taille N du signal et de la taille K de l’échantillon de fréquence.
— Ce théorème montre qu’il suffit d’un échantillonnage de la taille du signal modulo un facteur logarith-
mique pour avoir reconstruction exacte dans la majorité des cas.

1.2 Le vecteur dual π

Le problème (P1 ) est un problème d’optimisation convexe, on sait qu’il existe une solution à ce problème
mais il n’est pas clair que ce minimum soit unique, ni même qu’il permette de restituer le signal x. Une
condition nécessaire et suffisante pour que le signal x que l’on cherche à reconstruire soit l’unique solution du
problème (P1 ) est qu’il existe un vecteur dual π qui vérifie trois conditions énoncées dans le lemme suivant.

Lemme 1.3. — Soit Ω un sous-ensemble de NN et x un signal de support T . On suppose qu’il existe un vecteur π
de CN tel que
(i) La transformée de Fourier U π du vecteur π ait pour support Ω.
(ii) Le vecteur π coïncide avec le vecteur1 sgn(x) sur l’ensemble T .
(iii) L’amplitude de π est strictement inférieure à 1 en dehors de l’ensemble T .
Si de plus l’application UΩT : `2 (T ) 7→ `2 (Ω) (définie comme la projection sur le sous-espace vectoriel des vecteurs
de support Ω de l’application linéaire hermitienne U restreinte au sous-espace vectoriel des vecteurs de support T ) est
injective, le problème (P1 ) admet alors un unique minimum égal à x. Réciproquement, si x est l’unique minimum du
problème (P1 ) alors il existe un vecteur π de CN vérifiant les trois propriétés ci-dessus.

La preuve du théorème de reconstruction de Candès-Romberg-Tao (théorème 1.1) est articulée autour

du vecteur dual π. Les auteurs prennent le vecteur de plus petite norme `2 vérifiant les deux premières
hypothèses du lemme précédent et démontrent qu’avec une grande probabilité ce vecteur vérifie la troisième
et dernière hypothèse. Mais quel est précisément ce vecteur ?

Un bon candidat

On choisit en espérant que son amplitude sera petite en dehors de l’ensemble T , le vecteur d’énergie
minimale qui coïncide avec sgn(x) sur l’ensemble T et dont le support de sa transformée de Fourier est
inclus dans l’ensemble Ω. Pour définir ce vecteur π, qui on l’espère sera un bon candidat pour répondre
aux critères imposés par le lemme précédent, on introduit quelques notations. Soit E un ensemble inclus
dans NN , notons ιE : `2 (E) 7→ `2 (NN ), l’opérateur d’injection qui étend une application définie sur E en une
application définie sur NN (l’ensemble des applications définies sur NN peut être canoniquement identifié à
CN ) en la complétant par des zéros en dehors de E. On note UΩT : `2 (T ) 7→ `2 (Ω) la projection sur le sous-
espace vectoriel des vecteurs de support Ω de l’application linéaire hermitienne U restreinte au sous-espace
vectoriel des vecteurs de support T . On définit le vecteur π par :
−1 ∗
π := UΩ∗ UΩT (UΩT
∗
UΩT ) ιT sgn(x) . (2)

Le vecteur sgn(x) est le signal qui vaut +1 lorsque x est strictement positif, −1 lorsque x est strictement négatif et
1

0 sinon.
 1.3 Stabilité en norme `1 5

Le vecteur π vérifie-t-il les deux propriétés annoncées ?

On montre tout d’abord que π satisfait la condition (i) du lemme 1.3. On peut en effet remarquer2 que

U UΩ∗ = U (ι∗Ω U )∗ = U U ∗ ιΩ = ιΩ ,

on en déduit que U π a pour support l’ensemble Ω. On montre ensuite que π satisfait la condition (ii) du
lemme 1.3. En effet,
ι∗T UΩ∗ = ι∗T U ∗ ιΩ = (U ιT )∗ ιΩ = (ι∗Ω U ιT )∗ = UΩT
∗
,
on a bien ι∗T π = ι∗T sgn(x) comme attendu. La suite de la démonstration du théorème de reconstruction de
Candès-Romberg-Tao (théorème 1.1) consiste à montrer que π est bien défini, c’est-à-dire que l’opérateur
UT∗ Ω UT Ω est bien inversible, et qu’il est suffisamment petit en dehors de l’ensemble T .

1.3 Stabilité en norme `1

On ouvre dans cette section une parenthèse sur le lemme précédent et la place du vecteur dual au sein
des travaux de Candès sur le compressed sensing. On élargit le cadre de notre exposé en considérant un signal
x quelconque (on fait abstraction de l’hypothèse de support fini). On considère une matrice de mesure UΩ
quelconque et on note x] la solution du problème (P1 ) qui s’écrit ici :

min kgk`1 sachant que UΩ x = UΩ g .

g∈CN

On présente un lemme de localisation des solutions x] du problème (P1 ).

Lemme 1.4. — Soit x un vecteur de CN et x0 un vecteur de RN de support un ensemble T . On pose h le vecteur de
CN tel que x = x0 + h. On suppose qu’il existe un vecteur π appartenant à CN tel que
(i) Le vecteur π appartient à l’image de UΩ∗ , c’est-à-dire qu’il existe un vecteur V pour lequel π = UΩ∗ V ,
(ii) Le vecteur π coïncide avec le vecteur sgn(x0 ) sur l’ensemble T ,
(iii) Le vecteur π est de module inférieur à 1/2 sur le complémentaire de l’ensemble T .
Alors on a l’inégalité

x] `1 (T c )
≤ 3 khk`1 ,

où k . k`1 (T c ) est la norme induite par projection de la norme `1 sur l’espace vectoriel des signaux de support le
complémentaire de l’ensemble T .
Remarque 1.5. — Le vecteur π sera appelé vecteur dual associé au vecteur x0 .
Démonstration. — Par définition de x] ,

x] `1
≤ kxk`1 ≤ kx0 k`1 + khk`1 .

D’après l’hypothèse (i) le vecteur π appartient à l’image de UΩ∗ , il est donc orthogonal au noyau de UΩ :

hx] , πi = hx] , UΩ∗ V i = hUΩ x] , V i = hUΩ x, V i = hx, πi .

On utilise les propriétés (ii) et (iii) pour en déduire que :

hx, πi = hx0 + h, πi
≥ hx0 , πi − 1/2 khk`1
= kx0 k`1 − 1/2 khk`1

D’autre part,
X X
hx] , πi ≤ x] (t)π(t) + x] (t)π(t)
T Tc
X X
≤ x] (t)π(t) + 1/2 x] (t)
T Tc
= x] `1
− 1/2 x] `1 (T c )

2
On utilise ici le fait que U −1 = U ∗ .
6 1 Un modèle déterministe comme première approche

On en déduit que
kx0 k`1 − 1/2 khk`1 ≤ hx, πi = hx] , πi ≤ hx] , πi ≤ x] `1
− 1/2 x] `1 (T c )
≤ kx0 k`1 + khk`1 − 1/2 x] `1 (T c )
.
En simplifiant par kx0 k`1 on trouve le résultat attendu.
Remarque 1.6. — Ce lemme est un formidable outil pour localiser la solution x] du problème (P1 ) en fonction
de n’importe quel élément de support fini x0 appartenant à l’espace affine x + ker UΩ défini par l’information
a priori, c’est-à-dire n’importe quel vecteur de support fini x0 tel que UΩ x0 = UΩ x.

1.4 Le modèle de Bernoulli

Il est difficile de travailler avec un sous-ensemble Ω choisi aléatoirement de manière uniforme, car la
probabilité pour une fréquence donnée d’appartenir au sous-ensemble Ω est conditionnée par le fait que l’on
sache si les autres fréquences y appartiennent ou pas. On introduit un modèle probabiliste plus simple, dit
de Bernoulli, pour générer le sous-ensemble Ω ; et on montre dans cette section comment les résultats issus
de ce modèle peuvent être translatés en résultats pour le modèle aléatoire uniforme. Le modèle de Bernoulli est
un modèle simple où l’on considère que les fonctions indicatrices des fréquences mesurées sont des variables
aléatoires indépendantes identiquement distribuées selon la loi de Bernoulli de paramètre τ ∈ [0, 1]. On génère
alors un sous-ensemble aléatoire Ω0 de la manière suivante
Ω0 := {ω ∈ NN , δω = 1},
où δ0 , . . . , δN −1 sont des variables aléatoires indépendantes identiquement distribuées de loi de Bernoulli
de paramètre τ . La taille du sous-ensemble Ω0 est une variable aléatoire de loi binomiale de paramètre τ et
d’espérance
E(|Ω0 |) = τ N.
Remarque 1.7. — On remarque que |Ω0 |/N ≈ τ avec une grande probabilité. En effet, on peut montrer à
l’aide de l’inégalité de Hoeffding que pour tout réel ε strictement positif,
 0 
|Ω |
P − τ ≥ ε ≤ 2 exp(−2ε2 ).
N
On définit échec(Ω0 ) comme l’événement où il est impossible de trouver un vecteur dual π dont la
transformée de Fourier est supportée par Ω0 et vérifiant les trois conditions du lemme 1.3. Soit Ω un sous-
ensemble de taille K généré en utilisant le modèle aléatoire uniforme, et soit Ω0 un sous-ensemble généré
en utilisant le modèle de Bernoulli avec le paramètre τ = K/N . On a alors
N
X
P (échec (Ω0 )) = P (échec (Ω0 ) | |Ω0 | = k) P (|Ω0 | = k)
k=0
N
X
= P (échec (Ωk )) P (|Ω0 | = k)
k=0

où Ωk est choisi aléatoirement de manière uniforme parmi les sous-ensembles de taille k. On fait alors deux
remarques :
— La fonction k 7→ P (échec (Ωk )) est une fonction décroissante de la variable k. Cela vient du fait que plus
Ω est grand plus il est facile de construire un bon vecteur dual π.
— Lorsque τ N est un entier, il correspond à la valeur médiane de |Ω0 |,
P (|Ω0 | ≤ τ N − 1) < 1/2 < P (|Ω0 | ≤ τ N ) .
Ces remarques permettent d’écrire que
K
X
0
P (échec (Ω )) ≥ P (échec (Ωk )) P (|Ω0 | = k)
k=0
K
X
≥ P (échec (Ω)) P (|Ω0 | = k)
k=0
1
≥ P (échec (Ω)) .
2
On a ainsi montrer que si l’on pouvait borner la probabilité d’échec pour le modèle de Bernoulli, on sait
alors que le taux d’échec pour le modèle uniforme ne sera pas deux fois plus grand.
2
L’incohérence, levier de la reconstruction

On va présenter et démontrer un résultat dû à Candès et Romberg qui généralise le travail précédent aux
matrices N -hermitiennes. Soit U une matrice N × N , on dira que U est N -hermitienne si et seulement si

U ∗ U = N Id .

On fait le choix de cette définition pour simplifier les notations. La matrice U est une matrice de passage entre
deux bases orthogonales. Soit T un sous-ensemble d’indices fixé de taille S et Ω un sous-ensemble aléatoire
construit suivant le modèle de Bernoulli de paramètre τ = K/N . On rappelle que UΩ : `2 (NN ) 7→ `2 (Ω) est la
projection sur le sous-espace vectoriel des vecteurs de support Ω de l’application U ; que UT : `2 (T ) 7→ `2 (NN )
désigne l’application U restreinte au sous-espace vectoriel des vecteurs de support T ; et que UΩT : `2 (T ) 7→
`2 (Ω) est la projection sur le sous-espace vectoriel des vecteurs de support Ω de l’application U restreinte
au sous espace vectoriel des vecteurs de support T . On note uk la k-ième ligne de la matrice UT et k . k la
norme standard d’opérateur au sens de la norme `2 .

2.1 Principe d’incertitude et géométrie

Notre approche reste la même que précédemment, on cherche à reconstruire un signal x (ayant un
grand nombre de coefficients nuls dans la base canonique) à partir d’une mesure UΩ x faite dans une base
orthogonale B. Le vecteur U x est la lecture du signal x dans la base B définie par les vecteurs colonne de la
matrice U ∗ . La base B joue le rôle de la base de Fourier du chapitre précédent ; et intuitivement on voit que
si elle présente de bonnes propriétés, comme ce fut le cas avec la matrice de Fourier, on pourra reconstruire
le signal x dans de bonnes conditions. Mais quelle propriété doit vérifier la matrice U ?

Incohérence mutuelle

On appellera incohérence mutuelle d’une matrice N -hermitienne U , le réel µ(U ) défini par :

µ(U ) := max |Ui,j | .

i,j∈NN
√
La matrice U étant N -hermitienne, ses vecteurs colonne sont de norme `2 égale à N . Par équivalence de
la norme `2 et de la norme `∞ , on en déduit que
√
1 ≤ µ(U ) ≤ N .

L’incohérence µ est grossièrement une mesure de la localisation des vecteurs colonne de la matrice U dans
la base canonique. Dans le cas de la matrice de Fourier, l’incohérence vaut 1 et les vecteurs de la base de
Fourier sont non localisés dans le domaine temporel. C’est dans ce sens que doit être entendu le terme
d’incohérence : plus µ est proche de 1, plus les bases associées (la base canonique que l’on compare à la base
B associée à la matrice U ) vérifient le principe d’incertitude, c’est à dire que tout signal fortement localisé
dans la base canonique sera fortement non localisé dans la base B.

Un problème au caractère géométrique

Le problème de reconstruction à l’aide du basis pursuit est intimement lié à la géométrie de la sphère unité
de la norme `1 . On rappelle que l’information a priori est donnée par le vecteur y = UΩ x, c’est à dire par un
8 2 L’incohérence, levier de la reconstruction

plan affine x + ker UΩ de plan directeur le noyau de l’application linéaire UΩ . On peut dégager deux facteurs
importants dans la réussite du programme (P1 ). Tout d’abord, la matrice de mesure UΩ qui détermine la
direction du plan affine. Jusqu’ici tous nos modèles probabilistes portaient sur elle et uniquement elle. Celle-
ci va de pair avec un deuxième élément, la facette de la sphère unité de la norme `1 sur laquelle repose le
vecteur x. Une facette est un élément intime de la géométrie de la sphère unité `1 . On appelle S-facette de la
sphère unité `1 , l’ensemble des barycentres à coefficients positifs de S points extrémaux non diamétralement
opposés 2 à 2 de la sphère unité de la norme `1 . Ces points extrémaux sont exactement les vecteurs avec un
seul coefficient non nul qui vaut ±1. Le deuxième élément important de la réussite du problème (P1 ) est la
S-facette sur laquelle repose le vecteur x. De manière condensée on représente cette S-facette par le vecteur
Z := sgn(x). Toute l’information géométrique de la S-facette est contenue dans ce vecteur Z. Le problème
(P1 ) est entièrement déterminé par ces deux éléments géométriques. De manière intuitive, le problème de
reconstruction consiste à savoir si le plan affine donné par UΩ se présente bien par rapport à la S-facette
déterminée par le vecteur x.

Un modèle probabiliste pour les S-facettes

On introduit un modèle aléatoire pour les S-facettes. On rappelle que, depuis le début, le support T du
vecteur x est fixé. On introduit un modèle de Bernoulli pour construire une suite de signes ±1 de support
l’ensemble T . On construit un vecteur Z = (Z0 , . . . , ZN −1 ) de taille N et de support T de la manière suivante :

Zt := δT (t)(2 b1/2 (t) − 1) ,

où b1/2 est la variable aléatoire canonique de loi de Bernoulli de paramètre 1/2, qui vaut 1 avec probabilité
1/2 et 0 avec probabilité 1/2. Ainsi la variable aléatoire Zt vaut 0 si t n’appartient pas à T ; elle vaut 1 avec
probabilité 1/2 et −1 avec probabilité 1/2, si t appartient à l’ensemble T .

Enoncé du théorème de Candès-Romberg

On donne l’énoncé du théorème de Candès-Romberg que l’on démontre dans toute la suite de ce chapitre.
Ce théorème peut être trouvé dans leur article [3].

Théorème 2.1 (Théorème de reconstruction de Candès-Romberg). Soient N, K, S trois entiers naturels, θ un

réel strictement compris entre 0 et 1, U une matrice N -hermitienne (U ∗ U = N Id) telle que

|Ui,j | ≤ µ(U ) ,

et T un sous-ensemble fixé de NN de taille S. On se donne un sous-ensemble Ω de taille K et une suite de signes Z

de taille N et de support T en appliquant le modèle de Bernoulli. On suppose que

K ≥ C0 S µ2 (U ) log(N/θ) ,

et
K ≥ C00 log2 (N/θ) ,
où C0 et C00 sont deux constantes universelles strictement positives. Alors, avec une probabilité plus grande que 1 − θ,
tout signal x de support T tel que sgn(x) = Z, peut être reconstruit de manière exacte comme la solution du problème
(P1 ) sous la contrainte définie par la matrice de mesure UΩ .

On a vu au chapitre précédent que le vecteur dual π que l’on prend tel que
−1 ∗
π := UΩ∗ UΩT (UΩT
∗
UΩT ) ιT sgn(x) .

avait un rôle primordial dans la preuve du premier théorème de reconstruction. Mais, bien au delà de
∗
l’existence du vecteur dual π, le comportement de la matrice UΩT UΩT est une pièce bien plus profonde dans
la preuve. La démonstration du théorème de Candès-Romberg repose elle aussi sur l’aptitude, avec forte
∗
probabilité, qu’à la matrice UΩT UΩT à être proche d’une isométrie. La preuve se déroule en deux temps.
∗
Tout d’abord on montre que l’espérance de UΩT UΩT est proche de l’identité. Dans un deuxième et dernier
∗
temps on montre qu’avec forte probabilité la matrice UΩT UΩT est proche de son espérance. On démontre la
première étape avec une inégalité dû à Rudelson.
 2.2 Une inégalité de Rudelson 9

2.2 Une inégalité de Rudelson

Théorème 2.2 (Rudelson). Dès lors que le membre de droite est plus petit que deux, on a
√
1 ∗ log S
E UΩT UΩT − Id ≤ CR √ max uk , (3)
K K 1≤k≤N
où CR est une constante universelle strictement positive.

Démonstration. — On remarque que

N
X −1
∗
UΩT UΩT = δk uk ⊗ uk ,
k=0

où (δk ) est défini selon le modèle de Bernoulli (voir chapitre précédent), et la matrice uk ⊗ uk est définie par :

uk ⊗ uk i,j := uk,i uk,j .

On remarque que Ω est un sous-ensemble aléatoire généré par le modèle de Bernoulli, ainsi (δk ) peut être
vue comme une suite à N éléments de variables aléatoires indépendantes identiquement distribuées de loi
de Bernoulli de paramètre τ . On s’interesse à l’espérance E kY k où Y est la variable aléatoire définie par :
N −1
1 X
Y := δk uk ⊗ uk − Id .
K
k=0

On remarque que
N −1 N −1
1 X k k 1 X k
EY = τ u ⊗ u − Id = u ⊗ uk − Id = 0 .
K N
k=0 k=0

Par symétrie ("symmetrization trick", on peut avantageusement lire la page 5 de l’article [2]), on majore
l’espérance de la norme de la variable aléatoire Y . Soit Y 0 une copie indépendante identiquement distribuée
de Y :
N −1
1 X 0 k
Y 0 := δk u ⊗ uk − Id ,
K
k=0

δk0
où sont des variables aléatoires indépendantes identiquement distribuées de loi de Bernoulli de paramètre
τ . La fonction M 7→ kY − M k est convexe sur CN ×N . D’après l’inégalité de Jensen,

kY − E Y 0 k ≤ E kY − Y 0 k .

Comme l’espérance de la variable aléatoire Y est nulle, il vient que

kY k ≤ E kY − Y 0 k .

Le théorème de Fubini permet de conclure que :

E kY k ≤ E kY − Y 0 k . (4)

Soit ε0 , ε1 , . . . , εN −1 une suite de variables aléatoires indépendantes identiquement distribuées de loi de

Bernoulli de paramètre 1/2 prenant les valeurs ±1. D’après l’inégalité 4 on a,
N −1
1 X
E kY k ≤ Eδ,δ0 (δk − δk0 ) uk ⊗ uk .
K
k=0

Les variables aléatoires (δk − δk0 ) et −(δk − δk0 ) ont même loi, le théorème de Fubini donne
N −1 N −1
1 X 1 X
Eδ,δ0 (δk − δk0 ) uk ⊗ uk = Eε Eδ,δ0 εk (δk − δk0 ) uk ⊗ uk .
K K
k=0 k=0

On obtient un premier résultat à l’aide de l’inégalité triangulaire :

10 2 L’incohérence, levier de la reconstruction
N −1
1 X
E kY k ≤ 2 Eε Eδ εk δk uk ⊗ uk . (5)
K
k=0

Un lemme dû à Rudelson dans son article [10] montre que :

v
N −1 u N −1
X CR p u X
Eε εk δk uk ⊗ uk ≤ log S max uk t δk uk ⊗ uk , (6)
4 k|δk =1
k=0 k=0

où CR est une constante universelle strictement positive. Les inégalités 5 et 6, et l’inégalité de Jensen donnent :

√
v
u N −1
CR log S k
u X
E kY k ≤ max u Et δk uk ⊗ uk
2 K 0≤k≤N −1
k=0

√
v
u N −1
CR log S u X
≤ max uk tE δk uk ⊗ uk
2 K 0≤k≤N −1
k=0

L’inégalité triangulaire montre que

N
X −1
E δk uk ⊗ uk = E kK Y + K Idk ≤ K (E kY k + 1) .
k=0

On a l’inégalité √
p CR log S
E kY k ≤ a E kY k + 1 , où a := max uk .
2 K 0≤k≤N −1

En résolvant cette inéquation du second degré, on trouve que si le réel positif a est plus petit que 1 alors
l’espérance de la norme de la variable aléatoire Y est plus petite que 2a, comme attendu.

Remarque 2.3. — On a la majoration √

uk `2
≤ µ(U ) S .
L’inégalité 3 s’écrit alors de manière plus faible comme
√
1 ∗ S log S
E U UΩT − Id ≤ CR √ µ(U ) . (7)
K ΩT K

2.3 Un théorème de Talagrand

∗
On démontre ensuite que la matrice UΩT UΩT est proche de son espérance. On utilise un puissant théorème
dû à Talagrand.

Théorème 2.4 (Talagrand). Soit F une famille dénombrable de fonctions d’un espace de banach E à valeurs dans
R. Supposons qu’il existe un réel strictement positif B tel que pour toute fonction f appartenant à F, la valeur absolue
de f soit bornée par B. Soit n un entier naturel et Y1 , Y2 , . . . , Yn une suite de variables aléatoires indépendantes
identiquement distribuées à valeurs dans E. Soit Z la variable aléatoire définie par :
N
X
Z := sup f (Yi ) .
f ∈F i=1

On suppose que pour tout indice i = 1, . . . , n et tout f appartenant à F,

E f (Yi ) = 0 .

Alors pour tout réel t positif ou nul,

  
t Bt
P (|Z − E Z| > t) ≤ 3 exp − log 1 + 2 ,
KB σ + B EZ
où
 2.3 Un théorème de Talagrand 11
N
X
σ 2 := sup E f 2 (Yi ) ,
f ∈F i=1

N
X
Z := sup f (Yi ) ,
f ∈F i=1

et K est une constante universelle strictement positive.

Ce théorème permet de mettre en place la seconde étape de la démonstration.

Théorème 2.5 (Candès). Soit θ un réel strictement positif. On suppose que l’ensemble Ω est suffisamment grand au
sens où

K ≥ Sµ(U )2 max (C1 log S, C2 log(3/θ)) , (8)

où C1 , C2 sont deux constantes strictement positives. Alors,

 
1 ∗ 1
P U UΩT − Id ≥ ≤ θ.
K ΩT 2

Démonstration. — On rappelle que

N −1
1 X
Y := δk uk ⊗ uk − Id .
K
k=0

Ce que l’on écrit comme la somme de variables aléatoires Yk :

N −1  N −1
uk ⊗ uk

X K X
Y = δk − := Yk ,
N K
k=0 k=0

où
uk ⊗ uk
 
K
Yk := δk − .
N K
On s’intéresse à la norme spectrale de Y définie par :
N
X −1
kY k := sup hf1 , Y f2 i = sup hf1 , Yk f2 i ,
f1 ,f2 f1 ,f2
k=0

où le supremum est pris sur une famille dénombrable dense de la sphère unité pour la norme `2 . On applique
le théorème de Talagrand pour prouver le résultat (théorème 2.4). Tout d’abord, on remarque que

E Yk = 0 .

Soit un couple f = (f1 , f2 ) de vecteurs de la sphère unité `2 , on note abusivement f : CN ×N → R, l’application

qui à une matrice M associe hf1 , M f2 i. Soit k = 0, . . . , N − 1,
2
1 uk
|f (Yk )| ≤ hf1 , uk ihf2 , uk i ≤ .
K K
On pose
2
uk
B := max .
0≤k≤N −1 K
On majore l’espérance de f 2 (Yk ),
2 2 2 2
f1 , uk ⊗ uk f2 f1 , uk ⊗ uk f2
 
2 K K
E f (Yk ) = P(δk = 1) 1 − + P(δk = 0)
N K2 N K2
2
f1 , uk f2 , uk
 
K K
= 1−
N N K2
  k 2
K K u 2
≤ 1− f2 , u k
N N K2
12 2 L’incohérence, levier de la reconstruction

On remarque d’abord que

N −1
X 2 2
uk , f 2 = N kf2 k = N ,
k=0

on a alors la majoration attendue,

N −1  
X K 1 2
E f 2 (Yk ) ≤ 1− max uk ≤B.
N K 0≤k≤N −1
k=0

On applique le théorème de Talagrand (théorème 2.4). En remarquant que Z = kY k = Z, on obtient pour

tout réel t strictement positif :
  
t t
P (| kY k − E kY k | > t) ≤ 3 exp − log 1 + , (9)
KB 1 + E kY k
1 ∗
avec Y = K UΩT UΩT − Id. Le théorème 2.2 démontre l’inégalité 7 :
√
1 ∗ S log S
E kY k = E U UΩT − Id ≤ CR √ µ(U ) .
K ΩT K
En prenant K suffisamment grand,
2 2
K ≥ 4 CR µ (U ) S log S ,
on a
E kY k ≤ 1/4 .
Il suffit alors de prendre t = 1/4 dans l’inégalité 9 et de remarquer que B ≤ µ2 (U ) S/K pour obtenir :
 
K
P (kY k > 1/2) ≤ 3 exp − ,
CT µ2 (U ) S

où CT = 4K/ log(6/5). La preuve se termine en posant C1 = 16CR et C2 = CT .

2.4 Preuve du théorème de Candès-Romberg

Tous les éléments sont en place pour achever la preuve du théorème.

Démonstration. — On se place dans le cadre des hypothèses du théorème, en particulier on se donne un

vecteur de Bernoulli Z représentant une S-facette. Soit π le vecteur dual associé au vecteur Z. On renvoie à
la section 1.3 pour la définition du vecteur dual. On rappelle que1
−1
π := UΩ∗ UΩT (UΩT
∗
UΩT ) Z.
∗ −1
Soit t0 un élément du complémentaire du sous-ensemble T , la matrice (UΩT UΩT ) étant N -hermitienne,
D E
∗ −1
π(t0 ) = v 0 , (UΩT UΩT ) Z = w0 , Z ,

∗ −1
où w0 := (UΩT UΩT ) v 0 et v 0 est le t0 -ième vecteur de ligne de UΩ∗ UΩT .

Lemme 2.6. — Le moment d’ordre 2 de Z0 := v 0 vérifie

E Z02 ≤ µ2 (U )KS . (10)

Démonstration. — On pose λ0k = U t0 ,k . On rappelle que v 0 est le t0 -ième vecteur de ligne de UΩ∗ UΩT , le calcul
du produit matriciel donne
N
X −1
v0 = δk λ0k uk .
k=0

1
On renvoie à l’équation 2 pour plus de détails.
 2.4 Preuve du théorème de Candès-Romberg 13

Soit t un indice appartenant à T . On désigne par uk (t) l’entrée d’indice t du vecteur ligne uk , soit encore le
coefficient Uk,t . On note ut le t-ème vecteur colonne de la matrice U . On a
N
X −1 N
X −1
λ0k uk (t) = U t0 ,k Uk,t = hut0 , ut i = 0 ,
k=0 k=0

par orthogonalité des vecteurs ut0 et ut . On a

N
X −1
v0 = (δk − E δk ) λ0k uk . (11)
k=0

On écrit v 0 comme la somme de variables aléatoires d’espérance nulle,

N
X −1
v0 = Yk ,
k=0

avec
Yk := (δk − E δk ) λ0k uk .
On rappelle que la variable aléatoire Yk est d’espérance nulle et on calcule le moment d’ordre 2 de Z0
X X
E Z02 = E hYk , Yk i + E hYk , Yk0 i ,
k k6=k0
X
= E hYk , Yk i .
k

On majore le moment d’ordre 2 de kYk k,

 
2 K K 2 2
E kYk k = 1− λ0k uk ,
N N
 
K K 2
≤ 1− λ0k µ2 (U )S
N N
On remarque que
N −1
X 2
λ0k =N,
k=0

ce qui permet de conclure la preuve du lemme.

Lemme 2.7. — Soit t0 un élément du complémentaire de T . On pose

 √ 
σ 2 := µ2 (U )K max 1, µ(U )S K .

Soit un réel a strictement positif tel que

(
1/4 √
a ≤ K/µ2 (U ) si µ(U ) S/ K > 1

1/2
a ≤ K/µ2 (U )S sinon

Alors,  √ 
P Z0 ≥ µ(U ) KS + aσ 2 ≤ exp −γa2 ,

où γ est une constante universelle strictement positive.

Démonstration. — Par définition,

N
X −1
Z0 := sup v 0 , f = sup hYk , f i ,
kf k=1 kf k=1 k=0

avec (voir la preuve précédente)

Yk := (δk − E δk ) λ0k uk .
14 2 L’incohérence, levier de la reconstruction

On prouve que l’on est bien dans le cadre des hypothèses du théorème 2.4. Soit f un vecteur unité fixé
appartenant à un sous ensemble dense fixé de la sphère unité de la norme `2 . On note f (Yk ) l’application
hYk , f i. La variable aléatoire Yk est d’espérance nulle, et donc, par linéarité,

E f (Yk ) = 0 .

On majore la valeur absolue de f (Yk ),

|f (Yk )| ≤ λ0k uk , f ≤ λ0k uk ≤ µ2 (U ) S 1/2 = B ,

où on a posé
B := µ2 (U ) S 1/2 .
On majore l’espérance de Z0 à l’aide du lemme 2.6 sur le moment d’ordre 2 de Z0 et de l’inégalité de Jensen,
q √
E Z0 ≤ E Z02 ≤ µ(U ) KS .

On majore ensuite σ 2 , on a
   
K K 2 2 K K 2
E f 2 (Yk ) = 1− λ0k uk , f ≤ 1− µ2 (U ) uk , f .
N N N N
2
uk , f
P
Comme 1≤k≤N = N , on a

N −1  
X K
E f 2 (Yk ) ≤ K 1 − µ2 (U ) .
N
k=0

On applique le théorème 2.4, pour tout réel t positif ou nul,

  
t Bt
P (|Z0 − E Z0 | > t) ≤ 3 exp − log 1 + √ .
KB µ2 (U )K + Bµ(U ) KS
√
On suppose que σ 2 = Bµ(U ) KS ≥ µ2 (U )K et on pose t = aσ, alors l’inégalité ci-dessus montre que

P (|Z0 − E Z0 | > t) ≤ 3 exp −γa2 ,

√
dès lors que Bt ≤ σ 2 . On montre le même résultat lorsque σ 2 = µ2 (U )K ≥ Bµ(U ) KS et Bt ≤ µ2 (U )K, ce
qui prouve le lemme.
∗ −1
Lemme 2.8. — On rappelle que w0 := (UΩT UΩT ) v 0 . Avec les même notations que précédemment,
 
p ∗
P sup w0 ≥ 2µ(U ) S/K + 2aσ 2 /K ≤ N exp −γa2 + P (kUΩT


UΩT k ≤ 1/2) . (12)
t0 ∈T c

∗
n √ o
Démonstration. — Soient A et B les événements {kUΩT UΩT k ≥ K/2} et supt0 ∈T c v 0 ≤ µ(U ) KS + aσ .


Le lemme 2.7 montre que P(B c ) ≤ exp −γa2 . Sur A ∩ B, on a
p
sup w0 ≤ 2µ(U ) S/K + 2aσ 2 /K .
t0 ∈T c

Ce qui démontre le lemme.

Lemme 2.9. — Soit λ un réel strictement positif,

     
1 0
P sup |π(t)| > 1 ≤ 2N exp − 2 + P sup w > λ . (13)
t∈T c 2λ t0 ∈T c

Démonstration. — On rappelle que Z est la S-facette associée à x. La preuve de ce lemme repose sur l’inégalité
de Hoeffding, on pourra avantageusement lire l’article [1]. On écrit :
N
X −1 N
X −1
w0 , Z = w0 (k)δ k = Xk ,
k=0 k=0
 2.4 Preuve du théorème de Candès-Romberg 15

où Xk = w0 (k)δ k . Les variables aléatoires δk sont indépendantes et les variables aléatoires Xk sont encadrées
par 0 et w0 (k), l’inégalité de Hoeffding donne alors :
 2

P w0 , Z > 1 w0 ≤ 2 exp −2/ w0


.

On rappelle que π(t0 ) = w0 , Z , on en déduit que

 
sup w0 ≤ λ ≤ 2N exp −2/λ2 ,


P sup |π(t)| > 1
t∈T c t0 ∈T c

ce qui conclut la preuve du lemme.

On pose p
λ = 2µ(U ) S/K + 2aσ/K .
A l’aide des lemmes 2.8 et 2.9, on sait que pour tout réel a strictement positif obéissant aux conditions
imposées par le lemme 2.7,
   
1 ∗
P sup |π(t)| > 1 ≤ 2N exp − 2 + N exp −γa2 + P (kUΩT


UΩT k ≤ 1/2) . (14)
t∈T c 2λ

Pour rendre le second terme plus petit que δ, on choisit le réel a tel que

a2 := γ −1 log(N/δ) .

Le premier terme est plus petit que δ si

1
≥ 2 log(2N/δ) . (15)
λ2
√
1/4
On suppose que µ(U )S ≥ K. L’hypothèse du lemme 2.7 est a ≤ K/µ2 (U ) , ou de manière équivalente

log(N/δ)2
K ≥ µ2 (U ) .
γ2
√
Dans ces conditions, aσ ≤ µ(U ) KS, ou encore

1 1 K
≥ . (16)
λ2 16 µ2 (U )S
√
On suppose que µ(U )S ≤ K. Si de plus S ≥ a2 , l’inéquation 16 reste vraie. D’autre part, si S ≤ a alors
λ ≤ 4aσ/K et
1 1 K
≥ .
λ2 16 a2 (U )S
On veut que l’inéquation 15 est vraie. De l’analyse précédente, on voit qu’il suffit que le nombre de mesures
K vérifie :    
K 1 1 2N
min , ≥ 2 log .
16µ2 (U ) S a2 K
Le second terme du second membre de l’inéquation 14 est plus petit que δ dès lors que

K ≥ K1 µ2 (U ) max (S, log(N/δ)) log(N/δ) ,

où K1 est une constante strictement positive. Le théorème 2.5 permet de majorer par δ le troisième et dernier
terme du second membre de l’inéquation 14 dès lors que

K ≥ K2 µ2 (U )S log(N/δ) ,

où K2 est une constante strictement positive. Ce qui prouve le théorème.

Références

1. O. Bousqet S. Boucheron and G. Lugosi. Advanced Lectures in Machine Learning, pages 208–240. Springer, 2004.
2. O. Bousqet S. Boucheron and G. Lugosi. Theory of classification : A survey of some recent advances. 23 Septembre
2005.
3. E.J Candès and J. Romberg. Sparsity and incoherence in compressive sampling. Novembre 2006.
4. E.J Candès, J. Romberg, and T. Tao. Robust uncertainty principles : Exact signal reconstruction from highly incomplete
frequency information. Juin 2004.
5. E.J Candès and T. Tao. Near optimal signal recovery from random projections : Universal encoding strategies ?
Octobre 2004.
6. David L. Donoho. Compressed sensing. Septembre 2004.
7. D.L Donoho and P.B Stark. Uncertainty principles and signal recovery. SIAM J. Applied Math, 49(3) :906–931, Juin
1989.
8. Yves Meyer. Ondelettes et opérateurs I, Ondelettes. Hermann, 1990.
9. Yves Meyer. Oscillating patterns in image processing and some nonlinear evolution equations. The fifteenth Dean
Jaqueline B. Lewis, Memorial Lectures., 2002.
10. Mark Rudelson. Random vectors in the isotropic position. Journal of Functional Analysis, 1999.
11. T. Tao. An uncertainty principle for cyclic groups of prime order. Mathematical Research Letters, (12) :121–127, 2005.