Compressive sensing - Théorie et Applicationsimagine.enpc.fr/~dalalyan/Download/CS.pdf ·...

Compressivesensing

A. Dalalyan

IntroductionGénéralités

Motivations

Compression

Problématique du CS

ThéorieParcimonie

Récupération sparse

Echantillonnage incohérent

ApprocheBayésienneGénéralités

Estimateur de Gibbs

Résultats

Conclusion

1

Compressive sensingThéorie et Applications

Arnak DALALYANIMAGINE, Ecole des Ponts ParisTech

Compressivesensing

A. Dalalyan

IntroductionGénéralités

Motivations

Compression

Problématique du CS

ThéorieParcimonie

Récupération sparse

Echantillonnage incohérent

ApprocheBayésienneGénéralités

Estimateur de Gibbs

Résultats

Conclusion

2

Lignes directrices

• Introduction au Compressive Sensing (CS),• motivations• compression• problématique du CS

• Les bases théoriques du CS• représentation parcimonieuse• reconstruction sparse• échantillonnage incohérent

• Approche Bayésienne• généralités• estimateur de Gibbs• résultats théoriques et empiriques

• Conclusion

Compressivesensing

A. Dalalyan

IntroductionGénéralités

Motivations

Compression

Problématique du CS

ThéorieParcimonie

Récupération sparse

Echantillonnage incohérent

ApprocheBayésienneGénéralités

Estimateur de Gibbs

Résultats

Conclusion

3

IntroductionGénéralités

• CS est une branche récente de math. appliquées :premiers travaux publiés en 2006,

• Les fondateurs sont :

Emmanuel TerenceCANDES TAO

• Terminologie :compressive

sensing =compressed

sensing =compressive

sampling• CS sur le WEB :http://www.dsp.ece.rice.edu/cs/

Compressivesensing

A. Dalalyan

IntroductionGénéralités

Motivations

Compression

Problématique du CS

ThéorieParcimonie

Récupération sparse

Echantillonnage incohérent

ApprocheBayésienneGénéralités

Estimateur de Gibbs

Résultats

Conclusion

4

IntroductionMotivations

• De nos jours, l’acquisition de données se fait de plusen plus souvent de façon numérique (appareil photo,caméra, CD, etc.).

• Cela nécessite un renouvellement continu destechniques d’acquisition, de stockage et de l’analysedes données, notamment pour pouvoir :

- obtenir une meilleure résolution pour lesphotos/videos,

- augmenter le nombre de modalités (acoustique,vision, rayons X ou gamma)

- accroître le nombre de capteurs.

• Déluge de données : comment faire face ?

Compressivesensing

A. Dalalyan

IntroductionGénéralités

Motivations

Compression

Problématique du CS

ThéorieParcimonie

Récupération sparse

Echantillonnage incohérent

ApprocheBayésienneGénéralités

Estimateur de Gibbs

Résultats

Conclusion

5

IntroductionImage numérique

• Image monochrome : une fonction [0,1]2 → [0,1].

• Image couleur : trois fonctions [0,1]2 → [0,1].• Image numérique : version discrétisée (600× 450 pixels)

et quantifiée (256 = 28 valeurs - 8 bits dans le casmonochrome et 24 bits pour la couleur)

• Occupation mémoire importante : 600× 450× 24 ≈ 223

bits = 1 Mo.

Compressivesensing

A. Dalalyan

IntroductionGénéralités

Motivations

Compression

Problématique du CS

ThéorieParcimonie

Récupération sparse

Echantillonnage incohérent

ApprocheBayésienneGénéralités

Estimateur de Gibbs

Résultats

Conclusion

5

IntroductionImage numérique

• Image monochrome : une fonction [0,1]2 → [0,1].• Image couleur : trois fonctions [0,1]2 → [0,1].

• Image numérique : version discrétisée (600× 450 pixels)et quantifiée (256 = 28 valeurs - 8 bits dans le casmonochrome et 24 bits pour la couleur)

• Occupation mémoire importante : 600× 450× 24 ≈ 223

bits = 1 Mo.

Compressivesensing

A. Dalalyan

IntroductionGénéralités

Motivations

Compression

Problématique du CS

ThéorieParcimonie

Récupération sparse

Echantillonnage incohérent

ApprocheBayésienneGénéralités

Estimateur de Gibbs

Résultats

Conclusion

5

IntroductionImage numérique

• Image monochrome : une fonction [0,1]2 → [0,1].• Image couleur : trois fonctions [0,1]2 → [0,1].• Image numérique : version discrétisée (600× 450 pixels)

et quantifiée (256 = 28 valeurs - 8 bits dans le casmonochrome et 24 bits pour la couleur)

• Occupation mémoire importante : 600× 450× 24 ≈ 223

bits = 1 Mo.

Compressivesensing

A. Dalalyan

IntroductionGénéralités

Motivations

Compression

Problématique du CS

ThéorieParcimonie

Récupération sparse

Echantillonnage incohérent

ApprocheBayésienneGénéralités

Estimateur de Gibbs

Résultats

Conclusion

5

IntroductionImage numérique

• Image monochrome : une fonction [0,1]2 → [0,1].• Image couleur : trois fonctions [0,1]2 → [0,1].• Image numérique : version discrétisée (600× 450 pixels)

et quantifiée (256 = 28 valeurs - 8 bits dans le casmonochrome et 24 bits pour la couleur)

• Occupation mémoire importante : 600× 450× 24 ≈ 223

bits = 1 Mo.

Compressivesensing

A. Dalalyan

IntroductionGénéralités

Motivations

Compression

Problématique du CS

ThéorieParcimonie

Récupération sparse

Echantillonnage incohérent

ApprocheBayésienneGénéralités

Estimateur de Gibbs

Résultats

Conclusion

6

Et pourtant, le fichier JPEG contenant cetteimage n’occupe que 83 Ko sur mon disque dur !

Compressivesensing

A. Dalalyan

IntroductionGénéralités

Motivations

Compression

Problématique du CS

ThéorieParcimonie

Récupération sparse

Echantillonnage incohérent

ApprocheBayésienneGénéralités

Estimateur de Gibbs

Résultats

Conclusion

7

IntroductionCompression : idées de base

• Compression simple : changement de résolution, dequantification ou autre./ Point faible : perte d’information importante.

• Codage entropique : compression sans perte./ Point faible : taux de compression limité (facteur 4 de

compression dans le meilleur des cas).

Pour améliorer le taux de compression, il faut perdrede l’information ... mais le faire de façon intelligente !• JPEG et JPEG2000 font de la compression avec

perte de manière intelligente.• Idée principale : projeter l’image sur une base de

fonctions [0,1]2 → [0,1] bien adaptée pourreprésenter les images.

Compressivesensing

A. Dalalyan

IntroductionGénéralités

Motivations

Compression

Problématique du CS

ThéorieParcimonie

Récupération sparse

Echantillonnage incohérent

ApprocheBayésienneGénéralités

Estimateur de Gibbs

Résultats

Conclusion

7

IntroductionCompression : idées de base

• Compression simple : changement de résolution, dequantification ou autre./ Point faible : perte d’information importante.

• Codage entropique : compression sans perte./ Point faible : taux de compression limité (facteur 4 de

compression dans le meilleur des cas).

Pour améliorer le taux de compression, il faut perdrede l’information ... mais le faire de façon intelligente !

• JPEG et JPEG2000 font de la compression avecperte de manière intelligente.

• Idée principale : projeter l’image sur une base defonctions [0,1]2 → [0,1] bien adaptée pourreprésenter les images.

Compressivesensing

A. Dalalyan

IntroductionGénéralités

Motivations

Compression

Problématique du CS

ThéorieParcimonie

Récupération sparse

Echantillonnage incohérent

ApprocheBayésienneGénéralités

Estimateur de Gibbs

Résultats

Conclusion

7

IntroductionCompression : idées de base

• Compression simple : changement de résolution, dequantification ou autre./ Point faible : perte d’information importante.

• Codage entropique : compression sans perte./ Point faible : taux de compression limité (facteur 4 de

compression dans le meilleur des cas).

Pour améliorer le taux de compression, il faut perdrede l’information ... mais le faire de façon intelligente !• JPEG et JPEG2000 font de la compression avec

perte de manière intelligente.• Idée principale : projeter l’image sur une base de

fonctions [0,1]2 → [0,1] bien adaptée pourreprésenter les images.

Compressivesensing

A. Dalalyan

IntroductionGénéralités

Motivations

Compression

Problématique du CS

ThéorieParcimonie

Récupération sparse

Echantillonnage incohérent

ApprocheBayésienneGénéralités

Estimateur de Gibbs

Résultats

Conclusion

8

IntroductionProblématique du CS

Constatation Pour stocker une image, on procède à sacompression et, en général, on n’utilise qu’unepartie des données.

Question Est-il possible d’intégrer la compression dans leprocédé d’acquisition des données? Cela nouséviterait d’acquérir des données “inutiles”.

Réponse C’est ce qui constitue la problématique ducompressive sensing (échantillonnagecomprimé).

Méthodologie Mesures incohérentes, projection aléatoire, ...

Compressivesensing

A. Dalalyan

IntroductionGénéralités

Motivations

Compression

Problématique du CS

ThéorieParcimonie

Récupération sparse

Echantillonnage incohérent

ApprocheBayésienneGénéralités

Estimateur de Gibbs

Résultats

Conclusion

8

IntroductionProblématique du CS

Constatation Pour stocker une image, on procède à sacompression et, en général, on n’utilise qu’unepartie des données.

Question Est-il possible d’intégrer la compression dans leprocédé d’acquisition des données? Cela nouséviterait d’acquérir des données “inutiles”.

Réponse C’est ce qui constitue la problématique ducompressive sensing (échantillonnagecomprimé).

Méthodologie Mesures incohérentes, projection aléatoire, ...

Compressivesensing

A. Dalalyan

IntroductionGénéralités

Motivations

Compression

Problématique du CS

ThéorieParcimonie

Récupération sparse

Echantillonnage incohérent

ApprocheBayésienneGénéralités

Estimateur de Gibbs

Résultats

Conclusion

8

IntroductionProblématique du CS

Constatation Pour stocker une image, on procède à sacompression et, en général, on n’utilise qu’unepartie des données.

Question Est-il possible d’intégrer la compression dans leprocédé d’acquisition des données? Cela nouséviterait d’acquérir des données “inutiles”.

Réponse C’est ce qui constitue la problématique ducompressive sensing (échantillonnagecomprimé).

Méthodologie Mesures incohérentes, projection aléatoire, ...

Compressivesensing

A. Dalalyan

IntroductionGénéralités

Motivations

Compression

Problématique du CS

ThéorieParcimonie

Récupération sparse

Echantillonnage incohérent

ApprocheBayésienneGénéralités

Estimateur de Gibbs

Résultats

Conclusion

8

IntroductionProblématique du CS

Constatation Pour stocker une image, on procède à sacompression et, en général, on n’utilise qu’unepartie des données.

Question Est-il possible d’intégrer la compression dans leprocédé d’acquisition des données? Cela nouséviterait d’acquérir des données “inutiles”.

Réponse C’est ce qui constitue la problématique ducompressive sensing (échantillonnagecomprimé).

Méthodologie Mesures incohérentes, projection aléatoire, ...

Fondements Théoriques

Compressivesensing

A. Dalalyan

IntroductionGénéralités

Motivations

Compression

Problématique du CS

ThéorieParcimonie

Récupération sparse

Echantillonnage incohérent

ApprocheBayésienneGénéralités

Estimateur de Gibbs

Résultats

Conclusion

10

Représentation sparse (parcimonieuse)

� Dans le formalisme mathématique, l’image est unefonction : f : [0,1]2 → [0,1].

� Soient ϕ1,ϕ2, . . . une suite de fonctions orthonormées deL2([0,1]2;R).

� Grâce à cette base, on associe à chaque image f unesuite infinie (c1(f ), c2(f ), . . .) de réels définis par

ci (f ) =

∫[0,1]2

f (x)ϕi (x) dx := 〈f ,ϕi〉.

� A partir de la suite (c1(f ), c2(f ), . . .) on peut reconstruirel’image par la formule

f (x) =∞∑i=1

ci (f )ϕi (x).

� L’application f 7→ (c1(f ), c2(f ), . . .) préserve la norme (estune isométrie) :

‖f‖2 =

∫[0,1]2

f 2(x) dx =∞∑i=1

ci (f )2.

Compressivesensing

A. Dalalyan

IntroductionGénéralités

Motivations

Compression

Problématique du CS

ThéorieParcimonie

Récupération sparse

Echantillonnage incohérent

ApprocheBayésienneGénéralités

Estimateur de Gibbs

Résultats

Conclusion

10

Représentation sparse (parcimonieuse)

� Dans le formalisme mathématique, l’image est unefonction : f : [0,1]2 → [0,1].

� Soient ϕ1,ϕ2, . . . une suite de fonctions orthonormées deL2([0,1]2;R).

� Grâce à cette base, on associe à chaque image f unesuite infinie (c1(f ), c2(f ), . . .) de réels définis par

ci (f ) =

∫[0,1]2

f (x)ϕi (x) dx := 〈f ,ϕi〉.

� A partir de la suite (c1(f ), c2(f ), . . .) on peut reconstruirel’image par la formule

f (x) =∞∑i=1

ci (f )ϕi (x).

� L’application f 7→ (c1(f ), c2(f ), . . .) préserve la norme (estune isométrie) :

‖f‖2 =

∫[0,1]2

f 2(x) dx =∞∑i=1

ci (f )2.

Compressivesensing

A. Dalalyan

IntroductionGénéralités

Motivations

Compression

Problématique du CS

ThéorieParcimonie

Récupération sparse

Echantillonnage incohérent

ApprocheBayésienneGénéralités

Estimateur de Gibbs

Résultats

Conclusion

10

Représentation sparse (parcimonieuse)

� Dans le formalisme mathématique, l’image est unefonction : f : [0,1]2 → [0,1].

� Soient ϕ1,ϕ2, . . . une suite de fonctions orthonormées deL2([0,1]2;R).

� Grâce à cette base, on associe à chaque image f unesuite infinie (c1(f ), c2(f ), . . .) de réels définis par

ci (f ) =

∫[0,1]2

f (x)ϕi (x) dx := 〈f ,ϕi〉.

� A partir de la suite (c1(f ), c2(f ), . . .) on peut reconstruirel’image par la formule

f (x) =∞∑i=1

ci (f )ϕi (x).

� L’application f 7→ (c1(f ), c2(f ), . . .) préserve la norme (estune isométrie) :

‖f‖2 =

∫[0,1]2

f 2(x) dx =∞∑i=1

ci (f )2.

Compressivesensing

A. Dalalyan

IntroductionGénéralités

Motivations

Compression

Problématique du CS

ThéorieParcimonie

Récupération sparse

Echantillonnage incohérent

ApprocheBayésienneGénéralités

Estimateur de Gibbs

Résultats

Conclusion

10

Représentation sparse (parcimonieuse)

� Dans le formalisme mathématique, l’image est unefonction : f : [0,1]2 → [0,1].

� Soient ϕ1,ϕ2, . . . une suite de fonctions orthonormées deL2([0,1]2;R).

� Grâce à cette base, on associe à chaque image f unesuite infinie (c1(f ), c2(f ), . . .) de réels définis par

ci (f ) =

∫[0,1]2

f (x)ϕi (x) dx := 〈f ,ϕi〉.

� A partir de la suite (c1(f ), c2(f ), . . .) on peut reconstruirel’image par la formule

f (x) =∞∑i=1

ci (f )ϕi (x).

� L’application f 7→ (c1(f ), c2(f ), . . .) préserve la norme (estune isométrie) :

‖f‖2 =

∫[0,1]2

f 2(x) dx =∞∑i=1

ci (f )2.

Compressivesensing

A. Dalalyan

IntroductionGénéralités

Motivations

Compression

Problématique du CS

ThéorieParcimonie

Récupération sparse

Echantillonnage incohérent

ApprocheBayésienneGénéralités

Estimateur de Gibbs

Résultats

Conclusion

11

Représentation sparse

� Les images faciles à comprimer sont celles dont lareprésentation dans la base {ϕi} contient peu decoefficients non-nuls. Ces images sont appelées“sparse”.

� Il est crucial de trouver des bases bien adaptéespour représenter les images

� Très utilisées :� Base de Fourier : JPEG,� Base d’ondelettes : JPEG2000,

� Plus récentes :� Base de curvelettes,� Base de bandelettes,

Compressivesensing

A. Dalalyan

IntroductionGénéralités

Motivations

Compression

Problématique du CS

ThéorieParcimonie

Récupération sparse

Echantillonnage incohérent

ApprocheBayésienneGénéralités

Estimateur de Gibbs

Résultats

Conclusion

11

Représentation sparse

� Les images faciles à comprimer sont celles dont lareprésentation dans la base {ϕi} contient peu decoefficients non-nuls. Ces images sont appelées“sparse”.

� Il est crucial de trouver des bases bien adaptéespour représenter les images

� Très utilisées :� Base de Fourier : JPEG,� Base d’ondelettes : JPEG2000,

� Plus récentes :� Base de curvelettes,� Base de bandelettes,

Compressivesensing

A. Dalalyan

IntroductionGénéralités

Motivations

Compression

Problématique du CS

ThéorieParcimonie

Récupération sparse

Echantillonnage incohérent

ApprocheBayésienneGénéralités

Estimateur de Gibbs

Résultats

Conclusion

11

Représentation sparse

� Les images faciles à comprimer sont celles dont lareprésentation dans la base {ϕi} contient peu decoefficients non-nuls. Ces images sont appelées“sparse”.

� Il est crucial de trouver des bases bien adaptéespour représenter les images

� Très utilisées :� Base de Fourier : JPEG,� Base d’ondelettes : JPEG2000,

� Plus récentes :� Base de curvelettes,� Base de bandelettes,

Compressivesensing

A. Dalalyan

IntroductionGénéralités

Motivations

Compression

Problématique du CS

ThéorieParcimonie

Récupération sparse

Echantillonnage incohérent

ApprocheBayésienneGénéralités

Estimateur de Gibbs

Résultats

Conclusion

11

Représentation sparse

� Les images faciles à comprimer sont celles dont lareprésentation dans la base {ϕi} contient peu decoefficients non-nuls. Ces images sont appelées“sparse”.

� Il est crucial de trouver des bases bien adaptéespour représenter les images

� Très utilisées :� Base de Fourier : JPEG,� Base d’ondelettes : JPEG2000,

� Plus récentes :� Base de curvelettes,� Base de bandelettes,

Compressivesensing

A. Dalalyan

IntroductionGénéralités

Motivations

Compression

Problématique du CS

ThéorieParcimonie

Récupération sparse

Echantillonnage incohérent

ApprocheBayésienneGénéralités

Estimateur de Gibbs

Résultats

Conclusion

12

Base de Fourier univariée

Compressivesensing

A. Dalalyan

IntroductionGénéralités

Motivations

Compression

Problématique du CS

ThéorieParcimonie

Récupération sparse

Echantillonnage incohérent

ApprocheBayésienneGénéralités

Estimateur de Gibbs

Résultats

Conclusion

13

Base de Fourier bivariée

Compressivesensing

A. Dalalyan

IntroductionGénéralités

Motivations

Compression

Problématique du CS

ThéorieParcimonie

Récupération sparse

Echantillonnage incohérent

ApprocheBayésienneGénéralités

Estimateur de Gibbs

Résultats

Conclusion

14

Base d’ondelettes univariée

Compressivesensing

A. Dalalyan

IntroductionGénéralités

Motivations

Compression

Problématique du CS

ThéorieParcimonie

Récupération sparse

Echantillonnage incohérent

ApprocheBayésienneGénéralités

Estimateur de Gibbs

Résultats

Conclusion

15

Base d’ondelettes bivariée

Compressivesensing

A. Dalalyan

IntroductionGénéralités

Motivations

Compression

Problématique du CS

ThéorieParcimonie

Récupération sparse

Echantillonnage incohérent

ApprocheBayésienneGénéralités

Estimateur de Gibbs

Résultats

Conclusion

16

Représentation sparseExemple

• L’image d’origine en megapixel (à gauche),

• Les coefficients dans la base d’ondelettes (au milieu)

� Le pourcentage de coefficients significativementnon-nuls est faible !

• La reconstruction obtenue en gardant seuls les 25.000coefficients les plus grands (en valeur absolue).

� A l’oeil nu, on ne voit pas de différence.� 96.000 mesures suffisent pour reconstruire

parfaitement ces 25.000 coefficients.

Compressivesensing

A. Dalalyan

IntroductionGénéralités

Motivations

Compression

Problématique du CS

ThéorieParcimonie

Récupération sparse

Echantillonnage incohérent

ApprocheBayésienneGénéralités

Estimateur de Gibbs

Résultats

Conclusion

18

Récupération sparse

Constatation En pratique, il s’avère très utile de s’affranchirde l’hypothèse stipulant que les ϕi sontorthogonaux. On considère alors des famillesredondantes.

Problème Déterminer les coefficients de la représentationsparse, sachant qu’il n’y a pas d’unicité dereprésentation. Cela constitue l’objectif d’unethéorie nommée “Sparse recovery”.

Méthode L1 Au lieu de définir {ci (f )} comme le point deminimum du critère des moindres carrés

C({ci}) =

∫[0,1]2

(f (x)−

∑i

ciϕi (x))2

dx

on les définit comme la solution du problèmed’optimisation:

min{∑

i |ci | :∑

i ciϕi (x) ≡ f (x)}.

Compressivesensing

A. Dalalyan

IntroductionGénéralités

Motivations

Compression

Problématique du CS

ThéorieParcimonie

Récupération sparse

Echantillonnage incohérent

ApprocheBayésienneGénéralités

Estimateur de Gibbs

Résultats

Conclusion

18

Récupération sparse

Constatation En pratique, il s’avère très utile de s’affranchirde l’hypothèse stipulant que les ϕi sontorthogonaux. On considère alors des famillesredondantes.

Problème Déterminer les coefficients de la représentationsparse, sachant qu’il n’y a pas d’unicité dereprésentation. Cela constitue l’objectif d’unethéorie nommée “Sparse recovery”.

Méthode L1 Au lieu de définir {ci (f )} comme le point deminimum du critère des moindres carrés

C({ci}) =

∫[0,1]2

(f (x)−

∑i

ciϕi (x))2

dx

on les définit comme la solution du problèmed’optimisation:

min{∑

i |ci | :∑

i ciϕi (x) ≡ f (x)}.

Compressivesensing

A. Dalalyan

IntroductionGénéralités

Motivations

Compression

Problématique du CS

ThéorieParcimonie

Récupération sparse

Echantillonnage incohérent

ApprocheBayésienneGénéralités

Estimateur de Gibbs

Résultats

Conclusion

18

Récupération sparse

Constatation En pratique, il s’avère très utile de s’affranchirde l’hypothèse stipulant que les ϕi sontorthogonaux. On considère alors des famillesredondantes.

Problème Déterminer les coefficients de la représentationsparse, sachant qu’il n’y a pas d’unicité dereprésentation. Cela constitue l’objectif d’unethéorie nommée “Sparse recovery”.

Méthode L1 Au lieu de définir {ci (f )} comme le point deminimum du critère des moindres carrés

C({ci}) =

∫[0,1]2

(f (x)−

∑i

ciϕi (x))2

dx

on les définit comme la solution du problèmed’optimisation:

min{∑

i |ci | :∑

i ciϕi (x) ≡ f (x)}.

Compressivesensing

A. Dalalyan

IntroductionGénéralités

Motivations

Compression

Problématique du CS

ThéorieParcimonie

Récupération sparse

Echantillonnage incohérent

ApprocheBayésienneGénéralités

Estimateur de Gibbs

Résultats

Conclusion

18

Récupération sparse

Constatation En pratique, il s’avère très utile de s’affranchirde l’hypothèse stipulant que les ϕi sontorthogonaux. On considère alors des famillesredondantes.

Problème Déterminer les coefficients de la représentationsparse, sachant qu’il n’y a pas d’unicité dereprésentation. Cela constitue l’objectif d’unethéorie nommée “Sparse recovery”.

Méthode L1 Au lieu de définir {ci (f )} comme le point deminimum du critère des moindres carrés

C({ci}) =

∫[0,1]2

(f (x)−

∑i

ciϕi (x))2

dx

on les définit comme la solution du problèmed’optimisation:min

{∑i |ci | : maxx

∣∣∑i ciϕi (x)− f (x)

∣∣ ≤ ε}.

Compressivesensing

A. Dalalyan

IntroductionGénéralités

Motivations

Compression

Problématique du CS

ThéorieParcimonie

Récupération sparse

Echantillonnage incohérent

ApprocheBayésienneGénéralités

Estimateur de Gibbs

Résultats

Conclusion

19

Echantillonnage incohérent

• La procédure d’acquisition nous fournit une fonction f .

• Au lieu de sauvegarder f directement, on sauvegarde lescoefficients {ci (f )} de sa représentation sparse.

• On n’a pas forcément besoin de connaître la fonction fentièrement pour pouvoir estimer les valeurs ci (f ).

• Supposons qu’on dispose d’un appareil qui nous permetde calculer, pour toute fonction ψ donnée, l’intégrale∫[0,1]2 f (x)ψ(x) dx .

• Comment choisir les fonctions {ψj}j=1,...,M pour pouvoirbien reconstruire les valeurs ci (f ) à partir des mesuresmj (f ) =

∫[0,1]2 f (x)ψj (x) dx , avec un M relativement petit ?

• La théorie du CS dit :Il faut que les ψj soient incohérents avec les ϕi !

Compressivesensing

A. Dalalyan

IntroductionGénéralités

Motivations

Compression

Problématique du CS

ThéorieParcimonie

Récupération sparse

Echantillonnage incohérent

ApprocheBayésienneGénéralités

Estimateur de Gibbs

Résultats

Conclusion

19

Echantillonnage incohérent

• La procédure d’acquisition nous fournit une fonction f .

• Au lieu de sauvegarder f directement, on sauvegarde lescoefficients {ci (f )} de sa représentation sparse.

• On n’a pas forcément besoin de connaître la fonction fentièrement pour pouvoir estimer les valeurs ci (f ).

• Supposons qu’on dispose d’un appareil qui nous permetde calculer, pour toute fonction ψ donnée, l’intégrale∫[0,1]2 f (x)ψ(x) dx .

• Comment choisir les fonctions {ψj}j=1,...,M pour pouvoirbien reconstruire les valeurs ci (f ) à partir des mesuresmj (f ) =

∫[0,1]2 f (x)ψj (x) dx , avec un M relativement petit ?

• La théorie du CS dit :Il faut que les ψj soient incohérents avec les ϕi !

Compressivesensing

A. Dalalyan

IntroductionGénéralités

Motivations

Compression

Problématique du CS

ThéorieParcimonie

Récupération sparse

Echantillonnage incohérent

ApprocheBayésienneGénéralités

Estimateur de Gibbs

Résultats

Conclusion

19

Echantillonnage incohérent

• La procédure d’acquisition nous fournit une fonction f .

• Au lieu de sauvegarder f directement, on sauvegarde lescoefficients {ci (f )} de sa représentation sparse.

• On n’a pas forcément besoin de connaître la fonction fentièrement pour pouvoir estimer les valeurs ci (f ).

• Supposons qu’on dispose d’un appareil qui nous permetde calculer, pour toute fonction ψ donnée, l’intégrale∫[0,1]2 f (x)ψ(x) dx .

• Comment choisir les fonctions {ψj}j=1,...,M pour pouvoirbien reconstruire les valeurs ci (f ) à partir des mesuresmj (f ) =

∫[0,1]2 f (x)ψj (x) dx , avec un M relativement petit ?

• La théorie du CS dit :Il faut que les ψj soient incohérents avec les ϕi !

Compressivesensing

A. Dalalyan

IntroductionGénéralités

Motivations

Compression

Problématique du CS

ThéorieParcimonie

Récupération sparse

Echantillonnage incohérent

ApprocheBayésienneGénéralités

Estimateur de Gibbs

Résultats

Conclusion

19

Echantillonnage incohérent

• La procédure d’acquisition nous fournit une fonction f .

• Au lieu de sauvegarder f directement, on sauvegarde lescoefficients {ci (f )} de sa représentation sparse.

• On n’a pas forcément besoin de connaître la fonction fentièrement pour pouvoir estimer les valeurs ci (f ).

• Supposons qu’on dispose d’un appareil qui nous permetde calculer, pour toute fonction ψ donnée, l’intégrale∫[0,1]2 f (x)ψ(x) dx .

• Comment choisir les fonctions {ψj}j=1,...,M pour pouvoirbien reconstruire les valeurs ci (f ) à partir des mesuresmj (f ) =

∫[0,1]2 f (x)ψj (x) dx , avec un M relativement petit ?

• La théorie du CS dit :Il faut que les ψj soient incohérents avec les ϕi !

Compressivesensing

A. Dalalyan

IntroductionGénéralités

Motivations

Compression

Problématique du CS

ThéorieParcimonie

Récupération sparse

Echantillonnage incohérent

ApprocheBayésienneGénéralités

Estimateur de Gibbs

Résultats

Conclusion

19

Echantillonnage incohérent

• La procédure d’acquisition nous fournit une fonction f .

• Au lieu de sauvegarder f directement, on sauvegarde lescoefficients {ci (f )} de sa représentation sparse.

• On n’a pas forcément besoin de connaître la fonction fentièrement pour pouvoir estimer les valeurs ci (f ).

• Supposons qu’on dispose d’un appareil qui nous permetde calculer, pour toute fonction ψ donnée, l’intégrale∫[0,1]2 f (x)ψ(x) dx .

• Comment choisir les fonctions {ψj}j=1,...,M pour pouvoirbien reconstruire les valeurs ci (f ) à partir des mesuresmj (f ) =

∫[0,1]2 f (x)ψj (x) dx , avec un M relativement petit ?

• La théorie du CS dit :Il faut que les ψj soient incohérents avec les ϕi !

Compressivesensing

A. Dalalyan

IntroductionGénéralités

Motivations

Compression

Problématique du CS

ThéorieParcimonie

Récupération sparse

Echantillonnage incohérent

ApprocheBayésienneGénéralités

Estimateur de Gibbs

Résultats

Conclusion

20

Nécessité de l’incohérenceExemple

• Supposons que

� les {ϕi : i ∈ J1,nK} sont orthogonaux� toutes les images qu’on cherche à acquérir sont

k -sparse dans la base {ϕi}, où k � n.

• Mauvais choix : {ϕi} = {ψj}. Vu qu’on ne connaît pas lesindices des coefficients non-nuls, il faut acquérir tous lescoefficients pour être sûr de ne pas avoir perdud’information.

• Bon choix : {ψj} tel que la corrélation entre ψj et ϕi estpetite quels que soient i et j .

• Candès et Romberg : Si l’on choisit uniformément auhasard M mesures dans l’ensemble {mj (f )}, on peutreconstruire les ci (f ) avec une probabilité très prochede 1 lorsque M ≥ Ck log n.

Compressivesensing

A. Dalalyan

IntroductionGénéralités

Motivations

Compression

Problématique du CS

ThéorieParcimonie

Récupération sparse

Echantillonnage incohérent

ApprocheBayésienneGénéralités

Estimateur de Gibbs

Résultats

Conclusion

20

Nécessité de l’incohérenceExemple

• Supposons que

� les {ϕi : i ∈ J1,nK} sont orthogonaux� toutes les images qu’on cherche à acquérir sont

k -sparse dans la base {ϕi}, où k � n.

• Mauvais choix : {ϕi} = {ψj}. Vu qu’on ne connaît pas lesindices des coefficients non-nuls, il faut acquérir tous lescoefficients pour être sûr de ne pas avoir perdud’information.

• Bon choix : {ψj} tel que la corrélation entre ψj et ϕi estpetite quels que soient i et j .

• Candès et Romberg : Si l’on choisit uniformément auhasard M mesures dans l’ensemble {mj (f )}, on peutreconstruire les ci (f ) avec une probabilité très prochede 1 lorsque M ≥ Ck log n.

Compressivesensing

A. Dalalyan

IntroductionGénéralités

Motivations

Compression

Problématique du CS

ThéorieParcimonie

Récupération sparse

Echantillonnage incohérent

ApprocheBayésienneGénéralités

Estimateur de Gibbs

Résultats

Conclusion

20

Nécessité de l’incohérenceExemple

• Supposons que

� les {ϕi : i ∈ J1,nK} sont orthogonaux� toutes les images qu’on cherche à acquérir sont

k -sparse dans la base {ϕi}, où k � n.

• Mauvais choix : {ϕi} = {ψj}. Vu qu’on ne connaît pas lesindices des coefficients non-nuls, il faut acquérir tous lescoefficients pour être sûr de ne pas avoir perdud’information.

• Bon choix : {ψj} tel que la corrélation entre ψj et ϕi estpetite quels que soient i et j .

• Candès et Romberg : Si l’on choisit uniformément auhasard M mesures dans l’ensemble {mj (f )}, on peutreconstruire les ci (f ) avec une probabilité très prochede 1 lorsque M ≥ Ck log n.

Compressivesensing

A. Dalalyan

IntroductionGénéralités

Motivations

Compression

Problématique du CS

ThéorieParcimonie

Récupération sparse

Echantillonnage incohérent

ApprocheBayésienneGénéralités

Estimateur de Gibbs

Résultats

Conclusion

20

Nécessité de l’incohérenceExemple

• Supposons que

� les {ϕi : i ∈ J1,nK} sont orthogonaux� toutes les images qu’on cherche à acquérir sont

k -sparse dans la base {ϕi}, où k � n.

• Mauvais choix : {ϕi} = {ψj}. Vu qu’on ne connaît pas lesindices des coefficients non-nuls, il faut acquérir tous lescoefficients pour être sûr de ne pas avoir perdud’information.

• Bon choix : {ψj} tel que la corrélation entre ψj et ϕi estpetite quels que soient i et j .

• Candès et Romberg : Si l’on choisit uniformément auhasard M mesures dans l’ensemble {mj (f )}, on peutreconstruire les ci (f ) avec une probabilité très prochede 1 lorsque M ≥ Ck log n.

Compressivesensing

A. Dalalyan

IntroductionGénéralités

Motivations

Compression

Problématique du CS

ThéorieParcimonie

Récupération sparse

Echantillonnage incohérent

ApprocheBayésienneGénéralités

Estimateur de Gibbs

Résultats

Conclusion

21

Efficacité de l’échantillonnage incohérent

• A gauche, la reconstruction de l’image en utilisant 21.000coefficients de Fourier.

• A droite, la reconstruction de l’image en utilisant 1.000coefficients de Fourier et 20.000 mesures incohérentes(noiselets).

Compressivesensing

A. Dalalyan

IntroductionGénéralités

Motivations

Compression

Problématique du CS

ThéorieParcimonie

Récupération sparse

Echantillonnage incohérent

ApprocheBayésienneGénéralités

Estimateur de Gibbs

Résultats

Conclusion

21

Efficacité de l’échantillonnage incohérent

• A gauche, la reconstruction de l’image en utilisant 21.000coefficients de Fourier.

• A droite, la reconstruction de l’image en utilisant 1.000coefficients de Fourier et 20.000 mesures incohérentes(noiselets).

Compressivesensing

A. Dalalyan

IntroductionGénéralités

Motivations

Compression

Problématique du CS

ThéorieParcimonie

Récupération sparse

Echantillonnage incohérent

ApprocheBayésienneGénéralités

Estimateur de Gibbs

Résultats

Conclusion

21

Efficacité de l’échantillonnage incohérent

• A gauche, la reconstruction de l’image en utilisant 21.000coefficients de Fourier.

• A droite, la reconstruction de l’image en utilisant 1.000coefficients de Fourier et 20.000 mesures incohérentes(noiselets).

Compressivesensing

A. Dalalyan

IntroductionGénéralités

Motivations

Compression

Problématique du CS

ThéorieParcimonie

Récupération sparse

Echantillonnage incohérent

ApprocheBayésienneGénéralités

Estimateur de Gibbs

Résultats

Conclusion

22

Efficacité de l’échantillonnage incohérent

La qualité de reconstruction est mesurée par le PSNR (peaksignal-to-noise ration).

• coefficients de Fourier et estimation linéaire,

• échantillonnage incohérent et estimation sparse,

• coefficient de Fourier et estimation sparse.

Compressivesensing

A. Dalalyan

IntroductionGénéralités

Motivations

Compression

Problématique du CS

ThéorieParcimonie

Récupération sparse

Echantillonnage incohérent

ApprocheBayésienneGénéralités

Estimateur de Gibbs

Résultats

Conclusion

23

Extensions

• Robustesse : l’image n’admet pas nécessairementune représentation sparse, mais on sait qu’il y a unecombinaison sparse qui approche bien l’image.

• Bruit : on n’observe pas l’image parfaite, mais uneversion de l’image corrompue par un bruit aléatoire.

• Problème inverse : au lieu d’observer directementl’image (éventuellement bruitée), on observe unetransformation de l’image.

Compressivesensing

A. Dalalyan

IntroductionGénéralités

Motivations

Compression

Problématique du CS

ThéorieParcimonie

Récupération sparse

Echantillonnage incohérent

ApprocheBayésienneGénéralités

Estimateur de Gibbs

Résultats

Conclusion

23

Extensions

• Robustesse : l’image n’admet pas nécessairementune représentation sparse, mais on sait qu’il y a unecombinaison sparse qui approche bien l’image.

• Bruit : on n’observe pas l’image parfaite, mais uneversion de l’image corrompue par un bruit aléatoire.

• Problème inverse : au lieu d’observer directementl’image (éventuellement bruitée), on observe unetransformation de l’image.

Compressivesensing

A. Dalalyan

IntroductionGénéralités

Motivations

Compression

Problématique du CS

ThéorieParcimonie

Récupération sparse

Echantillonnage incohérent

ApprocheBayésienneGénéralités

Estimateur de Gibbs

Résultats

Conclusion

23

Extensions

• Robustesse : l’image n’admet pas nécessairementune représentation sparse, mais on sait qu’il y a unecombinaison sparse qui approche bien l’image.

• Bruit : on n’observe pas l’image parfaite, mais uneversion de l’image corrompue par un bruit aléatoire.

• Problème inverse : au lieu d’observer directementl’image (éventuellement bruitée), on observe unetransformation de l’image.

Compressivesensing

A. Dalalyan

IntroductionGénéralités

Motivations

Compression

Problématique du CS

ThéorieParcimonie

Récupération sparse

Echantillonnage incohérent

ApprocheBayésienneGénéralités

Estimateur de Gibbs

Résultats

Conclusion

24

Récapitulatif

• Pour accomplir la tâche de compression de manièreefficace, il faut� exhiber une famille Φ = {ϕi} capable d’expliquer

l’image de façon simple (théorie de l’approximation,analyse harmonique...).

� trouver une procédure générique qui, pour chaqueimage donnée, estime les coefficients de sareprésentation sparse dans Φ (théorie del’informaion, statistique...).

• Pour optimiser la tâche d’acquisition des données, ilfaut désigner une famille Ψ = {ψj} qui serait utiliséepour prendre des mesures de façon systématique oualéatoire (analyse harmonique, optimisation,matrices aléatoires...).

Compressivesensing

A. Dalalyan

IntroductionGénéralités

Motivations

Compression

Problématique du CS

ThéorieParcimonie

Récupération sparse

Echantillonnage incohérent

ApprocheBayésienneGénéralités

Estimateur de Gibbs

Résultats

Conclusion

24

Récapitulatif

• Pour accomplir la tâche de compression de manièreefficace, il faut

� exhiber une famille Φ = {ϕi} capable d’expliquerl’image de façon simple (théorie de l’approximation,analyse harmonique...).

� trouver une procédure générique qui, pour chaqueimage donnée, estime les coefficients de sareprésentation sparse dans Φ (théorie del’informaion, statistique...).

• Pour optimiser la tâche d’acquisition des données, ilfaut désigner une famille Ψ = {ψj} qui serait utiliséepour prendre des mesures de façon systématique oualéatoire (analyse harmonique, optimisation,matrices aléatoires...).

Compressivesensing

A. Dalalyan

IntroductionGénéralités

Motivations

Compression

Problématique du CS

ThéorieParcimonie

Récupération sparse

Echantillonnage incohérent

ApprocheBayésienneGénéralités

Estimateur de Gibbs

Résultats

Conclusion

24

Récapitulatif

• Pour accomplir la tâche de compression de manièreefficace, il faut� exhiber une famille Φ = {ϕi} capable d’expliquer

l’image de façon simple (théorie de l’approximation,analyse harmonique...).

� trouver une procédure générique qui, pour chaqueimage donnée, estime les coefficients de sareprésentation sparse dans Φ (théorie del’informaion, statistique...).

• Pour optimiser la tâche d’acquisition des données, ilfaut désigner une famille Ψ = {ψj} qui serait utiliséepour prendre des mesures de façon systématique oualéatoire (analyse harmonique, optimisation,matrices aléatoires...).

Compressivesensing

A. Dalalyan

IntroductionGénéralités

Motivations

Compression

Problématique du CS

ThéorieParcimonie

Récupération sparse

Echantillonnage incohérent

ApprocheBayésienneGénéralités

Estimateur de Gibbs

Résultats

Conclusion

24

Récapitulatif

• Pour accomplir la tâche de compression de manièreefficace, il faut� exhiber une famille Φ = {ϕi} capable d’expliquer

l’image de façon simple (théorie de l’approximation,analyse harmonique...).

� trouver une procédure générique qui, pour chaqueimage donnée, estime les coefficients de sareprésentation sparse dans Φ (théorie del’informaion, statistique...).

• Pour optimiser la tâche d’acquisition des données, ilfaut désigner une famille Ψ = {ψj} qui serait utiliséepour prendre des mesures de façon systématique oualéatoire (analyse harmonique, optimisation,matrices aléatoires...).

Compressivesensing

A. Dalalyan

IntroductionGénéralités

Motivations

Compression

Problématique du CS

ThéorieParcimonie

Récupération sparse

Echantillonnage incohérent

ApprocheBayésienneGénéralités

Estimateur de Gibbs

Résultats

Conclusion

24

Récapitulatif

• Pour accomplir la tâche de compression de manièreefficace, il faut� exhiber une famille Φ = {ϕi} capable d’expliquer

l’image de façon simple (théorie de l’approximation,analyse harmonique...).

� trouver une procédure générique qui, pour chaqueimage donnée, estime les coefficients de sareprésentation sparse dans Φ (théorie del’informaion, statistique...).

• Pour optimiser la tâche d’acquisition des données, ilfaut désigner une famille Ψ = {ψj} qui serait utiliséepour prendre des mesures de façon systématique oualéatoire (analyse harmonique, optimisation,matrices aléatoires...).

Approche Bayésienne

Compressivesensing

A. Dalalyan

IntroductionGénéralités

Motivations

Compression

Problématique du CS

ThéorieParcimonie

Récupération sparse

Echantillonnage incohérent

ApprocheBayésienneGénéralités

Estimateur de Gibbs

Résultats

Conclusion

26

Généralités

• Dans l’approche Bayésienne, on suppose que l’objetqu’on cherche à identifier a été généré par un phénomènealéatoire.

• La loi de probabilité de ce phénomène aléatoire nous estinconnue !

• Nous choisissons une loi de probabilité (appelée loi apriori) qui, selon nous, aurait pu avoir généré l’image enquestion.

• Sur la base des observations qu’on dispose, on révise laloi a priori. Cela nous conduit vers la loi a posteriori.

• Important :

• l’effet de la loi a priori s’estompe à mesure que lesobservations sont prises en compte,

• la mesure a posteriori a tendance à se concentrerautour de l’objet à identifier.

Compressivesensing

A. Dalalyan

IntroductionGénéralités

Motivations

Compression

Problématique du CS

ThéorieParcimonie

Récupération sparse

Echantillonnage incohérent

ApprocheBayésienneGénéralités

Estimateur de Gibbs

Résultats

Conclusion

26

Généralités

• Dans l’approche Bayésienne, on suppose que l’objetqu’on cherche à identifier a été généré par un phénomènealéatoire.

• La loi de probabilité de ce phénomène aléatoire nous estinconnue !

• Nous choisissons une loi de probabilité (appelée loi apriori) qui, selon nous, aurait pu avoir généré l’image enquestion.

• Sur la base des observations qu’on dispose, on révise laloi a priori. Cela nous conduit vers la loi a posteriori.

• Important :

• l’effet de la loi a priori s’estompe à mesure que lesobservations sont prises en compte,

• la mesure a posteriori a tendance à se concentrerautour de l’objet à identifier.

Compressivesensing

A. Dalalyan

IntroductionGénéralités

Motivations

Compression

Problématique du CS

ThéorieParcimonie

Récupération sparse

Echantillonnage incohérent

ApprocheBayésienneGénéralités

Estimateur de Gibbs

Résultats

Conclusion

26

Généralités

• Dans l’approche Bayésienne, on suppose que l’objetqu’on cherche à identifier a été généré par un phénomènealéatoire.

• La loi de probabilité de ce phénomène aléatoire nous estinconnue !

• Nous choisissons une loi de probabilité (appelée loi apriori) qui, selon nous, aurait pu avoir généré l’image enquestion.

• Sur la base des observations qu’on dispose, on révise laloi a priori. Cela nous conduit vers la loi a posteriori.

• Important :

• l’effet de la loi a priori s’estompe à mesure que lesobservations sont prises en compte,

• la mesure a posteriori a tendance à se concentrerautour de l’objet à identifier.

Compressivesensing

A. Dalalyan

IntroductionGénéralités

Motivations

Compression

Problématique du CS

ThéorieParcimonie

Récupération sparse

Echantillonnage incohérent

ApprocheBayésienneGénéralités

Estimateur de Gibbs

Résultats

Conclusion

26

Généralités

• Dans l’approche Bayésienne, on suppose que l’objetqu’on cherche à identifier a été généré par un phénomènealéatoire.

• La loi de probabilité de ce phénomène aléatoire nous estinconnue !

• Nous choisissons une loi de probabilité (appelée loi apriori) qui, selon nous, aurait pu avoir généré l’image enquestion.

• Sur la base des observations qu’on dispose, on révise laloi a priori. Cela nous conduit vers la loi a posteriori.

• Important :

• l’effet de la loi a priori s’estompe à mesure que lesobservations sont prises en compte,

• la mesure a posteriori a tendance à se concentrerautour de l’objet à identifier.

Compressivesensing

A. Dalalyan

IntroductionGénéralités

Motivations

Compression

Problématique du CS

ThéorieParcimonie

Récupération sparse

Echantillonnage incohérent

ApprocheBayésienneGénéralités

Estimateur de Gibbs

Résultats

Conclusion

26

Généralités

• Dans l’approche Bayésienne, on suppose que l’objetqu’on cherche à identifier a été généré par un phénomènealéatoire.

• La loi de probabilité de ce phénomène aléatoire nous estinconnue !

• Nous choisissons une loi de probabilité (appelée loi apriori) qui, selon nous, aurait pu avoir généré l’image enquestion.

• Sur la base des observations qu’on dispose, on révise laloi a priori. Cela nous conduit vers la loi a posteriori.

• Important :

• l’effet de la loi a priori s’estompe à mesure que lesobservations sont prises en compte,

• la mesure a posteriori a tendance à se concentrerautour de l’objet à identifier.

Compressivesensing

A. Dalalyan

IntroductionGénéralités

Motivations

Compression

Problématique du CS

ThéorieParcimonie

Récupération sparse

Echantillonnage incohérent

ApprocheBayésienneGénéralités

Estimateur de Gibbs

Résultats

Conclusion

27

Estimateur de Gibbs

• On cherche à identifier une image f : [0,1]2 → [0,1].

• On a un appareil qui, pour tout x ∈ [0,1]2, nous fournit lavaleur bruitée y(x) de f (x).

• On suppose que le générateur de l’image forme l’imagefinale comme la superposition pondérée des imagesd’une base de données Φ avec des poids choisis auhasard.

f (x) =M∑

i=1ciϕi (x).

• Un espion nous a communiqué la base de données Φ.

• Il nous a également dit que le générateur n’est pas trèsintelligent : il forme f à partir d’un faible nombre d’imagestirées dans Φ.

Compressivesensing

A. Dalalyan

IntroductionGénéralités

Motivations

Compression

Problématique du CS

ThéorieParcimonie

Récupération sparse

Echantillonnage incohérent

ApprocheBayésienneGénéralités

Estimateur de Gibbs

Résultats

Conclusion

27

Estimateur de Gibbs

• On cherche à identifier une image f : [0,1]2 → [0,1].

• On a un appareil qui, pour tout x ∈ [0,1]2, nous fournit lavaleur bruitée y(x) de f (x).

• On suppose que le générateur de l’image forme l’imagefinale comme la superposition pondérée des imagesd’une base de données Φ avec des poids choisis auhasard.

f (x) =M∑

i=1ciϕi (x).

• Un espion nous a communiqué la base de données Φ.

• Il nous a également dit que le générateur n’est pas trèsintelligent : il forme f à partir d’un faible nombre d’imagestirées dans Φ.

Compressivesensing

A. Dalalyan

IntroductionGénéralités

Motivations

Compression

Problématique du CS

ThéorieParcimonie

Récupération sparse

Echantillonnage incohérent

ApprocheBayésienneGénéralités

Estimateur de Gibbs

Résultats

Conclusion

27

Estimateur de Gibbs

• On cherche à identifier une image f : [0,1]2 → [0,1].

• On a un appareil qui, pour tout x ∈ [0,1]2, nous fournit lavaleur bruitée y(x) de f (x).

• On suppose que le générateur de l’image forme l’imagefinale comme la superposition pondérée des imagesd’une base de données Φ avec des poids choisis auhasard.

f (x) =M∑

i=1ciϕi (x).

• Un espion nous a communiqué la base de données Φ.

• Il nous a également dit que le générateur n’est pas trèsintelligent : il forme f à partir d’un faible nombre d’imagestirées dans Φ.

Compressivesensing

A. Dalalyan

IntroductionGénéralités

Motivations

Compression

Problématique du CS

ThéorieParcimonie

Récupération sparse

Echantillonnage incohérent

ApprocheBayésienneGénéralités

Estimateur de Gibbs

Résultats

Conclusion

27

Estimateur de Gibbs

• On cherche à identifier une image f : [0,1]2 → [0,1].

• On a un appareil qui, pour tout x ∈ [0,1]2, nous fournit lavaleur bruitée y(x) de f (x).

• On suppose que le générateur de l’image forme l’imagefinale comme la superposition pondérée des imagesd’une base de données Φ avec des poids choisis auhasard.

f (x) =M∑

i=1ciϕi (x).

• Un espion nous a communiqué la base de données Φ.

• Il nous a également dit que le générateur n’est pas trèsintelligent : il forme f à partir d’un faible nombre d’imagestirées dans Φ.

Compressivesensing

A. Dalalyan

IntroductionGénéralités

Motivations

Compression

Problématique du CS

ThéorieParcimonie

Récupération sparse

Echantillonnage incohérent

ApprocheBayésienneGénéralités

Estimateur de Gibbs

Résultats

Conclusion

27

Estimateur de Gibbs

• On cherche à identifier une image f : [0,1]2 → [0,1].

• On a un appareil qui, pour tout x ∈ [0,1]2, nous fournit lavaleur bruitée y(x) de f (x).

• On suppose que le générateur de l’image forme l’imagefinale comme la superposition pondérée des imagesd’une base de données Φ avec des poids choisis auhasard.

f (x) =M∑

i=1ciϕi (x).

• Un espion nous a communiqué la base de données Φ.

• Il nous a également dit que le générateur n’est pas trèsintelligent : il forme f à partir d’un faible nombre d’imagestirées dans Φ.

Compressivesensing

A. Dalalyan

IntroductionGénéralités

Motivations

Compression

Problématique du CS

ThéorieParcimonie

Récupération sparse

Echantillonnage incohérent

ApprocheBayésienneGénéralités

Estimateur de Gibbs

Résultats

Conclusion

27

Estimateur de Gibbs

• On cherche à identifier une image f : [0,1]2 → [0,1].

• On a un appareil qui, pour tout x ∈ [0,1]2, nous fournit lavaleur bruitée y(x) de f (x).

• On suppose que le générateur de l’image forme l’imagefinale comme la superposition pondérée des imagesd’une base de données Φ avec des poids choisis auhasard.

f (x) =M∑

i=1ciϕi (x).

• Un espion nous a communiqué la base de données Φ.

• Il nous a également dit que le générateur n’est pas trèsintelligent : il forme f à partir d’un faible nombre d’imagestirées dans Φ.

Compressivesensing

A. Dalalyan

IntroductionGénéralités

Motivations

Compression

Problématique du CS

ThéorieParcimonie

Récupération sparse

Echantillonnage incohérent

ApprocheBayésienneGénéralités

Estimateur de Gibbs

Résultats

Conclusion

28

Estimateur de Gibbs

• Afin de spécifier la loi a priori, nous supposons que :

• le générateur tire les coefficients ci indépendammentles uns des autres,

• chaque ci est petit, mais le maxi |ci | est grand avecune probabilité non-négligeable.

• Cela nous conduit à une densité marginale de la formeπi (t) ∝ (ε2 + t2)−2, où ε est un paramètre d’ajustement.

• En supposant qu’on observe y(·) en x1, . . . , xn et que leserreurs sont gaussiennes, on obtient la loi a posteriori

π(t) ∝ exp(−β

∑i

(y(xi )−〈Φ(xi ), t〉

)2−2∑

i log(ε2+t2i )).

• On estime les coefficients ci de l’image f par la moyennede la loi a posteriori : ci =

∫RM ti π(t) dt.

• L’image reconstituée est alors f (x) =M∑

i=1ciϕi (x).

Compressivesensing

A. Dalalyan

IntroductionGénéralités

Motivations

Compression

Problématique du CS

ThéorieParcimonie

Récupération sparse

Echantillonnage incohérent

ApprocheBayésienneGénéralités

Estimateur de Gibbs

Résultats

Conclusion

28

Estimateur de Gibbs

• Afin de spécifier la loi a priori, nous supposons que :

• le générateur tire les coefficients ci indépendammentles uns des autres,

• chaque ci est petit, mais le maxi |ci | est grand avecune probabilité non-négligeable.

• Cela nous conduit à une densité marginale de la formeπi (t) ∝ (ε2 + t2)−2, où ε est un paramètre d’ajustement.

• En supposant qu’on observe y(·) en x1, . . . , xn et que leserreurs sont gaussiennes, on obtient la loi a posteriori

π(t) ∝ exp(−β

∑i

(y(xi )−〈Φ(xi ), t〉

)2−2∑

i log(ε2+t2i )).

• On estime les coefficients ci de l’image f par la moyennede la loi a posteriori : ci =

∫RM ti π(t) dt.

• L’image reconstituée est alors f (x) =M∑

i=1ciϕi (x).

Compressivesensing

A. Dalalyan

IntroductionGénéralités

Motivations

Compression

Problématique du CS

ThéorieParcimonie

Récupération sparse

Echantillonnage incohérent

ApprocheBayésienneGénéralités

Estimateur de Gibbs

Résultats

Conclusion

28

Estimateur de Gibbs

• Afin de spécifier la loi a priori, nous supposons que :

• le générateur tire les coefficients ci indépendammentles uns des autres,

• chaque ci est petit, mais le maxi |ci | est grand avecune probabilité non-négligeable.

• Cela nous conduit à une densité marginale de la formeπi (t) ∝ (ε2 + t2)−2, où ε est un paramètre d’ajustement.

• En supposant qu’on observe y(·) en x1, . . . , xn et que leserreurs sont gaussiennes, on obtient la loi a posteriori

π(t) ∝ exp(−β

∑i

(y(xi )−〈Φ(xi ), t〉

)2−2∑

i log(ε2+t2i )).

• On estime les coefficients ci de l’image f par la moyennede la loi a posteriori : ci =

∫RM ti π(t) dt.

• L’image reconstituée est alors f (x) =M∑

i=1ciϕi (x).

Compressivesensing

A. Dalalyan

IntroductionGénéralités

Motivations

Compression

Problématique du CS

ThéorieParcimonie

Récupération sparse

Echantillonnage incohérent

ApprocheBayésienneGénéralités

Estimateur de Gibbs

Résultats

Conclusion

28

Estimateur de Gibbs

• Afin de spécifier la loi a priori, nous supposons que :

• le générateur tire les coefficients ci indépendammentles uns des autres,

• chaque ci est petit, mais le maxi |ci | est grand avecune probabilité non-négligeable.

• Cela nous conduit à une densité marginale de la formeπi (t) ∝ (ε2 + t2)−2, où ε est un paramètre d’ajustement.

• En supposant qu’on observe y(·) en x1, . . . , xn et que leserreurs sont gaussiennes, on obtient la loi a posteriori

π(t) ∝ exp(−β

∑i

(y(xi )−〈Φ(xi ), t〉

)2−2∑

i log(ε2+t2i )).

• On estime les coefficients ci de l’image f par la moyennede la loi a posteriori : ci =

∫RM ti π(t) dt.

• L’image reconstituée est alors f (x) =M∑

i=1ciϕi (x).

Compressivesensing

A. Dalalyan

IntroductionGénéralités

Motivations

Compression

Problématique du CS

ThéorieParcimonie

Récupération sparse

Echantillonnage incohérent

ApprocheBayésienneGénéralités

Estimateur de Gibbs

Résultats

Conclusion

28

Estimateur de Gibbs

• Afin de spécifier la loi a priori, nous supposons que :

• le générateur tire les coefficients ci indépendammentles uns des autres,

• chaque ci est petit, mais le maxi |ci | est grand avecune probabilité non-négligeable.

• Cela nous conduit à une densité marginale de la formeπi (t) ∝ (ε2 + t2)−2, où ε est un paramètre d’ajustement.

• En supposant qu’on observe y(·) en x1, . . . , xn et que leserreurs sont gaussiennes, on obtient la loi a posteriori

π(t) ∝ exp(−β

∑i

(y(xi )−〈Φ(xi ), t〉

)2−2∑

i log(ε2+t2i )).

• On estime les coefficients ci de l’image f par la moyennede la loi a posteriori : ci =

∫RM ti π(t) dt.

• L’image reconstituée est alors f (x) =M∑

i=1ciϕi (x).

Compressivesensing

A. Dalalyan

IntroductionGénéralités

Motivations

Compression

Problématique du CS

ThéorieParcimonie

Récupération sparse

Echantillonnage incohérent

ApprocheBayésienneGénéralités

Estimateur de Gibbs

Résultats

Conclusion

29

Estimateur de GibbsRésultats théoriques

Théorème : Si l’on choisit les x1, . . . , xn indépendammentde façon aléatoire selon une densité g(·) alors

E∫[0,1]2

(f (x)− f (x)

)2g(x) dx ≤ Cσ2k log(Mn)

n+résidu,

où k = #{ci : ci 6= 0} et σ est l’intensité du bruit.

Remarques :

• reconstitution d’image sans aucune hypothèse sur Φ !

• Si δ est la précision de reconstitution souhaitée, il suffitd’acquérir n ∼ (σ2k log(M))/δ2 observations bruitées !

Compressivesensing

A. Dalalyan

IntroductionGénéralités

Motivations

Compression

Problématique du CS

ThéorieParcimonie

Récupération sparse

Echantillonnage incohérent

ApprocheBayésienneGénéralités

Estimateur de Gibbs

Résultats

Conclusion

29

Estimateur de GibbsRésultats théoriques

Théorème : Si l’on choisit les x1, . . . , xn indépendammentde façon aléatoire selon une densité g(·) alors

E∫[0,1]2

(f (x)− f (x)

)2g(x) dx ≤ Cσ2k log(Mn)

n+résidu,

où k = #{ci : ci 6= 0} et σ est l’intensité du bruit.

Remarques :

• reconstitution d’image sans aucune hypothèse sur Φ !

• Si δ est la précision de reconstitution souhaitée, il suffitd’acquérir n ∼ (σ2k log(M))/δ2 observations bruitées !

Compressivesensing

A. Dalalyan

IntroductionGénéralités

Motivations

Compression

Problématique du CS

ThéorieParcimonie

Récupération sparse

Echantillonnage incohérent

ApprocheBayésienneGénéralités

Estimateur de Gibbs

Résultats

Conclusion

29

Estimateur de GibbsRésultats théoriques

Théorème : Si l’on choisit les x1, . . . , xn indépendammentde façon aléatoire selon une densité g(·) alors

E∫[0,1]2

(f (x)− f (x)

)2g(x) dx ≤ Cσ2k log(Mn)

n+résidu,

où k = #{ci : ci 6= 0} et σ est l’intensité du bruit.

Remarques :

• reconstitution d’image sans aucune hypothèse sur Φ !

• Si δ est la précision de reconstitution souhaitée, il suffitd’acquérir n ∼ (σ2k log(M))/δ2 observations bruitées !

Compressivesensing

A. Dalalyan

IntroductionGénéralités

Motivations

Compression

Problématique du CS

ThéorieParcimonie

Récupération sparse

Echantillonnage incohérent

ApprocheBayésienneGénéralités

Estimateur de Gibbs

Résultats

Conclusion

30

Résultats numériques

• Nous observons un signal bruité en n = 100 points,• le “dictionnaire” Φ contient M = 225 éléments,• le signal qu’on cherche à reconstruire est la somme

de 3 éléments de Φ.

La vraie image L’image observée L’image reconstruite

Compressivesensing

A. Dalalyan

IntroductionGénéralités

Motivations

Compression

Problématique du CS

ThéorieParcimonie

Récupération sparse

Echantillonnage incohérent

ApprocheBayésienneGénéralités

Estimateur de Gibbs

Résultats

Conclusion

30

Résultats numériques

• Nous observons un signal bruité en n = 100 points,• le “dictionnaire” Φ contient M = 225 éléments,• le signal qu’on cherche à reconstruire est la somme

de 3 éléments de Φ.

La vraie image

L’image observée L’image reconstruite

Compressivesensing

A. Dalalyan

IntroductionGénéralités

Motivations

Compression

Problématique du CS

ThéorieParcimonie

Récupération sparse

Echantillonnage incohérent

ApprocheBayésienneGénéralités

Estimateur de Gibbs

Résultats

Conclusion

30

Résultats numériques

• Nous observons un signal bruité en n = 100 points,• le “dictionnaire” Φ contient M = 225 éléments,• le signal qu’on cherche à reconstruire est la somme

de 3 éléments de Φ.

La vraie image L’image observée

L’image reconstruite

Compressivesensing

A. Dalalyan

IntroductionGénéralités

Motivations

Compression

Problématique du CS

ThéorieParcimonie

Récupération sparse

Echantillonnage incohérent

ApprocheBayésienneGénéralités

Estimateur de Gibbs

Résultats

Conclusion

30

Résultats numériques

• Nous observons un signal bruité en n = 100 points,• le “dictionnaire” Φ contient M = 225 éléments,• le signal qu’on cherche à reconstruire est la somme

de 3 éléments de Φ.

La vraie image L’image observée L’image reconstruite

Compressivesensing

A. Dalalyan

IntroductionGénéralités

Motivations

Compression

Problématique du CS

ThéorieParcimonie

Récupération sparse

Echantillonnage incohérent

ApprocheBayésienneGénéralités

Estimateur de Gibbs

Résultats

Conclusion

31

Conclusion

• Etant donné un dictionnaire Φ favorisant la sparsité,le CS fournit des procédures efficaces d’acquisitionet de compression de données.

• Il suffit d’effectuer Ck log M mesures pour identifierun objet M-dimensionnel qui est k -sparse.

• Au cas où le dictionnaire Φ contient des élémentsfortement corrélés, l’approche Bayésienne donne lesmeilleurs résultats.

• De nombreuses applications en� Traitement vidéo,� Imagerie médicale,� Astronomie,� Puce à ADN,� ...

Compressivesensing

A. Dalalyan

IntroductionGénéralités

Motivations

Compression

Problématique du CS

ThéorieParcimonie

Récupération sparse

Echantillonnage incohérent

ApprocheBayésienneGénéralités

Estimateur de Gibbs

Résultats

Conclusion

31

Conclusion

• Etant donné un dictionnaire Φ favorisant la sparsité,le CS fournit des procédures efficaces d’acquisitionet de compression de données.

• Il suffit d’effectuer Ck log M mesures pour identifierun objet M-dimensionnel qui est k -sparse.

• Au cas où le dictionnaire Φ contient des élémentsfortement corrélés, l’approche Bayésienne donne lesmeilleurs résultats.

• De nombreuses applications en� Traitement vidéo,� Imagerie médicale,� Astronomie,� Puce à ADN,� ...

Compressivesensing

A. Dalalyan

IntroductionGénéralités

Motivations

Compression

Problématique du CS

ThéorieParcimonie

Récupération sparse

Echantillonnage incohérent

ApprocheBayésienneGénéralités

Estimateur de Gibbs

Résultats

Conclusion

31

Conclusion

• Etant donné un dictionnaire Φ favorisant la sparsité,le CS fournit des procédures efficaces d’acquisitionet de compression de données.

• Il suffit d’effectuer Ck log M mesures pour identifierun objet M-dimensionnel qui est k -sparse.

• Au cas où le dictionnaire Φ contient des élémentsfortement corrélés, l’approche Bayésienne donne lesmeilleurs résultats.

• De nombreuses applications en� Traitement vidéo,� Imagerie médicale,� Astronomie,� Puce à ADN,� ...

Compressivesensing

A. Dalalyan

IntroductionGénéralités

Motivations

Compression

Problématique du CS

ThéorieParcimonie

Récupération sparse

Echantillonnage incohérent

ApprocheBayésienneGénéralités

Estimateur de Gibbs

Résultats

Conclusion

31

Conclusion

• Etant donné un dictionnaire Φ favorisant la sparsité,le CS fournit des procédures efficaces d’acquisitionet de compression de données.

• Il suffit d’effectuer Ck log M mesures pour identifierun objet M-dimensionnel qui est k -sparse.

• Au cas où le dictionnaire Φ contient des élémentsfortement corrélés, l’approche Bayésienne donne lesmeilleurs résultats.

• De nombreuses applications en� Traitement vidéo,� Imagerie médicale,� Astronomie,� Puce à ADN,� ...