On Lipschitz Analysis and Lipschitz Synthesis for the Phase Retrieval Problem

In this paper we prove two results regarding reconstruction from magnitudes of frame coefficients (the so called "phase retrieval problem"). First we show that phase retrievability as an algebraic property implies that nonlinear maps are bi-Lipschitz with respect to appropriate metrics on the quotient space. Second we prove that reconstruction can be performed using Lipschitz continuous maps. Specifically we show that when nonlinear analysis maps α,β:hatHrightarrow Rm are injective, with α(x)=(|langle x,fkrangle |)k=1m and β(x)=(|langle x,fk rangle|2)k=1m, where f1,ldots,fm is a frame for a Hilbert space H and hatH=H/T1, then α is bi-Lipschitz with respect to the class of "natural metrics" Dp(x,y)= minvarphi || x-eivarphiy ||p, whereas β is bi-Lipschitz with respect to the class of matrix-norm induced metrics dp(x,y)=|| xx^*-yy^*||p. Furthermore, there exist left inverse maps ω,psi:Rmrightarrow hatH of α and β respectively, that are Lipschitz continuous with respect to the appropriate metric. Additionally we obtain the Lipschitz constants of these inverse maps in terms of the lower Lipschitz constants of α and β. Surprisingly the increase in Lipschitz constant is a relatively small factor, independent of the space dimension or the frame redundancy.