Phase retrieval with rank $d$ measurements -- \emph{descending} algorithms phase transitions

Mihailo Stojnic

REVIEW 3 major objections 5 minor 135 references

Phase retrieval with rank $d$ measurements -- \emph{descending} algorithms phase transitions

T0 review · 3 major / 5 minor · reviewed 2026-08-15 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read For rank-2 phase retrieval, descending algorithms hit a sharp success threshold at 2.79 measurements per unknown.

desk verdict A real rank-d generalization of the author's RDT phase-transition program with new explicit d=2 formulas, but the headline thresholds are lower-bound estimates and the landscape-to-algorithm link is imported rather than proved here. read the letter →

arxiv 2506.18282 v1 pith:BG7PMI7R submitted 2025-06-23 stat.ML cs.ITcs.LGmath.IT

Mihailo Stojnic This is my paper · ORCID

classification stat.MLcs.ITcs.LGmath.IT MSC 60B2090C26

keywords phaseretrievalrankdmeasurementsdescendingalgorithmsrandomdualitytheorytransitionWirtingerflowsamplecomplexityratiocomplex

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper generalizes the companion rank-1 random duality theory (RDT) program to phase retrieval with rank-$d$ positive-semidefinite measurements, and uses it to predict when descending algorithms--gradient-descent-type solvers such as Wirtinger flow--succeed or fail in the high-dimensional limit. The central object is the fundamental RdM PR optimization $\xi(c,x)$; the paper computes a random-dual lower bound $\varphi_0$ whose shape, as a function of the overlap $x$, decides whether the objective has one minimum or two. For the practically important rank-2 case, which emulates complex phase retrieval, plain RDT predicts the phase transition at sample complexity ratio $\alpha \approx 2.79$, while lifted RDT lowers the estimate to roughly $2.3$--$2.5$ depending on initializer quality. A log-barrier gradient descent experiment at dimension $n=100$ finds transition points close to the safer compression adjusted theory. The result matters because it condenses the question of whether a descending algorithm works into a single threshold $\alpha$ for each rank $d$.

What carries the argument

The load-bearing object is the fundamental RdM PR optimization (fd-pro), $\xi(c,x)$, defined as the minimum over $x$ and auxiliary $z$ of the sum of squared differences between measured and candidate amplitude roots, subject to $Ax=z$, $x^T\bar{x}=x$, and $\|x\|_2^2=c$. Random duality theory replaces the random primal with a random dual whose expected value $\varphi_0$ the paper evaluates via non-central chi distributions; for $d=2$ the evaluation reduces to integrals of modified Bessel functions $I_0$ and $I_1$. The predictive instrument is the curve $\sqrt{\varphi_0}$ as a function of the overlap $x$ at $c=1$: a second minimum at $x=0$ indicates that a descending algorithm can be trapped, and its disappearance marks the phase transition. Lifted RDT refines the bound with a partially lifted dual and a large-deviation functional, lowering the predicted transition. The safer compression adjustment is a finite-dimensional heuristic that moves the working $\alpha$ about 10--20% above the asymptotic threshold to avoid local jitteriness.

What would settle it

At $n=1000$ with Gaussian rank-2 measurements, run a descending solver (for instance the paper's log-barrier gradient or a Wirtinger flow) with optimal diagonal spectral initialization over at least 100 random trials per value of $\alpha$, sweeping $\alpha$ from 2.2 to 3.0 in steps of 0.05. If the empirical success probability transitions far from the predicted plain-RDT value $\alpha \approx 2.79$ (or from the $\approx 2.3$--$2.5$ lifted range), or if a second local minimum of $\xi(1,x)$ survives at $\alpha > 2.79$, the landscape-to-algorithm prediction fails.

Watch

Extended reading notes

Core claim

The paper claims that for rank-$d$ measurements $B^{(i)} = \sum_{j=0}^{d-1} A_{jm+i,:}^T A_{jm+i,:}$ with iid standard Gaussian $A \in \mathbb{R}^{dm \times dn}$, the behavior of descending algorithms is controlled by the fd-pro objective $\xi(c,x)$: when the random-dual limit $\varphi_0$ is positive, $\xi(c,x)/(dn)>0$ for $x \neq 1$ with probability tending to one, and the phase retrieval problem is uniquely solvable up to global phase. It then identifies the dPR phase transition with the disappearance of the secondary minimum of $\sqrt{\varphi_0}$ at $x=0$ for $c=1$: curves for $\alpha=2.4$ and $\alpha=2.6$ have that minimum, while around $\alpha \approx 2.79$ the curve flattens and the minimum disappears. Because strong random duality is not in place, the plain RDT estimates are strictly lower bounds, and a lifted RDT version--using the partially lifted dual--produces decreasing curves already at $\alpha=2.5$ and, with optimal diagonal spectral initializers, a transition near $\alpha=2.3$. The paper reports simulations at $n=100$ using a log-barrier gradient descent with spectral initialization; the empirical transition falls close to the safer compression adjusted theoretical prediction.

Load-bearing premise

The load-bearing premise is that the landscape of the fd-pro objective--specifically whether $\xi(c,x)$ or its RDT lower-bound curve has a single minimum at $(c=1,x=1)$--determines whether descending algorithms converge on random instances; this landscape-to-algorithm link is imported from the companion paper and is never derived for the actual gradient dynamics.

Editorial extensions

If this is right

Above the predicted threshold, descending phase retrieval algorithms succeed with probability tending to one on Gaussian rank-$d$ measurements; below it, the objective's second minimum at $x=0$ means badly initialized descent can be trapped.
For the rank-2 case that emulates complex phase retrieval, plain RDT gives $\alpha \approx 2.79$ as the dPR phase transition, and lifted RDT lowers the usable transition to about $\alpha=2.5$ for the decreasing-curve regime and $\alpha \approx 2.3$ with optimal diagonal spectral initializers.
Because the same integrals extend to any rank $d$, the framework yields explicit phase-transition predictions for higher-rank measurements, with $d=1$ and $d=2$ recovering the real and complex phase retrieval scenarios.
In finite dimensions the safer compression rule recommends operating 10--20% above the asymptotic threshold; the $n=100$ simulations show the empirical transition near this adjusted value rather than at the raw asymptotic point.
The lack of strong random duality means the plain RDT numbers are strict lower bounds, so the lifted RDT estimates, not the plain ones, are the ones to use for predicting actual algorithm performance.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

A direct test would run unconstrained Wirtinger flow (not the constrained log-barrier variant) on the same rank-2 Gaussian model: the paper's landscape-to-algorithm link suggests the same thresholds near 2.3--2.79 should hold, but that is not derived for unconstrained dynamics in this paper.
If the phase transition depends monotonically on $d$, the required $\alpha$ should shrink as $d$ grows because each measurement carries $d$ independent Gaussian rows; computing the rank-3 and rank-4 transitions from the same Bessel/Laguerre integrals would settle this and is not done in the paper.
The Gaussian rotational invariance is central to the argument, so non-Gaussian or orthogonal measurement ensembles should shift or smear the transition; quantifying the shift would delimit how universal the predicted thresholds are.
The safer compression adjustment is an asymptotic-to-finite heuristic; a sharper finite-$n$ analysis could replace it by estimating the probability that local jitteriness creates traps as a function of $n$ and $\alpha$.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Short version: this is a genuine extension of the companion RDT program from rank-1 to rank-d phase retrieval, with new explicit formulas for d=2. But the advertised α≈2.79 should be read as a lower-bound-derived landscape estimate, not an established phase transition threshold. The simulation is supportive but not sharp enough to fix the exact location.

What the paper does well: the rank-d generalization is not in the cited prior literature; the d=2 Laguerre/Bessel expressions are new and concrete; the derivation is systematic and follows a documented methodology; and the lifted RDT section is a real improvement, giving a lower α around 2.5. The author is also candid about the lack of strong random duality and about finite-n jitteriness. No fitted constants enter the core φ0 formulas, so the central derivation is not circular in the strong sense.

The main soft spot is exactly where the stress-test note lands. Section 2.1 explicitly says plain RDT gives strict lower bounds on ξ(c,x), and Section 3 shows lifted RDT lowering the relevant α to about 2.5. So 'the dPR phase transitioning sample complexity ratio is α ≈ 2.79' overstates what the derivation supports: 2.79 is where the lower-bound curve loses its x=0 minimum, not the established location of the true landscape transition. The lifted α≈2.5 is also a partially lifted lower bound, not an exact threshold. These should be labeled as estimates from below, with the fully lifted RDT as the natural route to a definitive value.

The second soft spot is the landscape-to-algorithm step. The claim that a single minimum of ξ(c,x) at (c=1,x=1) makes descending algorithms succeed is imported from [118], not derived for the gradbar dynamics used here. The simulation partially covers this gap, but it minimizes a squared-magnitude log-barrier objective while the theory is for amplitude loss, and the 'safer compression' adjustment is hand-set at 10–20%. Figure 6 is consistent with a transition near the adjusted prediction, but it is not a sharp test of α≈2.79. No code or detailed protocol is given, which matters for a paper whose main evidence beyond the derivation is one simulation curve.

The citation pattern is heavily self-referential, but that is not a flaw here: the methodology genuinely comes from [118], and the author credits that dependence clearly. The paper is honestly written about its own limitations, which makes the few overstatements easy to isolate.

Who gets value from this: researchers working on nonconvex phase retrieval and on RDT-style lower bounds, especially anyone wanting explicit rank-d formulas or a template for extending RDT to other rank-d problems. It deserves a serious referee. The main revision requests should be: clarify that the thresholds are lower-bound estimates, reconcile or justify the amplitude-versus-squared-magnitude mismatch, and release code and full experimental details. I would engage with it as a conditional paper, not a reject.

Referee Report

3 major / 5 minor

Summary. This paper extends the author's random duality theory (RDT) program for descending phase retrieval algorithms (dPR) to rank d positive semidefinite measurements, with d = 2 treated as an emulation of complex phase retrieval. The author derives a lower bound on the scaled fundamental dPR objective ξ(c, x) via plain RDT (Section 2.1), observes that the lower-bound curve loses its spurious x = 0 minimum at α ≈ 2.79 (Section 2.2), develops a partially lifted RDT version that lowers the operating estimate to about α = 2.5 (Section 3), and reports simulations of a log-barrier gradient algorithm (gradbar) at n = 100 showing a transition near a "safer compression" adjusted value (Section 4, Figure 6). The abstract claims that phase transition locations are determined for both plain and lifted RDT.

Significance. If the quantitative phase-transition predictions were established, the paper would provide a useful design rule for practitioners and a rare precise statistical characterization of descending algorithms for rank d phase retrieval. Strengths include the explicit closed-form evaluation of f_q for d = 2 in Eq. (37), the step-by-step adaptation of the RDT machinery to the rank d setting, the recognition that the results are lower bounds, and a concrete, reproducible simulation protocol (gradbar with spectral initialization). However, the central threshold α ≈ 2.79 is inferred from a strict lower-bound curve, not from the actual objective, and the landscape-to-algorithm link is imported from the author's companion paper [118] rather than derived here. The significance is therefore conditional on these gaps being closed or the claims being appropriately weakened.

major comments (3)

[Section 2.2, Figure 1, Eq. (30)] The claimed phase transition at α ≈ 2.79 is read off from the disappearance of the x = 0 minimum of the plain-RDT lower-bound curve √φ0, not from the actual fd-pro objective ξ(c, x). Section 2.1, step 4 explicitly states that strong random duality is not in place and that these results are strict lower bounds. A lower-bound curve losing a spurious minimum is only a sufficient condition for the landscape condition on the true objective; ξ(c, x) may lose its bad minimum at a smaller α. Consequently, the sentence "RDT predicts the dPR phase transitioning sample complexity ratio to be α ≈ 2.79" is not supported by the derivation. The manuscript should either present 2.79 as an upper estimate/guarantee threshold or provide a concrete way to quantify the gap (for example, by comparing the lifted threshold with a simulation using the amplitude-based objective).
[Sections 2.2 and 4, Eqs. (49)–(50)] The inference from "ξ(c, x) has a single minimum" to "descending algorithms converge" is taken from the companion paper [118] and is not derived for the gradbar dynamics used in the simulations. Moreover, gradbar minimizes fbar (Eq. (49)) built on the squared-magnitude loss fplain (Eq. (50)), whereas the theory analyzes the amplitude-based fd-pro objective ξ(c, x). The agreement in Figure 6 therefore tests a different objective and a different algorithm than the one analyzed, so it cannot directly validate the predicted landscape condition or the specific value α ≈ 2.79. The authors should either supply a derivation of the landscape-to-algorithm correspondence for the actual dynamics or explicitly frame the simulation as a heuristic consistency check and state the objective mismatch in Section 4.
[Section 3, Eq. (48), Figures 3–5] The abstract claims that "for both plain and lifted RDT we determine phase transitions locations," but the lifted analysis does not actually determine a threshold. Equation (48) is again a lower bound (via Theorem 2 and Eq. (39)), and the text selects α = 2.5 as a convenient operating point, states that "there is really not much point in doing so" for the limiting transition, and only loosely associates a transition "around 2.3" with the spectral initializer's overlap. To support the abstract claim, the manuscript should give a precise characterization of the lifted threshold or explicitly restrict the claim to the plain-RDT lower-bound estimate.

minor comments (5)

[Abstract] The phrase "Wirt inger flows" contains a spacing typo and should be "Wirtinger flows."
[Section 1 and throughout] The dependence of the main claims on the unpublished companion paper [118] should be stated more prominently, since the landscape-to-algorithm step and parts of the random-dual machinery are not re-derived here.
[Section 2, Eq. (13)] The constraint "xT ¯x = x" in Eq. (13) is confusing because the same symbol x denotes both the vector and the scalar overlap; the later notation x1 = x in Eq. (15) should be introduced earlier.
[Section 4, Figure 6] Figure 6 would be more informative if the empirical transition point were reported numerically and compared explicitly with the plain-RDT, lifted-RDT, and safer-compression values, since the current text describes the agreement only qualitatively.
[Section 2.1, step 4, and Conclusion] The strict-lower-bound nature of the results is stated in the body, but the abstract and conclusion present the phase-transition locations as determined; adding a caveat there would accurately represent the strength of the results.

Circularity Check

2 steps flagged · score 4.0 of 10

Central phase-transition prediction rests on the landscape-to-algorithm link imported from the author's companion paper [118]; the φ0 derivation itself is parameter-free.

self citation load bearing [Section 2.2, 'Numerical evaluations and algorithmic implications' (see also Section 2 opening)]
"As discussed in great detail in [118], behavior of ξ(c, x) is directly related to the performance of the descending phase retrieval algorithms (dPR). The above results allow to evaluate φ0 and by doing so to estimate ξ(c, x)."

The central number α≈2.79 is read off from the φ0 lower-bound curve via the single-minimum criterion. The conversion of that landscape condition into a claim about dPR algorithm success is made solely by citing [118]; no rank-d landscape-to-dynamics theorem is derived here. Since [118] is the author's own unverified companion paper and Section 2.1 explicitly says strong random duality is not in place and the plain RDT results are strict lower bounds, the algorithmic phase-transition conclusion reduces to the self-citation rather than to a derivation appearing in this paper.
other [Section 2.2 ('safer compression' rule) and Section 4 / Figure 6]
"To combat such eventualities it is often practically safer to follow a simple “safer compression” rule of thumb which suggests to operate in sample complexity ratio regimes that are slightly (say 10 − 15%) above the phase transitioning prediction. ... the simulated phase transition is fairly close to the “safer compression” adjustment of the theoretical predictions."

The 10–20% shift is not derived from the RDT computation; it is a user-chosen offset. The simulation is then compared to the shifted curve, so the reported agreement partly reflects the freedom to set this offset rather than an independent confirmation of the unadjusted values α≈2.79 or 2.5. This is a mild validation circularity, not a fitted constant inside φ0.

full rationale

The plain- and lifted-RDT evaluations of φ0 are parameter-free: equations (28)–(30), (37), and (42)–(48) compute expectations over Gaussian and chi distributions and contain no constants fitted to simulations. Thus the core numerical derivation is not circular in the sense of a fitted parameter being renamed as a prediction. The circularity is located at the algorithmic interpretation: the paper asserts that the shape of ξ(c,x), and of its RDT lower bound φ0, determines dPR convergence, and this assertion is imported from the author's own companion paper [118] without a rank-d derivation. The strict-lower-bound caveat in Section 2.1 (strong random duality not in place) and the hand-set 'safer compression' margin (10–20%) further mean that the specific value α≈2.79 and the Figure 6 agreement are not fully independent tests of a derived law. Because the φ0 landscape computation itself has independent mathematical content, the overall circularity is partial rather than complete.

Assumptions & free parameters 2 free parameters · 5 assumptions · 0 invented entities

No new physical entity is introduced. The calculation rests on the Gaussian measurement model, the imported landscape-to-algorithm correspondence from the companion paper, and an amplitude-versus-intensity equivalence; the main hand-set input is the safer compression margin used in the simulation comparison.

free parameters (2)

safer compression margin = 10 to 20 percent (rule of thumb, not fitted)
Introduced in Section 2.2 and used to align the n=100 simulation with theory in Figure 6; the reported agreement depends on this hand-chosen upward adjustment.
gradbar schedule parameters = t0=0.01, growth factor 1.6, final t0 about 1e7
Log barrier gradient descent hyperparameters chosen in Section 4; not part of the analytical theory but required for the reported simulation.

assumptions (5)

domain assumption Measurement matrix A has iid standard normal entries and B_i is PSD of rank d built from d rows of A.
Section 2 states 'we consider a statistical scenario with A comprised of iid standard normals.' The entire RDT calculation depends on Gaussian rotational invariance.
domain assumption The fd-pro landscape, specifically whether ξ(c,x) has a single minimum at c=1, x=1, determines whether descending phase retrieval algorithms converge.
Section 2.2: 'behavior of ξ(c,x) is directly related to the performance of the descending phase retrieval algorithms', imported from [118]; no trajectory-level proof is given.
domain assumption Amplitude measurements (non-squared magnitudes) are conceptually equivalent to intensity measurements for the phase transition analysis.
Section 2: 'not much of a conceptual difference between the two options actually exists'; this justifies the amplitude objective used in theory while the simulation uses squared magnitudes.
standard math Gordon's comparison theorem and Gaussian concentration inequalities apply to the random primal and random dual objects.
Theorem 1 proof cites Gordon's comparison theorem and Stojnic's comparison results [112,113]; concentration of measure is used to replace frp by its expectation.
domain assumption Spectral initializers fall outside the flat region of the lifted RDT curve, so their overlap is high enough for descent to succeed.
Section 3, Figures 3 to 5 discussion; the simulation relies on the optimal diagonal spectral initializer, and theory assumes initializer overlap is measurement-independent.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Phase retrieval with rank $d$ measurements -- \emph{descending} algorithms phase transitions." pith.science (2026). https://pith.science/paper/BG7PMI7R

@misc{pith2026250618282,
  author       = {Pith},
  title        = {Pith review of: Phase retrieval with rank $d$ measurements -- \emphdescending algorithms phase transitions},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/BG7PMI7R}},
  note         = {Machine review of arXiv:2506.18282}
}

abstract

Companion paper [118] developed a powerful \emph{Random duality theory} (RDT) based analytical program to statistically characterize performance of \emph{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.

Figures

Figures reproduced from arXiv: 2506.18282 by the authors.

**Figure 1.** φ0 as a function of x for different values of α; fixed c = 1; plain RDT show that the above (plain RDT) α estimates can indeed be lowered. 3 Lifted RDT A lack of strong random duality implies that the above bounds are strict which then allows for their further lifting. Recent development of fully lifted (fl) RDT [114] allows the ultimate lifting and a precise characterization of the optimal α values. However, imple… view at source ↗

**Figure 2.** φ0 as a function of x for different values of c; fixed α = 2.79; plain RDT limn→∞ PA(frp(c, x; A) > φ¯ 0) −→ 1, (39) and (φ¯ 0 > 0) =⇒ limn→∞ PA(frp(c, x; A) > 0) −→ 1 =⇒ limn→∞ PA (RdM PR is (uniquely) solvable) −→ 1 . (40) Proof. Follows as a trivial extension of Theorem 2 in [118], which for any fixed ry is an automatic application of Corollary 3 from [112] (see in particular Section 3.2.1 and equation (… view at source ↗

**Figure 3.** φ0 as a function of x; fixed α = 2.5; Lifted RDT To get the limiting phase transition (valid for any nonzero overlap initializer) one would need to check for an α for which the lifted curve remains the flattest in the low x range. Since the flat regions become rather large and the associated sample complexity ratios often unusable in practice there is really not much point in doing so. Instead we selected α = 2.5 as… view at source ↗

Figures from the paper (3 more)

**Figure 4.** Figure 4: φ0 as a function of x; fixed α = 2.3; Lifted RDT properties (beyond optimal objectives landscape) might play in generic PR solvability. In particular, the entire discussion regarding overlap gap property (OGP) [1, 34, 46–49, 82, 90] and local entropy (LE) [7–9] applies…

**Figure 5.** Figure 5: φ0 as a function of x; fixed α = 2.2; Lifted RDT n = 100 and denote by xˆ the obtained estimate of x¯. As can be seen, the simulated phase transition is fairly close to the “safer compression” adjustment of the theoretical predictions. This happens despite the fact tha…

**Figure 6.** Figure 6: Simulation – gradbar; d = 2; n = 100 The above fplain(x) utilizes squared magnitudes in the parenthesis and therefore slightly differs from the corresponding one used in theoretical considerations. The variant from (50) is practically more convenient as the derivatives…

Review history (2 revisions) →

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

135 extracted references · 13 canonical work pages

[118]

M. Stojnic. Phase transition of descending phase retrieval algorithms. 2025. available online at arxi v

2025
[1]

Achlioptas, A

D. Achlioptas, A. Coja-Oghlan, and F. Ricci-Tersenghi. On the solution-space geometry of random constraint satisfaction problems. Random Struct. Algorithms , 38(3):251–268, 2011

2011
[2]

Ahmed, B

A. Ahmed, B. Recht, and J. Romberg. Blind deconvolution u sing convex programming. IEEE Trans- actions on Information Theory , 60(3):1711–1732, 2013

2013
[3]

Aubin, B

B. Aubin, B. Loureiro, A. Baker, F. Krzakala, and L. Zdebo rová. Exact asymptotics for phase retrieval and compressed sensing with random generative priors. In Proceedings of Mathematical and Scientiﬁc Machine Learning, MSML 2020, 20-24 July 2020, Virtual Confere nce / Princeton, NJ, USA , volume 107 of Proceedings of Machine Learning Research , pages 55–...

arXiv 2020
[4]

Bahmani and J

S. Bahmani and J. Romberg. Phase retrieval meets statist ical learning theory: A ﬂexible convex relaxation. Electronic Journal of Statistics , 11:5254–5281, 2016. 18

2016
[5]

Balan, B

R. Balan, B. Bodmann, P. Casazza, and D. Edidin. Painless reconstruction from magnitudes of frame coeﬃcients. J. Four. Anal. Appl. , 15:488–501, 2009

2009
[6]

Balan, P

R. Balan, P. Casazza, and D. Edidin. On signal reconstruc tion without phase. Applied and Computa- tional Harmonic Analysis , 20(3):343–356, 2006

2006
[7]

Baldassi, A

C. Baldassi, A. Ingrosso, C. Lucibello, L. Saglietti, an d R. Zecchina. Subdominant dense clusters allow for simple learning and high computational performance in n eural networks with discrete synapses. Physical Review letters , 115(12):128101, 2015

2015

Show all 135 references

[8]

Baldassi, A

C. Baldassi, A. Ingrosso, C. Lucibello, L. Saglietti, an d R. Zecchina. Local entropy as a measure for sampling solutions in constraint satisfaction problems. Journal of Statistical Mechanics: Theory and Experiment, (2):021301, 2016

2016
[9]

Baldassi, R

C. Baldassi, R. D. Vecchia, C. Lucibello, and R. Zecchina . Clustering of solutions in the symmetric binary perceptron. Journal of Statistical Mechanics: Theory and Experiment , (7):073303, 2020

2020
[10]

A. S. Bandeira, J. Cahill, D. G. Mixon, and A. A. Nelson. S aving phase: Injectivity and stability for phase retrieval. Applied and Computational Harmonic Analysis , 37(1):106–125, 2014

2014
[11]

Barahona, M

F. Barahona, M. Grotschel, M. Junger, , and G. Reinelt. A n application of combinatorial optimization to statistical physics and circuit layout design. Operations Research, 36(3):6493–513, 1988

1988
[12]

Barbier, F

J. Barbier, F. Krzakala, N. Macris, L. Miolane, and L. Zd eborová. Optimal errors and phase transi- tions in high-dimensional generalized linear models. In Conference On Learning Theory, COLT 2018, Stockholm, Sweden, 6-9 July 2018 , volume 75 of Proceedings of Machine Learning...

2018 arXiv
[13]

Basu and Y

S. Basu and Y. Bresler. Uniqueness of tomography with un known view angles. IEEE Transactions on Image Processing, 9(6):1094–1106, 2000

2000
[14]

Bhojanapalli, B

S. Bhojanapalli, B. Neyshabur, and N. Srebro. Global op timality of local search for low rank ma- trix recovery. In Proceedings of the 30th International Conference on Neural Inf ormation Processing Systems, pages 3880–3888, Red Hook, NY, USA, 2016. Curran Associate s Inc

2016
[15]

S. J. L. Billinge. Viewpoint: The nanostructure proble m. Physics, 3(25), 2010

2010
[16]

A. Bora, A. Jalal, E. Price, and A. G. Dimakis. Compresse d sensing using generative models. In Proceedings of the 34th International Conference on Machine L earning, ICML 2017, Sydney, NSW, Australia, 6-11 August 2017 , volume 70 of Proceedings of Machine Learning Research , ...

2017
[17]

Bruck and L.G

Y.M. Bruck and L.G. Sodin. On the ambiguity of the image r econstruction problem. Opt. Comm. , 30:304–308, 1979

1979
[18]

O. Bunk, A. Diaz, F. Pfefer, C. David, B. Schmitt, D. K. Sa tapathy, and J. F. Veen. Diﬀractive imaging for periodic samples: retrieving one-dimensional concent ration proﬁes across microuidic channels. Acta Crystallographica Section A: Foundations of Crystallograph y, 63(4):3...

2007
[19]

K. Wang C. Ma, Y. Chi, and Y. Chen. Implicit regularizati on in nonconvex statistical estimation: Gradient descent converges linearly for phase retrieval, m atrix completion, and blind deconvolution. Foundations of Computational Mathematics , pages 1–182, 2018

2018
[20]

T T. Cai, X. Li, and Z. Ma. Optimal rates of convergence fo r noisy sparse phase retrieval via thresholded Wirtinger ﬂow. The Annals of Statistics , 44(5):2221–2251, 2016

2016
[21]

E. J. Candès, Y. C. Eldar, T. Strohmer, and V. Voroninski . Phase retrieval via matrix completion. SIAM J. Imaging Sci. , 6(1):199–225, 2013. 19

2013
[22]

E. J. Candès and X. Li. Solving quadratic equations via p haselift when there are about as many equations as unknowns. Found. Comput. Math. , 14(5):1017–1026, 2014

2014
[23]

E. J. Candès, X. Li, and M. Soltanolkotabi. Phase retrie val from coded diﬀraction patterns. Applied and Computational Harmonic Analysis , 39(2):277–299, 2015

2015
[24]

E. J. Candès, X. Li, and M. Soltanolkotabi. Phase retrie val via Wirtinger ﬂow: Theory and algorithms. IEEE Trans. Inf. Theory , 61(4):1985–2007, 2015

1985
[25]

E. J. Candès, T. Strohmer, and V. Voroninski. Phaselift : Exact and stable signal recovery from magnitude measurements via convex programming. Comm. Pure Appl. Math. , 66:1241–1274, 2013

2013
[26]

Capponi and M

A. Capponi and M. Stojnic. Sparse vector and low rank rec overy phase transitions: Uncovering the explicit relations. IEEE Transactions on Information Theory , 70(12):9239–9260, 2024

2024
[27]

Carlsson and D

M. Carlsson and D. Gerosa. On phase retrieval via matrix completion and the estimation of low rank psd matrices. Inverse Problems, 36(1):015006, dec 2019

2019
[28]

Chen and E

Y. Chen and E. J. Candès. Solving random quadratic syste ms of equations is nearly as easy as solving linear systems. Comm. Pure Appl. Math. , 70(5):822–883, 2017

2017
[29]

Y. Chi, Y. M. Lu, and Y. Chen. Nonconvex optimization mee ts low-rank matrix factorization: An overview. IEEE Transactions on Signal Processing , 67(20):5239–5269, 2019

2019
[30]

Conca, D

A. Conca, D. Edidin, M. Hering, and C. Vinzant. An algebr aic characterization of injectivity in phase retrieval. Applied and Computational Harmonic Analysis , 38(2):346–245, 2015

2015
[31]

J. V. Corbett. The Pauli problem, state reconstruction and quantum-real numbers. Rep. Math. Phys. , 57:53–68, 2006

2006
[32]

J. C. Dainty and J. R. Fienup. Image recovery: Theory and application. Phase retrieval and image reconstruction for astronomy, 21:231–275, Aug 1987

1987
[33]

Daskalakis, D

C. Daskalakis, D. Rohatgi, and E. Zampetakis. Constant -expansion suﬃces for compressed sensing with generative priors. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, De cember 6-12, 2020,...

2020
[34]

Daude, M

H. Daude, M. Mezard, T. Mora, and R. Zecchina. Pairs of sa t-assignments in random boolean formulae. Theoretical Computer Science , 393(1):260–279, 2008

2008
[35]

Dhifallah, C

O. Dhifallah, C. Thrampoulidis, and Y. M. Lu. Phase retr ieval via linear programming: Fundamental limits and algorithmic improvements. In 55th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2017, Monticello, IL, USA, October 3- 6, 2017, pages 10...

2017
[36]

Dierolf, A

M. Dierolf, A. Menzel, P. Thibault, P. Schneider, C. M. K ewish, A. Wepf, O. Bunk, and F. Pfeiﬀer. Ptychographic x-ray computed tomography at the nanoscale. Nature, 477(7314):436–439, 2010

2010
[37]

Donoho, A

D. Donoho, A. Maleki, and A. Montanari. Message-passin g algorithms for compressed sensing. Proc. National Academy of Sciences , 106(45):18914–18919, Nov. 2009

2009
[38]

Duadi, O

H. Duadi, O. Margalit, V. Mico, J. A. Rodrigo, T. Alieva, J. Garcia, and Z. Zalevsky. Digital holography and phase retrieval. In J. Rosen, editor, Source: Holography, Research and Technolo gies. InTech, 2011

2011
[39]

Dudeja, M

R. Dudeja, M. Bakhshizadeh, J. Ma, and A. Maleki. Analys is of spectral methods for phase retrieval with random orthogonal matrices. IEEE Trans. Inf. Theory , 66(8):5182–5203, 2020

2020
[40]

Duxbury, L

P.M. Duxbury, L. Granlund, S.R. Gujarathi, P. Juhas, an d S.J.L. Billinge. The unassigned distance geometry problem. Discrete Appl. Math. , 204(C):117–132, May 2016

2016
[41]

Fannjiang and Z

A. Fannjiang and Z. Zhang. Fixed point analysis of Dougl as-Rachford splitting for ptychography and phase retrieval. SIAM J. Imaging Sci. , 13(2):609–650, 2020. 20

2020
[42]

J. R. Fienup. Reconstruction of an object from the modul us of its Fourier transform. Optics letters , 3(1):27–29, Aug 1978

1978
[43]

J. R. Fienup. Phase retrieval algorithms: a comparison . Appl. Opt. , 21(15):2758–2769, Aug 1982

1982
[44]

D. Gabor. A new microscopic principle. Nature, 161:777778, 1948

1948
[45]

Gabor, G

D. Gabor, G. W. Stroke, D. Brumm, A. Funkhouser, and A. La beyrie. Reconstruction of phase objects by holography. Applied and Computational Harmonic Analysis , 208(516):1159–1162, 1965

1965
[46]

Gamarnik

D. Gamarnik. The overlap gap property: A topological ba rrier to optimizing over random structures. Proceedings of the National Academy of Sciences , 118(41), 2021

2021
[47]

Gamarnik and M

D. Gamarnik and M. Sudan. Limits of local algorithms ove r sparse random graphs. Proceedings of the 5th conference on innovations in theoretical computer scie nce, pages 369–376, 2014

2014
[48]

Gamarnik and M

D. Gamarnik and M. Sudan. Limits of local algorithms ove r sparse random graphs. Ann. Probab., 45(4):2353–2376, 2017

2017
[49]

Gamarnik and M

D. Gamarnik and M. Sudan. Performance of sequential loc al algorithms for the random NAE-K-SAT problem. SIAM Journal on Computing , 46(2):590–619, 2017

2017
[50]

R. Ge, C. Jin, and Y. Zheng. No spurious local minima in no nconvex low rank problems: a uniﬁed geometric analysis. In Proceedings of the 34th International Conference on Machine L earning - Volume 70, pages 1233–1242. JMLR.org, 2017

2017
[51]

R. A. Gerchberg and W. O. Saxton. A practical algorithm f or the determination of phase from image and diﬀraction plane pictures. Optik, 35:237–246, 1972

1972
[52]

Goldstein and C

T. Goldstein and C. Studer. PhaseMax: Convex phase retr ieval via basis pursuit. IEEE Trans. Inf. Theory, 64(4):2675–2689, 2018

2018
[53]

Y. Gordon. On Milman’s inequality and random subspaces which escape through a mesh in Rn. Geometric Aspect of of functional analysis, Isr. Semin. 1986-8 7, Lect. Notes Math , 1317, 1988

1986
[54]

Gross, F

D. Gross, F. Krahmer, and R. Kueng. Improved recovery gu arantees for phase retrieval from coded diﬀraction patterns. Applied and Computational Harmonic Analysis , 42(1):37–64, 2017

2017
[55]

J. Haah, A. W. Harrow, Z. Ji, X. Wu, and N. Yu. Sample-opti mal tomography of quantum states. IEEE Trans. Inf. Theory , 63(9):5628–5641, 2017

2017
[56]

P. Hand. Phaselift is robust to a constant fraction of ar bitrary errors. Applied and Computational Harmonic Analysis , 42(3):550–362, 2017

2017
[57]

P. Hand, O. Leong, and V. Voroninski. Phase retrieval un der a generative prior. In Advances in Neural Information Processing Systems 31: Annual Conference on Neur al Information Processing Systems 2018, NeurIPS 2018, December 3-8, 2018, Montréal, Canada , pages 9154–9164, 2018

2018
[58]

Hand and V

P. Hand and V. Voroninski. An elementary proof of convex phase retrieval in the natural parameter space via the linear program phaseMax. 2016. available onli ne at http://arxiv.org/abs/1611. 03935

2016
[59]

R. W. Harrison. Phase problem in crystallography. J. Opt. Soc. Am. A , 10(5):1046–1055, May 1993

1993
[60]

Heinosaari, L

T. Heinosaari, L. Mazzarella, and M. M. Wolf. Quantum to mography under prior information. Com- munications in Mathematical Physics , 318(2):355–374, 2013

2013
[61]

Huang, S

S. Huang, S. Gupta, and I. Dokmanic. Solving complex qua dratic equations with full-rank random gaussian matrices. In ICASSP 2019 - 2019 IEEE International Conference on Acoustics, S peech and Signal Processing (ICASSP) , pages 5596–5600, 2019. 21

2019
[62]

Huang, S

S. Huang, S. Gupta, and I. Dokmanic. Solving complex qua dratic systems with full-rank random matrices. IEEE Transactions on Signal Processing , 68:4782–4796, 2020

2020
[63]

N. Hurt. Phase Retrieval and Zero Crossings . Kluwer Academic Publishers, Norwell, MA, 1989

1989
[64]

M. Iwen, A. Viswanathan, and Y. Wang. Robust sparse phas e retrieval made easy. Applied and Computational Harmonic Analysis , 42(1):135–142, 2017

2017
[65]

Jaganathan, S

K. Jaganathan, S. Oymak, and B. Hassibi. Sparse phase re trieval: Uniqueness guarantees and recovery algorithms. IEEE Trans. Signal Process. , 65(9):2402–2410, 2017

2017
[66]

Jordan and A

M. Jordan and A. G. Dimakis. Exactly computing the local lipschitz constant of relu networks. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, v irtual, 2020

2020
[67]

Juhas, D

P. Juhas, D. M. Cherba, P. M. Duxbury, W. F. Punch, and S. J . L. Billinge. Ab initio determination of solid-state nanostructure. Nature, 440:655–658, 2006

2006
[68]

P. Jung, F. Krahmer, and D. Stroger. Blind demixing and d econvolution at near-optimal rate. IEEE Transactions on Information Theory , 44(2):704–727, 2017

2017
[69]

M. V. Klibanov, P. E. Sacks, and A. V. Tikhonravov. The ph ase retrieval problem. Inverse Problems, 11(1):1, feb 1995

1995
[70]

Kueng, H

R. Kueng, H. Rauhut, and U. Terstiege. Low rank matrix re covery from rank one measurements. Applied and Computational Harmonic Analysis , 42(1):88–116, 2017

2017
[71]

Q. Lei, A. Jalal, I. S. Dhillon, and A. G. Dimakis. Invert ing deep generative models, one layer at a time. In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, December 8- 14, 2019, Vancouver, ...

2019
[72]

K.-C. Li. On principal hessian directions for data visu alization and dimension reduction: Another application of Stein’s lemma. J. Am. Stat. Assoc. , 87(420):1025–1039, 1992

1992
[73]

X. Li, S. Ling, T. Strohmer, and K. Wei. Rapid, robust, an d reliable blind deconvolution via nonconvex optimization. Applied and computational harmonic analysis , 47(3):893–934, 2017

2017
[74]

Li and V

X. Li and V. Voroninski. Sparse signal recovery from qua dratic measurements via convex programming. SIAM Journal on Mathematical Analysis , 45(5):3019–3033, 2013

2013
[75]

Y. M. Lu and G. Li. Spectral initialization for nonconve x estimation: High-dimensional limit and phase transitions. In 2017 IEEE International Symposium on Information Theory, ISIT 2017, Aachen, Germany, June 25-30, 2017 , pages 3015–3019. IEEE, 2017

2017
[76]

W. Luo, W. Alghamdi, and Y. M. Lu. Optimal spectral initi alization for signal recovery with applica- tions to phase retrieval. IEEE Trans. Signal Process. , 67(9):2347–2356, 2019

2019
[77]

W. Luo, W. Alghamdi, Y. M. Lu, and G. Li. Phase transition s of spectral initialization for high- dimensional non-convex estimation. Information and Inference: A Journal of the IMA , 9(3):5077–541, 2020

2020
[78]

J. Ma, R. Dudeja, J. Xu, A. Maleki, and X. Wang. Spectral m ethod for phase retrieval: An expectation propagation perspective. IEEE Trans. Inf. Theory , 67(2):1332–1355, 2021

2021
[79]

Maillard, A

A. Maillard, A. S. Bandeira, D. Belius, I. Dokmanic, and S. Nakajima. Injectivity of relu networks: perspectives from statistical physics. 2023. available on line at http://arxiv.org/abs/2302.14112. 22

2023 arXiv
[80]

Maillard, F

A. Maillard, F. Krzakala, Y. M. Lu, and L. Zdeborová. Con struction of optimal spectral methods in phase retrieval. In Mathematical and Scientiﬁc Machine Learning, 16-19 August 2 021, Virtual Conference / Lausanne, Switzerland , volume 145 of Proceedings of Machine Learning Re...

2021
[81]

Maillard, B

A. Maillard, B. Loureiro, F. Krzakala, and L. Zdeborová . Phase retrieval in high dimensions: Statistical and computational phase transitions. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2 020, NeurIPS 202...

2020
[82]

Mezard, T

M. Mezard, T. Mora, and R. Zecchina. Clustering of solut ions in the random satisﬁability problem. Physical Review Letters , 94:197204, 2005

2005
[83]

J. Miao, P. S. Charalambous, J. Kirz, and D. Sayre. Exten ding the methodology of x-ray crystallog- raphy to allow imaging of micrometre-sized non-crystallin e specimens. Nature, 400:342–344, 1999

1999
[84]

J. Miao, T. Ishikawa, Q. Shen, and T. Earnest. Extending x-ray crystallography to allow the imaging of noncrystalline materials, cells and single protein comp lexes. Annu. Rev. Phys. Chem. , 59:387–410, 2008

2008
[85]

Mignacco, P

F. Mignacco, P. Urbani, and L. Zdeborova. Stochasticit y helps to navigate rough landscapes: comparing gradient-descent-based algorithms in the phase retrieval problem. Machine Learning: Science and Technology, 2:035029, 2021

2021
[86]

R. P. Millane. Phase retrieval in crystallography and o ptics. J. Opt. Soc. Am. A , 7(3):394–411, Mar 1990

1990
[87]

R. P. Millane. Recent advances in phase retrieval. In Image Reconstruction from Incomplete Data IV , volume 6316, page 63160E. International Society for Optics and Photonics, SPIE, 2006

2006
[88]

D. L. Misell. A method for the solution of the phase probl em in electron microscopy. J. Phys. D: App. Phy., 6(1):L6–L9, 1973

1973
[89]

Mondelli and A

M. Mondelli and A. Montanari. Fundamental limits of wea k recovery with applications to phase retrieval. Found. Comput. Math. , 19(3):703–773, 2019

2019
[90]

Montanari

A. Montanari. Optimization of the Sherrington-Kirkpa trick hamiltonian. In 60th IEEE Annual Sympo- sium on Foundations of Computer Science, FOCS 2019, Baltimo re, Maryland, USA, November 9-12, 2019, pages 1417–1433. IEEE Computer Society, 2019

2019
[91]

Netrapalli, P

P. Netrapalli, P. Jain, and S. Sanghavi. Phase retrieva l using alternating minimization. In Advances in Neural Information Processing Systems , pages 2796–2804, 2013

2013
[92]

Netrapalli, P

P. Netrapalli, P. Jain, and S. Sanghavi. Phase retrieva l using alternating minimization. IEEE Trans. Signal Process., 63(18):4814–4826, 2015

2015
[93]

Ohlsson, A

H. Ohlsson, A. Y. Yang, R. Dong, and S. S. Sastry. Compres sive phase retrieval from squared output measurements via semi-deﬁnite programming. In IF AC Proceedings, volume 45, pages 89–94, 2012

2012
[94]

D. Park, A. Kyrillidis, C. Carmanis, and S. Sanghavi. No n-square matrix sensing without spurious local minima via the Burer-Monteiro approach. In Proceedings of the 20th International Conference on Artiﬁcial Intelligence and Statistics , volume 54 of Proceedings of Machine Le...

2017
[95]

Rangan, P

S. Rangan, P. Schniter, and A. K. Fletcher. Vector appro ximate message passing. In 2017 IEEE International Symposium on Information Theory, ISIT 2017, Aachen, Germany, June 25-30, 2017 , pages 1588–1592. IEEE, 2017

2017
[96]

Recht, M

B. Recht, M. Fazel, and P. A. Parrilo. Guaranteed minimu m-rank solutions of linear matrix equations via nuclear norm minimization. SIAM Review , 52(3):471–501, 2010. 23

2010
[97]

Rodenburg

J.M. Rodenburg. Ptychography and related diﬀractive i maging methods. Advances in Imaging and Electron Physics, 150:87–184, 2008

2008
[98]

Salehi, E

F. Salehi, E. Abbasi, and B. Hassibi. A precise analysis of phasemax in phase retrieval. In 2018 IEEE International Symposium on Information Theory, ISIT 2018, Vail, CO , USA, June 17-22, 2018 , pages 976–980. IEEE, 2018

2018
[99]

Schniter and S

P. Schniter and S. Rangan. Compressive phase retrieval via generalized approximate message passing. IEEE Trans. Signal Process. , 63(4):1043–1055, 2015

2015
[100]

Schniter, S

P. Schniter, S. Rangan, and A. K. Fletcher. Vector appr oximate message passing for the generalized linear model. In 50th Asilomar Conference on Signals, Systems and Computers, ACSSC 2016, Paciﬁc Grove, CA, USA, November 6-9, 2016 , pages 1525–1529. IEEE, 2016

2016
[101]

Shechtman, Y

Y. Shechtman, Y. C. Eldar, O. Cohen, H. N. Chapman, J. Mi ao, and M. Segev. Phase retrieval with application to optical imaging: A contemporary overview. IEEE Signal Process. Mag. , 32(3):87–109, 2015

2015
[102]

Soltanolkotabi

M. Soltanolkotabi. Structured signal recovery from q uadratic measurements: Breaking sample com- plexity barriers via nonconvex optimization. IEEE Trans. Inf. Theory , 65(4):2374–2400, 2019

2019
[103]

M. Stojnic. A framework for perfromance characteriza tion of LASSO algortihms. available online at http://arxiv.org/abs/1303.7291

arXiv
[104]

M. Stojnic. Various thresholds for ℓ1-optimization in compressed sensing. available online at http:// arxiv.org/abs/0907.3666

arXiv
[105]

M. Stojnic. Block-length dependent thresholds for ℓ2/ℓ1-optimization in block-sparse compressed sens- ing. ICASSP, IEEE International Conference on Acoustics, Signal and Speech Processing, pages 3918– 3921, 14-19 March 2010. Dallas, TX

2010
[106]

M. Stojnic. ℓ1 optimization and its various thresholds in compressed sens ing. ICASSP, IEEE Inter- national Conference on Acoustics, Signal and Speech Proces sing, pages 3910–3913, 14-19 March 2010. Dallas, TX

2010
[107]

M. Stojnic. Recovery thresholds for ℓ1 optimization in binary compressed sensing. ISIT, IEEE Inter- national Symposium on Information Theory , pages 1593 – 1597, 13-18 June 2010. Austin, TX

2010
[108]

M. Stojnic. Another look at the Gardner problem. 2013. available online at http://arxiv.org/abs/ 1306.3979

2013 arXiv
[109]

M. Stojnic. Lifting ℓ1-optimization strong and sectional thresholds. 2013. avai lable online at http:// arxiv.org/abs/1306.3770

2013 arXiv
[110]

M. Stojnic. Lifting/lowering Hopﬁeld models ground s tate energies. 2013. available online at http:// arxiv.org/abs/1306.3975

2013 arXiv
[111]

M. Stojnic. Regularly random duality. 2013. availabl e online at http://arxiv.org/abs/1303.7295

2013 arXiv
[112]

M. Stojnic. Fully bilinear generic and lifted random p rocesses comparisons. 2016. available online at http://arxiv.org/abs/1612.08516

2016 arXiv
[113]

M. Stojnic. Generic and lifted probabilistic compari sons – max replaces minmax. 2016. available online at http://arxiv.org/abs/1612.08506

2016 arXiv
[114]

M. Stojnic. Fully lifted random duality theory. 2023. available online at http://arxiv.org/abs/ 2312.00070

2023 arXiv
[115]

M. Stojnic. Deep relu networks – injectivity capacity upper bounds. 2024. available online at http:// arxiv.org/abs/2412.19677. 24

2024 arXiv
[116]

M. Stojnic. Injectivity capacity of relu gates. 2024. available online at http://arxiv.org/abs/2410. 20646

2024
[117]

M. Stojnic. Optimal spectral initializers impact on p hase retrieval phase transitions – an RDT view
[119]

Straziota and L

D. Straziota and L. Saglietti. Isolating the hard core of phaseless inference: the phase selection formulation. 2025. available online at http://arxiv.org/abs/2502.04282

2025 arXiv
[120]

J. Sun, Q. Qu, and J. Wright. A geometric analysis of pha se retrieval. Found. Comput. Math. , 18(5):1131–1198, 2018

2018
[121]

Takahashi and Y

T. Takahashi and Y. Kabashima. Macroscopic analysis o f vector approximate message passing in a model-mismatched setting. IEEE Trans. Inf. Theory , 68(8):5579–5600, 2022

2022
[122]

Y. S. Tan and R. Vershynin. Phase retrieval via randomi zed kaczmarz: Theoretical guarantees. Infor- mation and Inference: A Journal of the IMA , 8(1):97–123, 2019

2019
[123]

Thibault, M

P. Thibault, M. Dierolf, A. Menzel, O. Bunk, C. David, a nd F. Pfeﬀer. High-resolution scanning x-ray diﬀraction microscopy. Science, 322(5887):379–382, 2008

2008
[124]

S. Tu, R. Boczar, M. Simchowitz, M. Soltanolkotabi, an d B. Recht. Low-rank solutions of linear matrix equations via procrustes ﬂow. In Proceedings of the 33rd International Conference on Internatio nal Conference on Machine Learning - Volume 48 , pages 964–973. JMLR.org, 2016

2016
[125]

C. Vinzant. A small frame and a certiﬁcate of its inject ivity. In IEEE International Conference on Sampling Theory and Applications (SampTA) , pages 197–200, 2015

2015
[126]

Waldspurger

I. Waldspurger. Phase retrieval with random Gaussian sensing vectors by alternating projections. IEEE Trans. Inf. Theory , 64(5):3301–3312, 2018

2018
[127]

Waldspurger, A

I. Waldspurger, A. d’Aspremont, and S. Mallat. Phase r ecovery, maxcut and complex semideﬁnite programming. Math. Program., 149(1-2):47–81, 2015

2015
[128]

A. Walther. The question of phase retrieval in optics. Optica Acta: International Journal of Optics , 10(1):41–49, 1963

1963
[129]

G. Wang, G. B. Giannakis, and Y. C. Eldar. Solving syste ms of random quadratic equations via truncated amplitude ﬂow. IEEE Trans. Inf. Theory , 64(2):773–794, 2018

2018
[130]

K. Wei. Solving systems of phaseless equations via Kac zmarz methods: A proof of concept study. Inverse Problems, 31(12):125008, 2015

2015
[131]

Z. Yuan, H. Wang, and Q. Wang. Phase retrieval via spars e Wirtinger ﬂow. Journal of Computational and Applied Mathematics , 355:162–173, 2019

2019
[132]

Zehni, S

M. Zehni, S. Huang, I. Dokmanic, and Z. Zhao. Geometric invariants for sparse unknown view to- mography. In ICASSP 2019 - 2019 IEEE International Conference on Acoustics, S peech and Signal Processing (ICASSP), pages 5027–5031, 2019

2019
[133]

Zehni, S

M. Zehni, S. Huang, I. Dokmanic, and Z. Zhao. 3d unknown view tomography via rotation invariants. In ICASSP 2020 - 2020 IEEE International Conference on Acoustics, S peech and Signal Processing (ICASSP), pages 1449–1453, 2020

2020
[134]

Zheng and J

Q. Zheng and J. Laﬀerty. A convergent gradient descent algorithm for rank minimization and semidef- inite programming from random linear measurements. In Advances in Neural Information Processing Systems, volume 28. Curran Associates, Inc., 2015. 25

2015
[2025]

available online at arxiv

Pith tools

Reviewed August 15, 2026 · model on record in the stance chip above.

[1] [118]

M. Stojnic. Phase transition of descending phase retrieval algorithms. 2025. available online at arxi v

2025

[2] [1]

Achlioptas, A

D. Achlioptas, A. Coja-Oghlan, and F. Ricci-Tersenghi. On the solution-space geometry of random constraint satisfaction problems. Random Struct. Algorithms , 38(3):251–268, 2011

2011

[3] [2]

Ahmed, B

A. Ahmed, B. Recht, and J. Romberg. Blind deconvolution u sing convex programming. IEEE Trans- actions on Information Theory , 60(3):1711–1732, 2013

2013

[4] [3]

Aubin, B

B. Aubin, B. Loureiro, A. Baker, F. Krzakala, and L. Zdebo rová. Exact asymptotics for phase retrieval and compressed sensing with random generative priors. In Proceedings of Mathematical and Scientiﬁc Machine Learning, MSML 2020, 20-24 July 2020, Virtual Confere nce / Princeton, NJ, USA , volume 107 of Proceedings of Machine Learning Research , pages 55–...

arXiv 2020

[5] [4]

Bahmani and J

S. Bahmani and J. Romberg. Phase retrieval meets statist ical learning theory: A ﬂexible convex relaxation. Electronic Journal of Statistics , 11:5254–5281, 2016. 18

2016

[6] [5]

Balan, B

R. Balan, B. Bodmann, P. Casazza, and D. Edidin. Painless reconstruction from magnitudes of frame coeﬃcients. J. Four. Anal. Appl. , 15:488–501, 2009

2009

[7] [6]

Balan, P

R. Balan, P. Casazza, and D. Edidin. On signal reconstruc tion without phase. Applied and Computa- tional Harmonic Analysis , 20(3):343–356, 2006

2006

[8] [7]

Baldassi, A

C. Baldassi, A. Ingrosso, C. Lucibello, L. Saglietti, an d R. Zecchina. Subdominant dense clusters allow for simple learning and high computational performance in n eural networks with discrete synapses. Physical Review letters , 115(12):128101, 2015

2015