We consider the problem of phase retrieval, i.e. that of solving systems of quadratic equations. A simple variant of the randomized Kaczmarz method was recently proposed for phase retrieval, and it was shown numerically to have a computational edge over state-of-the-art Wirtinger flow methods. In this paper, we provide the first theoretical guarantee for the convergence of the randomized Kaczmarz method for phase retrieval. We show that it is sufficient to have as many Gaussian measurements as the dimension, up to a constant factor. Along the way, we introduce a sufficient condition on measurement sets for which the randomized Kaczmarz method is guaranteed to work. We show that Gaussian sampling vectors satisfy this property with high probability; this is proved using a chaining argument coupled with bounds on VC dimension and metric entropy.
During the preparation of this manuscript, we became aware of independent simultaneous work done by Jeong and G "u nt "u rk. They also studied the randomized Kaczmarz method adapted to phase retrieval, and obtained almost the same result that we did (see @cite_14 and Theorem 1.1 therein). In order to prove their guarantee, they use a stopping time argument similar to ours, but replace the ACW condition with a stronger condition called . They prove that measurement systems comprising vectors drawn independently and uniformly from the sphere satisfy this property with high probability, and the main tools they use in their proof are hyperplane tessellations and a net argument together with Lipschitz relaxation of indicator functions.
@cite_14
2462226338
In this paper we explore first passage percolation (FPP) on the Erd os-Renyi random graph Gn(pn), where each edge is given an independent exponential edge weight with rate 1. In the sparse regime, i.e., when npn   > 1, we find refined asymptotics both for the minimal weight of the path between uniformly chosen vertices in the giant component, as well as for the hopcount (i.e., the number of edges) on this minimal weight path. More precisely, we prove a central limit theorem for the hopcount, with asymptotic mean and variance both equal to  (  1) log n. Furthermore, we prove that the minimal weight centered by log n (  1) converges in distribution. We also investigate the dense regime, where npn  . We find that although the base graph is a ultra small (meaning that graph distances between uniformly chosen vertices are o(log n)), attaching random edge weights changes the geometry of the network completely. Indeed, the hopcount Hn satisfies the universality property that whatever be the value of pn, Hn log n  1 in probability and, more precisely, (Hnn log n)  log n, where n = n (n 1), has a limiting standard normal distribution. The constant n can be replaced by 1 precisely when n   log n, a case that has appeared in the literature (under stronger conditions on n) in (2, 12). We also find bounds for the maximal weight and maximal hopcount between vertices in the graph. This paper continues the investigation of FPP initiated in (2) and (3). Compared to the setting on the configuration model studied in (3), the proofs presented here are much simpler due to a direct relation between FPP on the Erd os-Renyi random graph and thinned continuous-time branching processes.