### Citations

349 | Introduction to the non-asymptotic analysis of random matrices
- Vershynin
- 2011
(Show Context)
Citation Context ...h avoid being trapped near saddle points, and efficiently obtain a local minimizer. Theorem 2.2 shows that for our problem, every local minimizer is global, and so for our problem, these algorithms efficiently obtain a global minimizer. 2.3 Key Steps in the Geometric Analysis Our proof strategy is fairly simple: we work out uniform bounds on the quantities for each of the four regions, and finally show the regions together cover the space. Since (1.1) and associated derivatives take the form of summation ofm independent random variables, the proof involves concentration and covering arguments [Ver12]. The main challenge in our argument will be the heavy tailed nature of f and its gradient. Proposition 2.3 (Negative Curvature) When m ≥ Cn log n, it holds with probability at least 1 − ca exp (−cbm/ logm)− ccm−1 that 1 ‖x‖2 [ xeiφ(z) xe−iφ(z) ]∗ ∇2f(z) [ xeiφ(z) xe−iφ(z) ] ≤ − 1 100 ‖x‖2 for all z ∈ R1 defined in (2.4). Here C, and ca to cc are positive absolute constants. Proof See Section 6.2 on Page 30. The expected gradient ∇zE [f(z)] is a linear combination of z and x. We will divide R2 into two overlapped regions,Rz2 andRh2 , roughly matching the case < (z∗∇zE [f(z)]) > 0 and the case ... |

293 |
Optimization algorithms on matrix manifolds.
- Absil, Mahony, et al.
- 2009
(Show Context)
Citation Context ...ts several sophisticated solvers for tackling optimization problems on Riemannian manifolds. The most developed solver is based on the TRM. This solver uses the truncated conjugate gradient (tCG; see, e.g., Section 7.5.4 of [CGT00]) method to (approximately) solve the trust-region subproblem (vs. the exact solver in our analysis). It also dynamically adjusts the step size. However, the original implementation (Manopt 2.0) is not adequate for our purposes. Their tCG solver uses the gradient as the initial search direction, which does not ensure that the TRM solver can escape from saddle points [ABG07, AMS09]. We modify the tCG solver, such that when the current gradient is small and there is a negative curvature direction (i.e., the current point is near a saddle point or a local maximizer for f(z)), the tCG solver explicitly uses the negative curvature direction10 as the initial search direction. This modification ensures the TRM solver always escapes saddle points/local maximizers with directional negative curvature. Hence, the modified TRM algorithm based on Manopt is expected to have the same qualitative behavior as the idealized version we analyzed. We fix n = 1, 000 and vary the ratiom/n fr... |

287 | Phase retrieval algorithms: A comparison
- Fienup
- 1982
(Show Context)
Citation Context ... |F(x) |is naturally termed (Fourier) phase retrieval (PR). 1 It is easy to see PR as a special version of GPR, with the ak’s the Fourier basis vectors. GPR also sees applications in electron microscopy [MIJ+02], diffraction and array imaging [BDP+07, CMP11], acoustics [BCE06, Bal10], quantum mechanics [Cor06, Rei65] and quantum information [HMW13]. We refer the reader to survey papers [SEC+15, JEH15] for accounts of recent developments in the theory, algorithms, and applications of GPR. For GPR, heuristic methods based on nonconvex optimization often work surprisingly well in practice (e.g., [Fie82, GS72], and many more cited in [SEC+15, JEH15]). However, investigation into provable recoverymethods, particularly based on nonconvex optimization, has started only relatively recently [NJS13, CESV13, CSV13, CL14, CLS15a, WdM15, VX14, ABFM14, CLS15b, CC15,WWS15]. The surprising effectiveness of nonconvex heuristics on GPR remains largely mysterious. In this paper, we take a step towards bridging this gap. We focus on a natural least-squares formulation1 – discussed systematically in [SEC+15, JEH15] and studied theoretically in [CLS15b, WWS15], minimizez∈Cn f(z) . = 1 2m m∑ k=1 ( y2k − |a∗kz| 2 )2 .... |

286 |
A practical algorithm for the determination of phase from image and diffraction plane pictures
- Gerchberg, Saxton
- 1972
(Show Context)
Citation Context ... |F(x) |is naturally termed (Fourier) phase retrieval (PR). 1 It is easy to see PR as a special version of GPR, with the ak’s the Fourier basis vectors. GPR also sees applications in electron microscopy [MIJ+02], diffraction and array imaging [BDP+07, CMP11], acoustics [BCE06, Bal10], quantum mechanics [Cor06, Rei65] and quantum information [HMW13]. We refer the reader to survey papers [SEC+15, JEH15] for accounts of recent developments in the theory, algorithms, and applications of GPR. For GPR, heuristic methods based on nonconvex optimization often work surprisingly well in practice (e.g., [Fie82, GS72], and many more cited in [SEC+15, JEH15]). However, investigation into provable recoverymethods, particularly based on nonconvex optimization, has started only relatively recently [NJS13, CESV13, CSV13, CL14, CLS15a, WdM15, VX14, ABFM14, CLS15b, CC15,WWS15]. The surprising effectiveness of nonconvex heuristics on GPR remains largely mysterious. In this paper, we take a step towards bridging this gap. We focus on a natural least-squares formulation1 – discussed systematically in [SEC+15, JEH15] and studied theoretically in [CLS15b, WWS15], minimizez∈Cn f(z) . = 1 2m m∑ k=1 ( y2k − |a∗kz| 2 )2 .... |

201 | Trust-region methods
- Conn, Gould, et al.
- 2000
(Show Context)
Citation Context ...astic gradientmethods [GHJY15] (see also [LSJR16]), curvilinear search [Gol80] and trust-regionmethods 3Note that the global sign cannot be recovered. 4The probability is with respect to drawing of ak’s. 3 Figure 2: Function landscape of (1.1) for x = [1; 0] and m → ∞. The only local and also global minimizers are ±x. There are two saddle points near ±[0; 1/ √ 2], around each there is a negative curvature direction along ±x. (Left) The function graph; (Right) The same function visualized as a color image. The measurement vectors ak’s are taken as i.i.d. standard real Gaussian in this version. [CGT00, NP06, SQW15b]. The key property that the methods must possess is the ability to escape saddle points at which the Hessian has a strictly negative eigenvalue. We corroborate this claim by developing a second-order trust-region method for this problem, and prove that (Theorem 3.10) (i) from any initialization, it efficiently obtains a close approximation (i.e., up to numerical precision) of the target x (up to a global phase) and (ii) it exhibits quadratic convergence in the vicinity of the global minimizers. In sum, our geometric analysis produces the following result. Informal Statement ofOurMainResults; S... |

132 |
Phaselift : exact and stable signal recovery from magnitude measurements via convex programming
- Candes, Strohmer, et al.
(Show Context)
Citation Context ...icroscopy [MIJ+02], diffraction and array imaging [BDP+07, CMP11], acoustics [BCE06, Bal10], quantum mechanics [Cor06, Rei65] and quantum information [HMW13]. We refer the reader to survey papers [SEC+15, JEH15] for accounts of recent developments in the theory, algorithms, and applications of GPR. For GPR, heuristic methods based on nonconvex optimization often work surprisingly well in practice (e.g., [Fie82, GS72], and many more cited in [SEC+15, JEH15]). However, investigation into provable recoverymethods, particularly based on nonconvex optimization, has started only relatively recently [NJS13, CESV13, CSV13, CL14, CLS15a, WdM15, VX14, ABFM14, CLS15b, CC15,WWS15]. The surprising effectiveness of nonconvex heuristics on GPR remains largely mysterious. In this paper, we take a step towards bridging this gap. We focus on a natural least-squares formulation1 – discussed systematically in [SEC+15, JEH15] and studied theoretically in [CLS15b, WWS15], minimizez∈Cn f(z) . = 1 2m m∑ k=1 ( y2k − |a∗kz| 2 )2 . (1.1) We assume the ak’s are independent identically distributed (i.i.d.) complex Gaussian: ak = 1√ 2 (Xk + iYk) , with Xk, Yk ∼ N (0, In) independent. (1.2) f(z) is a fourth-order polynomial in z, and is nonconvex. A-priori, there is little reason to beli... |

111 |
Concentration inequalities; A nonasymptotic theory of independence.
- Boucheron, Lugosi, et al.
- 2013
(Show Context)
Citation Context ... P (∣∣∣∣∣ N∑ k=1 bkXk ∣∣∣∣∣ ≥ t ) ≤ e exp ( − ct 2 K2 ‖b‖22 ) . (A.2) Here c is a universal constant. Lemma A.6 (Bernstein-type Inequality, Proposition 5.17 of [Ver12]) LetX1, · · · , XN be independent centered sub-exponetial random variables, and letK = maxi ‖Xi‖ψ1 , where the sub-exponential norm ‖Xi‖ψ1 . = sup p≥1 p−1 (E [|X|p])1/p . (A.3) Then for every b = [b1; · · · ; bN ] ∈ CN and every t ≥ 0, we have P (∣∣∣∣∣ N∑ k=1 bkXk ∣∣∣∣∣ ≥ t ) ≤ 2 exp ( −cmin ( t2 K2 ‖b‖22 , t K ‖b‖∞ )) . (A.4) Here c is a universal constant. Lemma A.7 (Subgaussian Lower Tail for Nonnegative RV’s, Problem 2.9 of [BLM13]) LetX1, . . . , XN be i.i.d. copies of the nonnegative random variable X with finite second moment. Then it holds that P [ 1 N N∑ i=1 (Xi − E [Xi]) < −t ] ≤ exp ( −Nt 2 2σ2 ) for any t > 0, where σ2 = E [ X2 ] . Proof For any λ > 0, we have logE [ e−λ(X−E[X]) ] = λE [X] + logE [ e−λX ] ≤ λE [X] + E [ e−λX ] − 1, where the last inequality holds thanks to log u ≤ u − 1 for all u > 0. Moreover, using the fact eu ≤ 1 + u+ u2/2 for all u ≤ 0, we obtain logE [ e−λ(X−E[X]) ] ≤ 1 2 λ2E [ X2 ] ⇐⇒ E [ e−λ(X−E[X]) ] ≤ exp ( 1 2 λ2E [ X2 ]) . Thus, by the usual exponential transform trick, we obtain that... |

72 |
Phase retrieval in crystallography and optics
- Millane
- 1990
(Show Context)
Citation Context ...hase, as xeiφ for all φ ∈ [0, 2π) gives exactly the same set of measurements. The generalized phase retrieval problem asks whether it is possible to recover x, up to this fundamental ambiguity: Generalized Phase Retrieval Problem: Is it possible to efficiently recover an unknown x from yk = |a∗kx |(k = 1, . . . ,m), up to a global phase factor eiφ? This problem has attracted substantial recent interest, due to its connections to fields such as crystallography, optical imaging and astronomy. In these areas, one often has access only to the Fourier magnitudes of a complex signal x, i.e., |F(x) |[Mil90, Rob93, Wal63, DF87]. The phase information is hard or infeasible to record due to physical constraints. The problem of recovering the signal x from its Fourier magnitudes |F(x) |is naturally termed (Fourier) phase retrieval (PR). 1 It is easy to see PR as a special version of GPR, with the ak’s the Fourier basis vectors. GPR also sees applications in electron microscopy [MIJ+02], diffraction and array imaging [BDP+07, CMP11], acoustics [BCE06, Bal10], quantum mechanics [Cor06, Rei65] and quantum information [HMW13]. We refer the reader to survey papers [SEC+15, JEH15] for accounts of recent developments in the t... |

67 |
Cubic regularization of Newton method and its global performance.
- Nesterov, Polyak
- 2006
(Show Context)
Citation Context ...astic gradientmethods [GHJY15] (see also [LSJR16]), curvilinear search [Gol80] and trust-regionmethods 3Note that the global sign cannot be recovered. 4The probability is with respect to drawing of ak’s. 3 Figure 2: Function landscape of (1.1) for x = [1; 0] and m → ∞. The only local and also global minimizers are ±x. There are two saddle points near ±[0; 1/ √ 2], around each there is a negative curvature direction along ±x. (Left) The function graph; (Right) The same function visualized as a color image. The measurement vectors ak’s are taken as i.i.d. standard real Gaussian in this version. [CGT00, NP06, SQW15b]. The key property that the methods must possess is the ability to escape saddle points at which the Hessian has a strictly negative eigenvalue. We corroborate this claim by developing a second-order trust-region method for this problem, and prove that (Theorem 3.10) (i) from any initialization, it efficiently obtains a close approximation (i.e., up to numerical precision) of the target x (up to a global phase) and (ii) it exhibits quadratic convergence in the vicinity of the global minimizers. In sum, our geometric analysis produces the following result. Informal Statement ofOurMainResults; S... |

62 | Trust-region methods on Riemannian manifolds
- Absil, Baker, et al.
- 2007
(Show Context)
Citation Context ...ts several sophisticated solvers for tackling optimization problems on Riemannian manifolds. The most developed solver is based on the TRM. This solver uses the truncated conjugate gradient (tCG; see, e.g., Section 7.5.4 of [CGT00]) method to (approximately) solve the trust-region subproblem (vs. the exact solver in our analysis). It also dynamically adjusts the step size. However, the original implementation (Manopt 2.0) is not adequate for our purposes. Their tCG solver uses the gradient as the initial search direction, which does not ensure that the TRM solver can escape from saddle points [ABG07, AMS09]. We modify the tCG solver, such that when the current gradient is small and there is a negative curvature direction (i.e., the current point is near a saddle point or a local maximizer for f(z)), the tCG solver explicitly uses the negative curvature direction10 as the initial search direction. This modification ensures the TRM solver always escapes saddle points/local maximizers with directional negative curvature. Hence, the modified TRM algorithm based on Manopt is expected to have the same qualitative behavior as the idealized version we analyzed. We fix n = 1, 000 and vary the ratiom/n fr... |

54 | Low-rank matrix completion using alternating minimization. - Jain, Netrapalli, et al. - 2013 |

53 |
Philosophic Foundations of Quantum Mechanics
- Reichenbach
- 1944
(Show Context)
Citation Context ...nd astronomy. In these areas, one often has access only to the Fourier magnitudes of a complex signal x, i.e., |F(x) |[Mil90, Rob93, Wal63, DF87]. The phase information is hard or infeasible to record due to physical constraints. The problem of recovering the signal x from its Fourier magnitudes |F(x) |is naturally termed (Fourier) phase retrieval (PR). 1 It is easy to see PR as a special version of GPR, with the ak’s the Fourier basis vectors. GPR also sees applications in electron microscopy [MIJ+02], diffraction and array imaging [BDP+07, CMP11], acoustics [BCE06, Bal10], quantum mechanics [Cor06, Rei65] and quantum information [HMW13]. We refer the reader to survey papers [SEC+15, JEH15] for accounts of recent developments in the theory, algorithms, and applications of GPR. For GPR, heuristic methods based on nonconvex optimization often work surprisingly well in practice (e.g., [Fie82, GS72], and many more cited in [SEC+15, JEH15]). However, investigation into provable recoverymethods, particularly based on nonconvex optimization, has started only relatively recently [NJS13, CESV13, CSV13, CL14, CLS15a, WdM15, VX14, ABFM14, CLS15b, CC15,WWS15]. The surprising effectiveness of nonconvex heur... |

49 | Painless reconstruction from magnitudes of frame coefficients
- Balan, Bodmann, et al.
- 2009
(Show Context)
Citation Context ...f a nonconvex formulation, we derived a provable efficient algorithm for recovering square invertible dictionaries when the coefficient matrix has a constant fraction of nonzero entries. Previous results required the dictionary matrix to have far fewer nonzero entries. [SQW15b] provides a high-level overview of the common geometric structure that arises in dictionary learning, GPR and several other problems. Despite these similarities, GPR raises several novel technical challenges: the objective is heavy-tailed, and minimizing the number of measurements is important. 5Another line of research [BCE06, BBCE09, ABFM14] seeks to co-design the measurements and recovery algorithms based on frame- or graph-theoretic tools. 6In addition, [CC15] shows that the measurements can be non-adaptive, in the sense that a single, randomly chosen collection of vectors ai can simultaneously recover every x ∈ Cn. Results in [NJS13, CLS15b] and this paper pertain only to adaptive measurements that recover any fixed signal x with high probability. 5 Our work sits amid the recent surge of work on provable nonconvex heuristics for practical problems. Besides GPR studied here, this line of work includes low-rank matrix recovery [... |

47 |
Fienup, "Phase Retrieval and Image Reconstruction for Astronomy
- Dainty, R
- 1987
(Show Context)
Citation Context ...hase, as xeiφ for all φ ∈ [0, 2π) gives exactly the same set of measurements. The generalized phase retrieval problem asks whether it is possible to recover x, up to this fundamental ambiguity: Generalized Phase Retrieval Problem: Is it possible to efficiently recover an unknown x from yk = |a∗kx |(k = 1, . . . ,m), up to a global phase factor eiφ? This problem has attracted substantial recent interest, due to its connections to fields such as crystallography, optical imaging and astronomy. In these areas, one often has access only to the Fourier magnitudes of a complex signal x, i.e., |F(x) |[Mil90, Rob93, Wal63, DF87]. The phase information is hard or infeasible to record due to physical constraints. The problem of recovering the signal x from its Fourier magnitudes |F(x) |is naturally termed (Fourier) phase retrieval (PR). 1 It is easy to see PR as a special version of GPR, with the ak’s the Fourier basis vectors. GPR also sees applications in electron microscopy [MIJ+02], diffraction and array imaging [BDP+07, CMP11], acoustics [BCE06, Bal10], quantum mechanics [Cor06, Rei65] and quantum information [HMW13]. We refer the reader to survey papers [SEC+15, JEH15] for accounts of recent developments in the t... |

41 | Simultaneously structured models with application to sparse and low-rank matrices, arXiv preprint arXiv:1212.3753 - Oymak, Jalali, et al. - 2012 |

38 | Sparse signal recovery from quadratic measurements via convex programming
- Li, Voroninski
(Show Context)
Citation Context .... It is interesting to see if the gaps can be closed. Our current analysis pertains to Gaussian measurements only which are not practical, it is important to extend the geometric analysis to more practical measurement schemes, such as t-designs [GKK13] and masked Fourier transformmeasurements [CLS15a]. A preliminary study of the low-dimensional function landscape for the latter scheme produces very positive result; see Figure 5. Sparse phase retrieval. A special case of GPR is when the underlying signal x is known to be sparse, which can be considered as a quadratic compressed sensing problem [OYVS13, OYDS13, OYDS12, LV13, JOH13, SBE14]. Since x is sparse, the lifted matrixX = xx∗ is sparse and has rank one. Thus, existing convex relaxation methods [OYVS13, OYDS13, LV13, JOH13] formulated it as a simultaneously low-rank and sparse recovery problem. For the latter problem, however, known convex relaxations are suboptimal [OJF+12, MHWG14]. Let k be the number of nonzeros in the target signal. [LV13, JOH13] showed that natural convex relaxations require C5k2 log n samples for correct recovery, instead of the optimal order O(k log(n/k). A similar gap is also observed with 12Numerics in [CC15] suggest that under the same measurem... |

32 | Array imaging using intensity-only measurements - Chai, Moscoso, et al. |

32 | Quantum tomography under prior information,” arXiv:1109.5478
- Heinosaari, Mazzarella, et al.
- 2011
(Show Context)
Citation Context ... has access only to the Fourier magnitudes of a complex signal x, i.e., |F(x) |[Mil90, Rob93, Wal63, DF87]. The phase information is hard or infeasible to record due to physical constraints. The problem of recovering the signal x from its Fourier magnitudes |F(x) |is naturally termed (Fourier) phase retrieval (PR). 1 It is easy to see PR as a special version of GPR, with the ak’s the Fourier basis vectors. GPR also sees applications in electron microscopy [MIJ+02], diffraction and array imaging [BDP+07, CMP11], acoustics [BCE06, Bal10], quantum mechanics [Cor06, Rei65] and quantum information [HMW13]. We refer the reader to survey papers [SEC+15, JEH15] for accounts of recent developments in the theory, algorithms, and applications of GPR. For GPR, heuristic methods based on nonconvex optimization often work surprisingly well in practice (e.g., [Fie82, GS72], and many more cited in [SEC+15, JEH15]). However, investigation into provable recoverymethods, particularly based on nonconvex optimization, has started only relatively recently [NJS13, CESV13, CSV13, CL14, CLS15a, WdM15, VX14, ABFM14, CLS15b, CC15,WWS15]. The surprising effectiveness of nonconvex heuristics on GPR remains largely my... |

27 | Manopt, a matlab toolbox for optimization on manifolds.
- Boumal, Mishra, et al.
- 2014
(Show Context)
Citation Context ...the analysis, but also render the TRM algorithm impractical. In practice, the trust-region subproblem is never exactly solved, and the trust-region step size is adjusted to the local geometry, by backtracking. It is relatively straightforward to modify our analysis to account for inexact subproblem solvers; for sake of brevity, we do not pursue this here. In this section, we investigate experimentally the number of measurementsm required to ensure that f(z) is well-structured, in the sense of our theorems. This entails solving large instances of f(z). To this end, we deploy the Manopt toolbox [BMAS14]9. Manopt is a user-friendly Matlab toolbox 9Available online: http://www.manopt.org. 22 that implements several sophisticated solvers for tackling optimization problems on Riemannian manifolds. The most developed solver is based on the TRM. This solver uses the truncated conjugate gradient (tCG; see, e.g., Section 7.5.4 of [CGT00]) method to (approximately) solve the trust-region subproblem (vs. the exact solver in our analysis). It also dynamically adjusts the step size. However, the original implementation (Manopt 2.0) is not adequate for our purposes. Their tCG solver uses the gradient as ... |

27 | GESPAR: Efficient phase retrieval of sparse signals
- Shechtman, Beck, et al.
- 2014
(Show Context)
Citation Context .... It is interesting to see if the gaps can be closed. Our current analysis pertains to Gaussian measurements only which are not practical, it is important to extend the geometric analysis to more practical measurement schemes, such as t-designs [GKK13] and masked Fourier transformmeasurements [CLS15a]. A preliminary study of the low-dimensional function landscape for the latter scheme produces very positive result; see Figure 5. Sparse phase retrieval. A special case of GPR is when the underlying signal x is known to be sparse, which can be considered as a quadratic compressed sensing problem [OYVS13, OYDS13, OYDS12, LV13, JOH13, SBE14]. Since x is sparse, the lifted matrixX = xx∗ is sparse and has rank one. Thus, existing convex relaxation methods [OYVS13, OYDS13, LV13, JOH13] formulated it as a simultaneously low-rank and sparse recovery problem. For the latter problem, however, known convex relaxations are suboptimal [OJF+12, MHWG14]. Let k be the number of nonzeros in the target signal. [LV13, JOH13] showed that natural convex relaxations require C5k2 log n samples for correct recovery, instead of the optimal order O(k log(n/k). A similar gap is also observed with 12Numerics in [CC15] suggest that under the same measurem... |

24 | Curvilinear path steplength algorithms for minimization which use directions of negative curvature
- Goldfarb
- 1980
(Show Context)
Citation Context ...2π); (ii) at any point in Cn, either the gradient is large, or the curvature is negative in a certain direction, or it is near a minimizer. Moreover, in the vicinity of the minimizers, on the orthogonal complement of a single flat direction (which occurs because f(zeiφ) = f(z) for every z, φ), the objective function is strongly convex. Because of this global geometry, a wide range of efficient iterative methods can obtain a global minimizer to f(z), regardless of initialization. Examples include the noisy gradient and stochastic gradientmethods [GHJY15] (see also [LSJR16]), curvilinear search [Gol80] and trust-regionmethods 3Note that the global sign cannot be recovered. 4The probability is with respect to drawing of ak’s. 3 Figure 2: Function landscape of (1.1) for x = [1; 0] and m → ∞. The only local and also global minimizers are ±x. There are two saddle points near ±[0; 1/ √ 2], around each there is a negative curvature direction along ±x. (Left) The function graph; (Right) The same function visualized as a color image. The measurement vectors ak’s are taken as i.i.d. standard real Gaussian in this version. [CGT00, NP06, SQW15b]. The key property that the methods must possess is the a... |

23 | Phase retrieval using alternating minimization
- Netrapalli, Jain, et al.
- 2013
(Show Context)
Citation Context ...icroscopy [MIJ+02], diffraction and array imaging [BDP+07, CMP11], acoustics [BCE06, Bal10], quantum mechanics [Cor06, Rei65] and quantum information [HMW13]. We refer the reader to survey papers [SEC+15, JEH15] for accounts of recent developments in the theory, algorithms, and applications of GPR. For GPR, heuristic methods based on nonconvex optimization often work surprisingly well in practice (e.g., [Fie82, GS72], and many more cited in [SEC+15, JEH15]). However, investigation into provable recoverymethods, particularly based on nonconvex optimization, has started only relatively recently [NJS13, CESV13, CSV13, CL14, CLS15a, WdM15, VX14, ABFM14, CLS15b, CC15,WWS15]. The surprising effectiveness of nonconvex heuristics on GPR remains largely mysterious. In this paper, we take a step towards bridging this gap. We focus on a natural least-squares formulation1 – discussed systematically in [SEC+15, JEH15] and studied theoretically in [CLS15b, WWS15], minimizez∈Cn f(z) . = 1 2m m∑ k=1 ( y2k − |a∗kz| 2 )2 . (1.1) We assume the ak’s are independent identically distributed (i.i.d.) complex Gaussian: ak = 1√ 2 (Xk + iYk) , with Xk, Yk ∼ N (0, In) independent. (1.2) f(z) is a fourth-order polynomial in z, and is nonconvex. A-priori, there is little reason to beli... |

21 | Phase retrieval with polarization
- Alexeev, Bandeira, et al.
(Show Context)
Citation Context ...icroscopy [MIJ+02], diffraction and array imaging [BDP+07, CMP11], acoustics [BCE06, Bal10], quantum mechanics [Cor06, Rei65] and quantum information [HMW13]. We refer the reader to survey papers [SEC+15, JEH15] for accounts of recent developments in the theory, algorithms, and applications of GPR. For GPR, heuristic methods based on nonconvex optimization often work surprisingly well in practice (e.g., [Fie82, GS72], and many more cited in [SEC+15, JEH15]). However, investigation into provable recoverymethods, particularly based on nonconvex optimization, has started only relatively recently [NJS13, CESV13, CSV13, CL14, CLS15a, WdM15, VX14, ABFM14, CLS15b, CC15,WWS15]. The surprising effectiveness of nonconvex heuristics on GPR remains largely mysterious. In this paper, we take a step towards bridging this gap. We focus on a natural least-squares formulation1 – discussed systematically in [SEC+15, JEH15] and studied theoretically in [CLS15b, WWS15], minimizez∈Cn f(z) . = 1 2m m∑ k=1 ( y2k − |a∗kz| 2 )2 . (1.1) We assume the ak’s are independent identically distributed (i.i.d.) complex Gaussian: ak = 1√ 2 (Xk + iYk) , with Xk, Yk ∼ N (0, In) independent. (1.2) f(z) is a fourth-order polynomial in z, and is nonconvex. A-priori, there is little reason to beli... |

18 | High resolution 3D X-Ray diffraction microscopy, - Miao, Ishikawa, et al. - 2002 |

18 | Phase retrieval with application to optical imaging - Shechtman, Eldar, et al. |

17 | Matrix completion from a few entries. Information Theory, - Keshavan, Montanari, et al. - 2010 |

16 | Understanding alternating minimization for matrix completion. - Hardt - 2014 |

13 |
The pauli problem, state reconstruction and quantumreal numbers
- Corbett
(Show Context)
Citation Context ...nd astronomy. In these areas, one often has access only to the Fourier magnitudes of a complex signal x, i.e., |F(x) |[Mil90, Rob93, Wal63, DF87]. The phase information is hard or infeasible to record due to physical constraints. The problem of recovering the signal x from its Fourier magnitudes |F(x) |is naturally termed (Fourier) phase retrieval (PR). 1 It is easy to see PR as a special version of GPR, with the ak’s the Fourier basis vectors. GPR also sees applications in electron microscopy [MIJ+02], diffraction and array imaging [BDP+07, CMP11], acoustics [BCE06, Bal10], quantum mechanics [Cor06, Rei65] and quantum information [HMW13]. We refer the reader to survey papers [SEC+15, JEH15] for accounts of recent developments in the theory, algorithms, and applications of GPR. For GPR, heuristic methods based on nonconvex optimization often work surprisingly well in practice (e.g., [Fie82, GS72], and many more cited in [SEC+15, JEH15]). However, investigation into provable recoverymethods, particularly based on nonconvex optimization, has started only relatively recently [NJS13, CESV13, CSV13, CL14, CLS15a, WdM15, VX14, ABFM14, CLS15b, CC15,WWS15]. The surprising effectiveness of nonconvex heur... |

12 | On signal reconstruction from its spectrogram,
- Balan
- 2010
(Show Context)
Citation Context ...crystallography, optical imaging and astronomy. In these areas, one often has access only to the Fourier magnitudes of a complex signal x, i.e., |F(x) |[Mil90, Rob93, Wal63, DF87]. The phase information is hard or infeasible to record due to physical constraints. The problem of recovering the signal x from its Fourier magnitudes |F(x) |is naturally termed (Fourier) phase retrieval (PR). 1 It is easy to see PR as a special version of GPR, with the ak’s the Fourier basis vectors. GPR also sees applications in electron microscopy [MIJ+02], diffraction and array imaging [BDP+07, CMP11], acoustics [BCE06, Bal10], quantum mechanics [Cor06, Rei65] and quantum information [HMW13]. We refer the reader to survey papers [SEC+15, JEH15] for accounts of recent developments in the theory, algorithms, and applications of GPR. For GPR, heuristic methods based on nonconvex optimization often work surprisingly well in practice (e.g., [Fie82, GS72], and many more cited in [SEC+15, JEH15]). However, investigation into provable recoverymethods, particularly based on nonconvex optimization, has started only relatively recently [NJS13, CESV13, CSV13, CL14, CLS15a, WdM15, VX14, ABFM14, CLS15b, CC15,WWS15]. The surprisi... |

12 | A partial derandomization of phaselift using spherical designs, arXiv preprint arXiv:1310.2267
- Gross, Krahmer, et al.
- 2013
(Show Context)
Citation Context ...chemes. Our result (Theorem 2.2 and Theorem 3.10) indicates thatm ≥ C1n log3(n) samples are sufficient to guarantee the favorable geometric property and efficient recovery, while our simulations suggested that C2n log(n) or even C3n is enough. For efficient recovery only, m ≥ C4n are known to be sufficient [CC15] (and for all signals; see also [CLS15b]). It is interesting to see if the gaps can be closed. Our current analysis pertains to Gaussian measurements only which are not practical, it is important to extend the geometric analysis to more practical measurement schemes, such as t-designs [GKK13] and masked Fourier transformmeasurements [CLS15a]. A preliminary study of the low-dimensional function landscape for the latter scheme produces very positive result; see Figure 5. Sparse phase retrieval. A special case of GPR is when the underlying signal x is known to be sparse, which can be considered as a quadratic compressed sensing problem [OYVS13, OYDS13, OYDS12, LV13, JOH13, SBE14]. Since x is sparse, the lifted matrixX = xx∗ is sparse and has rank one. Thus, existing convex relaxation methods [OYVS13, OYDS13, LV13, JOH13] formulated it as a simultaneously low-rank and sparse recovery ... |

10 | Guaranteed matrix completion via nonconvex factorization. - Sun, Luo - 2015 |

8 | Animashree Anandkumar, Prateek Jain, Praneeth Netrapalli, and Rashish Tandon, Learning sparsely used overcomplete dictionaries via alternating minimization, arXiv preprint arXiv:1310.7991 - Agarwal - 2013 |

8 |
Escaping from saddle points—online stochastic gradient for tensor decomposition.
- Ge, Huang, et al.
- 2015
(Show Context)
Citation Context ...imizers to (1.1) are the target xeiφ for φ ∈ [0, 2π); (ii) at any point in Cn, either the gradient is large, or the curvature is negative in a certain direction, or it is near a minimizer. Moreover, in the vicinity of the minimizers, on the orthogonal complement of a single flat direction (which occurs because f(zeiφ) = f(z) for every z, φ), the objective function is strongly convex. Because of this global geometry, a wide range of efficient iterative methods can obtain a global minimizer to f(z), regardless of initialization. Examples include the noisy gradient and stochastic gradientmethods [GHJY15] (see also [LSJR16]), curvilinear search [Gol80] and trust-regionmethods 3Note that the global sign cannot be recovered. 4The probability is with respect to drawing of ak’s. 3 Figure 2: Function landscape of (1.1) for x = [1; 0] and m → ∞. The only local and also global minimizers are ±x. There are two saddle points near ±[0; 1/ √ 2], around each there is a negative curvature direction along ±x. (Left) The function graph; (Right) The same function visualized as a color image. The measurement vectors ak’s are taken as i.i.d. standard real Gaussian in this version. [CGT00, NP06, SQW15b]. The key... |

8 | andMaryWootters, Fast matrix completion without the condition number, - Hardt - 2014 |

7 | Animashree Anandkumar, and Praneeth Netrapalli, Exact recovery of sparsely used overcomplete dictionaries, arXiv preprint arXiv:1309.1952 - Agarwal - 2013 |

7 | Near optimal compressed sensing of sparse rank-one matrices via sparse power factorization, arXiv preprint arXiv:1312.0525
- Lee, Wu, et al.
- 2013
(Show Context)
Citation Context ...LS15b] and this paper pertain only to adaptive measurements that recover any fixed signal x with high probability. 5 Our work sits amid the recent surge of work on provable nonconvex heuristics for practical problems. Besides GPR studied here, this line of work includes low-rank matrix recovery [KMO10, JNS13, Har14, HW14, NNS+14, JN14, SL14, WCCL15, SRO15, ZL15, TBSR15, CW15], tensor recovery [JO14, AGJ14a, AGJ14b, AJSN15, GHJY15], structured element pursuit [QSW14, HSSS15], dictionary learning [AAJ+13, AGM13, AAN13, ABGM14, AGMM15, SQW15a], mixed regression [YCS13, SA14], blind deconvolution [LWB13, LJ15, LLJB15], super resolution [EW15], phase synchronization [Bou16], numerical linear algebra [JJKN15], and so forth. Most of the methods adopt the strategy of initialization plus local refinement we alluded to above. In contrast, our geometric analysis allows flexible algorithm design (i.e., separation of geometry and algorithms) and gives some clues as to the behavior of nonconvex heuristics used in practice, which often succeed without clever initialization. Recovering low-rank positive semidefinite matrices. The phase retrieval problem has a natural generalization to recovering low-rank positive semi... |

7 | CPRL – An extension of compressive sensing to the phase retrieval problem
- Ohlsson, Yang, et al.
- 2012
(Show Context)
Citation Context .... It is interesting to see if the gaps can be closed. Our current analysis pertains to Gaussian measurements only which are not practical, it is important to extend the geometric analysis to more practical measurement schemes, such as t-designs [GKK13] and masked Fourier transformmeasurements [CLS15a]. A preliminary study of the low-dimensional function landscape for the latter scheme produces very positive result; see Figure 5. Sparse phase retrieval. A special case of GPR is when the underlying signal x is known to be sparse, which can be considered as a quadratic compressed sensing problem [OYVS13, OYDS13, OYDS12, LV13, JOH13, SBE14]. Since x is sparse, the lifted matrixX = xx∗ is sparse and has rank one. Thus, existing convex relaxation methods [OYVS13, OYDS13, LV13, JOH13] formulated it as a simultaneously low-rank and sparse recovery problem. For the latter problem, however, known convex relaxations are suboptimal [OJF+12, MHWG14]. Let k be the number of nonzeros in the target signal. [LV13, JOH13] showed that natural convex relaxations require C5k2 log n samples for correct recovery, instead of the optimal order O(k log(n/k). A similar gap is also observed with 12Numerics in [CC15] suggest that under the same measurem... |

5 | Simple, efficient, and neural algorithms for sparse coding, arXiv preprint arXiv:1503.00778 - Arora, Ge, et al. - 2015 |

5 | Fast exact matrix completion with finite samples, arXiv preprint arXiv:1411.1087 - Jain, PraneethNetrapalli - 2014 |

5 | Provable tensor factorization with missing data,
- Jain, Oh
- 2014
(Show Context)
Citation Context ...ls. 6In addition, [CC15] shows that the measurements can be non-adaptive, in the sense that a single, randomly chosen collection of vectors ai can simultaneously recover every x ∈ Cn. Results in [NJS13, CLS15b] and this paper pertain only to adaptive measurements that recover any fixed signal x with high probability. 5 Our work sits amid the recent surge of work on provable nonconvex heuristics for practical problems. Besides GPR studied here, this line of work includes low-rank matrix recovery [KMO10, JNS13, Har14, HW14, NNS+14, JN14, SL14, WCCL15, SRO15, ZL15, TBSR15, CW15], tensor recovery [JO14, AGJ14a, AGJ14b, AJSN15, GHJY15], structured element pursuit [QSW14, HSSS15], dictionary learning [AAJ+13, AGM13, AAN13, ABGM14, AGMM15, SQW15a], mixed regression [YCS13, SA14], blind deconvolution [LWB13, LJ15, LLJB15], super resolution [EW15], phase synchronization [Bou16], numerical linear algebra [JJKN15], and so forth. Most of the methods adopt the strategy of initialization plus local refinement we alluded to above. In contrast, our geometric analysis allows flexible algorithm design (i.e., separation of geometry and algorithms) and gives some clues as to the behavior of nonconvex heuristics used in practice, which oft... |

5 |
Complete dictionary recovery over the sphere, arXiv preprint arXiv:1504.06785
- Sun, Qu, et al.
- 2015
(Show Context)
Citation Context ...used in [CLS15b] lands the iterate sequence in the region in which the objective is (restrictedly) strongly convex (R3 in Theorem 2.2). The analysis of [CLS15b] is based on a property that ensures the gradient descent method is locally contractive near the target set, which is closely linked to local convexity. [Sol14] and [WWS15] explicitly established local strong convexity near the target set for GPR in Rn. Geometric analysis of other nonconvex problems. The approach taken here is similar in spirit to our recent geometric analysis of a nonconvex formulation for complete dictionary learning [SQW15a]. For that problem, we also identified a similar geometric structure that allows efficient global optimization without special initialization. There, by analyzing the geometry of a nonconvex formulation, we derived a provable efficient algorithm for recovering square invertible dictionaries when the coefficient matrix has a constant fraction of nonzero entries. Previous results required the dictionary matrix to have far fewer nonzero entries. [SQW15b] provides a high-level overview of the common geometric structure that arises in dictionary learning, GPR and several other problems. Despite the... |

5 | Global convergence of stochastic gradient descent for some nonconvex matrix problems.
- Sa, Olukotun, et al.
- 2015
(Show Context)
Citation Context ...rieval problem has a natural generalization to recovering low-rank positive semidefinite matrices. Consider the problem of recovering an unknown rank-r matrix M 0 in Rn×n from linear measurement of the form zk = tr(AkM) with symmetricAk for k = 1, . . . ,m. One can solve the problem by considering the “factorized” version: recoveringX ∈ Rn×r (up to right invertible transform) from measurements zk = tr(X ∗AkX). This is a natural generalization of GPR, as one can write the GPR measurements as y2k = |a∗kx| 2 = x∗(aka ∗ k)x. This generalization and related problems have recently been studied in [SRO15, ZL15, TBSR15, CW15]. 1.5 Notations, Organization, and Reproducible Research Basic notations and facts. Throughout the paper, we define complex inner product as: 〈a, b〉 .= a∗b for any a, b ∈ Cn. We use CSn−1 for the complex unit sphere in Cn. CSn−1(λ) with λ > 0 denotes the centered complex sphere with radius λ in Cn. Similarly, we use CBn(λ) to denote the centered complex ball of radius λ. We use CN (k) for a standard complex Gaussian vector of length k defined in (1.2). We reserve C and c, and their indexed versions to denote absolute constants. Their value vary with the context. Let < (z) ∈ Rn and =(z) ∈ Rn de... |

4 |
Optimal rates of convergence for noisy sparse phase retrieval via thresholded wirtinger flow, arXiv preprint arXiv:1506.03382
- Cai, Li, et al.
- 2015
(Show Context)
Citation Context ...and hence “initialization-free" algorithm may need the additional complexity. 13The main limitation in this experiment was not the TRM solver, but the need to store the vectors a1, . . .am. For other measurement models, such as the coded diffraction model [CLS15a], “matrix-free” calculation is possible, and storage is no longer a bottleneck. 24 Figure 5: Function landscape of (1.1) for x = [1; 0] and m → ∞ for the masked Fourier transform measurements (coded diffraction model [CLS15a]). The landscape is qualitatively similar to that for the Gaussian model (Figure 2). certain nonconvex methods [CLM15]. It is tempting to ask whether novel nonconvex formulations and analogous geometric analysis as taken here could shed light on this problem. Other structured nonconvex problems. We have mentioned recent surge of works on provable nonconvex heuristics [JNS13, Har14, HW14, NNS+14, JN14, SL14, JO14, WCCL15, SRO15, ZL15, TBSR15, CW15, AGJ14a, AGJ14b, AJSN15, GHJY15, QSW14, HSSS15, AAJ+13, AGM13, AAN13, ABGM14, AGMM15, SQW15a, YCS13, SA14, LWB13, LJ15, LLJB15, EW15, Bou16, JJKN15]. While the initialization plus local refinement analyses generally produce interesting theoretical results, they do no... |

4 | Sparse phase retrieval: Convex algorithms and limitations,
- Jaganathan, Oymak, et al.
- 2013
(Show Context)
Citation Context |

4 |
The complex gradient operator and the CR-calculus, arXiv preprint arXiv:0906.4835
- Kreutz-Delgado
- 2009
(Show Context)
Citation Context ...ed target x), gradient descent seems to always return a global minimizer (i.e., the target x up to a global phase shift), across many independent random initializations! This contrasts with the typical “mental picture” of nonconvex objectives as possessing many spurious local minimizers. 1Another least-squares formulation,minimizez 12m ∑m k=1(yk−|a ∗ kz|)2, was studied in the seminalworks [Fie82, GS72]. An obvious advantage of the f(z) studied here is that it is differentiable. 2Mathematically, f(z) is not complex differentiable; here the gradient is defined based on the Wirtinger derivatives [KD09]; see also [CLS15b]. This notion of gradient is a natural choice when optimizing real-valued functions of complex variables. 2 Figure 1: Gradient descent with random initialization seems to always return a global solution for (1.1)! Here n = 100,m = 5n log n, step size µ = 0.05, and stopping criterion is ‖∇zf(z)‖ ≤ 10−5. We fix the set of random measurements and the ground-truth signal x. The experiments are repeated for 100 times with independent random initializations. z? denotes the final iterate at convergence. (Left) Final distance to the target; (Right) Final function value (0 if globall... |

4 |
Algorithms and theory for clustering and nonconvex quadratic programming,
- Soltanolkotabi
- 2014
(Show Context)
Citation Context ...pectral initializer being sufficiently close to the target signal. In contrast, we explicitly characterize the global function landscape of (1.1). Its benign geometric structure allows several algorithmic choices that need no special initialization. In fact, the spectral initialization used in [CLS15b] lands the iterate sequence in the region in which the objective is (restrictedly) strongly convex (R3 in Theorem 2.2). The analysis of [CLS15b] is based on a property that ensures the gradient descent method is locally contractive near the target set, which is closely linked to local convexity. [Sol14] and [WWS15] explicitly established local strong convexity near the target set for GPR in Rn. Geometric analysis of other nonconvex problems. The approach taken here is similar in spirit to our recent geometric analysis of a nonconvex formulation for complete dictionary learning [SQW15a]. For that problem, we also identified a similar geometric structure that allows efficient global optimization without special initialization. There, by analyzing the geometry of a nonconvex formulation, we derived a provable efficient algorithm for recovering square invertible dictionaries when the coefficient... |

4 | Low-rank solutions of linear matrix equations via procrustes flow. arXiv preprint arXiv:1507.03566,
- Tu, Boczar, et al.
- 2015
(Show Context)
Citation Context ...rieval problem has a natural generalization to recovering low-rank positive semidefinite matrices. Consider the problem of recovering an unknown rank-r matrix M 0 in Rn×n from linear measurement of the form zk = tr(AkM) with symmetricAk for k = 1, . . . ,m. One can solve the problem by considering the “factorized” version: recoveringX ∈ Rn×r (up to right invertible transform) from measurements zk = tr(X ∗AkX). This is a natural generalization of GPR, as one can write the GPR measurements as y2k = |a∗kx| 2 = x∗(aka ∗ k)x. This generalization and related problems have recently been studied in [SRO15, ZL15, TBSR15, CW15]. 1.5 Notations, Organization, and Reproducible Research Basic notations and facts. Throughout the paper, we define complex inner product as: 〈a, b〉 .= a∗b for any a, b ∈ Cn. We use CSn−1 for the complex unit sphere in Cn. CSn−1(λ) with λ > 0 denotes the centered complex sphere with radius λ in Cn. Similarly, we use CBn(λ) to denote the centered complex ball of radius λ. We use CN (k) for a standard complex Gaussian vector of length k defined in (1.2). We reserve C and c, and their indexed versions to denote absolute constants. Their value vary with the context. Let < (z) ∈ Rn and =(z) ∈ Rn de... |

4 | A convergent gradient descent algorithm for rank minimization and semidefinite programming from random linear measurements.
- Zheng, Lafferty
- 2015
(Show Context)
Citation Context ...rieval problem has a natural generalization to recovering low-rank positive semidefinite matrices. Consider the problem of recovering an unknown rank-r matrix M 0 in Rn×n from linear measurement of the form zk = tr(AkM) with symmetricAk for k = 1, . . . ,m. One can solve the problem by considering the “factorized” version: recoveringX ∈ Rn×r (up to right invertible transform) from measurements zk = tr(X ∗AkX). This is a natural generalization of GPR, as one can write the GPR measurements as y2k = |a∗kx| 2 = x∗(aka ∗ k)x. This generalization and related problems have recently been studied in [SRO15, ZL15, TBSR15, CW15]. 1.5 Notations, Organization, and Reproducible Research Basic notations and facts. Throughout the paper, we define complex inner product as: 〈a, b〉 .= a∗b for any a, b ∈ Cn. We use CSn−1 for the complex unit sphere in Cn. CSn−1(λ) with λ > 0 denotes the centered complex sphere with radius λ in Cn. Similarly, we use CBn(λ) to denote the centered complex ball of radius λ. We use CN (k) for a standard complex Gaussian vector of length k defined in (1.2). We reserve C and c, and their indexed versions to denote absolute constants. Their value vary with the context. Let < (z) ∈ Rn and =(z) ∈ Rn de... |

3 |
Candès and Xiaodong Li. Solving quadratic equations via PhaseLift when there are about as many equations as unknowns.
- Emmanuel
- 2014
(Show Context)
Citation Context |

3 |
Fast low-rank estimation by projected gradient descent: General statistical and algorithmic guarantees. arXiv preprint arXiv:1509.03025,
- Chen, Wainwright
- 2015
(Show Context)
Citation Context |

3 | Sujay Sanghavi, Animashree Anandkumar, and Prateek Jain. Non-convex robust pca. - Netrapalli, Niranjan - 2014 |

2 |
Efficient approaches for escaping higher order saddle points in non-convex optimization, arXiv preprint arXiv:1602.05908
- Anandkumar, Ge
- 2016
(Show Context)
Citation Context ...oned recent surge of works on provable nonconvex heuristics [JNS13, Har14, HW14, NNS+14, JN14, SL14, JO14, WCCL15, SRO15, ZL15, TBSR15, CW15, AGJ14a, AGJ14b, AJSN15, GHJY15, QSW14, HSSS15, AAJ+13, AGM13, AAN13, ABGM14, AGMM15, SQW15a, YCS13, SA14, LWB13, LJ15, LLJB15, EW15, Bou16, JJKN15]. While the initialization plus local refinement analyses generally produce interesting theoretical results, they do not explain certain empirical successes that do not rely on special initializations. The geometric structure and analysis we work with in our recent work [SQW15a, SQW15b] (see also [GHJY15] and [AG16]) seempromising in this regard. It is interesting to considerwhether analogous geometric structure exists for other practical problems. 6 Proofs of Technical Results for Function Landscape 6.1 Auxiliary Lemmas Lemma 6.1 For the function f(z) : Cn 7→ R defined in (1.1), we have E [f(z)] = ‖x‖4 + ‖z‖4 − ‖x‖2 ‖z‖2 − |x∗z|2 , (6.1) ∇E [f(z)] = [ ∇zE [f(z)] ∇zE [f(z)] ] = (2 ‖z‖2 I − ‖x‖2 I − xx∗) z( 2 ‖z‖2 I − ‖x‖2 I − xx∗ ) z , (6.2) ∇2E [f(z)] = 2zz∗ − xx∗ + (2 ‖z‖2 − ‖x‖2) I 2zz> 2zz∗ 2zz> − xx> + ( 2 ‖z‖2 − ‖x‖2 ) I . (6.3) Proof By definition (1.1), notice that E [f(z)] = 1 2 Ea∼CN ... |

2 | Rong Ge, and AnkurMoitra,New algorithms for learning incoherent and overcomplete dictionaries, arXiv preprint arXiv:1308.6273 - Arora - 2013 |

2 | Solving random quadratic systems of equations is nearly as easy as solving linear systems.
- Chen, Candès
- 2015
(Show Context)
Citation Context |

2 |
Speeding up sum-of-squares for tensor decomposition and planted sparse vectors, arXiv preprint arXiv:1512.02337
- Hopkins, Schramm, et al.
- 2015
(Show Context)
Citation Context ...ptive, in the sense that a single, randomly chosen collection of vectors ai can simultaneously recover every x ∈ Cn. Results in [NJS13, CLS15b] and this paper pertain only to adaptive measurements that recover any fixed signal x with high probability. 5 Our work sits amid the recent surge of work on provable nonconvex heuristics for practical problems. Besides GPR studied here, this line of work includes low-rank matrix recovery [KMO10, JNS13, Har14, HW14, NNS+14, JN14, SL14, WCCL15, SRO15, ZL15, TBSR15, CW15], tensor recovery [JO14, AGJ14a, AGJ14b, AJSN15, GHJY15], structured element pursuit [QSW14, HSSS15], dictionary learning [AAJ+13, AGM13, AAN13, ABGM14, AGMM15, SQW15a], mixed regression [YCS13, SA14], blind deconvolution [LWB13, LJ15, LLJB15], super resolution [EW15], phase synchronization [Bou16], numerical linear algebra [JJKN15], and so forth. Most of the methods adopt the strategy of initialization plus local refinement we alluded to above. In contrast, our geometric analysis allows flexible algorithm design (i.e., separation of geometry and algorithms) and gives some clues as to the behavior of nonconvex heuristics used in practice, which often succeed without clever initialization. Re... |

2 |
Computing matrix squareroot via non convex local search, arXiv preprint arXiv:1507.05854
- Jain, Jin, et al.
- 2015
(Show Context)
Citation Context ...obability. 5 Our work sits amid the recent surge of work on provable nonconvex heuristics for practical problems. Besides GPR studied here, this line of work includes low-rank matrix recovery [KMO10, JNS13, Har14, HW14, NNS+14, JN14, SL14, WCCL15, SRO15, ZL15, TBSR15, CW15], tensor recovery [JO14, AGJ14a, AGJ14b, AJSN15, GHJY15], structured element pursuit [QSW14, HSSS15], dictionary learning [AAJ+13, AGM13, AAN13, ABGM14, AGMM15, SQW15a], mixed regression [YCS13, SA14], blind deconvolution [LWB13, LJ15, LLJB15], super resolution [EW15], phase synchronization [Bou16], numerical linear algebra [JJKN15], and so forth. Most of the methods adopt the strategy of initialization plus local refinement we alluded to above. In contrast, our geometric analysis allows flexible algorithm design (i.e., separation of geometry and algorithms) and gives some clues as to the behavior of nonconvex heuristics used in practice, which often succeed without clever initialization. Recovering low-rank positive semidefinite matrices. The phase retrieval problem has a natural generalization to recovering low-rank positive semidefinite matrices. Consider the problem of recovering an unknown rank-r matrix M 0 in Rn×... |

2 |
Finding a sparse vector in a subspace: Linear sparsity using alternating directions,
- Qu, Sun, et al.
- 2014
(Show Context)
Citation Context ...ptive, in the sense that a single, randomly chosen collection of vectors ai can simultaneously recover every x ∈ Cn. Results in [NJS13, CLS15b] and this paper pertain only to adaptive measurements that recover any fixed signal x with high probability. 5 Our work sits amid the recent surge of work on provable nonconvex heuristics for practical problems. Besides GPR studied here, this line of work includes low-rank matrix recovery [KMO10, JNS13, Har14, HW14, NNS+14, JN14, SL14, WCCL15, SRO15, ZL15, TBSR15, CW15], tensor recovery [JO14, AGJ14a, AGJ14b, AJSN15, GHJY15], structured element pursuit [QSW14, HSSS15], dictionary learning [AAJ+13, AGM13, AAN13, ABGM14, AGMM15, SQW15a], mixed regression [YCS13, SA14], blind deconvolution [LWB13, LJ15, LLJB15], super resolution [EW15], phase synchronization [Bou16], numerical linear algebra [JJKN15], and so forth. Most of the methods adopt the strategy of initialization plus local refinement we alluded to above. In contrast, our geometric analysis allows flexible algorithm design (i.e., separation of geometry and algorithms) and gives some clues as to the behavior of nonconvex heuristics used in practice, which often succeed without clever initialization. Re... |

2 | Guarantees of Riemannian optimization for low rank matrix recovery, arXiv preprint arXiv:1511.01562 - Wei, Cai, et al. - 2015 |

2 |
Alexandre d’Aspremont, and Stéphane Mallat. Phase recovery, MaxCut and complex semidefinite programming.
- Waldspurger
- 2015
(Show Context)
Citation Context |

1 | Aditya Bhaskara, Rong Ge, and Tengyu Ma,More algorithms for provable dictionary learning, arXiv preprint arXiv:1401.0579 - Arora - 2014 |

1 |
andMajid Janzamin,Analyzing tensor powermethod dynamics: Applications to learning overcomplete latent variable models, arXiv preprint arXiv:1411.1488
- AnimashreeAnandkumar
- 2014
(Show Context)
Citation Context ...ls. 6In addition, [CC15] shows that the measurements can be non-adaptive, in the sense that a single, randomly chosen collection of vectors ai can simultaneously recover every x ∈ Cn. Results in [NJS13, CLS15b] and this paper pertain only to adaptive measurements that recover any fixed signal x with high probability. 5 Our work sits amid the recent surge of work on provable nonconvex heuristics for practical problems. Besides GPR studied here, this line of work includes low-rank matrix recovery [KMO10, JNS13, Har14, HW14, NNS+14, JN14, SL14, WCCL15, SRO15, ZL15, TBSR15, CW15], tensor recovery [JO14, AGJ14a, AGJ14b, AJSN15, GHJY15], structured element pursuit [QSW14, HSSS15], dictionary learning [AAJ+13, AGM13, AAN13, ABGM14, AGMM15, SQW15a], mixed regression [YCS13, SA14], blind deconvolution [LWB13, LJ15, LLJB15], super resolution [EW15], phase synchronization [Bou16], numerical linear algebra [JJKN15], and so forth. Most of the methods adopt the strategy of initialization plus local refinement we alluded to above. In contrast, our geometric analysis allows flexible algorithm design (i.e., separation of geometry and algorithms) and gives some clues as to the behavior of nonconvex heuristics used in practice, which oft... |

1 |
and Uma Naresh Niranjan, Tensor vs matrix methods: Robust tensor decomposition under block sparse perturbations, arXiv preprint arXiv:1510.04747
- Anandkumar, Jain, et al.
- 2015
(Show Context)
Citation Context ...ls. 6In addition, [CC15] shows that the measurements can be non-adaptive, in the sense that a single, randomly chosen collection of vectors ai can simultaneously recover every x ∈ Cn. Results in [NJS13, CLS15b] and this paper pertain only to adaptive measurements that recover any fixed signal x with high probability. 5 Our work sits amid the recent surge of work on provable nonconvex heuristics for practical problems. Besides GPR studied here, this line of work includes low-rank matrix recovery [KMO10, JNS13, Har14, HW14, NNS+14, JN14, SL14, WCCL15, SRO15, ZL15, TBSR15, CW15], tensor recovery [JO14, AGJ14a, AGJ14b, AJSN15, GHJY15], structured element pursuit [QSW14, HSSS15], dictionary learning [AAJ+13, AGM13, AAN13, ABGM14, AGMM15, SQW15a], mixed regression [YCS13, SA14], blind deconvolution [LWB13, LJ15, LLJB15], super resolution [EW15], phase synchronization [Bou16], numerical linear algebra [JJKN15], and so forth. Most of the methods adopt the strategy of initialization plus local refinement we alluded to above. In contrast, our geometric analysis allows flexible algorithm design (i.e., separation of geometry and algorithms) and gives some clues as to the behavior of nonconvex heuristics used in practice, which oft... |

1 |
On signal reconstruction without phase,
- Balana, Casazzab, et al.
- 2006
(Show Context)
Citation Context ...crystallography, optical imaging and astronomy. In these areas, one often has access only to the Fourier magnitudes of a complex signal x, i.e., |F(x) |[Mil90, Rob93, Wal63, DF87]. The phase information is hard or infeasible to record due to physical constraints. The problem of recovering the signal x from its Fourier magnitudes |F(x) |is naturally termed (Fourier) phase retrieval (PR). 1 It is easy to see PR as a special version of GPR, with the ak’s the Fourier basis vectors. GPR also sees applications in electron microscopy [MIJ+02], diffraction and array imaging [BDP+07, CMP11], acoustics [BCE06, Bal10], quantum mechanics [Cor06, Rei65] and quantum information [HMW13]. We refer the reader to survey papers [SEC+15, JEH15] for accounts of recent developments in the theory, algorithms, and applications of GPR. For GPR, heuristic methods based on nonconvex optimization often work surprisingly well in practice (e.g., [Fie82, GS72], and many more cited in [SEC+15, JEH15]). However, investigation into provable recoverymethods, particularly based on nonconvex optimization, has started only relatively recently [NJS13, CESV13, CSV13, CL14, CLS15a, WdM15, VX14, ABFM14, CLS15b, CC15,WWS15]. The surprisi... |

1 | Friso van der Veen,Diffractive imaging for periodic samples: retrieving one-dimensional concentration profiles across microfluidic channels, - Bunk, Diaz, et al. - 2007 |

1 |
Nonconvex phase synchronization, arXiv preprint arXiv:1601.06114
- Boumal
- 2016
(Show Context)
Citation Context ...er any fixed signal x with high probability. 5 Our work sits amid the recent surge of work on provable nonconvex heuristics for practical problems. Besides GPR studied here, this line of work includes low-rank matrix recovery [KMO10, JNS13, Har14, HW14, NNS+14, JN14, SL14, WCCL15, SRO15, ZL15, TBSR15, CW15], tensor recovery [JO14, AGJ14a, AGJ14b, AJSN15, GHJY15], structured element pursuit [QSW14, HSSS15], dictionary learning [AAJ+13, AGM13, AAN13, ABGM14, AGMM15, SQW15a], mixed regression [YCS13, SA14], blind deconvolution [LWB13, LJ15, LLJB15], super resolution [EW15], phase synchronization [Bou16], numerical linear algebra [JJKN15], and so forth. Most of the methods adopt the strategy of initialization plus local refinement we alluded to above. In contrast, our geometric analysis allows flexible algorithm design (i.e., separation of geometry and algorithms) and gives some clues as to the behavior of nonconvex heuristics used in practice, which often succeed without clever initialization. Recovering low-rank positive semidefinite matrices. The phase retrieval problem has a natural generalization to recovering low-rank positive semidefinite matrices. Consider the problem of recovering an... |

1 |
Thomas Strohmer, and Vladislav Voroninski, Phase retrieval via matrix completion,
- Candès, Eldar
- 2013
(Show Context)
Citation Context |

1 |
Xiaodong Li, andMahdi Soltanolkotabi, Phase retrieval from coded diffraction patterns,
- Candès
- 2015
(Show Context)
Citation Context |

1 |
retrieval via wirtinger flow: Theory and algorithms, Information Theory,
- Phase
- 2015
(Show Context)
Citation Context |

1 |
Greed is super: A fast algorithm for super-resolution, arXiv preprint arXiv:1511.03385
- Eftekhari, Wakin
- 2015
(Show Context)
Citation Context ...aptive measurements that recover any fixed signal x with high probability. 5 Our work sits amid the recent surge of work on provable nonconvex heuristics for practical problems. Besides GPR studied here, this line of work includes low-rank matrix recovery [KMO10, JNS13, Har14, HW14, NNS+14, JN14, SL14, WCCL15, SRO15, ZL15, TBSR15, CW15], tensor recovery [JO14, AGJ14a, AGJ14b, AJSN15, GHJY15], structured element pursuit [QSW14, HSSS15], dictionary learning [AAJ+13, AGM13, AAN13, ABGM14, AGMM15, SQW15a], mixed regression [YCS13, SA14], blind deconvolution [LWB13, LJ15, LLJB15], super resolution [EW15], phase synchronization [Bou16], numerical linear algebra [JJKN15], and so forth. Most of the methods adopt the strategy of initialization plus local refinement we alluded to above. In contrast, our geometric analysis allows flexible algorithm design (i.e., separation of geometry and algorithms) and gives some clues as to the behavior of nonconvex heuristics used in practice, which often succeed without clever initialization. Recovering low-rank positive semidefinite matrices. The phase retrieval problem has a natural generalization to recovering low-rank positive semidefinite matrices. Consid... |

1 | Phase retrieval: An overview of recent developments, arXiv preprint arXiv:1510.07713 - Jaganathan, Eldar, et al. - 2015 |

1 |
RIP-like properties in subsampled blind deconvolution, arXiv preprint arXiv:1511.06146
- Junge
- 2015
(Show Context)
Citation Context ...LS15b] and this paper pertain only to adaptive measurements that recover any fixed signal x with high probability. 5 Our work sits amid the recent surge of work on provable nonconvex heuristics for practical problems. Besides GPR studied here, this line of work includes low-rank matrix recovery [KMO10, JNS13, Har14, HW14, NNS+14, JN14, SL14, WCCL15, SRO15, ZL15, TBSR15, CW15], tensor recovery [JO14, AGJ14a, AGJ14b, AJSN15, GHJY15], structured element pursuit [QSW14, HSSS15], dictionary learning [AAJ+13, AGM13, AAN13, ABGM14, AGMM15, SQW15a], mixed regression [YCS13, SA14], blind deconvolution [LWB13, LJ15, LLJB15], super resolution [EW15], phase synchronization [Bou16], numerical linear algebra [JJKN15], and so forth. Most of the methods adopt the strategy of initialization plus local refinement we alluded to above. In contrast, our geometric analysis allows flexible algorithm design (i.e., separation of geometry and algorithms) and gives some clues as to the behavior of nonconvex heuristics used in practice, which often succeed without clever initialization. Recovering low-rank positive semidefinite matrices. The phase retrieval problem has a natural generalization to recovering low-rank positive semi... |

1 |
Blind recovery of sparse signals from subsampled convolution, arXiv preprint arXiv:1511.06149
- Lee, Li, et al.
- 2015
(Show Context)
Citation Context ...LS15b] and this paper pertain only to adaptive measurements that recover any fixed signal x with high probability. 5 Our work sits amid the recent surge of work on provable nonconvex heuristics for practical problems. Besides GPR studied here, this line of work includes low-rank matrix recovery [KMO10, JNS13, Har14, HW14, NNS+14, JN14, SL14, WCCL15, SRO15, ZL15, TBSR15, CW15], tensor recovery [JO14, AGJ14a, AGJ14b, AJSN15, GHJY15], structured element pursuit [QSW14, HSSS15], dictionary learning [AAJ+13, AGM13, AAN13, ABGM14, AGMM15, SQW15a], mixed regression [YCS13, SA14], blind deconvolution [LWB13, LJ15, LLJB15], super resolution [EW15], phase synchronization [Bou16], numerical linear algebra [JJKN15], and so forth. Most of the methods adopt the strategy of initialization plus local refinement we alluded to above. In contrast, our geometric analysis allows flexible algorithm design (i.e., separation of geometry and algorithms) and gives some clues as to the behavior of nonconvex heuristics used in practice, which often succeed without clever initialization. Recovering low-rank positive semidefinite matrices. The phase retrieval problem has a natural generalization to recovering low-rank positive semi... |

1 |
Gradient descent converges to minimizers, arXiv preprint arXiv:1602.04915
- Lee, Simchowitz, et al.
- 2016
(Show Context)
Citation Context ...e the target xeiφ for φ ∈ [0, 2π); (ii) at any point in Cn, either the gradient is large, or the curvature is negative in a certain direction, or it is near a minimizer. Moreover, in the vicinity of the minimizers, on the orthogonal complement of a single flat direction (which occurs because f(zeiφ) = f(z) for every z, φ), the objective function is strongly convex. Because of this global geometry, a wide range of efficient iterative methods can obtain a global minimizer to f(z), regardless of initialization. Examples include the noisy gradient and stochastic gradientmethods [GHJY15] (see also [LSJR16]), curvilinear search [Gol80] and trust-regionmethods 3Note that the global sign cannot be recovered. 4The probability is with respect to drawing of ak’s. 3 Figure 2: Function landscape of (1.1) for x = [1; 0] and m → ∞. The only local and also global minimizers are ±x. There are two saddle points near ±[0; 1/ √ 2], around each there is a negative curvature direction along ±x. (Left) The function graph; (Right) The same function visualized as a color image. The measurement vectors ak’s are taken as i.i.d. standard real Gaussian in this version. [CGT00, NP06, SQW15b]. The key property that the ... |

1 | Square deal: Lower bounds and improved convex relaxations for tensor recovery., - Mu, Huang, et al. - 2014 |

1 |
Sastry, Quadratic basis pursuit, arXiv preprint arXiv:1301.7002
- Ohlsson, Yang, et al.
- 2013
(Show Context)
Citation Context |

1 |
Phase problem in crystallography,
- Robert
- 1993
(Show Context)
Citation Context ...hase, as xeiφ for all φ ∈ [0, 2π) gives exactly the same set of measurements. The generalized phase retrieval problem asks whether it is possible to recover x, up to this fundamental ambiguity: Generalized Phase Retrieval Problem: Is it possible to efficiently recover an unknown x from yk = |a∗kx |(k = 1, . . . ,m), up to a global phase factor eiφ? This problem has attracted substantial recent interest, due to its connections to fields such as crystallography, optical imaging and astronomy. In these areas, one often has access only to the Fourier magnitudes of a complex signal x, i.e., |F(x) |[Mil90, Rob93, Wal63, DF87]. The phase information is hard or infeasible to record due to physical constraints. The problem of recovering the signal x from its Fourier magnitudes |F(x) |is naturally termed (Fourier) phase retrieval (PR). 1 It is easy to see PR as a special version of GPR, with the ak’s the Fourier basis vectors. GPR also sees applications in electron microscopy [MIJ+02], diffraction and array imaging [BDP+07, CMP11], acoustics [BCE06, Bal10], quantum mechanics [Cor06, Rei65] and quantum information [HMW13]. We refer the reader to survey papers [SEC+15, JEH15] for accounts of recent developments in the t... |

1 |
Stewart and Ji-guang Sun,Matrix perturbation theory,
- Gilbert
- 1990
(Show Context)
Citation Context ...rsm ≥ 3. Let S .= 1p ∑p k=1Xk, then for ... , it holds that P [|S − E [S] |≥ t] ≤ 2 exp ( − pt 2 2σ2X + 2Rt ) . Lemma A.9 (Angles Between Two Subspaces) Consider two linear subspaces U , V of dimension k in Rn (k ∈ [n]) spanned by orthonormal bases U and V , respectively. Suppose π/2 ≥ θ1 ≥ θ2 · · · ≥ θk ≥ 0 are the principal angles between U and V . Then it holds that i) minQ∈Ok ‖U − V Q‖ ≤ √ 2− 2 cos θ1; ii) sin θ1 = ‖UU∗ − V V ∗‖; iii) Let U⊥ and V⊥ be the orthogonal complement of U and V , respectively. Then θ1(U ,V) = θ1(U⊥,V⊥). Proof Proof to i) is similar to that of II. Theorem 4.11 in [SS90]. For 2k ≤ n, w.l.o.g., we can assume U and V are the canonical bases for U and V , respectively. Then min Q∈Ok ∥∥∥∥∥∥ I − ΓQ−ΣQ 0 ∥∥∥∥∥∥ ≤ ∥∥∥∥∥∥ I − Γ−Σ 0 ∥∥∥∥∥∥ ≤ ∥∥∥∥[I − Γ−Σ ]∥∥∥∥ . Now by definition∥∥∥∥[I − Γ−Σ ]∥∥∥∥2 = max‖x‖=1 ∥∥∥∥[I − Γ−Σ ] x ∥∥∥∥2 = max‖x‖=1 k∑ i=1 (1− cos θi)2x2i + sin2 θix2i = max ‖x‖=1 k∑ i=1 (2− 2 cos θi)x2i ≤ 2− 2 cos θ1. Note that the upper bound is achieved by taking x = e1. When 2k > n, by the results from CS decomposition (see, e.g., I Theorem 5.2 of [SS90]). min Q∈Ok ∥∥∥∥∥∥ I 00 I 0 0 − Γ 00 I Σ 0 ∥∥∥∥∥∥ ≤ ∥∥∥∥[I − Γ−Σ ]∥∥∥∥ , and the same a... |

1 |
A strong restricted isometry property, with an application to phaseless compressed sensing, arXiv preprint arXiv:1404.3811
- Voroninski, Xu
- 2014
(Show Context)
Citation Context |

1 |
The question of phase retrieval in optics,
- AdriaanWalther
- 1963
(Show Context)
Citation Context |

1 |
The local convexity of solving quadratic equations, arXiv preprint arXiv:1506.07868
- White, Ward, et al.
- 2015
(Show Context)
Citation Context |

1 |
Constantine Caramanis, and Sujay Sanghavi, Alternating minimization for mixed linear regression, arXiv preprint arXiv:1310.3745
- Yi
- 2013
(Show Context)
Citation Context ... every x ∈ Cn. Results in [NJS13, CLS15b] and this paper pertain only to adaptive measurements that recover any fixed signal x with high probability. 5 Our work sits amid the recent surge of work on provable nonconvex heuristics for practical problems. Besides GPR studied here, this line of work includes low-rank matrix recovery [KMO10, JNS13, Har14, HW14, NNS+14, JN14, SL14, WCCL15, SRO15, ZL15, TBSR15, CW15], tensor recovery [JO14, AGJ14a, AGJ14b, AJSN15, GHJY15], structured element pursuit [QSW14, HSSS15], dictionary learning [AAJ+13, AGM13, AAN13, ABGM14, AGMM15, SQW15a], mixed regression [YCS13, SA14], blind deconvolution [LWB13, LJ15, LLJB15], super resolution [EW15], phase synchronization [Bou16], numerical linear algebra [JJKN15], and so forth. Most of the methods adopt the strategy of initialization plus local refinement we alluded to above. In contrast, our geometric analysis allows flexible algorithm design (i.e., separation of geometry and algorithms) and gives some clues as to the behavior of nonconvex heuristics used in practice, which often succeed without clever initialization. Recovering low-rank positive semidefinite matrices. The phase retrieval problem has a natural generali... |