Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userStable Phase Retrieval from Locally Stable and Conditionally Connected Measurements
111
0
0.0
(
0
)
Added by
Nadav Dym
Publication date
2020
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
This paper is concerned with stable phase retrieval for a family of phase retrieval models we name locally stable and conditionally connected (LSCC) measurement schemes. For every signal $f$, we associate a corresponding weighted graph $G_f$, defined by the LSCC measurement scheme, and show that the phase retrievability of the signal $f$ is determined by the connectivity of $G_f$. We then characterize the phase retrieval stability of the signal $f$ by two measures that are commonly used in graph theory to quantify graph connectivity: the Cheeger constant of $G_f$ for real valued signals, and the algebraic connectivity of $G_f$ for complex valued signals. We use our results to study the stability of two phase retrieval models that can be cast as LSCC measurement schemes, and focus on understanding for which signals the curse of dimensionality can be avoided. The first model we discuss is a finite-dimensional model for locally supported measurements such as the windowed Fourier transform. For signals without large holes, we show the stability constant exhibits only a mild polynomial growth in the dimension, in stark contrast with the exponential growth which uniform stability constants tend to suffer from; more precisely, in $R^d$ the constant grows proportionally to $d^{1/2}$, while in $C^d$ it grows proportionally to $d$. We also show the growth of the constant in the complex case cannot be reduced, suggesting that complex phase retrieval is substantially more difficult than real phase retrieval. The second model we consider is an infinite-dimensional phase retrieval problem in a principal shift invariant space. We show that despite the infinite dimensionality of this model, signals with monotone exponential decay will have a finite stability constant. In contrast, the stability bound provided by our results will be infinite if the signals decay is polynomial.
rate research
Read More
We study the phase reconstruction of signals $f$ belonging to complex Gaussian shift-invariant spaces $V^infty(varphi)$ from spectrogram measurements $|mathcal{G}f(X)|$ where $mathcal{G}$ is the Gabor transform and $X subseteq mathbb{R}^2$. An explicit reconstruction formula will demonstrate that such signals can be recovered from measurements located on parallel lines in the time-frequency plane by means of a Riesz basis expansion. Moreover, connectedness assumptions on $|f|$ result in stability estimates in the situation where one aims to reconstruct $f$ on compact intervals. Driven by a recent observation that signals in Gaussian shift-invariant spaces are determined by lattice measurements [Grohs, P., Liehr, L., Injectivity of Gabor phase retrieval from lattice measurements, arXiv:2008.07238] we prove a sampling result on the stable approximation from finitely many spectrogram samples. The resulting algorithm provides a non-iterative, provably stable and convergent approximation technique. In addition, it constitutes a method of approximating signals in function spaces beyond $V^infty(varphi)$, such as Paley-Wiener spaces.
The problem of phase retrieval is to determine a signal $fin mathcal{H}$, with $mathcal{H}$ a Hilbert space, from intensity measurements $|F(omega)|$, where $F(omega):=langle f , varphi_omegarangle$ are measurements of $f$ with respect to a measurement system $(varphi_omega)_{omegain Omega}subset mathcal{H}$. Although phase retrieval is always stable in the finite dimensional setting whenever it is possible (i.e. injectivity implies stability for the inverse problem), the situation is drastically different if $mathcal{H}$ is infinite-dimensional: in that case phase retrieval is never uniformly stable [8, 4]; moreover the stability deteriorates severely in the dimension of the problem [8]. On the other hand, all empirically observed instabilities are of a certain type: they occur whenever the function $|F|$ of intensity measurements is concentrated on disjoint sets $D_jsubset Omega$, i.e., when $F= sum_{j=1}^k F_j$ where each $F_j$ is concentrated on $D_j$ (and $k geq 2$). Motivated by these considerations we propose a new paradigm for stable phase retrieval by considering the problem of reconstructing $F$ up to a phase factor that is not global, but that can be different for each of the subsets $D_j$, i.e., recovering $F$ up to the equivalence $$ F sim sum_{j=1}^k e^{i alpha_j} F_j.$$ We present concrete applications (for example in audio processing) where this new notion of stability is natural and meaningful and show that in this setting stable phase retrieval can actually be achieved, for instance if the measurement system is a Gabor frame or a frame of Cauchy wavelets.
In recent work [P. Grohs and M. Rathmair. Stable Gabor Phase Retrieval and Spectral Clustering. Communications on Pure and Applied Mathematics (2018)] the instabilities of the Gabor phase retrieval problem, i.e., the problem of reconstructing a function $f$ from its spectrogram $|mathcal{G}f|$, where $$ mathcal{G}f(x,y)=int_{mathbb{R}^d} f(t) e^{-pi|t-x|^2} e^{-2pi i tcdot y} dt, quad x,yin mathbb{R}^d, $$ have been completely classified in terms of the disconnectedness of the spectrogram. These findings, however, were crucially restricted to the onedimensional case ($d=1$) and therefore not relevant for many practical applications. In the present paper we not only generalize the aforementioned results to the multivariate case but also significantly improve on them. Our new results have comprehensive implications in various applications such as ptychography, a highly popular method in coherent diffraction imaging.
This paper studies the problem of accurately recovering a structured signal from a small number of corrupted sub-Gaussian measurements. We consider three different procedures to reconstruct signal and corruption when different kinds of prior knowledge are available. In each case, we provide conditions (in terms of the number of measurements) for stable signal recovery from structured corruption with added unstructured noise. Our results theoretically demonstrate how to choose the regularization parameters in both partially and fully penalized recovery procedures and shed some light on the relationships among the three procedures. The key ingredient in our analysis is an extended matrix deviation inequality for isotropic sub-Gaussian matrices, which implies a tight lower bound for the restricted singular value of the extended sensing matrix. Numerical experiments are presented to verify our theoretical results.
This paper investigates the convergence of the randomized Kaczmarz algorithm for the problem of phase retrieval of complex-valued objects. While this algorithm has been studied for the real-valued case}, its generalization to the complex-valued case is nontrivial and has been left as a conjecture. This paper establishes the connection between the convergence of the algorithm and the convexity of an objective function. Based on the connection, it demonstrates that when the sensing vectors are sampled uniformly from a unit sphere and the number of sensing vectors $m$ satisfies $m>O(nlog n)$ as $n, mrightarrowinfty$, then this algorithm with a good initialization achieves linear convergence to the solution with high probability.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
