Contributions individuelles
Progress on Hard Thresholding Pursuit for sparse signal recovery //Progrès sur Hard Thresholding Pursuit pour la reconstruction de signaux parcimoniaux
Bouchot, Jean-Luc, Simon Foucart and Pawel Hitczenko
Drexel University

In this talk, theoretical results for the recovery of sparse vectors via the Hard Thresholding Pursuit algorithm are revisited. The main result states that all sparse vectors can be exactly recovered from incomplete linear measurements in a number of iterations at most proportional to the sparsity level as soon as the measurement matrix obeys a restricted isometry condition. Moreover we show that this recovery is robust against noise.

We also see that these results hold for a novel algorithm called Graded Hard Thresholding Pursuit which does not require a prior estimation of the sparsity level. We also show that under for certain particular shapes of vectors, a fixed sparse vector can be recovered with high probability in a number of iterations precisely equal to the sparsity level. These results are validated experimentally.

Dans cette présentation, les arguments théoriques pour la reconstruction de signaux parcimonieux par Hard Thresholding Pursuit sont revisités. Le résultat principal  établit en particulier que tout signal parcimonieux peut être reconstruit  à partir d’un nombre de mesures réduit en un nombre d’itérations au plus proportionnel  à  la sparsité des signaux considérés, dès lors que la matrice de mesure  a  une propriété d’isométrie réduite. On montre par ailleurs que cette reconstruction est robuste face au bruit.

On prouve  également que ces résultats sont valides pour une nouvelle variante de l’algorithme appelée Graded Hard Thresholding Pursuit pour laquelle une estimation a priori du niveau de parcimonie n’est pas nécessaire. Enfin on montre que pour certains types de vecteurs la  reconstruction d’un vecteur fixe est possible avec une grande certitude en un nombre d’itérations exactement  égal à  la sparsité du signal. Tous ces résultats sont également illustrés numériquement.

Mardi, 18 juin, 18h00
Salle George V