Phase transition of \emph{descending} phase retrieval algorithms

Mihailo Stojnic

REVIEW 4 major objections 5 minor 137 references

Phase transition of \emph{descending} phase retrieval algorithms

T0 review · 4 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 Gaussian phase retrieval, the paper claims that a single funneling point on a random-duality manifold is equivalent to global convergence of every descending algorithm, placing the transition near an oversampling ratio of 1.79, or…

desk verdict Novel manifold/funneling-point picture and sharp numerical thresholds for descending phase retrieval, but the load-bearing 'isomorphism' is asserted without proof, so the thresholds remain predictions. read the letter →

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

Mihailo Stojnic This is my paper · ORCID

classification stat.MLcs.ITcs.LGmath.IT MSC 90C2665K1094A12

keywords phaseretrievaldescendingalgorithmsrandomdualitytheoryparametricmanifoldfunnelingpointstransitiongradientdescentoversamplingratio

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

Phase retrieval asks for a signal from only the squared magnitudes of linear measurements. This paper tries to establish exactly when the most natural class of solvers—descending algorithms such as gradient descent and Wirtinger flow—are guaranteed to find the true signal, up to global phase, regardless of initialization. The answer it proposes is geometric: performance is controlled by a two-parameter parametric manifold of lower bounds, and success coincides with the manifold having a single funneling point at the true solution. Using Random duality theory, the paper locates the transition at about 1.79 measurements per unknown, and at about 1.4 after a lifted bound. If correct, this gives a quantitative phase-transition limit for nonconvex phase retrieval and explains why a simple hybrid gradient method succeeds in simulations near those values.

What carries the argument

The central objects are the parametric manifold PM(α) and its funneling points. PM(α) plots the random-duality lower bound φ0(c, x) on the scaled objective ξ(c, x)/n against two parameters: c = ‖x‖², the squared norm of the algorithmic iterate, and x = xᵀx̄, its overlap with the true signal. A funneling point is a collector of all descending paths on the manifold, and the paper's claimed isomorphism is that a single funneling point at (1, 1) guarantees global convergence of every descending algorithm. The machinery that produces the manifold is the Random duality theory recipe: rewrite phase retrieval as a random optimization problem, form a random dual through a Gaussian comparison inequality, solve the scalarized dual in closed form for amplitude objectives, and lift the resulting lower bound using a partially lifted RDT variant.

What would settle it

Run a norm-constrained descending algorithm at α = 1.4 with n = 10,000 Gaussian measurements and many random starts, including starts with overlap near 0; if a positive fraction converge to a point with overlap far below 1, the single-funneling-point claim is false. A second check: numerically trace the true objective's stationary points over (c, x) at α = 1.5 and look for any local minimum besides ±x̄.

Watch

Extended reading notes

Core claim

The paper's central claim is that the success of descending phase retrieval algorithms is governed by the shape of a two-parameter random-duality manifold: for each allowed pair (c, x), representing the squared norm of the iterate and its overlap with the true signal, a lower bound φ0(c, x) defines a surface over which descent flows. If that manifold has exactly one funneling point, located at the true solution (c, x) = (1, 1), then any norm-constrained descending algorithm converges to the global optimum from any initialization. If it has more than one funneling point, descent generically fails by being captured at an undesired collector such as (c, x) = (1, 0). The paper derives this manifold from a fundamental phase-retrieval optimization via Random duality theory, observes that increasing the oversampling ratio α = lim_{n→∞} m/n changes the manifold from multi-funnel to single-funnel, and locates the transition at α ≈ 1.7932 for plain RDT and α ≈ 1.4 for partially lifted RDT.

Load-bearing premise

The load-bearing premise is that when the random-duality lower-bound surface has exactly one collecting point, every descending algorithm converges globally; this transfer from a lower bound to the real optimization landscape is asserted rather than proved.

Editorial extensions

If this is right

Above α ≈ 1.7932, plain RDT predicts that any norm-constrained descending algorithm reaches the global optimum from any initialization, and below that ratio descending algorithms generically fail.
Partially lifted RDT lowers the guaranteed-success oversampling to α ≈ 1.4, so the true algorithmic phase transition should lie between 1.4 and 1.7932 rather than at the plain-RDT value.
The manifold parameter c, the squared norm of the iterate, is load-bearing: unconstrained plain gradient can fail even for larger α because it enters the c > 1 region where undesired funneling points reappear.
The same single-funneling-point conclusion holds for squared-magnitude objectives, the form used in practical implementations, with the lifted bound flattening the curve at α = 1.4.
A hybrid alternating barrier-gradient and plain-gradient method run at n = 300 shows a simulated transition fairly close to both theoretical predictions, indicating that finite-dimension jitteriness does not wash out the effect.

Reading between the lines

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

If the funneling-point criterion transfers to the true optimization landscape, the finite-n success probability should sharpen toward a step function at the threshold as n grows; this is a testable prediction the paper does not run at large n.
The same two-parameter manifold analysis could be applied to other nonconvex recovery problems whose objectives admit random-duality lower bounds, such as matrix completion, blind deconvolution, or phase retrieval with generative priors.
Because plain RDT gives strict lower bounds and the lifted threshold still sits above the information limit α = 1, a fully lifted treatment may push the guaranteed-success threshold lower; the paper identifies this as a next step but does not claim the lower value.
Spectral initialization probably makes the practical transition appear at slightly lower α than the worst-case guarantee, because it places the start inside the good basin; the paper observes the favorable overlap but does not quantify this gain.

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

Colleague,

Read the Stojnic paper. The novel piece is real: the parametric manifold PM(α) with (c,x) coordinates and the notion of funneling points give a clean way to visualize why descending phase-retrieval might fail, and the paper produces concrete numbers—α≈1.7932 from plain RDT, ≈1.4 after partial lifting—that are not in the earlier RDT literature. The closed-form evaluation of the random dual for the amplitude objective is competently done, and the numerical experiments at n=300 land surprisingly close to the advertised transitions. Credit where due: the paper also flags its own weak spots, noting no strong random duality, and Section 4.3 admits the squared-magnitude lifted curve is flat enough that α=1.4 is hard to pin down.

The soft spot is exactly where the reader puts it. The claim that a single funneling point in the parametric manifold is isomorphic to global convergence of descending algorithms appears in the abstract, Section 1.2, and Section 2.2, but no formal definition of funneling point and no proof of the implication are given. The water-pouring analogy is an intuition, not an argument. Worse, the manifold is computed from φ0, which the paper itself states is a strict lower bound on the true objective. A lower-bound landscape with one funnel says essentially nothing about the actual objective, which can have extra local minima under a positive perturbation. So the thresholds are best read as predictions from a heuristic, not as theorems about descending algorithms. The simulated agreement is encouraging but cannot certify the missing proof, especially since the simulation uses squared magnitudes with a log-barrier while the derivation uses amplitudes.

The citation pattern is heavy on the author's own RDT work, but in context that is the natural toolkit; the thresholds are evaluated from integrals, not fit to data, so I don't see a circularity problem of that kind.

Bottom line: this is a substantial, thought-provoking paper with real numerical suggestions, but the central claim is not established. It deserves a serious referee—the machinery is nontrivial and the predictions are falsifiable—so send it out, but expect the main contribution to be reframed as conjecture plus strong evidence, or to require a genuinely new proof. I would not cite it as a proved phase transition, but I'd read follow-ups.

Referee Report

4 major / 5 minor

Summary. The paper studies the performance of descending (gradient-type) algorithms for real phase retrieval in the proportional high-dimensional regime. It introduces a constrained optimization formulation called f-pro, whose optimal value ξ(c,x) depends on the squared norm c and the overlap x with the true signal. Using Random Duality Theory (RDT) and a lifted variant, the paper derives lower bounds φ0 on the scaled objective and defines a 'parametric manifold' PM(α) in the (c,x) plane. It then claims an isomorphism between a single 'funneling point' of this manifold and global convergence of descending algorithms, and reports thresholds α≈1.7932 for plain RDT and α≈1.4 for lifted RDT. A hybrid barrier/plain gradient algorithm is implemented for n=300 squared-magnitude measurements, and its simulated success probability is compared with the theoretical thresholds.

Significance. If the central claim were established, the paper would provide a quantitative, parameter-free prediction of the oversampling ratio at which descending phase retrieval algorithms stop being trapped in spurious local minima. The RDT lower-bound derivations follow a known template and are explicit; the thresholds are evaluated from the derived integrals rather than fitted to simulations, and the numerical experiments in Figure 7 are suggestive. However, the paper's headline contribution, the funneling-point isomorphism, is only asserted through an informal water-pouring analogy in Section 2.2 and is never formalized or proved. Since the derived φ0 is explicitly a lower bound and strong random duality is absent, the manifold-shape analysis cannot by itself establish algorithmic convergence on the true objective. The gap between the non-squared constrained theory and the squared unconstrained/log-barrier simulated objective is also not rigorously closed, and Section 4.3 concedes that the α≈1.4 threshold is difficult to confirm numerically.

major comments (4)

[Section 2.2] The claimed 'isomorphism' between a single funneling point of the parametric manifold and global convergence of descending algorithms is asserted, not proved. The formal statements in Theorems 1 and 2 (and their lifted analogues) only show that φ0 > 0 implies that the random primal value is positive with probability tending to one, i.e., uniqueness/solvability of the feasibility problem. Because Section 2.1 states that strong random duality is not in place, φ0 is a strict lower bound on the true objective; a single-funnel structure of a lower-bounding manifold does not transfer to the true objective, since a positive perturbation of a monotone funnel can create additional local minima. No formal definition of 'funneling point' or statement of the isomorphism is supplied. This missing step is load-bearing for the central thresholds α≈1.7932 and α≈1.4.
[Sections 4.2 and 4.3] The simulations minimize fbar(t0;x) with squared magnitudes and a log barrier, whereas the theoretical analysis in Sections 2–3 treats a constrained non-squared objective. Theorems 3 and 4 provide lower-bound analogues for squared magnitudes, but they do not establish that the phase-transition threshold of the constrained non-squared problem governs the unconstrained/log-barrier squared objective actually run in the experiments. Moreover, Section 4.3 explicitly concedes that the lifted squared-magnitude curve is flat and that 'it is a bit difficult to make a definite conclusion' about α≈1.4, which directly weakens the use of this value as the simulated transition point. The numerical agreement in Figure 7 is suggestive but does not replace the missing mathematical bridge.
[Section 4, Eq. (54)] The hybrid algorithm whose success probabilities are reported in Figure 7 includes sign-reshuffling steps and an increasing barrier schedule; it is not an instance of a pure descending algorithm on the manifold analyzed in Sections 2 and 3. The theoretical claims concern 'any descending algorithm,' but the simulated procedure can leave the descent path through the reshuﬄe operation. Thus the comparison in Figure 7 is not a direct test of the funneling-point isomorphism, and the numerical agreement cannot validate an unproved universal algorithmic statement.
[Section 4.1] The paper concedes that the plain gradient has no generic phase transition because for any α one can find c>1 with multiple funneling points, and it explains the observed transition by the empirical fact that trajectories stay below c≈1.4 in practice. This explanation is trajectory-dependent and algorithm-dependent; it does not support the universal claim that above the threshold any norm-constrained descending algorithm reaches the global optimum. A trajectory-dependent empirical observation cannot substitute for a manifold-level convergence theorem.

minor comments (5)

[Throughout] The manuscript contains many typos and grammatical errors, including 'Paramatric manifold', 'agrement', 'matheamtical', 'go9ng', 'proeprties', and 'Figure 8 and 9'; these should be corrected.
[References] Several references have incomplete bibliographic data, e.g., [117]–[119] are listed as 'available online at arxiv' without identifiers; full citations should be provided.
[Section 2.1, Eqs. (28)–(29)] The derivation from the integral definitions in (28) to the closed form for f_q in (29) is difficult to verify; a step-by-step derivation or an appendix would improve reproducibility.
[Section 2, notation] The symbol x is used both for the overlap variable and for the optimization variable; although the paper notes this convention, the double use makes equations such as (7) and (11) unnecessarily confusing.
[Figure 7] The vertical lines for 'Theoretical phase transition – RDT' and 'Lifted RDT' are not defined precisely; the caption should state whether they mark the threshold values themselves or a transition band.

Circularity Check

1 steps flagged · score 6.0 of 10

Central 'isomorphism' between single funneling points and global convergence is definitional; algorithmic phase-transition thresholds inherit the assumption.

self definitional [Section 2.2 (Algorithmic implications), pages 9–10; echoed in the abstract and contribution bullets]
"The shape of the manifold directly correlates to the ability of the descending algorithms to reach the global optimum in the following way: If the manifold has single “funneling point” (collector of all descending paths) then any descending algorithm will converge to the global optimum."

The key term 'funneling point' is defined in this very sentence as 'collector of all descending paths,' so the claimed implication 'single funneling point ⇒ any descending algorithm converges' is true by definition, not by proof. Theorems 1 and 2 only establish lower bounds on the scaled objective and uniqueness/solvability via φ0>0; they say nothing about gradient trajectories or the actual optimization landscape. The abstract and contribution list nonetheless promote this to an 'isomorphism ... established,' and the phase-transition values α≈1.7932 and α≈1.4 are read off from the shape of the RDT lower-bound manifold.

full rationale

The RDT and lifted-RDT computations themselves are not circular: φ0 and the lifted bounds are evaluated from Gaussian integrals via Gordon-type comparison arguments, and the thresholds α≈1.7932 and α≈1.4 are not fitted to the simulations; the n=300 hybrid-gradient experiment is independent external evidence. However, the paper's central algorithmic claim is carried by the informal notion of a 'funneling point,' which is defined in Section 2.2 as a 'collector of all descending paths.' Under that definition, the sentence 'if the manifold has single funneling point then any descending algorithm will converge' is a tautology rather than a derived theorem. The contribution bullet and abstract escalate this to 'an isomorphism ... established,' but no proof connects the RDT lower-bound manifold to the true objective landscape; indeed the paper explicitly notes the absence of strong random duality, so φ0 is a strict lower bound. Consequently the phase-transition values are predictions only under the definitional identification of lower-bound manifold shape with algorithmic success. Section 4.3 further concedes that the lifted squared-magnitude curve is too flat for a definite conclusion at α≈1.4. This is a partial, definition-level circularity, not a fitted-parameter circularity, and because the RDT integral evaluations and the numerical simulation are independent, it does not warrant the highest score.

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

The central claim rests on the RDT lower-bound computation (supported by Gordon's comparison theorem) plus the unproved funneling-point isomorphism. No constants are fitted to data, but several domain assumptions (Gaussian measurements, proportional asymptotics, generic solvability) and the squared/non-squared equivalence enter without rigorous control. The paper explicitly acknowledges the lack of strong random duality, so the thresholds are lower-bound predictions.

assumptions (6)

domain assumption Measurement matrix A has iid standard normal entries.
Used throughout Section 2 as the standard Gaussian sensing model; the rotational invariance argument and all Gaussian integral evaluations depend on it.
domain assumption Proportional high-dimensional regime with α = lim m/n constant as n grows.
Defines the asymptotic setting in Section 1, equation (3). All phase transition statements are in this regime.
domain assumption The PR instance is generically solvable: besides ±x̄ there are no other solutions of (2).
Stated in Section 1 to ensure that success of an algorithm coincides with reaching the true signal up to global phase.
standard math Gordon's comparison theorem for Gaussian processes is applicable.
Used in the proof of Theorem 1 to pass from the random primal to the random dual; cited to [54] and to Stojnic's generalizations [112,113].
ad hoc to paper Single funneling point in the lower-bound manifold implies global convergence of descending algorithms.
Central heuristic in Section 2.2. No formal definition or proof is given; the water-pouring analogy substitutes for a theorem.
ad hoc to paper Non-squared and squared magnitude objectives have equivalent phase transition behavior.
Claimed in Sections 4.2 and 4.3. Closed-form analysis is only possible for non-squared magnitudes, while simulations use squared magnitudes, and the bridge between them is not rigorously established.

invented entities (2)

Parametric manifold PM(α)
purpose: Represents the RDT lower-bound objective φ0 as a function of (c,x); its shape is claimed to govern algorithm success.
Introduced in Section 2.2; no independent empirical or formal verification beyond the paper's own simulations.
Funneling point
purpose: A point on the manifold that collects descending paths; single vs multi funneling is claimed to determine success vs failure.
Defined informally via the water-pouring analogy; no rigorous definition or proof of the claimed isomorphism.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Phase transition of \emph{descending} phase retrieval algorithms." pith.science (2026). https://pith.science/paper/EHCFUZE6

@misc{pith2026250618275,
  author       = {Pith},
  title        = {Pith review of: Phase transition of \emphdescending phase retrieval algorithms},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/EHCFUZE6}},
  note         = {Machine review of arXiv:2506.18275}
}

read the original abstract

We study theoretical limits of \emph{descending} phase retrieval algorithms. Utilizing \emph{Random duality theory} (RDT) we develop a generic program that allows statistical characterization of various algorithmic performance metrics. Through these we identify the concepts of \emph{parametric manifold} and its \emph{funneling points} as key mathematical objects that govern the underlying algorithms' behavior. An isomorphism between single funneling point manifolds and global convergence of descending algorithms is established. The structure and shape of the parametric manifold as well as its dependence on the sample complexity are studied through both plain and lifted RDT. Emergence of a phase transition is observed. Namely, as sample complexity increases, parametric manifold transitions from a multi to a single funneling point structure. This in return corresponds to a transition from the scenarios where descending algorithms generically fail to the scenarios where they succeed in solving phase retrieval. We also develop and implement a practical algorithmic variant that in a hybrid alternating fashion combines a barrier and a plain gradient descent. Even though the theoretical results are obtained for infinite dimensional scenarios (and consequently non-jittery parametric manifolds), we observe a strong agrement between theoretical and simulated phase transitions predictions for fairly small dimensions on the order of a few hundreds.

Figures

Figures reproduced from arXiv: 2506.18275 by the authors.

**Figure 1.** φ0 as a function of x for different values of c; α = 1.7932 The importance of parametric structure for both theoretical analysis and algorithmic designs was brought to prominence with the appearance of the RDT in [104–107, 111]. To get a bit clearer picture as to how it relates to what is actually happening here and why the above indication is indeed correct, we in Figures 2, 3, and 4 plot the entire so-called param… view at source ↗

**Figure 2.** Parametric manifold for α = 1.5, PM(1.5); Red/purple curves – undesired/desired funneling flows be lowered. 0 0.2 0.4 0.6 c 0.8 Parametric manifold α = 1.7932 1 1 0.8 x 0.6 0.4 0.2 0 0.4 0.8 0.2 0 1 0.6 √ φ0 [PITH_FULL_IMAGE:figures/full_fig_p011_2.png] view at source ↗

**Figure 3.** Parametric manifold for α = 1.7932; Red/purple curves – undesired/desired funneling flows 2.3 Beyond optimal objective landscape The above discussed algorithmic implications are driven by the structure of the optimal objective related parametric manifold. The intuition suggests that given that fl RDT is likely needed to exactly determine all associated quantities, the above manifold study can indeed be among the key… view at source ↗

Figures from the paper (12 more)

**Figure 4.** Figure 4: Parametric manifold for α = 2.3; Red/purple curves – undesired/desired funneling flows observed in many well known random optimization problems [3, 4, 48–51, 84]. While the algorithms that we consider here are in no way generic representatives of the best practically f…

**Figure 5.** Figure 5: Effect of lifted RDT – φ0 as a function of x for different values of c; α = 1.4 (c, x) = (1, 0) and (c, x) = (1, 1), manifold after lifting has only one funneling point (c, x) = (1, 1). As discussed earlier, if the manifold has single (desired) “funneling point” (colle…

**Figure 6.** Figure 6: Lifted parametric manifold for α = 1.4 where fplain(x) , k|Ax¯| 2 − |Ax| 2 k 2 2 (49) One should note that fplain(x) is slightly different from the version analyzed earlier as we here utilize (derivative) smoother squared magnitudes rather than just magnitudes (the ana…

**Figure 7.** Figure 7: Simulated and theoretical RDT and lifted RDT phase [PITH_FULL_IMAGE:figures/full_fig_p018_7.png]

**Figure 8.** Figure 8: Barrier objective – parametric manifold; [PITH_FULL_IMAGE:figures/full_fig_p019_8.png]

**Figure 9.** Figure 9: Barrier objective – parametric manifold; [PITH_FULL_IMAGE:figures/full_fig_p020_9.png]

**Figure 10.** Figure 10: φ0 as a function of x; c is allowed to go above 1; α = 1.7932 the principle of trying to recreate quantities analogous to those discussed in the non-squared magnitudes scenarios. Theorem 3. Assume the setup of Lemma 1. Let the elements of A ∈ R m×n (g (0) ∈ R m×1 and …

**Figure 11.** Figure 11: φ0 as a function of x; c is allowed to go above 1; α = 2.3 We can then proceed to handle the random dual as in the third part of Section 2.1. Analogously to (17 and (18, we first write φ (sq) 0 , limn→∞ EGf (sq) rd (G) ≥ max ry>0 EG min zi L (sq) 1 (ry), (62) where L …

**Figure 12.** Figure 12: Parametric manifold for α = 1.7932; Purple curve – path of local (or boundary) optima ac,3 = ac,1 −1 + √ −3 2 , (67) one obtains through the Cardano’s formula sets of possible candidates for optimal |zi | Z (sq) = ( {ac,1, 0}, if q 2 c 4 + p 3 c 27 ≥ 0 {ac,1, ac,2, ac…

**Figure 13.** Figure 13: Parametric manifold for α = 2.3; Purple curve – path of local (or boundary) optima 4.3 Squared magnitudes – Lifted RDT The above RDT analysis can be lifted relying on the concepts from Section 3. One starts by establishing the following squared magnitudes analogue to …

**Figure 14.** Figure 14: We conducted numerical eval [PITH_FULL_IMAGE:figures/full_fig_p026_14.png]

**Figure 14.** Figure 14: Squared magnitudes – effect of lifted RDT ; c = 1 and α = 1.4 5 Conclusion We considered the descending phase retrieval algorithms and theoretically studied their performance. Relying on Random duality theory (RDT) we established a generic analytical program that allo…

Review history (2 revisions) →

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

137 extracted references · 49 canonical work pages

[1]

E. Abbe, S. Li, and A. Sly. Proof of the contiguity conject ure and lognormal limit for the symmetric perceptron. In 62nd IEEE Annual Symposium on Foundations of Computer Scienc e, FOCS 2021, Denver, CO, USA, February 7-10, 2022 , pages 327–338. IEEE, 2021

2021
[2]

E. Abbe, S. Li, and A. Sly. Binary perceptron: eﬃcient alg orithms can ﬁnd solutions in a rare well- connected cluster. In STOC ’22: 54th Annual ACM SIGACT Symposium on Theory of Computi ng, Rome, Italy, June 20 - 24, 2022 , pages 860–873. ACM, 2022

2022
[3]

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
[4]

Achlioptas and F

D. Achlioptas and F. Ricci-Tersenghi. On the solution-s pace geometry of random constraint satisfaction problems. In Proceedings of the 38th Annual ACM Symposium on Theory of Comp uting, Seattle, W A, USA, May 21-23, 2006 , pages 130–139. ACM, 2006

2006
[5]

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
[6]

A. E. Alaoui, A. Montanari, and M. Sellke. Optimization o f mean-ﬁeld spin glasses. The Annals of Probability, 49(6), 2021

2021
[7]

A. E. Alaoui, A. Montanari, and M. Sellke. Sampling from t he Sherrington-Kirkpatrick gibbs measure via algorithmic stochastic localization. In 63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022, Denver, CO, USA, October 31 - November 3, 2 022, pages 323–334. IEEE, 2022

2022
[8]

A. E. Alaoui amd D. Gamarnik. Hardness of sampling soluti ons from the symmetric binary perceptron

Show all 137 references

[9]

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 / Princet...

2020 arXiv
[10]

Bahmani and J

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

2016
[11]

Balan, B

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

2009
[12]

Balan, P

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

2006
[13]

Baldassi, A

C. Baldassi, A. Ingrosso, C. Lucibello, L. Saglietti, a nd 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
[14]

Baldassi, A

C. Baldassi, A. Ingrosso, C. Lucibello, L. Saglietti, a nd 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
[15]

Baldassi, R

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

2020
[16]

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. 28

2014
[17]

Bansal and J

N. Bansal and J. H Spencer. On-line balancing of random i nputs. Random Structures & Algorithms , 57(4):879–891, 2020

2020
[18]

Barbier, A

D. Barbier, A. E. Alaoui, F. Krzakala, and L. Zdeborova. On the atypical solutions of the symmetric binary perceptron. Journal of Physics A: Mathematical and Theoretical , 57(19):195202, 2024

2024
[19]

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
[20]

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
[21]

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
[22]

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
[23]

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
[24]

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
[25]

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

2013
[26]

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
[27]

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
[28]

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
[29]

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
[30]

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
[31]

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
[32]

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

2006
[33]

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
[34]

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
[35]

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
[36]

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
[37]

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
[38]

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
[39]

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
[40]

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
[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

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, E

D. Gamarnik, E. C. Kizildag, W. Perkins, and C. Xu. Algor ithms and barriers in the symmetric binary perceptron model. In 63rd IEEE Annual Symposium on Foundations of Computer Scienc e, FOCS 2022, Denver, CO, USA, October 31 - November 3, 2022 , pages 576–587. IEEE, 2022

2022
[48]

Gamarnik, C

D. Gamarnik, C. Moore, and L. Zdeborova. Disordered sys tems insights on computational hardness. Journal of Statistical Mechanics: Theory and Experiment , (11):115015, 2022

2022
[49]

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
[50]

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
[51]

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
[52]

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
[53]

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
[54]

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
[55]

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. 30

2017
[56]

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
[57]

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

2017
[58]

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
[59]

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
[60]

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

1993
[61]

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
[62]

Huang and M

B. Huang and M. Sellke. Tight lipschitz hardness for opt imizing mean ﬁeld spin glasses. In 63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2 022, Denver, CO, USA, October 31 - November 3, 2022 , pages 312–322. IEEE, 2022

2022
[63]

Huang and Y

H. Huang and Y. Kabashima. Origin of the computational h ardness for learning with binary synapses. Phys. Rev. E , 90:052813, 2014

2014
[64]

Huang, K

H. Huang, K. Y M. Wong, and Y. Kabashima. Entropy landsca pe of solutions in the binary perceptron problem. Journal of Physics A: Mathematical and Theoretical , 46(37):375002, 2013

2013
[65]

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

1989
[66]

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
[67]

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
[68]

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
[69]

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
[70]

E. C. Kizildag. Sharp phase transition for multi overla p gap property in ising p-spin glass and random k-SAT models. 2023. available online at http://arxiv.org/abs/2309.09913

2023 arXiv
[71]

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

1995
[72]

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
[73]

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
[74]

Li and T

S. Li and T. Schramm. Some easy optimization problems ha ve the overlap-gap property. 2020. available online at http://arxiv.org/abs/2411.01836 . 31

2020 arXiv
[75]

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
[76]

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
[77]

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
[78]

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
[79]

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
[80]

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
[81]

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

2023 arXiv
[82]

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
[83]

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
[84]

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
[85]

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
[86]

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
[87]

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

1990
[88]

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
[89]

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
[90]

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
[91]

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. 32

2019
[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]

Perkins and C

W. Perkins and C. Xu. Frozen 1-RSB structure of the symme tric Ising perceptron. STOC 2021: Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory o f Computing , pages 1579–1588, 2021

2021
[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]

Rodenburg

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

2008
[97]

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
[98]

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
[99]

Schniter, S

P. Schniter, S. Rangan, and A. K. Fletcher. Vector appro ximate 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
[100]

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
[101]

Sherrington and S

D. Sherrington and S. Kirkpatrick. Solvable model of a spin glass. Phys. Rev. Letters , 35:1792–1796, 1972

1972
[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. 33

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

2024 arXiv
[116]

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

2024
[117]

M. Stojnic. Fully lifted interpolation of bilinearly indexed random processes – a large deviation view
[118]

M. Stojnic. A large deviation view of stationarized fully lifted blirp interpolation. 2025. available online at arxiv

2025
[119]

M. Stojnic. Rare dense solutions clusters in asymmetr ic binary perceptrons – local entropy via fully lifted RDT. 2025. available online at arxiv

2025
[120]

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
[121]

The complexity of spherical p-spin models - A s econd moment approach

E Subag. The complexity of spherical p-spin models - A s econd moment approach. Ann. Probab., 45:3385 – 3450, 2017

2017
[122]

The geometry of the gibbs measure of pure spher ical spin glasses

E Subag. The geometry of the gibbs measure of pure spher ical spin glasses. Inventiones Mathematicae, 210:135 – 209, 2017

2017
[123]

Following the ground states of full-rsb spher ical spin glasses

E Subag. Following the ground states of full-rsb spher ical spin glasses. Comm. Pure Appl. Math. , 74:1021–1044, 2021

2021
[124]

Free energy landscapes in spherical spin glas ses

E Subag. Free energy landscapes in spherical spin glas ses. Duke Math. J. , 173:1291 – 1357, 2024

2024
[125]

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

2018
[126]

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
[127]

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
[128]

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
[129]

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
[130]

Waldspurger

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

2018
[131]

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
[132]

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

1963
[133]

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
[134]

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

2015
[135]

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

2019
[2024]

available online at http://arxiv.org/abs/2407.16627

arXiv
[2025]

available online at arxiv

Pith tools

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

[1] [1]

E. Abbe, S. Li, and A. Sly. Proof of the contiguity conject ure and lognormal limit for the symmetric perceptron. In 62nd IEEE Annual Symposium on Foundations of Computer Scienc e, FOCS 2021, Denver, CO, USA, February 7-10, 2022 , pages 327–338. IEEE, 2021

2021

[2] [2]

E. Abbe, S. Li, and A. Sly. Binary perceptron: eﬃcient alg orithms can ﬁnd solutions in a rare well- connected cluster. In STOC ’22: 54th Annual ACM SIGACT Symposium on Theory of Computi ng, Rome, Italy, June 20 - 24, 2022 , pages 860–873. ACM, 2022

2022

[3] [3]

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

[4] [4]

Achlioptas and F

D. Achlioptas and F. Ricci-Tersenghi. On the solution-s pace geometry of random constraint satisfaction problems. In Proceedings of the 38th Annual ACM Symposium on Theory of Comp uting, Seattle, W A, USA, May 21-23, 2006 , pages 130–139. ACM, 2006

2006

[5] [5]

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

[6] [6]

A. E. Alaoui, A. Montanari, and M. Sellke. Optimization o f mean-ﬁeld spin glasses. The Annals of Probability, 49(6), 2021

2021

[7] [7]

A. E. Alaoui, A. Montanari, and M. Sellke. Sampling from t he Sherrington-Kirkpatrick gibbs measure via algorithmic stochastic localization. In 63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022, Denver, CO, USA, October 31 - November 3, 2 022, pages 323–334. IEEE, 2022

2022

[8] [8]

A. E. Alaoui amd D. Gamarnik. Hardness of sampling soluti ons from the symmetric binary perceptron