PaperlayerView exact revision on arXiv

Source-linked AI summary

Sparse Phase Retrieval: Convex Algorithms and Limitations

Kishore Jaganathan, Samet Oymak, Babak Hassibi

arXiv:1303.4128v3cs.ITmath.ITmath.OC

TL;DR

Phase retrieval asks how to recover a signal when only its power spectral density is measured, although that mapping is not one-to-one. This paper uses sparsity with reweighted l1-minimization and studies both Fourier and designed phaseless measurements. It reports recovery guarantees at O(k^2 log n) Fourier measurements and O(k log n) designed measurements, while noting a nonconvex constraint in the latter approach.

  • Problem

    Power spectral density measurements lose Fourier phase, and the mapping from signals to Fourier magnitude is not one-to-one, so additional measurements or prior information are needed for unique recovery.

    Source: §I · p. 1

  • Method

    The paper develops iterative reweighted l1-minimization for sparse phase retrieval and also considers a combinatorial approach using a specific choice of phaseless measurements.

    Source: §I · p. 1, §IV · p. 3, C. Combinatorial Approach · p. 4

  • Results

    O(k^2 log n) randomly selected Fourier-frequency measurements permit polynomial-time recovery with arbitrarily high probability, while designed phaseless measurements permit tractable recovery with O(k log n) measurements with very high probability.

    Source: §V · p. 3, C. Combinatorial Approach · p. 4

  • Takeaways & Limitations

    The paper reports that tractable sparse phase retrieval with O(k log n) measurements is possible when measurement matrices can be specifically chosen.

    Source: C. Combinatorial Approach · p. 4

    The proposed route to O(k log n) measurements depends on solving a nonconvex constraint, whose useful relaxation requires further investigation.

    Source: §V · p. 3

Abstract

from arXiv · show

We consider the problem of recovering signals from their power spectral density. This is a classical problem referred to in literature as the phase retrieval problem, and is of paramount importance in many fields of applied sciences. In general, additional prior information about the signal is required to guarantee unique recovery as the mapping from signals to power spectral density is not one-to-one. In this paper, we assume that the underlying signals are sparse. Recently, semidefinite programming (SDP) based approaches were explored by various researchers. Simulations of these algorithms strongly suggest that signals upto $o(\sqrt{n})$ sparsity can be recovered by this technique. In this work, we develop a tractable algorithm based on reweighted $l_1$-minimization that recovers a sparse signal from its power spectral density for significantly higher sparsities, which is unprecedented. We discuss the square-root bottleneck of the existing convex algorithms and show that a $k$-sparse signal can be efficiently recovered using $O(k^2logn)$ phaseless Fourier measurements. We also show that a $k$-sparse signal can be recovered using only $O(k log n)$ phaseless measurements if we are allowed to design the measurement matrices.

I. INTRODUCTION

Phase retrieval seeks to recover a signal when measurements provide its power spectral density but not Fourier phase, so recovery is not generally unique without additional measurements or prior information. This work assumes sparsity and proposes reweighted l1-minimization to address the sparsity limits of existing SDP-based approaches.

I. INTRODUCTION

  • Fourier-magnitude measurements do not uniquely determine a signal in general, motivating additional measurements or prior information such as sparsity.The paper frames this as phase retrieval, arising when power spectral density is measurable but Fourier phase is lost.Source: §I · p. 1
  • Sparse signals are used as prior information in SDP-based phase-retrieval work and are considered reasonable in X-ray crystallography, microscopy, and astronomical imaging.The cited prior work includes, and [13].Source: §I · p. 1
  • Existing SDP-based methods are associated with an o(√ n) sparsity regime, while this work develops reweighted l1-minimization for significantly higher sparsities.The paper also discusses SDP limitations and a combinatorial technique requiring fewer measurements for guaranteed recovery.Source: §I · p. 1
  • The paper proceeds from problem formulation and SDP limitations to a reweighted recovery algorithm, a combinatorial measurement approach, and numerical simulations.The introduction identifies Sections 2–6 as covering these topics.Source: §I · p. 1

II. PROBLEM FORMULATION

The paper formulates recovery of a real sparse signal from Fourier-magnitude data through its autocorrelation. It also notes that time shift, flipping, and global sign change leave autocorrelation unchanged, and introduces lifting to express the measurements using a higher-dimensional variable.

II. PROBLEM FORMULATION

  • The signal is real-valued, has length n, and has sparsity k, defined as its number of nonzero entries.Its Fourier transform is denoted y, and its autocorrelation is denoted a.Source: §II · p. 2
  • Because Fourier magnitude squared and autocorrelation are Fourier pairs, recovery from Fourier magnitude can be reformulated as recovery from autocorrelation.The passage identifies a as the autocorrelation of x.Source: §II · p. 2
  • Time shift, flipping, and global sign change preserve autocorrelation, so recovery has a trivial ambiguity among signals related by these operations.The paper treats such resulting signals as equivalent and says recovering any equivalent signal is sufficient in its applications.Source: §II · p. 2
  • Lifting embeds the nonconvex recovery problem in a higher-dimensional space so its constraints can be relaxed into convex constraints.The formulation squares Fourier-magnitude constraints and expresses them using X = xxT and trace measurements.Source: §II · p. 2

III. BACKGROUND

The SDP formulation leads to rank minimization, which is nonconvex. The background discusses log-determinant as a rank surrogate and summarizes sparsity limits observed or established for SDP-based recovery.

III. BACKGROUND

  • The lifted formulation can be posed as rank minimization, but rank is a nonconvex function.For positive semidefinite matrices, trace minimization is described as the tightest convex relaxation, yet it is not useful here because trace corresponds to fixed signal energy.Source: §III · p. 2
  • In phase retrieval, proposes minimizing log det(X + ǫI) as a rank surrogate, because trace minimization is not useful when trace(X) is fixed by Fourier-magnitude signal energy.Source: §III · p. 2
  • SDP simulations and theory indicate recovery with arbitrarily high probability for o(√ n)-sparse signals; with support information available by other means, recovery was observed up to roughly o(n) sparsity.The two-stage approach first uses autocorrelation-support information to recover signal support, then solves an SDP with known support, [17],.Source: §III · p. 2

IV. RECOVERY ALGORITHM

The recovery algorithm uses iterative reweighted l1-minimization to exploit support information contained in a leading eigenvector, including beyond the o(√ n) regime. It updates weights to encourage prospective support locations while retaining a convex optimization step at each iteration.

IV. RECOVERY ALGORITHM

  • Randomly weighted formulation (10) has rank-1 solutions with high probability for o(√ n) sparsity, but fails beyond that regime; its leading eigenvector can still contain support information at higher sparsities.The largest eigenvalue is described as considerably stronger than the others.Source: §IV · p. 3
  • The iterative method sets weights to zero at prospective support locations and positive outside them, encouraging those locations in the next minimization.The algorithm updates the weight matrix using locations where the rank-1 approximation has entries above a threshold.Source: §IV · p. 3
  • The algorithm takes Fourier-transform magnitudes and a maximum iteration count as input and returns an underlying signal estimate.The output is obtained from the rank-1 approximation.Source: §IV · p. 3
  • The procedure initializes weights uniformly at random, solves the optimization problem, and repeats weight updates until convergence or the iteration limit.If the solution is not rank 1, it uses the best rank-1 approximation before updating weights and ultimately returns that approximation.Source: §IV · p. 3

V. PHASE RETRIEVAL AS A COMPRESSION PROBLEM

The paper gives a polynomial-time recovery guarantee from partial power spectral density using O(k^2 log n) measurements. It also proposes a more ambitious route toward O(k log n) measurements, while noting that a useful relaxation of its nonconvex constraint remains unresolved.

V. PHASE RETRIEVAL AS A COMPRESSION PROBLEM

  • O(k^2 log n) randomly selected frequency measurements suffice for polynomial-time recovery from partial power spectral density with arbitrarily high probability, under Theorem V.1’s conditions.The proof recovers the autocorrelation by ℓ1 minimization and then applies Theorem V.1.Source: §V · p. 3
  • The proposed more sophisticated approach aims to use the valid-autocorrelation structure rather than solve only for a k^2-sparse vector.The paper presents it as a possible future direction, not an established result.Source: §V · p. 3
  • A useful relaxation of the sole nonconvex constraint could reduce the measurement requirement from O(k^2 log n) to O(k log n), but further investigation is required.The paper cautions against simply dropping that constraint.Source: §V · p. 3
  • With full power spectral density, the reweighted algorithm seemingly exceeds the o(√n)-sparsity bottleneck, although the authors provide no theoretical guarantees for it.The full power spectral density corresponds to n measurements.Source: §V · p. 3

A. Two-stage recovery

The two-stage approach relies on locating the signal support from the autocorrelation support. Under the lemma’s random-support and continuous-entry assumptions, the autocorrelation support becomes full at sufficiently high sparsity, removing that information source.

A. Two-stage recovery

  • The two-stage method seeks the signal support from the autocorrelation support, but the paper argues this approach cannot find the signal support above O(√n) sparsity.The lemma gives a random-signal condition under which the autocorrelation support is full.Source: A. Two-stage recovery · p. 4
  • For a uniformly random support and continuous i.i.d. nonzero entries, the autocorrelation support is full with arbitrarily high probability when k ≥ c√(n log n), for some constant c.This rules out the support-finding step of the two-stage approach in that regime.Source: A. Two-stage recovery · p. 4

B. Relation to Gaussian Phase Retrieval

The paper relates sparse Fourier phase retrieval to Gaussian phase retrieval and reports a square-root sparsity bottleneck for tractable methods in both settings. It contrasts those guarantees with recovery by low-rank, sparse search using fewer measurements.

B. Relation to Gaussian Phase Retrieval

  • The generalized phase-retrieval problem is structurally similar but simpler because it lacks trivial ambiguities such as time-shift and flipping.The paper notes that a related gap is illustrated for Fourier phase retrieval in [12].Source: B. Relation to Gaussian Phase Retrieval · p. 4
  • For the Gaussian-measurement SDP, the cited analyses report that recovery is not possible with very high probability when m ≤ O(min{k^2, n}), regardless of the regularizer λ.They infer that even when k^2 ≪ n, recovery needs Ω(k^2) measurements.Source: B. Relation to Gaussian Phase Retrieval · p. 4
  • The paper contrasts tractable recovery with low-rank, sparse matrix search, which the cited works show can recover xxT with k log n / k measurements.This is presented as a significant gap between tractable recovery and combinatorial search.Source: B. Relation to Gaussian Phase Retrieval · p. 4
  • For both Fourier and Gaussian phaseless measurements, existing algorithms’ theoretical guarantees face an o(√n)-sparsity bottleneck.The paper frames tractable sparse phase retrieval with few measurements as an open question.Source: B. Relation to Gaussian Phase Retrieval · p. 4

C. Combinatorial Approach

The combinatorial approach uses a specific measurement design to recover a k-sparse signal from phaseless measurements with O(k log n) measurements. Its theorem gives high-probability recovery of xx* in O(mn) time, while the authors note that the result demonstrates tractability rather than robustness to imperfect sparsity.

C. Combinatorial Approach

  • O(k log n) designed phaseless measurements suffice for high-probability recovery of xx* in O(mn) time.The theorem applies to arbitrary k-sparse vectors for k ≥ 2 and requires m ≥ ck log n for some constant c > 0.Source: C. Combinatorial Approach · p. 4
  • Without prior knowledge of k, the measurement design can use k log^2(n) measurements by covering dyadic sparsity levels.The proof uses measurements for sparsity levels k_i = 2^i, so the actual sparsity lies between two covered levels.Source: C. Combinatorial Approach · p. 4
  • The authors require perfectly sparse signals and present the theorem as demonstrating tractable recovery, not a robust algorithm for artificially designed measurements.Source: C. Combinatorial Approach · p. 4

VI. NUMERICAL SIMULATIONS

The simulations compare recovery success across sparsities for signals of lengths 32 and 64. Reweighted minimization outperforms the compared methods outside the o(√n) sparsity region, where existing SDP methods begin to fade.

VI. NUMERICAL SIMULATIONS

  • The evaluation varies signal length and sparsity, plotting recovery success rate against sparsity for n = 32 and n = 64.The success probability is the percentage of successful recoveries across 100 simulations for each sparsity.Source: §VI · pp. 4–5, Figure 1 · p. 5, Figure 2 · p. 5
  • The simulations choose support locations uniformly at random and draw signal values at those locations uniformly from [0,1].An output counts as successful when it matches the input; CandesPR, HassibiPR, and GS are comparison algorithms.Source: §VI · p. 5
  • Beyond the o(√n) sparsity region, reweighted minimization outperforms the compared methods, while existing SDP algorithms begin to fade.The plotted success rates use 100 simulations per sparsity; the figures cover n = 32 and n = 64.Source: §VI · p. 5, Figure 1 · p. 5, Figure 2 · p. 5

APPENDIX

The appendix proof recovers the signal by first finding its support and magnitudes, then determining relative phases along a connected graph. The graph-based phase recovery uses measurements whose supports intersect the true support in pairs.

APPENDIX

  • Zero measurements identify support sets disjoint from the signal support; taking the union of these sets and complementing it recovers the exact support.The proof uses the fact that a measurement is zero almost surely when its support intersects the signal support, and requires m ≥ 8k log n for the stated high-probability coverage argument.Source: APPENDIX · p. 6
  • Measurements intersecting the signal support at a single index determine that index's squared magnitude from the measurement and the corresponding coefficient.The proof bounds the chance of missing such a measurement for each support index and gives a high-probability guarantee when m ≥ 8k log n.Source: APPENDIX · p. 6
  • Measurements intersecting the support in pairs form edges of a graph; with m ≥ c k log k, the graph is connected with high probability.The proof forms the graph from pairwise intersections and uses a spanning tree to propagate relative phases from an initial node.Source: APPENDIX · p. 6
  • Two independent real-part measurements determine the phase difference on each tree edge, allowing recovery of all phases up to an overall phase ambiguity.The proof propagates the edgewise phase differences along tree paths and states an O(mn) total recovery time.Source: APPENDIX · p. 6
Loading 1303.4128v3…