Provable Phase retrieval via Mirror Descent

Reconstruction de Phase Garantie par Descente Miroir

Jean-Jacques Godeme (1, 2, 3, 4) , Jalal Fadili (1, 2, 3, 4) , Xavier Buet (5, 6, 7) , Myriam Zerrad (5, 6, 7) , Michel Lequime (5, 6, 7) , Claude Amra (5, 6, 7)

1 Equipe Image - Laboratoire GREYC - UMR6072
2 NU - Normandie Université
3 ENSICAEN - École Nationale Supérieure d'Ingénieurs de Caen
4 GREYC - Groupe de Recherche en Informatique, Image et Instrumentation de Caen
5 FRESNEL - Institut FRESNEL
6 AMU - Aix Marseille Université
7 ECM - École Centrale de Marseille

We consider the problem of phase retrieval that consists in recovering an n-dimensional real vector from the magnitude of its m-linear measurements. This paper presents a new approach allowing to lift the classical global Lipschitz continuity requirement on the gradient of the non-convex objective to minimize. We propose a mirror descent algorithm based on a wisely chosen Bregman divergence. We show that when the number of measurements m is large enough, the mirror descent algorithm, carefully initialized, converges linearly with a dimension-independent convergence rate. Consequently, the original signal can be reconstructed exactly up to a global sign change. We state our results for two types of measurements: iid standard Gaussian and those obtained by Coded Diffraction Patterns (CDP) for Randomized Fourier Transform.

Dans ce travail, nous considérons le problème de reconstruction de phase, qui consiste à recouvrer un signal de dimension n à partir des modules de ses m mesures linéaires. Nous présentons une nouvelle approche permettant de se passer de la Lipschitz continuité globale du gradient de l'objective non-convexe à minimiser. Pour ce faire, nous introduisons un algorithme de descente miroir non-euclidienne via la divergence de Bregman d'une entropie bien choisie. Nous montrons que lorsqu'on le nombre de mesures m est suffisamment grand, alors avec grande probabilité, l'algorithme de descente miroir, bien initialisé, converge linéairement avec un taux indépendant de la dimension n, permettant ainsi de recouvrer le signal original à un changement de signe près. Nous énonçons nos résultats pour deux types de mesures: Gaussiennes iid et celles obtenues par des masques codés pour des transformées de Fourier aléatoires.

Domaines: Optimisation et contrôle [math.OC]

Jean-Jacques Godeme, Jalal Fadili, Xavier Buet, Myriam Zerrad, Michel Lequime, et al.. Reconstruction de Phase Garantie par Descente Miroir. 2022. ⟨hal-03622580v3⟩