Phase retrieval with rank d d measurements – descending algorithms phase transitions
Mihailo Stojnic · 2025
Read Phase retrieval with rank d d measurements – descending algorithms phase transitions by Mihailo Stojnic (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-18282.txt.
Introduction
Phase retrieval asks a hard question: can you rebuild a signal from measurements that record only sizes, not phases? Mihailo Stojnic studies the descent algorithms used for the job when each measurement is a rank-d matrix rather than a single vector, the setting that covers both real and complex cases. Using random duality theory, he computes exactly where success flips to failure as the number of measurements per dimension crosses a threshold.
A log-barrier gradient descent built to test the math lands its phase transitions where the theory says they should be, even at modest problem sizes around one hundred. The result gives practitioners a sharp rule for how much data descent methods need.
Catalog record
| CREATOR | Mihailo Stojnic |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 63 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2506-18282
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Phase retrieval with rank d d measurements – descending algorithms phase transitions Mihailo Stojnic Abstract Abstract Companion paper [ 118 ] developed a powerful Random duality theory (RDT) based analytical program to statistically characterize performance of descending phase retrieval algorithms (dPR) (these include all variants of gradient descents and among them widely popular Wirtinger flows). We here generalize the program and show how it can be utilized to handle rank d positive definite phase retrieval (PR) measurements (with special cases d=1 and d=2 serving as emulations of the real and complex phase retrievals, respectively). In particular, we observe that the minimal sample complexity ratio (number of measurements scaled by the dimension of the unknown signal) which ensures dPR’s success exhibits a phase transition (PT) phenomenon. For both plain and lifted RDT we determine phase transitions locations. To complement theoretical results we implement a log barrier gradient descent variant and observe that, even in small dimensional scenarios (with problem sizes on the order of 100), the simulated phase transitions are in an excellent agreement with the theoretical predictions. Index Terms: Phase retrieval; Rank d measurements; Descending algorithms; Random duality theory . 1 Introduction Assume that a unit norm \bar{{\bf x}}\in{\bf R}^{n} is measured through the collection of phaseless measurements \displaystyle{\bf y} \displaystyle= \displaystyle|A\bar{{\bf x}}|^{2}, (1) where A\in{\mathbb{R}}^{m\times n} . Provided access to {\bf y} and A , recovering \bar{{\bf x}} amounts to solving the following system of quadratic equations find \displaystyle{\bf x} subject to \displaystyle|A{\bf x}|^{2}={\bf y}(=|A\bar{{\bf x}}|^{2}). (2) The above is the phase retrieval (PR) problem in its real form. In a host of signal and image processing protocols acquiring signal’s phase is technically infeasible. In such scenarios efficiently solving PRs appears as a key mathematical/algorithmic challenge that allows practical data acquisition and recovery. Fairly reach history of PR applications dates back to early days of x-ray crystallography [ 59 , 86 , 87 ] . Expansion of x-ray crystallography to noncrystalline materials, allowed PR to became an irreplaceable component of coherent diffraction, ptychography, optical, microscopic, and astronomical imaging (see, e.g., [ 123 , 63 , 69 , 83 , 101 , 84 , 18 , 128 , 32 , 42 , 97 , 36 , 17 , 88 ] ). As understanding of main PR principles improved over the last several decades, the range of applications within and outside image processing widened. Some examples of further extensions include digital holography [ 38 , 44 , 45 ] , quantum physics [ 31 , 60 , 55 ] , blind deconvolution/demixing [ 19 , 73 , 68 , 2 ] , and many others. 1.1 A first look at PR’s difficulty In this paper we consider practically relevant scenario where the underlying problem dimensions are large. Moreover, we consider mathematically the most challenging linear/proportional regime \displaystyle\alpha\triangleq\lim_{n\rightarrow\infty}\frac{m}{n}, (3) where \alpha is the so-called oversampling or sample complexity ratio which remains constant as n and m grow. Two aspects of ( 2 ) are important. The first one is of predominantly theoretical character and relates to the “mathematical soundness”. It particularly focuses on algebraic characterizations of uniqueness, injectivity, and stability (see, e.g., [ 30 , 6 , 5 , 10 , 125 ] and references therein). The second is of more practical relevance and relates to algorithmic solving of ( 2 ) (since both \bar{{\bf x}} and -\bar{{\bf x}} are admissible solutions, solving up to a global phase is assumed throughout the paper). The key algorithmic difficulty is the appearance of (squared) magnitudes. A naive removal of magnitudes transforms the problem into an easily solvable linear system but incurs an exponential complexity (on the order of O(2^{m}) ) and is practically useless. 1.2 PR with rank d measurements Since the simple methods (along the lines of the above naive combinatorial approach) were not computationally satisfactory, development of computationally more efficient solvers ensued and a rather vast algorithmic theory has been built. Particularly relevant progress has been made over the last 10-15 years and is in large part due to the appearance of breakthrough papers [ 25 , 21 , 24 ] . One of these breakthroughs, [ 24 ] , uncovered that a simple gradient algorithm (also called Wirtinger flow) can often act as a very successful PR solver. Companion paper [ 118 ] made a strong theoretical progress in justifying such a remarkable gradient property. In particular, [ 118 ] provided phase transition level of performance analysis of a more general class of descending phase retrieval algorithms (dPR). Here we make a substantial progress, move things on a higher level and provide similar phase transition type of analysis for the so-called rank d measurements phase retrieval (basically a rank d variant of ( 2 )). As stated above, ( 2 ) is a phase retrieval real variant. Within the rank d measurements context it is obtained as a special case, d=1 . For d=2 one then obtains the emulation of the complex phase retrieval – a more relevant scenario in some imaging application. Higher ranks d are providing further theoretical support when the measurements’ structure can be controlled beyond what is typically seen in the standard PR imaging applications (for similar higher rank measurements considerations see e.g., [ 40 , 13 , 132 , 133 , 15 , 67 , 61 , 62 , 11 ] ). While the standard phase retrieval is usually described through ( 1 ) and ( 2 ), ( 1 ) can also be rewritten in the following (slightly different) form \displaystyle\bar{{\bf y}}_{i}=|A_{i,:}\bar{{\bf x}}|^{2}=\bar{{\bf x}}^{T}A_{i,:}^{T}A_{i,:}\bar{{\bf x}}=\bar{{\bf x}}^{T}{\cal B}_{(i)}\bar{{\bf x}},\quad{\cal B}_{(i)}=A_{i,:}^{T}A_{i,:},\quad i=1,2,\dots,m, (4) where A_{i,:}\in{\mathbb{R}}^{1\times n} is the i -th row of A . Moreover, the above matrix form of measurements allows one to further describe the data acquisition as \displaystyle\bar{{\bf y}}_{i} \displaystyle= \displaystyle\bar{{\bf x}}^{T}{\cal B}_{(i)}\bar{{\bf x}},\quad{\cal B}_{(i)}^{T}={\cal B}_{(i)}\geq 0\mbox{ is rank $1$},\quad i=1,2,\dots,m. (5) Formulation from ( 5 ) implies that ( 1 ) is the so-called real phase retrieval (PR) with rank 1 positive-semidefinite (PSD) measurements. Its a rank d analogue is then naturally given as \displaystyle\hskip-5.78172pt{\color[rgb]{0,0,1}\textbf{\emph{Rank $d$ measurements (RdM):}}}\quad\quad\bar{{\bf y}}_{i} \displaystyle= \displaystyle\bar{{\bf x}}^{T}{\cal B}_{(i)}\bar{{\bf x}},\quad{\cal B}_{(i)}^{T}={\cal B}_{(i)}\geq 0\mbox{ is rank $d$},\quad i=1,2,\dots,m. (6) Recovering \bar{{\bf x}} provided the access to \bar{{\bf y}} and rank d PSD {\cal B}_{(i)} assumes solving the following inverse feasibility problem (basically rank d measurements analogue to ( 2 )) RdM phase retrieval (RdM PR): find \displaystyle{\bf x} subject to \displaystyle{\bf x}^{T}{\cal B}_{(i)}{\bf x}=\bar{{\bf y}}_{i}(=\bar{{\bf x}}^{T}{\cal B}_{(i)}\bar{{\bf x}}),\quad i=1,2,\dots,m. (7) To be able to make a clear parallel with the standard real and complex PR we take {\cal B}_{(i)} as PSD. In general, however, one can also consider the higher rank indefinite {\cal B}_{(i)} as well [ 61 , 62 ] . Moreover, ( 7 ) can also be rewritten as find \displaystyle X subject to \displaystyle{\rm tr}\,\left({\cal B}_{(i)}X\right)=\bar{{\bf y}}_{i}(=\bar{{\bf x}}^{T}{\cal B}_{(i)}\bar{{\bf x}}),\quad i=1,2,\dots,m (8) \displaystyle X^{T}=X\geq 0,\text{rank}(X)=1. Problems of this type have been extensively studied throughout the low rank recovery literature [ 96 , 124 , 134 , 29 , 50 , 94 , 14 , 27 , 26 ] . Often X’s rank is taken to be proportional to n and the so-called nuclear norm relaxations heuristics have shown a great theoretical promise. Despite being provably polynomial, their