Create your own awesome maps

Even on the go

with our free apps for iPhone, iPad and Android

Get Started

Already have an account?
Log In

Compressive sampling by Mind Map: Compressive sampling
5.0 stars - 1 reviews range from 0 to 5

Compressive sampling

Caractéristiques

Tutorial p.23

CS changes the rules of the data acquisition game

Exploits a priori signal sparsity information

Universal

            same random projections / hardware can be used for any compressible signal class (generic )

Democratic

– each measurement carries the same amount of information – simple encoding – robust to measurement loss and quantization

Assymetrical

most procesing at decoder

Random projections weakly encrypted

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

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

New Idea

Exemples

De matrices Phi

Tutorial p.34

Gros pixels

Lignes (Tomographie)

Sinusïdes (MRI)

D'utilisations

Single Pixel Camera

MRI

Principe

Compressive Sensing - Richard Baraniuk - Lecture Notes in IEEE Signal Processing Magazine, vol 24, Juillet 2007 Voir lien pour la formule de base  

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

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

M mesures (y) permettant de reconstruire le signal x de longueur N, M<N, seulement besoin de reconstruire les K coordonnées de la représentation de x dans la base Psi, M>=K

Matrice de mesure doit être "stable", Matrice Theta doit-être bien conditionnée, Condition nécessaire et suffisante : Theta conserve la norme de tout vecteur ayant les mêmes coordonnées non nulles que s, Problème : on ne connaît pas à l'avance les coefficients non nuls, Condition suffisante : Restricted Isometry Property, Vérifier la propriété précédente pour un vecteur arbitraire possédant 3K coordonnées non nulles, Demande de nombreux calculs : vérifier la propriété avec 3K parmi N combinaisons de coordonnées non nulles, Autre solution : s'assurer que la matrice Phi est incohérente avec la matrice Psi, Les vecteurs Phi_j n'ont pas de coordonnées nulles dans la base des vecteurs Psi_i et vice-versa., Exemple : Phi_j : diracs et Psi_i : sinusoïdes, Solution "pratique" : matrice Phi aléatoire, Exemple : Les Phi_j,i sont des variables gaussienne iid de moyenne nulle de variance 1/N (bruit blanc), Phi incohérent avec la matrice Psi=I avec une grande probabilité, Plus rigoureusement : Theta = Phi a le RIP avec une grande probabilité si M >= cK log(N/K) avec c constante "petite"., Theta = PhiPsi est iid gaussienne pour toute matrice Psi orthonormale, Phi est universelle, Exemple : matrices de Rademacher (coefficients alétoires +1 ou -1), Respecte le RIP avec une grande probabilité, Universelles

Reconstruire le signal (y->x)

On connait y, Theta et Phi

Problème : Theta s' = y possède une infinité de solutions (hyperplan de dimension (N-M)), Norme l2 minimum, Moindres carrés, énergie minimum, fonctionne mal, Norme l0 minimum, Reflète bien l'aspect "creux" du signal désiré, Pour M = K+1 mesures gaussiennes, donne le résultat exact avec une haute probabilité, Mais : système à résoudre instable et NP-complet, Norme l1 minimum, Marche étonnamment bien pour M>=cK log(N/K) mesures iid gaussiennes, Pour C de la forme 22(delta+1), la probabilité de succès est supérieure à 1-O(N^-delta), Problème d'optimisation linéaire, Algorithme : "basis pursuit", Complexité O(N^3), Voir interprétation géométrique

Autres techniques

Inconvénients

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

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

Méthode approchée "goutonne", nécessite un M plus grand, Matching Pursuit