The minimal measurement number problem in phase retrieval: a review of recent developments
---
paper_title: Generalized phase retrieval : measurement number, matrix recovery and beyond

paper_content:

Abstract In this paper, we develop a framework of generalized phase retrieval in which one aims to reconstruct a vector x in R d or C d through quadratic samples x ⁎ A 1 x , … , x ⁎ A N x . The generalized phase retrieval includes as special cases the standard phase retrieval as well as the phase retrieval by orthogonal projections. We first explore the connections among generalized phase retrieval, low-rank matrix recovery and nonsingular bilinear form. Motivated by the connections, we present results on the minimal measurement number needed for recovering a matrix that lies in a set W ∈ C d × d . Applying the results to phase retrieval, we show that generic d × d matrices A 1 , … , A N have the phase retrieval property if N ≥ 2 d − 1 in the real case and N ≥ 4 d − 4 in the complex case for very general classes of A 1 , … , A N , e.g. matrices with prescribed ranks or orthogonal projections. We also give lower bounds on the minimal measurement number required for generalized phase retrieval. For several classes of dimensions d we obtain the precise values of the minimal measurement number. Our work unifies and enhances results from the standard phase retrieval, phase retrieval by projections and low-rank matrix recovery.
---
paper_title: Saving phase: Injectivity and stability for phase retrieval

paper_content:

Recent advances in convex optimization have led to new strides in the phase retrieval problem over finite-dimensional vector spaces. However, certain fundamental questions remain: What sorts of measurement vectors uniquely determine every signal up to a global phase factor, and how many are needed to do so? Furthermore, which measurement ensembles lend stability? This paper presents several results that address each of these questions. We begin by characterizing injectivity, and we identify that the complement property is indeed a necessary condition in the complex case. We then pose a conjecture that 4M-4 generic measurement vectors are both necessary and sufficient for injectivity in M dimensions, and we prove this conjecture in the special cases where M=2,3. Next, we shift our attention to stability, both in the worst and average cases. Here, we characterize worst-case stability in the real case by introducing a numerical version of the complement property. This new property bears some resemblance to the restricted isometry property of compressed sensing and can be used to derive a sharp lower Lipschitz bound on the intensity measurement mapping. Localized frames are shown to lack this property (suggesting instability), whereas Gaussian random measurements are shown to satisfy this property with high probability. We conclude by presenting results that use a stochastic noise model in both the real and complex cases, and we leverage Cramer-Rao lower bounds to identify stability with stronger versions of the injectivity characterizations.
---
paper_title: Generalized phase retrieval : measurement number, matrix recovery and beyond

paper_content:

Abstract In this paper, we develop a framework of generalized phase retrieval in which one aims to reconstruct a vector x in R d or C d through quadratic samples x ⁎ A 1 x , … , x ⁎ A N x . The generalized phase retrieval includes as special cases the standard phase retrieval as well as the phase retrieval by orthogonal projections. We first explore the connections among generalized phase retrieval, low-rank matrix recovery and nonsingular bilinear form. Motivated by the connections, we present results on the minimal measurement number needed for recovering a matrix that lies in a set W ∈ C d × d . Applying the results to phase retrieval, we show that generic d × d matrices A 1 , … , A N have the phase retrieval property if N ≥ 2 d − 1 in the real case and N ≥ 4 d − 4 in the complex case for very general classes of A 1 , … , A N , e.g. matrices with prescribed ranks or orthogonal projections. We also give lower bounds on the minimal measurement number required for generalized phase retrieval. For several classes of dimensions d we obtain the precise values of the minimal measurement number. Our work unifies and enhances results from the standard phase retrieval, phase retrieval by projections and low-rank matrix recovery.
---
paper_title: Phase retrieval and norm retrieval

paper_content:

Phase retrieval has become a very active area of research. We will classify when phase retrieval by Parseval frames passes to the Naimark complement and when phase retrieval by projections passes to the orthogonal complements. We introduce a new concept we call norm retrieval and show that this is what is necessary for passing phase retrieval to complements. This leads to a detailed study of norm retrieval and its relationship to phase retrieval. One fundamental result: a frame $\{\varphi_i\}_{i=1}^M$ yields phase retrieval if and only if $\{T\varphi_i\}_{i=1}^M$ yields norm retrieval for every invertible operator $T$.
---
paper_title: An algebraic characterization of injectivity in phase retrieval

paper_content:

Abstract A complex frame is a collection of vectors that span C M and define measurements, called intensity measurements, on vectors in C M . In purely mathematical terms, the problem of phase retrieval is to recover a complex vector from its intensity measurements, namely the modulus of its inner product with these frame vectors. We show that any vector is uniquely determined (up to a global phase factor) from 4 M − 4 generic measurements. To prove this, we identify the set of frames defining non-injective measurements with the projection of a real variety and bound its dimension.
---
paper_title: Phase Retrieval By Projections

paper_content:

The problem of recovering a vector from the absolute values of its inner products against a family of measurement vectors has been well studied in mathematics and engineering. A generalization of this phase retrieval problem also exists in engineering: recovering a vector from measurements consisting of norms of its orthogonal projections onto a family of subspaces. There exist semidefinite programming algorithms to solve this problem, but much remains unknown for this more general case. Can families of subspaces for which such measurements are injective be completely classified? What is the minimal number of subspaces required to have injectivity? How closely does this problem compare to the usual phase retrieval problem with families of measurement vectors? In this paper, we answer or make incremental steps toward these questions. We provide several characterizations of subspaces which yield injective measurements, and through a concrete construction, we prove the surprising result that phase retrieval can be achieved with $2M-1$ projections of arbitrary rank in $\HH_M$. Finally we present several open problems as we discuss issues unique to the phase retrieval problem with subspaces.
---
paper_title: Saving phase: Injectivity and stability for phase retrieval

paper_content:

Recent advances in convex optimization have led to new strides in the phase retrieval problem over finite-dimensional vector spaces. However, certain fundamental questions remain: What sorts of measurement vectors uniquely determine every signal up to a global phase factor, and how many are needed to do so? Furthermore, which measurement ensembles lend stability? This paper presents several results that address each of these questions. We begin by characterizing injectivity, and we identify that the complement property is indeed a necessary condition in the complex case. We then pose a conjecture that 4M-4 generic measurement vectors are both necessary and sufficient for injectivity in M dimensions, and we prove this conjecture in the special cases where M=2,3. Next, we shift our attention to stability, both in the worst and average cases. Here, we characterize worst-case stability in the real case by introducing a numerical version of the complement property. This new property bears some resemblance to the restricted isometry property of compressed sensing and can be used to derive a sharp lower Lipschitz bound on the intensity measurement mapping. Localized frames are shown to lack this property (suggesting instability), whereas Gaussian random measurements are shown to satisfy this property with high probability. We conclude by presenting results that use a stochastic noise model in both the real and complex cases, and we leverage Cramer-Rao lower bounds to identify stability with stronger versions of the injectivity characterizations.
---
paper_title: Stable signal recovery from incomplete and inaccurate measurements

paper_content:

Suppose we wish to recover an n-dimensional real-valued vector x_0 (e.g. a digital signal or image) from incomplete and contaminated observations y = A x_0 + e; A is a n by m matrix with far fewer rows than columns (n << m) and e is an error term. Is it possible to recover x_0 accurately based on the data y? ::: To recover x_0, we consider the solution x* to the l1-regularization problem min \|x\|_1 subject to \|Ax-y\|_2 <= epsilon, where epsilon is the size of the error term e. We show that if A obeys a uniform uncertainty principle (with unit-normed columns) and if the vector x_0 is sufficiently sparse, then the solution is within the noise level \|x* - x_0\|_2 \le C epsilon. ::: As a first example, suppose that A is a Gaussian random matrix, then stable recovery occurs for almost all such A's provided that the number of nonzeros of x_0 is of about the same order as the number of observations. Second, suppose one observes few Fourier samples of x_0, then stable recovery occurs for almost any set of p coefficients provided that the number of nonzeros is of the order of n/[\log m]^6. In the case where the error term vanishes, the recovery is of course exact, and this work actually provides novel insights on the exact recovery phenomenon discussed in earlier papers. The methodology also explains why one can also very nearly recover approximately sparse signals.
---
paper_title: A strong restricted isometry property, with an application to phaseless compressed sensing

paper_content:

The many variants of the restricted isometry property (RIP) have proven to be crucial theoretical tools in the fields of compressed sensing and matrix completion. The study of extending compressed sensing to accommodate phaseless measurements naturally motivates a strong notion of restricted isometry property (SRIP), which we develop in this paper. We show that if $A \in \mathbb{R}^{m\times n}$ satisfies SRIP and phaseless measurements $|Ax_0| = b$ are observed about a $k$-sparse signal $x_0 \in \mathbb{R}^n$, then minimizing the $\ell_1$ norm subject to $ |Ax| = b $ recovers $x_0$ up to multiplication by a global sign. Moreover, we establish that the SRIP holds for the random Gaussian matrices typically used for standard compressed sensing, implying that phaseless compressed sensing is possible from $O(k \log (n/k))$ measurements with these matrices via $\ell_1$ minimization over $|Ax| = b$. Our analysis also yields an erasure robust version of the Johnson-Lindenstrauss Lemma.
---
paper_title: Stable Signal Recovery from Phaseless Measurements

paper_content:

The aim of this paper is to study the stability of the $\ell_1$ minimization for the compressive phase retrieval and to extend the instance-optimality in compressed sensing to the real phase retrieval setting. We first show that the $m={\mathcal O}(k\log(N/k))$ measurements is enough to guarantee the $\ell_1$ minimization to recover $k$-sparse signals stably provided the measurement matrix $A$ satisfies the strong RIP property. We second investigate the phaseless instance-optimality with presenting a null space property of the measurement matrix $A$ under which there exists a decoder $\Delta$ so that the phaseless instance-optimality holds. We use the result to study the phaseless instance-optimality for the $\ell_1$ norm. The results build a parallel for compressive phase retrieval with the classical compressive sensing.
---
paper_title: Robust Compressive Phase Retrieval via L1 Minimization With Application to Image Reconstruction

paper_content:

Phase retrieval refers to a classical nonconvex problem of recovering a signal from its Fourier magnitude measurements. Inspired by the compressed sensing technique, signal sparsity is exploited in recent studies of phase retrieval to reduce the required number of measurements, known as compressive phase retrieval (CPR). In this paper, l1 minimization problems are formulated for CPR to exploit the signal sparsity and alternating direction algorithms are presented for problem solving. For real-valued, nonnegative image reconstruction, the image of interest is shown to be an optimal solution of the formulated l1 minimization in the noise free case. Numerical simulations demonstrate that the proposed approach is fast, accurate and robust to measurements noises.
---
paper_title: Compressive phase retrieval via generalized approximate message passing

paper_content:

In this paper, we propose a novel approach to compressive phase retrieval based on loopy belief propagation and, in particular, on the generalized approximate message passing (GAMP) algorithm. Numerical results show that the proposed PR-GAMP algorithm has excellent phase-transition behavior, noise robustness, and runtime. In particular, for successful recovery of synthetic Bernoulli-circular-Gaussian signals, PR-GAMP requires ≈4 times the number of measurements as a phase-oracle version of GAMP and, at moderate to large SNR, the NMSE of PR-GAMP is only ≈3 dB worse than that of phase-oracle GAMP. A comparison to the recently proposed convex-relation approach known as “CPRL” reveals PR-GAMP's superior phase transition and orders-of-magnitude faster runtimes, especially as the problem dimensions increase. When applied to the recovery of a 65k-pixel grayscale image from 32k randomly masked magnitude measurements, numerical results show a median PR-GAMP runtime of only 13.4 seconds.
---
paper_title: The minimal measurement number for low-rank matrices recovery

paper_content:

Abstract The paper presents several results that address a fundamental question in low-rank matrix recovery: how many measurements are needed to recover low-rank matrices? We begin by investigating the complex matrices case and show that 4 n r − 4 r 2 generic measurements are both necessary and sufficient for the recovery of rank-r matrices in C n × n . Thus, we confirm a conjecture which is raised by Eldar, Needell and Plan for the complex case. We next consider the real case and prove that the bound 4 n r − 4 r 2 is tight provided n = 2 k + r , k ∈ Z + . Motivated by Vinzant's work [19] , we construct 11 matrices in R 4 × 4 by computer random search and prove they define injective measurements on rank-1 matrices in R 4 × 4 . This disproves the conjecture raised by Eldar, Needell and Plan for the real case. Finally, we use the results in this paper to investigate the phase retrieval by projection and show fewer than 2 n − 1 orthogonal projections are possible for the recovery of x ∈ R n from the norm of them, which gives a negative answer for a question raised in [1] .
---

Title: The minimal measurement number problem in phase retrieval: a review of recent developments

Section 1: Introduction
Description 1: Provide an overview of the phase retrieval problem, its importance in various fields, and the fundamental goal of determining the minimal measurement number for unique phase retrieval.

Section 2: Minimal measurement number in real and complex fields
Description 2: Introduce and review the results related to the minimal measurement number \( m_F(d) \) for \( F = \mathbb{R} \) and \( F = \mathbb{C} \).

Section 3: Phase retrieval for sparse signals
Description 3: Discuss the phase retrieval problem under the assumption that the signal \( x_0 \) is s-sparse, including conditions and results related to sparse phase retrieval.

Section 4: Generalized phase retrieval
Description 4: Present the concept of generalized phase retrieval and summarize the results, including the connections to other mathematical topics such as nonsingular bilinear forms and topology embedding.

Section 5: Conclusion
Description 5: Summarize the recent developments reviewed in the paper, highlight the relevance of algebraic geometry and topology in obtaining these results, and discuss generalized problems and open questions for future research.