#### DMCA

## Phase retrieval with polarization (2013)

Venue: | SIAM J. ON IMAGING SCI |

Citations: | 21 - 5 self |

### Citations

2207 | Probability inequalities for sums of bounded random variables
- Hoeffding
- 1963
(Show Context)
Citation Context ... Pr ( 2M‖ϕi‖2 ≥ 5M ) ≤ e−M/2. (6.17) Substituting (6.16) and (6.16) into (6.15) then gives Pr ( ϕi 6∈ Gδ(v) ) ≤ 12δ √ M 2pi + e −M/2. (6.18) Now, to bound (6.14), we will apply Hoeffding’s inequality =-=[28]-=-, which says that the tail probability of a sum of independent Bernoulli random variables Xi, each with success probability p, has the following bound: Pr ( n∑ i=1 Xi ≥ n(p+ t) ) ≤ e−2nt. 21 Also, not... |

1035 | Random Graphs
- Janson, Luczak, et al.
- 2000
(Show Context)
Citation Context ...nt of size at least M (the remainder of Phase Retrieval Procedure A accumulates only round-off errors, which are negligible here). At this point, we appeal to a result which appears in Section 5.2 of =-=[30]-=-, namely that if c > 1 is held constant, then with high probability, the Erdős-Rényi random graph with n vertices and edge probability p = c/n has a unique giant connected component of size (β+ o(1)... |

399 | Eigenvalues and expanders.
- Alon
- 1986
(Show Context)
Citation Context ...xpansion λ. Spectral graph families known as Ramanujan graphs are asymptotically optimal in this sense; taking Gdn to be the set of connected d-regular graphs with ≥ n vertices, Alon and Boppana (see =-=[2]-=-) showed that for any fixed d, lim n→∞ infG∈Gdn λ(G) ≥ 2 √ d− 1 d , while Ramanujan graphs are defined to have spectral expansion ≤ 2 √ d−1 d . To date, Ramanujan graphs have only been constructed for... |

349 | Introduction to the non-asymptotic analysis of random matrices
- Vershynin
- 2011
(Show Context)
Citation Context ...ndependent with rotationally symmetric probability distributions. It therefore suffices to bound both |Nδ| and Pr(Ev). To bound |Nδ|, we follow a standard argument, found in the proof of Lemma 5.2 in =-=[47]-=-. Let Nδ be a maximal δ-packing of points on the unit sphere in CM . Since the packing is maximal, it follows that Nδ is a δ-net. To count these points, map them into R2M according to f : v 7→ (Re v, ... |

334 | A lower bound for the smallest eigenvalue of the Laplacian, in: Problems in Analysis (Papers dedicated to Salomon Bochner), - Cheeger - 1970 |

287 | Phase retrieval algorithms: A comparison
- Fienup
- 1982
(Show Context)
Citation Context ...column space of Φ∗ (to bring phase to the measurements) and onto the nonconvex set of vectors y whose entry magnitudes match the intensity measurements |Φ∗x|2 (to maintain fidelity in the magnitudes) =-=[21, 23, 24]-=-. Unfortunately, the convergence of these algorithms (and various modifications thereof) is particularly sensitive to the choice of initial phases [36]. These deficiencies have prompted two important ... |

286 |
A practical algorithm for the determination of phase from image and diffraction plane pictures
- Gerchberg, Saxton
- 1972
(Show Context)
Citation Context ...column space of Φ∗ (to bring phase to the measurements) and onto the nonconvex set of vectors y whose entry magnitudes match the intensity measurements |Φ∗x|2 (to maintain fidelity in the magnitudes) =-=[21, 23, 24]-=-. Unfortunately, the convergence of these algorithms (and various modifications thereof) is particularly sensitive to the choice of initial phases [36]. These deficiencies have prompted two important ... |

275 |
λ1, isoperimetric inequalities for graphs and super concentrators
- ALON, MILLMAN
- 1985
(Show Context)
Citation Context ...ified using spectral clustering (Algorithm 2), a process which is strongly motivated by an inequality in Riemannian geometry by Cheeger [15] and which has performance guarantees originating with Alon =-=[2, 3]-=-. The main idea of spectral clustering follows the intuition that a random walk on a graph tends to be trapped in sections of the graph which have few connections to the rest of the vertices (this int... |

204 |
Adaptive estimation of a quadratic functional by model selection
- Laurent, Massart
(Show Context)
Citation Context ...that Pr ( |〈v, ϕi〉| < 3δ ) ≤ 2Pr ( |a1| < 3√2δ ) ≤ 12δ √ M 2pi . (6.16) For the other term in (6.15), note that 2M‖ϕi‖2 is a sum of independent standard Gaussian random variables. Applying Lemma 1 of =-=[32]-=- then gives that for every t > 0, Pr ( 2M‖ϕi‖2 ≥ √ 8Mt+ 2t+ 2M ) ≤ e−t. Thus, taking t = M2 gives Pr ( ‖ϕi‖ > 2 ) = Pr ( 2M‖ϕi‖2 > 8M ) ≤ Pr ( 2M‖ϕi‖2 ≥ 5M ) ≤ e−M/2. (6.17) Substituting (6.16) and (6... |

170 | Signal estimation from modified short-time fourier transform
- Griffin, Lim
- 1984
(Show Context)
Citation Context ...column space of Φ∗ (to bring phase to the measurements) and onto the nonconvex set of vectors y whose entry magnitudes match the intensity measurements |Φ∗x|2 (to maintain fidelity in the magnitudes) =-=[21, 23, 24]-=-. Unfortunately, the convergence of these algorithms (and various modifications thereof) is particularly sensitive to the choice of initial phases [36]. These deficiencies have prompted two important ... |

165 | A proof of Alon’s second eigenvalue conjecture and related problems. Available from
- Friedman
(Show Context)
Citation Context ...hat random graphs are nearly Ramanujan with high probability. In particular, for every ε > 0 and even d, a random d-regular graph has spectral expansion λ ≤ 2 √ d−1+ε d with high probability as n → ∞ =-=[22]-=-. Thus, picking ε and d to satisfy 2 √ d−1+ε d < 1, we may take M = b(1− 2 √ d−1+ε d ) n 6 + 1c to get N M ≤ ( 3 2d+ 1)n (1− 2 √ d−1+ε d ) n 6 , 5 and this choice will satisfy M ≤ (λ26 )n+ 1 with high... |

132 |
Phaselift : exact and stable signal recovery from magnitude measurements via convex programming
- Candes, Strohmer, et al.
(Show Context)
Citation Context ...nder graphs. We also give an efficient phase retrieval procedure, and use recent results in spectral graph theory to produce a stable performance guarantee which rivals the guarantee for PhaseLift in =-=[14]-=-. We use numerical simulations to illustrate the performance of our phase retrieval procedure, and we compare reconstruction error and runtime with a common alternating-projections-type procedure. Key... |

109 | Diffusion maps, spectral clustering and eigenfunctions of fokker-planck operators
- Nadler, Lafon, et al.
- 2005
(Show Context)
Citation Context ...tering follows the intuition that a random walk on a graph tends to be trapped in sections of the graph which have few connections to the rest of the vertices (this intuition is made more explicit in =-=[35, 40]-=-). Moreover, the second eigenvector of the corresponding stochastic matrix tends to identify these sections. Note that when implementing spectral clustering, the values of E(Si, S c i ), vol(Si) and v... |

73 | Phase retrieval via matrix completion
- Candes, Eldar, et al.
- 2013
(Show Context)
Citation Context ...f the art comes from Candès, Strohmer and Voroninski [14], who use semidefinite programming to stably reconstruct from N = O(M logM) Gaussian-random measurements. There is other work along this vein =-=[12, 13, 18, 48]-=- which also uses semidefinite programming and provides related guarantees. Typically, semidefinite programs are solved via interior point methods. Since these methods are computationally expensive, in... |

72 |
On signal reconstruction without phase
- Balan, Casazza, et al.
(Show Context)
Citation Context ...t remains an open problem to find the smallest such N [7], but embedding results in differential geometry give that N ≥ (4 + o(1))M is necessary [4, 27]. As for sufficiency, Balan, Casazza and Edidin =-=[6]-=- show that for almost every choice of Φ, A is injective whenever N ≥ 4M − 2, and recent work has leveraged more structured constructions to slightly decrease this number of measurement vectors [10, 39... |

72 |
Phase retrieval in crystallography and optics
- Millane
- 1990
(Show Context)
Citation Context ... x ∈ CM , consider measurements of the form z` := |〈x, ϕ`〉|2 + ν`, (1.1) where ν` is noise; we call these noisy intensity measurements. Several areas of imaging science, such as X-ray crystallography =-=[25, 37, 38]-=-, diffraction imaging [11], astronomy [17] and optics [49], use measurements of this form with the intent of reconstructing the original signal; this inverse problem is called phase retrieval. Note th... |

53 |
Phase recovery, MaxCut and complex semidefinite programming.
- Waldspurger, d’Aspremont, et al.
- 2015
(Show Context)
Citation Context ...f the art comes from Candès, Strohmer and Voroninski [14], who use semidefinite programming to stably reconstruct from N = O(M logM) Gaussian-random measurements. There is other work along this vein =-=[12, 13, 18, 48]-=- which also uses semidefinite programming and provides related guarantees. Typically, semidefinite programs are solved via interior point methods. Since these methods are computationally expensive, in... |

50 |
Spectral phase interferometry for direct electric-field reconstruction of ultrashort optical pulses Opt
- Iaconis, Walmsley
- 1998
(Show Context)
Citation Context ... for direct electric-field reconstruction (SPIDER) interferes the signal of interest x ∈ CM with time- and frequency-shifted versions of itself Sx ∈ CM , taking measurements of the form |F (x + Sx)|2 =-=[29]-=-; while popular in practice for ultrashort pulse measurement, SPIDER fails to accurately resolve the relative phase of well-separated frequency components [31]. Another interesting approach is ptychog... |

49 | Painless reconstruction from magnitudes of frame coefficients
- Balan, Bodmann, et al.
- 2009
(Show Context)
Citation Context ...ne to attempt provably stable and efficient reconstruction from measurements of the form (1.1) with particular ensembles Φ. Until recently, this was only known to be possible in cases where N = Ω(M2) =-=[5]-=-. By contrast, the state of the art comes from Candès, Strohmer and Voroninski [14], who use semidefinite programming to stably reconstruct from N = O(M logM) Gaussian-random measurements. There is o... |

49 |
Solving quadratic equations via phaselift when there are about as many equations as unknowns, August 2012, ArXiv e-prints
- Candes, Li
(Show Context)
Citation Context ...f the art comes from Candès, Strohmer and Voroninski [14], who use semidefinite programming to stably reconstruct from N = O(M logM) Gaussian-random measurements. There is other work along this vein =-=[12, 13, 18, 48]-=- which also uses semidefinite programming and provides related guarantees. Typically, semidefinite programs are solved via interior point methods. Since these methods are computationally expensive, in... |

47 |
Fienup, "Phase Retrieval and Image Reconstruction for Astronomy
- Dainty, R
- 1987
(Show Context)
Citation Context ...|〈x, ϕ`〉|2 + ν`, (1.1) where ν` is noise; we call these noisy intensity measurements. Several areas of imaging science, such as X-ray crystallography [25, 37, 38], diffraction imaging [11], astronomy =-=[17]-=- and optics [49], use measurements of this form with the intent of reconstructing the original signal; this inverse problem is called phase retrieval. Note that in the measurement process (1.1), we in... |

44 | Angular synchronization by eigenvectors and semidefinite programming,” Applied and computational harmonic analysis
- Singer
- 2011
(Show Context)
Citation Context ...how in the appendix (using results from [9]), this estimate is stable provided the spectral gap of G′ is sufficiently large. This spectral method is known in the literature as angular synchronization =-=[46]-=-, and we summarize the procedure in Algorithm 4 9 Algorithm 4: Angular synchronization Input: Graph G′ = (V ′, E′), noisy versions of (2.4) for every {i, j} ∈ E′ Output: Vector of phases corresponding... |

38 |
Phase problem in crystallography
- Harrison
- 1993
(Show Context)
Citation Context ... x ∈ CM , consider measurements of the form z` := |〈x, ϕ`〉|2 + ν`, (1.1) where ν` is noise; we call these noisy intensity measurements. Several areas of imaging science, such as X-ray crystallography =-=[25, 37, 38]-=-, diffraction imaging [11], astronomy [17] and optics [49], use measurements of this form with the intent of reconstructing the original signal; this inverse problem is called phase retrieval. Note th... |

35 | Stable optimizationless recovery from phaseless linear measurements. Arxiv preprint arXiv:1208.1803
- Demanet, Hand
- 2012
(Show Context)
Citation Context |

32 | Quantum tomography under prior information,” arXiv:1109.5478
- Heinosaari, Mazzarella, et al.
- 2011
(Show Context)
Citation Context ...g how large N must be in order for A to be injective. It remains an open problem to find the smallest such N [7], but embedding results in differential geometry give that N ≥ (4 + o(1))M is necessary =-=[4, 27]-=-. As for sufficiency, Balan, Casazza and Edidin [6] show that for almost every choice of Φ, A is injective whenever N ≥ 4M − 2, and recent work has leveraged more structured constructions to slightly ... |

32 | tight frames with maximal robustness to erasures
- Püschel, Kovačević, et al.
- 2005
(Show Context)
Citation Context ... spark, that is, ΦV has the property that every subcollection of M vectors spans. Full spark frames appear in a wide variety of applications. Explicit deterministic constructions of them are given in =-=[1, 41]-=-. For example, we can select the first M rows of the |V | × |V | discrete Fourier transform matrix, and take ΦV to be the columns of the resulting M ×|V | matrix; in this case, the fact that ΦV is ful... |

31 | Saving phase: Injectivity and Stability for phase retrieval, arXiv submission , arXiv: 1302.4618
- Bandeira, Cahill, et al.
(Show Context)
Citation Context ... [x] be reconstructed stably and efficiently? A first step toward solving (i) is determining how large N must be in order for A to be injective. It remains an open problem to find the smallest such N =-=[7]-=-, but embedding results in differential geometry give that N ≥ (4 + o(1))M is necessary [4, 27]. As for sufficiency, Balan, Casazza and Edidin [6] show that for almost every choice of Φ, A is injectiv... |

31 |
Extending x-ray crystallography to allow the imaging of noncrystalline materials, cells, and single protein complexes
- Miao, Ishikawa, et al.
(Show Context)
Citation Context ... x ∈ CM , consider measurements of the form z` := |〈x, ϕ`〉|2 + ν`, (1.1) where ν` is noise; we call these noisy intensity measurements. Several areas of imaging science, such as X-ray crystallography =-=[25, 37, 38]-=-, diffraction imaging [11], astronomy [17] and optics [49], use measurements of this form with the intent of reconstructing the original signal; this inverse problem is called phase retrieval. Note th... |

27 |
Diffractive imaging for periodic samples: retrieving one-dimensional concentration profiles across microfluidic channels. Acta Crystallographica Section A: Foundations of Crystallography
- Bunk, Diaz, et al.
(Show Context)
Citation Context ... the form z` := |〈x, ϕ`〉|2 + ν`, (1.1) where ν` is noise; we call these noisy intensity measurements. Several areas of imaging science, such as X-ray crystallography [25, 37, 38], diffraction imaging =-=[11]-=-, astronomy [17] and optics [49], use measurements of this form with the intent of reconstructing the original signal; this inverse problem is called phase retrieval. Note that in the measurement proc... |

26 | Stable phase retrieval with lowredundancy frames,” arXiv:1302.5487
- Bodmann, Hammen
- 2013
(Show Context)
Citation Context ...din [6] show that for almost every choice of Φ, A is injective whenever N ≥ 4M − 2, and recent work has leveraged more structured constructions to slightly decrease this number of measurement vectors =-=[10, 39]-=-. Though the community has investigated various conditions for injectivity, very little is known about how to stably and efficiently ∗Department of Mathematics, Princeton University, Princeton, NJ 085... |

23 | A Cheeger inequality for the graph connection Laplacian
- Bandeira, Singer, et al.
(Show Context)
Citation Context ...re each coordinate of D −1/2u to have unit modulus. Provided u has no entries which are zero, we can normalize the entries to form an estimate of ω, and as we show in the appendix (using results from =-=[9]-=-), this estimate is stable provided the spectral gap of G′ is sufficiently large. This spectral method is known in the literature as angular synchronization [46], and we summarize the procedure in Alg... |

19 |
A unified evaluation of iterative projection algorithms for phase retrieval,
- Marchesini
- 2006
(Show Context)
Citation Context ...(to maintain fidelity in the magnitudes) [21, 23, 24]. Unfortunately, the convergence of these algorithms (and various modifications thereof) is particularly sensitive to the choice of initial phases =-=[36]-=-. These deficiencies have prompted two important lines of research in phase retrieval: (i) For which measurement designs Φ is [x] 7→ |Φ∗x|2 injective? (ii) For which injective designs can [x] be recon... |

18 |
Phase retrieval from power spectra of masked signals
- Bandeira, Chen, et al.
(Show Context)
Citation Context ...on come from our use of different spectral methods. While the ideas in this paper can be applied for phase retrieval of 2-D images, we focus on the 1-D case for simplicity. Also, note that the sequel =-=[8]-=- leverages the techniques of this paper to construct masked Fourier measurements, thereby mimicking the illumination methodology of [12]; we suspect that these ideas can be similarly leveraged to tack... |

15 |
Four proofs for the cheeger inequality and graph partition algorithms
- Chung
- 2010
(Show Context)
Citation Context ... with at least q|V | vertices. To prove this theorem, we will apply a graph version of the Cheeger inequality, which provides a guarantee for Algorithm 2: Theorem 6.2 (Constructive Cheeger inequality =-=[16]-=-). Consider a graph G = (V,E) with spectral gap λ2. Then Algorithm 2 outputs a set of vertices S such that h(S) ≤ √2λ2. Proof. [Proof of Theorem 6.1] First, Algorithm 1 removes a set of vertices, whic... |

14 |
Ptychography and related diffractive imaging methods
- Rodenburg
(Show Context)
Citation Context ...ency components [31]. Another interesting approach is ptychography, in which overlapping spatial components Pix, Pjx ∈ CM are interfered with each other, and measurements have the form |F (Pix+Pjx)|2 =-=[44]-=-. Recently, vectorial phase retrieval was proposed, in which two unknown signals x, y ∈ CM are interfered with each other, and the measurements are |Fx|2, |Fy|2, |F (x+ y)|2 and |F (x+ iy)|2 [43]; fur... |

13 | Determination of all pure quantum states from a minimal number of observables, online arXiv:1306.1214v1 [math-ph] 5
- Mondragon, Voroninski
- 2013
(Show Context)
Citation Context ...din [6] show that for almost every choice of Φ, A is injective whenever N ≥ 4M − 2, and recent work has leveraged more structured constructions to slightly decrease this number of measurement vectors =-=[10, 39]-=-. Though the community has investigated various conditions for injectivity, very little is known about how to stably and efficiently ∗Department of Mathematics, Princeton University, Princeton, NJ 085... |

13 |
The question of phase retrieval in optics,” Opt
- Walther
- 1963
(Show Context)
Citation Context ... (1.1) where ν` is noise; we call these noisy intensity measurements. Several areas of imaging science, such as X-ray crystallography [25, 37, 38], diffraction imaging [11], astronomy [17] and optics =-=[49]-=-, use measurements of this form with the intent of reconstructing the original signal; this inverse problem is called phase retrieval. Note that in the measurement process (1.1), we inherently lose so... |

12 | An improved ptychographical phase retrieval algorithm for diffractive imaging,”
- Maiden, Rodenburg
- 2009
(Show Context)
Citation Context ...technique for quality phase retrieval, the reconstruction algorithms which are typically used, much like the classical algorithms in [21, 23, 24], are iterative and lack convergence guarantees (e.g., =-=[19, 34]-=-, though [42, 43] are noteworthy exceptions). Returning to measurements of the form (1.1), this paper combines ideas from both state-of-the-art theory and state-of-the-art practice by proposing an exc... |

12 |
A random walks view of spectral segmentation. In:
- Maila, Shi
- 2001
(Show Context)
Citation Context ...tering follows the intuition that a random walk on a graph tends to be trapped in sections of the graph which have few connections to the rest of the vertices (this intuition is made more explicit in =-=[35, 40]-=-). Moreover, the second eigenvector of the corresponding stochastic matrix tends to identify these sections. Note that when implementing spectral clustering, the values of E(Si, S c i ), vol(Si) and v... |

7 |
Quelques théorème de non-plongement pour les variétès differentiables
- Atiyah, Hirzebruch
- 1959
(Show Context)
Citation Context ...g how large N must be in order for A to be injective. It remains an open problem to find the smallest such N [7], but embedding results in differential geometry give that N ≥ (4 + o(1))M is necessary =-=[4, 27]-=-. As for sufficiency, Balan, Casazza and Edidin [6] show that for almost every choice of Φ, A is injective whenever N ≥ 4M − 2, and recent work has leveraged more structured constructions to slightly ... |

7 |
Numerically erasure-robust frames, Linear Algebra Appl.,
- Fickus, Mixon
- 2012
(Show Context)
Citation Context ...iction possible: If the members of ΦV are independent Gaussian vectors, then with high probability, every submatrix of columns ΦV ′′ with κ = |V ′′|/|V | sufficiently large has a stable pseudoinverse =-=[20]-=-. This concludes the phase retrieval procedure, briefly outlined below together with the measurement design. Measurement Design B (noisy case) • Fix d > 2 even and ε ∈ (0, d− 2√d− 1). • Given M , pick... |

7 |
On phase retrieval of finite-length sequences using the initial time sample
- Sahinoglou, Cabrera
- 1991
(Show Context)
Citation Context ...SA (dustin.mixon@afit.edu). 1 ar X iv :1 21 0. 77 52 v2s[ cs .IT ]s12sSe p 2 01 3 reconstruct in the injective case. In fact, some instances of the phase retrieval problem are known to be NP-complete =-=[45]-=-, and so any general reconstruction process is necessarily inefficient, assuming P 6= NP. This leads one to attempt provably stable and efficient reconstruction from measurements of the form (1.1) wit... |

5 | Vectorial phase retrieval for 1-d signals.
- Raz, Nadler, et al.
- 2013
(Show Context)
Citation Context ..., vectorial phase retrieval was proposed, in which two unknown signals x, y ∈ CM are interfered with each other, and the measurements are |Fx|2, |Fy|2, |F (x+ y)|2 and |F (x+ iy)|2 [43]; furthermore, =-=[42]-=- gives that almost every pair of signals is uniquely determined by these 4M scalar measurements, in which case both signals can be reconstructed using the polarization identity. While practitioners se... |

4 |
Vectorial phase retrieval for linear characterization of attosecond pulses.
- Raz
- 2011
(Show Context)
Citation Context ...x)|2 [44]. Recently, vectorial phase retrieval was proposed, in which two unknown signals x, y ∈ CM are interfered with each other, and the measurements are |Fx|2, |Fy|2, |F (x+ y)|2 and |F (x+ iy)|2 =-=[43]-=-; furthermore, [42] gives that almost every pair of signals is uniquely determined by these 4M scalar measurements, in which case both signals can be reconstructed using the polarization identity. Whi... |

3 | Relative-phase ambiguities in measurements of ultrashort pulses with well-separated multiple frequency components
- Keusters, Tan, et al.
(Show Context)
Citation Context ...g measurements of the form |F (x + Sx)|2 [29]; while popular in practice for ultrashort pulse measurement, SPIDER fails to accurately resolve the relative phase of well-separated frequency components =-=[31]-=-. Another interesting approach is ptychography, in which overlapping spatial components Pix, Pjx ∈ CM are interfered with each other, and measurements have the form |F (Pix+Pjx)|2 [44]. Recently, vect... |

2 |
available online at http://www.intechopen. com/books/holography-research-and-technologies/digital-holography-and-phase-retrieval
- Duadi, Margalit, et al.
- 2011
(Show Context)
Citation Context ...lography interferes the signal of interest x ∈ CM with a known reference signal y ∈ CM , taking measurements of the form |F (x+ ωy)|2, where ω ∈ C has unit modulus and F denotes the Fourier transform =-=[19]-=-; three such measurements (i.e., 3M scalar measurements) suffice for injectivity [50]. Alternatively, spectral phase interferometry for direct electric-field reconstruction (SPIDER) interferes the sig... |

1 |
Minimal frames for phase retrieval
- Wang
- 2013
(Show Context)
Citation Context ...M , taking measurements of the form |F (x+ ωy)|2, where ω ∈ C has unit modulus and F denotes the Fourier transform [19]; three such measurements (i.e., 3M scalar measurements) suffice for injectivity =-=[50]-=-. Alternatively, spectral phase interferometry for direct electric-field reconstruction (SPIDER) interferes the signal of interest x ∈ CM with time- and frequency-shifted versions of itself Sx ∈ CM , ... |