Compressive sampling

Get Started. It's Free
or sign up with your email address
Rocket clouds
Compressive sampling by Mind Map: Compressive sampling

1. Caractéristiques

1.1. CS changes the rules of the data acquisition game

1.2. Universal

1.3. Democratic

1.4. Assymetrical

1.5. Random projections weakly encrypted

1.6. Permet de s'"affranchir" du critère de Nyquist : moins de mesures que de coefficients

1.7. Evite de gâcher de l'information en faisant une acquisition sans perte + compression

1.8. New Idea

2. Exemples

2.1. De matrices Phi

2.1.1. Gros pixels

2.1.2. Lignes (Tomographie)

2.1.3. Sinusïdes (MRI)

2.2. D'utilisations

2.2.1. Single Pixel Camera

2.2.2. MRI

3. Principe

3.1. Acquisition de signaux "creux" directement dans une base appropriée

3.2. Acquérir des combinaisons linéaires des coefficients du signal reçu (x->y)

3.2.1. M mesures (y) permettant de reconstruire le signal x de longueur N, M<N

3.2.1.1. seulement besoin de reconstruire les K coordonnées de la représentation de x dans la base Psi, M>=K

3.2.2. Matrice de mesure doit être "stable"

3.2.2.1. Matrice Theta doit-être bien conditionnée

3.2.2.1.1. Condition nécessaire et suffisante : Theta conserve la norme de tout vecteur ayant les mêmes coordonnées non nulles que s

3.2.2.1.2. Condition suffisante : Restricted Isometry Property

3.2.2.1.3. Autre solution : s'assurer que la matrice Phi est incohérente avec la matrice Psi

3.2.2.1.4. Solution "pratique" : matrice Phi aléatoire

3.3. Reconstruire le signal (y->x)

3.3.1. On connait y, Theta et Phi

3.3.2. Problème : Theta s' = y possède une infinité de solutions (hyperplan de dimension (N-M))

3.3.2.1. Norme l2 minimum

3.3.2.1.1. Moindres carrés, énergie minimum, fonctionne mal

3.3.2.2. Norme l0 minimum

3.3.2.2.1. Reflète bien l'aspect "creux" du signal désiré

3.3.2.2.2. Pour M = K+1 mesures gaussiennes, donne le résultat exact avec une haute probabilité

3.3.2.2.3. Mais : système à résoudre instable et NP-complet

3.3.2.3. Norme l1 minimum

3.3.2.3.1. Marche étonnamment bien pour M>=cK log(N/K) mesures iid gaussiennes

3.3.2.3.2. Problème d'optimisation linéaire

3.3.2.3.3. Voir interprétation géométrique

4. Autres techniques

5. Inconvénients

5.1. Algorithme de reconstruction par minimisation de la norme l1 très complexe

5.1.1. Utilisation de GPU pour la reconstruction d'images (30x plus rapide que CPU)

5.1.2. Méthode approchée "goutonne", nécessite un M plus grand

5.1.2.1. Matching Pursuit