In the phase retrieval problem one seeks to recover an unknown$n$dimensional signal vector$\mathbf {x}$from$m$measurements of the form$y_{i} = |(\mathbf {A} \mathbf {x})_{i}|$, where$\mathbf {A}$denotes the sensing matrix. Many algorithms for this problem are based on approximate message passing. For these algorithms, it is known that if the sensing matrix$\mathbf {A}$is generated by sub-sampling$n$columns of a uniformly random (i.e., Haar distributed) orthogonal matrix, in the high dimensional asymptotic regime ($m,n \rightarrow \infty, n/m \rightarrow \kappa $), the dynamics of the algorithm are given by a deterministic recursion known as the state evolution. For a special class of linearized message-passing algorithms, we show that the state evolution is universal: it continues to hold even when$\mathbf {A}$is generated by randomly sub-sampling columns of the Hadamard-Walsh matrix, if the signal is drawn from a Gaussian prior.

Compressive phase retrieval refers to the problem of recovering a structured n-dimensional complex-valued vector from its phase-less under-determined linear measurements. The non-linearity of the measurement process makes designing theoretically-analyzable efficient phase retrieval algorithms challenging. As a result, to a great extent, existing recovery algorithms only take advantage of simple structures such as sparsity and its convex generalizations. The goal of this article is to move beyond simple models through employing compression codes. Such codes are typically developed to take advantage of complex signal models to represent the signals as efficiently as possible. In this work, it is shown how an existing compression code can be treated as a black box and integrated into an efficient solution for phase retrieval. First, COmpressive PhasE Retrieval (COPER) optimization, a computationally-intensive compression-based phase retrieval method, is proposed. COPER provides a theoretical framework for studying compression-based phase retrieval. The number of measurements required by COPER is connected to κ, the α-dimension (closely related to the ratedistortion dimension) of a given family of compression codes. To finds the solution of COPER, an efficient iterative algorithm called gradient descent for COPER (GD-COPER) is proposed. It is proven that under some mild conditions on the initialization and the compression code, if the number of measurements is larger than Cκ2log2n, where C is a constant, GD-COPER obtains an accurate estimate of the input vector in polynomial time. In the simulation results, JPEG2000 is integrated in GD-COPER to confirm the state-of-the-art performance of the resulting algorithm on real-world images.

Phase retrieval refers to algorithmic methods for recovering a signal from its phaseless measurements. There has been recent interest in understanding the performance of local search algorithms that work directly on the non-convex formulation of the problem. Due to the non-convexity of the problem, the success of these local search algorithms depends heavily on their starting points. The most widely used initialization scheme is the spectral method, in which the leading eigenvector of a data-dependent matrix is used as a starting point. Recently, the performance of the spectral initialization was characterized accurately for measurement matrices with independent and identically distributed entries. This paper aims to obtain the same level of knowledge for isotropically random column-orthogonal matrices, which are substantially better models for practical phase retrieval systems. Towards this goal, we consider the asymptotic setting in which the number of measurements m, and the dimension of the signal, n, diverge to infinity with m/n = δ ∈ (1, ∞), and obtain a simple expression for the overlap between the spectral estimator and the true signal vector.

Compressive phase retrieval is the problem of recovering a structured vector x ∈ ℂnfrom its phaseless linear measurements. A compression algorithm aims to represent structured signals with as few bits as possible. As a result of extensive research devoted to compression algorithms, in many signal classes, compression algorithms are capable of employing sophisticated structures in signals and compress them efficiently. This raises the following important question: Can a compression algorithm be used to solve a compressive phase retrieval problem? To address this question, COmpressive PhasE Retrieval (COPER) optimization is proposed, which is a compression-based phase retrieval method. For a family of compression codes with rate-distortion function denoted by r(δ), in the noiseless setting, COPER is shown to require slightly more than limδ→0(r(δ))/(log (1/δ)) observations for an almost accurate recovery of x.