{"id":"08887ebd-a030-43f7-8268-fbfaa67f7a1c","arxiv_id":"2608.02450","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":4,"one_line_summary":"PhaseLift exactly recovers any fixed complex signal from O(log n) random coded-diffraction masks, matching the Ω(log n) information-theoretic lower bound.","lead":"PhaseLift can now recover signals from coded diffraction patterns using O(n log n) intensity measurements, matching the theoretical minimum any algorithm could need. This settles a long-open question about how many random masks are necessary and sufficient for computationally tractable phase retrieval.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The O(log n) claim rests on an unproved extension of the tangent-space robust injectivity estimate (Prop. 2) to complex masks; an independent verification is needed.","rationale":"After a full pass, I agree with the reader's assessment. The central construction is the adaptive golfing scheme of §2.6, which is self-contained except for two imports. Proposition 4's bias bound is written as O(e^{-τ}) but the displayed Hölder step gives O(e^{-τ/2}); while this is an internal inconsistency, it is patchable by increasing the constant τ0 and does not change the O(log n) mask count. The genuinely load-bearing gap is Proposition 2: the paper's optimal rate depends on a robust injectivity estimate with failure probability 2n exp(−c ν^4 L/M^8) for all masks in Assumption 1. The cited [23, Prop. 8] was proved for real erasure masks, and the paper's Remark 3 explicitly omits the details of the extension. Because the tangent-space operator for complex octanary masks has a different small-ball/noise structure, the extension is not a trivial corollary of near-isotropicity (Prop. 1). If the constant c is smaller than claimed, or if the argument only works for L=Ω(log^2 n), then the central claim O(log n) masks is unsupported. The lower bound appendix is correct, so the optimality claim would not be contradicted by a worse upper bound, but the theorem as stated would be false. No other internal errors were found; the numerical experiments are consistent with the claimed scaling but cannot close this gap. Thus the verdict remains CONDITIONAL: the paper is credible and likely correct, but the missing proof must be supplied.","tokens_in":21415,"tokens_out":29885,"duration_ms":234928,"concrete_test":"Independently re-derive Proposition 2 for a general mask satisfying Assumption 1 by transcribing the proof of [23, Prop. 8] step by step, replacing the real erasure mask law with the complex octanary law. Specifically, verify (i) the small-ball estimate for ⟨f_k,Dv⟩ and (ii) the matrix-Bernstein variance bound ||Σ E[(F_ℓ|_T − E F_ℓ|_T)^2]||_op ≲ M^8/ν^4, using only |d|≤M, E d=0, E d^2=0, E|d|^4=2ν^2. If the resulting failure probability is ≤2n exp(−c ν^4 L/M^8) for L=C(M,ν) log n, the concern is resolved; if it yields only L=Ω(log^2 n), then Theorem 1 is false as stated.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Theorem 1's proof has two probabilistic pillars: the golfing certificate (Prop. 7) and robust injectivity on the tangent space (Prop. 2). Prop. 2 is the load-bearing one for the optimal O(log n) rate: it asserts that with L=C log n masks, (1/(ν^2 nL))||A(Z)||^2 ≥ (1/4)||Z||_F^2 for all Z∈T with probability ≥1−2n exp(−c ν^4 L/M^8). The paper imports this from [23, Prop. 8] (Remark 3): 'Combining the near isotropicity identity in Proposition 1 with the argument of [23, Proposition 8] yields Proposition 2... Since the proof follows the same lines, we omit the details.' But [23] proved the estimate for the real erasure ensemble with n odd; the stated extension to all complex symmetric masks satisfying Assumption 1 (including the octanary ensemble d=b1b2) is not shown. If the small-ball/spectral-norm estimates in [23] rely on real-valuedness or on the erasure structure, the constant c in the tail bound could fail, or the required mask count could become Ω(log^2 n). Either way, the union bound in §2.7 collapses and the optimal-sampling-rate claim is not established. This is a missing proof of a central ingredient, not a cosmetic gap.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the PhaseLift feasibility formulation for coded-diffraction-pattern phase retrieval under i.i.d. random masks. Theorem 1 claims that, for any fixed unit-norm signal x0 in C^n and any ω≥1, L≥C(M,ν)ω log n masks suffice for X0=x0x0* to be the unique feasible point of the program (6) with probability at least 1−n^{−ω}; equivalently, m=O(ω n log n) scalar intensity measurements. The proof combines a near-isotropy identity, a tangent-space robust injectivity estimate, and an approximate dual certificate built by a golfing scheme with adaptively allocated batches and a dimension-independent truncation threshold. An appendix proves an Ω(ω log n) mask lower bound for the flat signal under the erasure mask ensemble, supporting optimality. Numerical experiments compare fixed and logarithmic mask budgets and probe Poisson-noise robustness.","tokens_in":21768,"tokens_out":13915,"duration_ms":121775,"significance":"If the proof can be completed, the paper resolves an open problem of Candès–Li–Soltanolkotabi by closing the gap between O(log^2 n) and Ω(log n) masks for PhaseLift in the random-mask CDP model. The adaptive allocation of masks and the dimension-free truncation are genuine technical novelties, and the lower-bound appendix extends earlier coordinate-signal obstructions to the flat signal. The main proof is detailed and, apart from the gaps identified below, internally coherent. The main caveat is that one of the two probabilistic pillars of Theorem 1 is imported without proof, so the central theorem is at present conditional.","major_comments":[{"comment":"Proposition 2 is the second probabilistic pillar of Theorem 1: it supplies the tangent-space lower bound (12) with failure probability 1−2n exp(−cν^4L/M^8), and §2.7 uses it in the union bound. The proof is omitted, and the cited [23, Proposition 8] is described as covering real-valued mask ensembles with n odd. The claimed extension to all complex masks in Assumption 1, including the octanary ensemble, requires verification: the argument in [23] may rely on real-valuedness or on the special erasure structure. Without a proof or an exact statement covering the present setting, the O(log n) guarantee is not established as written.","section":"2.1.4, Proposition 2 and Remark 3"},{"comment":"The displayed bias bound (15) states O(e^{−τ}), but the proof gives only O(e^{−τ/2}). Specifically, after the Hölder step the factor (E 1_{U^c})^{1/2} is bounded by sqrt(8)e^{−τ/2}, which is then multiplied by the O(M^4) moment factors. Thus the proposition as stated is false. The consequence is local and fixable: enlarging τ0 in (35) by an absolute factor restores the argument, and the O(log n) conclusion survives, but the bias estimates in Propositions 5 and 6 should be re-derived with the correct exponent.","section":"2.3, Proposition 4"}],"minor_comments":[{"comment":"The axis labels and legends write 'm = n 4log n'; this should be typeset as n⌈4 log n⌉ to avoid ambiguity.","section":"Section 3, Figures 1–4"},{"comment":"There are many small typographical artifacts (missing spaces, malformed equals signs, broken displayed formulas). A careful copyedit is needed before publication.","section":"Throughout"}],"recommendation":"major_revision","confidential_remarks":"The manuscript is worth pursuing. The main obstacle is the unproved extension of [23, Proposition 8]; if the authors can supply that proof or a precise citation covering Assumption 1, the result is likely acceptable. The Proposition 4 exponent error is repairable and does not affect the O(log n) conclusion after adjusting constants. I do not see circularity or undue reliance on the authors' own prior work."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Here's my read. The main result is what it claims: PhaseLift recovers any fixed complex signal from O(omega log n) random masks with failure probability n^{-omega}, matching the erasure lower bound, and this improves the prior O(log^2 n) constant-probability guarantee by a log factor while also giving polynomial failure decay. The adaptive golfing construction with shrinking batch sizes and dimension-independent truncation is a genuine methodological step, and the lower-bound appendix is correct. The numerical experiments are modest but consistent with the claimed scaling.\n\nThe place to look before believing it is Section 2.1.4, Proposition 2. That robust injectivity estimate on the tangent space is load-bearing: Theorem 1's union bound needs it at L = O(log n). The paper imports it from [23, Proposition 8] and says the proof follows the same lines for all masks satisfying Assumption 1, including complex octanary masks. That extension is not shown. Since [23]'s estimate was written for the real erasure ensemble with n odd, the optimal-rate claim literally depends on an unverified step. I do not think this is fatal — the argument likely goes through for complex symmetric distributions because Ed^2 = 0 replaces real-valuedness — but it has to be written out. As it stands, the paper is conditional, not complete.\n\nSecond, Proposition 4 claims a bias bound O(e^{-tau}), but the written proof only gives O(e^{-tau/2}): the factor (E 1_{U^c})^{1/2} costs half the exponent. This is a minor local fix — enlarge tau0 by a constant — and it does not affect the O(log n) scaling. A referee should ask for the corrected exponent.\n\nAlso worth noting: the result is nonuniform, as the authors acknowledge, and the Poisson experiments are empirical only. Neither is a flaw in the main theorem.\n\nBottom line: the result deserves a serious referee. If the Proposition 2 extension is supplied and the Proposition 4 exponent corrected, this should be a very good paper. I would rather see it in print with the gap closed; right now I would treat the optimal-rate claim as highly plausible but not fully established. Send it to review, with instructions to verify Proposition 2.","headline":"The O(log n) mask result is real and important, but the paper as written rests on an omitted proof of tangent-space robust injectivity plus a minor exponent error in the bias bound; both look fixable.","tokens_in":22288,"tokens_out":3924,"would_cite":true,"duration_ms":35596,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["94A12","42A38","60B20"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper proves that PhaseLift exactly recovers any fixed complex signal from O(log n) random coded-diffraction masks, with failure probability at most n^{-ω}, and that this sampling rate is optimal up to constants.","keywords":["phase retrieval","coded diffraction patterns","PhaseLift","random masks","optimal sampling rate","convex recovery","dual certificate","golfing scheme"],"falsifier":"Compute the smallest singular value of the restricted coded-diffraction sampling map on the tangent space of a fixed signal for small n (e.g., n = 8, 16, 32) and many independent octanary mask sets with L = ⌈C log n⌉. If the minimum of ||A(Z)||_2 / (ν√(nL) ||Z||_F) over the tangent space is consistently below 1/4, or if the failure probability decays slower than n^{-ω}, then the imported robust injectivity estimate—and hence Theorem 1—would be refuted.","tokens_in":21277,"feed_emoji":"🔬","tokens_out":5421,"duration_ms":52212,"temperature":0.7,"pith_summary":"The paper proves that PhaseLift—a convex program that lifts the unknown signal to a rank-one matrix—recovers any fixed unit-norm complex signal from coded diffraction patterns taken with L ≥ C ω log n random masks, succeeding with probability at least 1−n^{-ω}. Because each mask supplies n intensity measurements, the total sampling rate is m = O(ω n log n), matching the information-theoretic lower bound up to constants. The result closes the logarithmic gap left by previous PhaseLift guarantees and settles the optimal mask complexity for computationally tractable recovery from coded diffraction patterns. The proof works by constructing an approximate dual certificate through a refined golfing scheme that allocates masks adaptively and truncates measurements at a dimension-independent threshold. If correct, PhaseLift attains the best possible trade-off between dimension, failure probability, and measurement cost for this structured phase retrieval problem.","feed_headline":"Exact recovery from O(log n) coded-diffraction masks","feed_subtitle":"PhaseLift matches the Ω(log n) lower bound, settling the optimal sampling rate for coded diffraction phase retrieval.","key_machinery":"The argument lifts the signal to X0 = x0x0* and works in the Hermitian matrix space, with the linear sampling map A defined by A(Z) = {tr(F_{k,ℓ} Z)}. Two components carry the proof: (1) a robust injectivity estimate, imported from an earlier result, asserting that (1/(ν^2 n L)) ||A(Z)||_2^2 ≥ (1/4) ||Z||_F^2 uniformly on the tangent space T = {x0 z* + z x0*}; and (2) an approximate dual certificate Y in range(A*) + span{I} with ||Y_T − X0||_F ≤ ν/(4 M^2 √n) and ||Y_{T⊥}||_op ≤ 1/2, constructed by an adaptive golfing scheme. The scheme's two refinements are adaptive mask allocation, with batch sizes shrinking as the residual contracts, and a stage-adaptive truncation operator with a dimensio","core_discovery":"The central claim is Theorem 1: for every fixed signal x0 ∈ C^n with ||x0|| = 1 and every ω ≥ 1, if the number of random masks L is at least C(M,ν) ω log n, then the rank-one matrix X0 = x0 x0* is the unique feasible point of the PhaseLift feasibility program with probability at least 1−n^{-ω}. Consequently x0 is recovered up to a global phase, and the total number of scalar measurements is m = nL = O(ω n log n). The paper also proves a matching lower bound for the erasure mask ensemble: recovering even the flat signal with probability at least 1−n^{-ω} requires L = Ω(ω log n) masks, so the mask complexity is optimal in its joint dependence on dimension and failure probability, up to constan","pith_inferences":["Because the certificate construction is modular, a similar adaptive golfing scheme might yield O(log n) mask guarantees for other computationally tractable phase retrieval algorithms, including nonconvex methods, if they can consume an approximate dual certificate; the paper explicitly leaves this as an open direction.","The numerical experiments on Poisson observations suggest a nonasymptotic stability bound of the form ||X̂ − X0||_F ≲ κ^{-1/2} for photon-limited measurements; proving such a bound with O(n log n) masks would be a natural extension.","The lower bound uses masks that can erase coordinates entirely; for erasure-free ensembles such as the octanary one, it is unclear whether Ω(log n) masks remain necessary, and testing this would clarify whether the optimal sampling rate is ensemble-specific.","The dimension-independent truncation threshold suggests the analysis may extend to mask distributions with heavier tails, where dimension-dependent thresholds would fail, but this would require new tail and variance estimates."],"forward_implications":["PhaseLift achieves exact recovery of any fixed signal from m = O(n log n) intensity measurements, the same order as the information-theoretic lower bound for the erasure mask ensemble.","The previous logarithmic gap between upper and lower bounds on the number of masks is closed: L = O(ω log n) masks suffice and Ω(ω log n) are necessary when the target success probability is 1−n^{-ω}.","The lower bound holds for the flat signal, not merely for sparse or coordinate signals, so the optimality is not an artifact of localized signals.","The guarantee is nonuniform: it holds for each fixed signal but not simultaneously for all signals from one mask realization, a limitation the paper explicitly leaves open.","The adaptive truncation and mask-allocation ideas are presented as having independent use for other structured sampling problems beyond coded diffraction patterns."],"fun_headline_variants":["PhaseLift achieves optimal mask count for coded diffraction","Exact recovery from O(log n) coded-diffraction masks","Coded diffraction: PhaseLift matches Ω(log n) lower bound","Optimal sampling rate: PhaseLift recovers from log n masks","PhaseLift: exact recovery with optimal mask complexity"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The argument rests on a robust injectivity estimate on the tangent space—the set of small rank-two perturbations around the true rank-one solution—that is imported from an earlier paper and asserted, without proof, to hold for all masks in the assumed model; if that estimate's constants fail for the complex mask ensembles, the O(log n) guarantee collapses.","fun_headline_variants_meta":{"raw":{"variants":["PhaseLift achieves optimal mask count for coded diffraction","Exact recovery from O(log n) coded-diffraction masks","Coded diffraction: PhaseLift matches Ω(log n) lower bound","Optimal sampling rate: PhaseLift recovers from log n masks","PhaseLift: exact recovery with optimal mask complexity"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000812,"raw_usage":{"total_tokens":3415,"prompt_tokens":776,"completion_tokens":2639,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":520,"completion_tokens_details":{"reasoning_tokens":2552}},"tokens_in":520,"tokens_out":2639,"duration_ms":19557,"temperature":1.0,"reasoning_tokens":2552,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-04T07:05:56.607288+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Compute the smallest singular value of the restricted coded-diffraction sampling map on the tangent space of a fixed signal for small n (e.g., n = 8, 16, 32) and many independent octanary mask sets with L = ⌈C log n⌉. If the minimum of ||A(Z)||_2 / (ν√(nL) ||Z||_F) over the tangent space is consistently below 1/4, or if the failure probability decays slower than n^{-ω}, then the imported robust injectivity estimate—and hence Theorem 1—would be refuted.","supporting_citations":[],"review_version":1}