betaFeedback

WorksMathematics

Radar Waveform Design via Convex Semidefinite Relaxation

Abstract

The ambiguity function (AF) of a radar waveform describes its ability to resolve targets in range and Doppler. Designing a waveform that attains a prescribed AF magnitude is a phase retrieval problem with four trivial ambiguities, and a time- or band-limited pulse is determined up to these ambiguities by at most three times as many AF samples as it has time samples or frequencies. Existing solvers for the narrowband AF, however, are non-convex: they cannot guarantee that they reach the global minimizer, which is unique only up to the trivial ambiguities, so the recovered pulse depends on the starting point. This letter addresses this gap by lifting the problem to positive semidefinite matrices supported on the pulse band, where each AF sample becomes the magnitude of a linear functional. In the lifted space, recovery is formulated as a convex program, and a dual certificate provides a sufficient condition for exactness. The proposed algorithm, wavex, combines an initialization by relaxed reflections, convex semidefinite surrogate steps, and a local polish. Numerical experiments show that wavex accurately recovers band-limited pulses from complete AFs and from AFs with most of their samples removed, provided the remaining samples determine the pulse, and that its accuracy degrades gracefully as the noise increases. wavex is built on the open-source library invexapi, and the code that reproduces every result is available at https://github.com/samuelpinilla/waveX.

Introduction

The matched filter [1] is optimal for an echo of known shape but does not describe the response to any other echo. Woodward filled this gap [2] with the ambiguity function (AF), the filter output versus delay and Doppler mismatch, whose properties were developed in [3, 4]. For a discrete signal x∈CNx \in\mathbb{C}^{N}, the conventional AF is

A[τ,f]=∣∑n=0N−1x[n] x[n−τ]e−2πinf/N∣2,(1)A[\tau,f]=\left|\sum_{n=0}^{N-1}x[n]\,x[n-\tau]e^{-2\pi inf/N}\right|^{2}, \tag*{(1)}

with τ,f=0,…,N−1\tau,f=0,\ldots,N-1 and indices modulo NN. Its bilinear form traces back to Wigner [5] and Ville [6], and the AF was later interpreted through the Heisenberg group [7, 8] and extended to wideband [9, 10] and multiple-input multiple-output [11] radar.

The mainlobe width of the AF sets the range and velocity resolution, and its sidelobes indicate how strongly a target in one delay-Doppler cell can mask a target in another, which makes the AF the standard criterion for matching a waveform to an application [12]. A response concentrated at a single delay-Doppler point is impractical, since a target would rarely fall exactly on it [13, 14], so waveform design seeks a thumbtack AF, with a narrow central peak and low sidelobes. Finding the signal that produces a prescribed AF is the inverse of this task; in an early result, Buda [15] showed that an AF bounded by a Hermite function belongs to a Hermite-function signal. The following trivial ambiguities of xx leave (1) unchanged:

T1 Rotated signal eiϕxe^{i\phi}x for some ϕ∈R\phi\in\mathbb{R}.

T2 Translated signal x[n−a]x[n-a] for some a∈Ra \in\mathbb{R}.

T3 Reflected signal x[−n]x[-n].

T4 Modulated signal eibnx[n]e^{ibn}x[n] for some b∈Rb \in\mathbb{R}.

Since the AF is phaseless, the inverse problem is a bivariate phase retrieval (PR) problem [16, 17], related to short-time Fourier and frequency-resolved optical gating (FROG) PR [18, 19]. The conjugation in the AF adds a fourth trivial ambiguity to those of FROG [20].

For almost all band- or time-limited pulses, at most three times as many AF samples as frequencies or time samples determine the pulse up to T1–T4 [20, 21]. Existing solvers are non-convex: the trust-region method of [20], minimizing a smoothed amplitude loss [22, 23], guarantees convergence only to a critical point. Lacking a certificate of global optimality, its output cannot be accepted as the unique solution [24], a concern across phaseless problems [25, 26, 27, 28]. WaveMax [29, 30], a convex program in the line of [31, 32, 33, 34], is posed on the AF of the fractional Fourier transform of the pulse, whose samples differ from (1), so its program and guarantees do not transfer directly. A convex formulation for the conventional AF, the one used by most radar systems [35], is still missing.

This letter fills that gap with wavex, a convex method based on lifting the AF. Its contributions are: (i) a band-restricted lifting in which every sample of (1) is the magnitude of a linear functional of X=xxHX=xx^{H}; (ii) a convex program over this lifting, with a dual certificate as a sufficient condition for exact recovery; (iii) a new initialization by relaxed averaged reflections from a single random start; (iv) convex surrogate steps that update the lifted matrix by proximal-gradient iterations, followed by a local polish; and (v) experiments on complete, decimated and noisy AFs. The code is public [36] and built on invexapi [37].

Notation. Boldface lowercase and uppercase letters denote vectors and matrices. HN\mathbb{H}^{N} denotes the N×NN \times N Hermitian matrices, ⟨U,V⟩=tr⁡(UHV)\langle U,V\rangle=\operatorname{tr}(U^{H}V), ∥⋅∥F\|\cdot\|_{F}, ∥⋅∥∗\|\cdot\|_{*} and ∥⋅∥2\|\cdot\|_{2} the Frobenius, nuclear and spectral norms of a matrix, ⊙\odot the entrywise product, sgn⁡(z)=z/∣z∣\operatorname{sgn}(z)=z/|z| (with sgn⁡(0)=0\operatorname{sgn}(0)=0), and lead⁡(W)=λ1v1\operatorname{lead}(W)=\sqrt{\lambda_{1}}v_{1} with v1v_{1} the scaled leading eigenvector of WW.

Problem Formulation

Let x∈CNx \in\mathbb{C}^{N} be the pulse. A delay by τ∈R\tau\in\mathbb{R} is applied by the operator Φτ=FHdiag⁡(e−2πiτl/N)F\Phi_{\tau}=F^{H}\operatorname{diag}(e^{-2\pi i\tau l/N})F, where $F is the unitary DFT and l=−N/2,…,N/2−1l=-N/2,\ldots,N/2-1 indexes its frequencies. For integer τ\tau it is the cyclic shift of (1), (Φτx)[n]=x[n−τ](\Phi_\tau x)[n]=x[n-\tau], and for real τ\tau it defines the translation in T2. With the matrices Bτ,f=ΦτHdiag⁡(e−2πinf/N)B_{\tau,f}=\Phi_\tau^H\operatorname{diag}(e^{-2\pi inf/N}), n=0,…,N−1n=0,\ldots,N-1, the sum in (1) is the quadratic form xHBτ,fxx^H B_{\tau,f}x, so that

A[τ,f]=∣xHBτ,fx∣2=∣tr⁡(Bτ,fX)∣2,(τ,f)∈Ω(2)A[\tau,f]=\left|x^H B_{\tau,f}x\right|^2=\left|\operatorname{tr}(B_{\tau,f}X)\right|^2,\qquad(\tau,f)\in\Omega \tag*{(2)}

where X=xxHX=xx^H is the lifted pulse and Ω\Omega is the set of mm measured delay-Doppler pairs. Every AF sample is thus the squared magnitude of a linear functional of XX.

Let B:HN→Cm\mathcal{B}:\mathbb{H}^N\to\mathbb{C}^m stack the functionals tr⁡(Bτ,f⋅)\operatorname{tr}(B_{\tau,f}\cdot) for (τ,f)∈Ω(\tau,f)\in\Omega, and let b∈Rmb\in\mathbb{R}^m stack the amplitudes b[τ,f]=A[τ,f]b[\tau,f]=\sqrt{A[\tau,f]}. Unlike classical lifting, where ∣aHx∣2=tr⁡(aaHX)|a^Hx|^2=\operatorname{tr}(aa^HX) is linear in XX [31], the AF is quartic in xx, so the lifted problem is still a PR problem, now over the positive semidefinite (PSD) cone: find X⪰0X\succeq0 of rank one with ∣B(X)∣=b|\mathcal{B}(X)|=b.

Let xx occupy at most SS contiguous DFT bins; because a modulation is trivial (T4), the band can be taken centered. Let Q∈CN×SQ\in\mathbb{C}^{N\times S} hold the DFT columns e2πink/N/Ne^{2\pi i nk/N}/\sqrt{N} for k=−S/2,…,S/2−1k=-S/2,\ldots,S/2-1, so that x=Qcx=Qc with c∈CSc\in\mathbb{C}^S and X=QWQHX=QWQ^H with W=ccH∈HSW=cc^H\in\mathbb{H}^S. The band-limited lift BQ(W)=B(QWQH)\mathcal{B}_Q(W)=\mathcal{B}(QWQ^H) has S2S^2 unknowns instead of N2N^2, and QWQH⪰0QWQ^H\succeq0 exactly when W⪰0W\succeq0.

The trivial ambiguities T1–T4 of xx are collected in the set T(x)\mathcal{T}(x). For almost all pulses with S≤N/2S\le N/2, 3S−13S-1 AF samples determine xx up to T(x)\mathcal{T}(x) [20 Prop. 1]. We take S=N/2S=N/2, the widest band covered by this uniqueness result. Since B0,0=IB_{0,0}=I, the origin sample fixes the trace: tr⁡(W)=∥x∥22=b[0,0]\operatorname{tr}(W)=\|x\|_2^2=b[0,0] for every exact fit.

Convex Program and Recovery Guarantees

Let W⋆=ccHW_\star=cc^H denote the lifted pulse in the band. The convex program takes as input an anchor W0=c0c0HW_0=c_0c_0^H, a rank-one estimate of W⋆W_\star computed from the data by the initialization of Section III-A. Given the anchor, and following [30], we relax the equalities ∣BQ(W)∣=b|\mathcal{B}_Q(W)|=b to inequalities and, among the matrices that satisfy them, recover W⋆W_\star as the one best aligned with the anchor:

maximize⁡W∈HS⟨W0,W⟩subject to∣BQ(W)∣≤b,W⪰0.(3)\begin{aligned} \underset{W\in\mathbb{H}^S}{\operatorname{maximize}}\quad&\langle W_0,W\rangle\\ \text{subject to}\quad&|\mathcal{B}_Q(W)|\le b,\quad W\succeq0. \tag*{(3)} \end{aligned}

The objective is linear and the constraints are convex, so (P) is convex [30 Lemma 1]. The lift of every member of T(x)\mathcal{T}(x) that remains in the band is feasible with all constraints active, so the anchor is what singles out W⋆W_\star.

To state when W⋆W_\star is the unique solution of (P), let u=sgn⁡(BQ(W⋆))u=\operatorname{sgn}(\mathcal{B}_Q(W_\star)) hold the phases of the AF samples, and define on HS\mathbb{H}^S the real-linear map L(Z)=Re⁡(u‾⊙BQ(Z))∈Rm\mathcal{L}(Z)=\operatorname{Re}(\overline{u}\odot\mathcal{B}_Q(Z))\in\mathbb{R}^m, with adjoint L∗\mathcal{L}^*. Since L(W)≤∣BQ(W)∣\mathcal{L}(W)\le|\mathcal{B}_Q(W)|, with equality L(W⋆)=b\mathcal{L}(W_\star)=b at the pulse, every feasible WW satisfies L(W−W⋆)≤0\mathcal{L}(W-W_\star)\le0.

Moving the pulse from cc to c+hc+h changes ccHcc^H, to first order, by chH+hcHch^H+hc^H; these matrices form the tangent space E={chH+hcH:h∈CS}E=\{ch^H+hc^H:h\in\mathbb{C}^S\} of the rank-one matrices at W⋆W_\star [30 Sec. IV-C]. Its orthogonal complement E⊥E^\perp holds the Hermitian matrices whose range is orthogonal to cc, with projection PE⊥(Z)=ΠZΠP_{E^\perp}(Z)=\Pi Z\Pi, Π=I−ccH/∥c∥22\Pi=I-cc^H/\|c\|_2^2. We write ZE=PE(Z)Z_E=P_E(Z), and likewise for the other subspaces.

The map L\mathcal{L} cannot be injective on all of EE: a continuous trivial ambiguity, such as a fractional translation, moves W⋆W_\star along a curve of rank-one matrices on which ∣BQ∣|\mathcal{B}_Q| is constant, so the tangent of this curve lies in K=E∩ker⁡LK=E\cap\ker\mathcal{L}. Injectivity is therefore required only on E′=E⊖KE'=E\ominus K, the orthogonal complement of KK in EE:

α=min⁡Z∈E′∥Z∥F=1∥L(Z)∥1.(4)\alpha=\min_{\substack{Z\in E'\\\|Z\|_F=1}}\|\mathcal{L}(Z)\|_1. \tag*{(4)}

In the opposite direction, ∥QHBτ,fQ∥2≤1\|Q^H B_{\tau,f}Q\|_2\le1 gives ∥L(Z)∥1≤m∥Z∥∗\|\mathcal{L}(Z)\|_1\le m\|Z\|_* for every Z∈HSZ\in\mathbb{H}^S.

Theorem 1. Assume (A1) α>0\alpha>0; (A2) there are λ∈Rm\lambda\in\mathbb{R}^m with λj≥λmin⁡>0\lambda_j\ge\lambda_{\min}>0 and ν,ζ≥0\nu,\zeta\ge0 such that Y=L∗(λ)−W0Y=\mathcal{L}^*(\lambda)-W_0 satisfies PE⊥(Y)⪰νΠP_{E^\perp}(Y)\succeq\nu\Pi and ∥PE⊥(Y)∥F≤ζ\|P_{E^\perp}(Y)\|_F\le\zeta; and (A3) the anchor is aligned, PK(W0)=0P_K(W_0)=0. If mλmin⁡>νm\lambda_{\min}>\nu and ζ<αλmin⁡\zeta<\alpha\lambda_{\min}, then W⋆W_\star is the unique solution of (P).

Proof. Let W≠W⋆W\ne W_\star be feasible and H=W−W⋆H=W-W_\star. Feasibility gives L(H)≤0\mathcal{L}(H)\le0 and HE⊥=ΠWΠ⪰0H_{E^\perp}=\Pi W\Pi\succeq0. Since ⟨W0,H⟩=λTL(H)−⟨Y,H⟩\langle W_0,H\rangle=\lambda^T\mathcal{L}(H)-\langle Y,H\rangle, we bound the two terms. First, as L(H)≤0\mathcal{L}(H)\le0 and L(HK)=0\mathcal{L}(H_K)=0,

λTL(H)≤−λmin⁡∥L(H)∥1≤−λmin⁡(α∥HE′∥F−m∥HE⊥∥∗).\lambda^T\mathcal{L}(H)\le-\lambda_{\min}\|\mathcal{L}(H)\|_1 \le-\lambda_{\min}\left(\alpha\|H_{E'}\|_F-m\|H_{E^\perp}\|_*\right).

Second, PK(L∗(λ))=0P_K(\mathcal{L}^*(\lambda))=0 because the range of L∗\mathcal{L}^* is orthogonal to ker⁡L⊇K\ker\mathcal{L}\supseteq K, so (A3) gives PK(Y)=0P_K(Y)=0 and, by (A2) and HE⊥⪰0H_{E^\perp}\succeq0,

−⟨Y,H⟩=−⟨PE′(Y),HE′⟩−⟨PE⊥(Y),HE⊥⟩≤ζ∥HE′∥F−ν∥HE⊥∥∗.-\langle Y,H\rangle=-\langle P_{E'}(Y),H_{E'}\rangle-\langle P_{E^\perp}(Y),H_{E^\perp}\rangle \le\zeta\|H_{E'}\|_F-\nu\|H_{E^\perp}\|_*.

Hence ⟨W0,H⟩≤−(αλmin⁡−ζ)∥HE′∥F−(ν−mλmin⁡)∥HE⊥∥∗\langle W_0,H\rangle\le-(\alpha\lambda_{\min}-\zeta)\|H_{E'}\|_F-(\nu-m\lambda_{\min})\|H_{E^\perp}\|_*, which is negative unless H∈KH\in K. In that case H=chH+hcHH=ch^H+hc^H with W⋆+H⪰0W_\star+H\succeq0; writing h=βc+rh=\beta c+r with r⊥cr\perp c, the 2×22\times2 compression of W⋆+HW_\star+H to {c,r}\{c,r\} has determinant −∥r∥22∥c∥22-\|r\|_2^2\|c\|_2^2, so r=0r=0 and H=tccHH=tcc^H with tt real. Then L(H)=tb=0\mathcal{L}(H)=tb=0 forces t=0t=0, a contradiction. ▪

Conditions (A1) and (A2) are the restricted injectivity and approximate dual certificate of [30 Thm. 2], stated modulo the kernel KK that the continuous ambiguities create; (A3) is the first-order optimality of the alignment between the anchor and the orbit of W⋆W_\star. When an exact certificate is available, the injectivity and alignment conditions are not needed:

Proposition 1. If there is λ>0\lambda>0 such that Y=L∗(λ)−W0Y=\mathcal{L}^*(\lambda)-W_0 satisfies Y⪰0Y\succeq0, Yc=0Yc=0 and rank⁡(Y)=S−1\operatorname{rank}(Y)=S-1, then W⋆W_\star is the unique solution of (P).

Proof. For a feasible WW, ⟨W0,W⟩=λTL(W)−⟨Y,W⟩≤λTb=⟨W0,W⋆⟩\langle W_0,W\rangle=\lambda^T\mathcal{L}(W)-\langle Y,W\rangle\le\lambda^Tb=\langle W_0,W_\star\rangle, using L(W)≤b\mathcal{L}(W)\le b, ⟨Y,W⟩≥0\langle Y,W\rangle\ge0 and Yc=0Yc=0. Equality forces ⟨Y,W⟩=0\langle Y,W\rangle=0, so W=tccHW=tc c^H with t≥0t\ge0 because the null space of YY is spanned by cc, and λTL(W)=λTb\lambda^T\mathcal{L}(W)=\lambda^Tb forces t=1t=1. ▪

Since ∥ν∥1≥∥ν∥2\|\nu\|_1\ge\|\nu\|_2, the smallest singular value of L\mathcal{L} on E′E' bounds α\alpha from below; Section IV evaluates it numerically (Table I).

The wavexwavex Algorithm

wavexwavex recovers the pulse in three steps, summarized in Algorithm 1: an initialization that computes the anchor W0W_0 of (P), convex surrogate steps that approach the solution of (P) in the lifted space, and a polish of the resulting pulse in the full signal space.

Initialization

The lifted pulse W⋆W_\star belongs to two sets, the matrices that reproduce the measured magnitudes, ∣BQ(W)∣=b\lvert\mathcal{B}_Q(W)\rvert=b, and the rank-one PSD matrices, and the initialization looks for a common point by moving between them. Let PM(W)=W+BQ+(b⊙sgn⁡(BQ(W))−BQ(W))P_M(W)=W+\mathcal{B}_Q^+(\boldsymbol{b}\odot\operatorname{sgn}(\mathcal{B}_Q(W))-\mathcal{B}_Q(W)) fit the measured magnitudes while keeping the current phases, with BQ+\mathcal{B}_Q^+ the minimum-norm pseudoinverse, and let PS(W)=λ1v1v1HP_S(W)=\lambda_1v_1v_1^H be the best rank-one PSD approximation. Alternating them, W←PSPM(W)W\gets P_SP_M(W), is the spectral step behind earlier estimates [20, 30]. The initialization instead uses the relaxed averaged alternating reflections (RAAR) [38], which reflect through both sets so that the iterate does not stall, as plain alternation can:

W←β2(RSRM+Id)(W)+(1−β)PM(W),R=2P−Id,(5)W\gets\frac{\beta}{2}(R_SR_M+\mathrm{Id})(W)+(1-\beta)P_M(W),\qquad R=2P-\mathrm{Id}, \tag*{(5)}

with β=0.9\beta=0.9 and 300 steps, from a single random start ggHgg^H scaled to ∥g∥2=A[0,0]1/4=∥x∥2\lVert g\rVert_2=A[0,0]^{1/4}=\lVert x\rVert_2. Applying BQ+\mathcal{B}_Q^+ by ten conjugate-gradient steps from zero keeps the correction in the range of BQ+\mathcal{B}_Q^+, so the pulse remains a fixed point even where BQ\mathcal{B}_Q has a null space. The anchor is c0=lead⁡(PM(W))c_0=\operatorname{lead}(P_M(W)).

Convex Surrogate Steps

Problem (P) has S2=4096S^2=4096 real unknowns and up to 16384 second-order cone constraints, which is costly for interior-point solvers. wavexwavex instead applies the fast adaptive shrinkage/thresholding algorithm (FASTA) [39], started at W0W_0, to the penalized form

minimize⁡W⪰012∥BQ(W)∥22+∥ξ−b∥22+μtr⁡(W).(6)\underset{W\succeq0}{\operatorname{minimize}}\quad\frac{1}{2}\lVert\mathcal{B}_Q(W)\rVert_2^2+\lVert\xi-\boldsymbol{b}\rVert_2^2+\mu\operatorname{tr}(W). \tag*{(6)}

The fit penalizes violations of the constraints of (P), and the slack ξ≥0\xi\geq0, refreshed between rounds as ξ=max⁡(b−∣BQ(W)∣,0)\xi=\max(\boldsymbol{b}-\lvert\mathcal{B}_Q(W)\rvert,0), stops pulling up the samples that already lie below their bound. The trace, which is the nuclear norm on the PSD cone, is a convex surrogate of rank; since tr⁡(W)=b[0,0]\operatorname{tr}(W)=b[0,0] on exact fits, it does not change the set of exact solutions, and its O(μ)O(\mu) bias is removed by continuation, μ←0.1μ\mu\gets0.1\mu over three rounds, from μ=10−2∥BQ∗(b)∥∗\mu=10^{-2}\lVert\mathcal{B}_Q^*(\boldsymbol{b})\rVert_*.

With t=b−ξt=\boldsymbol{b}-\xi and uk=sgn⁡(BQ(Wk))u_k=\operatorname{sgn}(\mathcal{B}_Q(W_k)) at the iterate WkW_k, the convex quadratic Gk(W)=12∥BQ(W)−t⊙uk∥22G_k(W)=\frac{1}{2}\lVert\mathcal{B}_Q(W)-t\odot u_k\rVert_2^2 majorizes the fit, because ∣z−tu∣≥∣z∣−t\lvert z-tu\rvert\geq\lvert z\rvert-t for ∣u∣=1\lvert u\rvert=1, and touches it with the same gradient at WkW_k. The forward–backward step of FASTA at WkW_k is therefore a step on the convex semidefinite program of minimizing Gk(W)+μtr⁡(W)G_k(W)+\mu\operatorname{tr}(W) over W⪰0W\succeq0, a majorization–minimization scheme, whose proximal map soft-thresholds the eigenvalues. FASTA chooses the step γ\gamma adaptively [39], and each iteration costs one S×SS\times S Hermitian eigendecomposition and two applications of BQ\mathcal{B}_Q. The lifted estimate is xL=Qlead⁡(W)x_L=Q\operatorname{lead}(W).

Algorithm 1 wavexwavex: estimate x^\hat{x} from AF samples AA on Ω\Omega

Require: AA on Ω\Omega; S=N/2S=N/2; β=0.9\beta=0.9

  1. b←A\boldsymbol{b}\gets\sqrt{A}; W←ggHW\gets gg^H, g∈CSg\in\mathbb{C}^S random, ∥g∥2=A[0,0]1/4\lVert g\rVert_2=A[0,0]^{1/4}

  2. Initialization

  3. for 300 steps do

  4. W←PM(W)W\gets P_M(W) — fit magnitudes, keep phases

  5. W←β2(RSRM+Id)(W)+(1−β)WMW\gets\frac{\beta}{2}(R_SR_M+\mathrm{Id})(W)+(1-\beta)W_M

  6. end for

  7. c0←lead⁡(PM(W));W←c0c0Hc_0\gets\operatorname{lead}(P_M(W));\quad W\gets c_0c_0^H — anchor W0W_0

  8. ξ←0;μ←10−2∥BQ∗(b)∥∗\xi\gets0;\quad\mu\gets10^{-2}\lVert\mathcal{B}_Q^*(\boldsymbol{b})\rVert_*

  9. Convex surrogate steps

  10. for 3 rounds do

  11. repeat

  12. z←BQ(W)z\gets\mathcal{B}_Q(W)

  13. W←W−γBQ∗(sgn⁡(z)⊙(∣z∣+ξ−b))W\gets W-\gamma\mathcal{B}_Q^*(\operatorname{sgn}(z)\odot(\lvert z\rvert+\xi-\boldsymbol{b}))

  14. VDVH←WV D V^H\gets W — eigendecomposition

  15. W←Vmax⁡(D−γμI,0)VHW\gets V\max(D-\gamma\mu I,0)V^H

  16. until the residual falls below 10−510^{-5} of its maximum

  17. ξ←max⁡(b−∣BQ(W)∣,0),μ←0.1μ\xi\gets\max(\boldsymbol{b}-\lvert\mathcal{B}_Q(W)\rvert,0),\quad\mu\gets0.1\mu

  18. end for

  19. xL←Qlead⁡(W)x_L\gets Q\operatorname{lead}(W) — lifted estimate

  20. Polish

  21. x^←\hat{x}\gets LM iterations on ℓ\ell in (6), started at xLx_L

  22. return x^\hat{x} (noiseless data) or xLx_L (noisy data)

Polish

The lifted estimate need not be the pulse itself: every member of T(x)\mathcal{T}(x) is an equally valid solution, and a member modulated by a fraction of a bin (T4) lies outside the band, where the convex steps can only return its band-limited approximation. The polish (i.e. step to remove the trivial ambiguity) moves the estimate onto that member in the full space CN\mathbb{C}^N by decreasing the intensity misfit

ℓ(q)=12∑(τ,f)∈Ω(∣qHBτ,fq∣2−A[τ,f])2,q∈CN,(7)\ell(q)=\frac{1}{2}\sum_{(\tau,f)\in\Omega}\left(\lvert q^H B_{\tau,f}q\rvert^2-A[\tau,f]\right)^2,\qquad q\in\mathbb{C}^N, \tag*{(7)}

with at most 150 Levenberg–Marquardt (LM) iterations [40] started at q=xLq=x_L; the result is the estimate x^\hat{x}.

Numerical Experiments

Following [20], we build 100 unit-norm pulses with N=128N=128 samples on t∈[−1,1] μst\in[-1,1]\,\mu\mathrm{s} (Δt=15.7\Delta t=15.7 ns), each as the inverse DFT of a Gaussian-shaped amplitude spectrum multiplied by a uniformly random phase. The centered band of N/2N/2 bins holds all but 1.1×10−71.1\times10^{-7} of the energy of each pulse, so the pulses are band-limited with S≤N/2S\leq N/2 up to the Gaussian tail. The error is dist⁡(x,x^)/∥x∥2\operatorname{dist}(x,\hat{x})/\lVert x\rVert_2, with the distance of [20 Def. 2] taken over T(x)\mathcal{T}(x) with continuous shifts and modulations, and a trial succeeds when it is below 10−310^{-3}. wavexwavex uses at most 1000 FASTA iterations per round and a single random start per pulse; all results use one seed.

Numerical validation of (A1): Table 1 evaluates condition (A1) of Theorem 1 on three of the pulses, for the complete AF and the delay decimations of Table 2, through the singular values of L\mathcal{L} on EE; the smallest on E′E' is a lower bound for

Delays keptmmOn KK (shift)Smallest on E′E'Next on E′E'
All16384≤3.7×10−13\le3.7 \times10^{-13}5.25.2–10.7×10−310.7 \times10^{-3}3.13.1–3.63.6
Every 2nd8192≤2.5×10−13\le2.5 \times10^{-13}3.73.7–7.6×10−37.6 \times10^{-3}2.22.2–2.52.5
Every 3rd5504≤2.1×10−13\le2.1 \times10^{-13}3.03.0–6.2×10−36.2 \times10^{-3}1.81.8–2.12.1
Every 5th3328≤1.6×10−13\le1.6 \times10^{-13}2.32.3–4.8×10−34.8 \times10^{-3}1.41.4–1.61.6
Every 7th2432≤1.5×10−13\le1.5 \times10^{-13}2.02.0–4.0×10−34.0 \times10^{-3}1.21.2–1.31.3
Every 8th2048≤1.3×10−13\le1.3 \times10^{-13}1.61.6–2.7×10−32.7 \times10^{-3}0.130.13–0.160.16

Table 1. Numerical validation of (A1) on pulses 1, 6 and 11: singular values of L\mathcal{L} on EE (range over the pulses).

MeasuredRemovedMedian errorSuccess
All delays0%6.2×10−76.2 \times10^{-7}100%
Every 3rd delay66%1.2×10−71.2 \times10^{-7}100%
Every 5th delay80%4.5×10−74.5 \times10^{-7}100%
Every 7th delay86%7.8×10−77.8 \times10^{-7}100%
Every 2nd delay50%3.6×10−43.6 \times10^{-4}55%
Every 4th delay75%1.7×10−31.7 \times10^{-3}25%
Every 8th delay88%5.9×10−25.9 \times10^{-2}0%
∣τ∣<N/4|\tau| < N/450%1.4×10−71.4 \times10^{-7}100%
∣f∣<N/4|f| < N/450%6.5×10−76.5 \times10^{-7}100%
Middle half of delays50%2.6×10−12.6 \times10^{-1}10%
Middle half of Doppler50%7.4×10−17.4 \times10^{-1}5%

Table 2. Median error and success rate of wavex for incomplete AF.

α\alpha. In every case α>0\alpha> 0: KK is one-dimensional (the fractional shift), and E′E' has one weak direction, the modulation by a fraction of a bin that the band cannot express and the polish corrects, with all other singular values above one up to every seventh delay. Keeping every eighth delay adds two more weak directions, consistent with its failure in Table II.

Example: Figure 1 shows a recovery by wavex when only every third delay is measured. The AF of the recovered pulse x^\hat{x} matches the original over the whole delay-Doppler plane, including the unmeasured delays, and x^\hat{x} overlaps xx after alignment over T(x)\mathcal{T}(x), with a relative error of 4.8×10−64.8 \times10^{-6} (9.8×10−49.8 \times10^{-4} for the anchor).

Figure 1. Recovery by wavex when every third delay is kept (66% of the AF samples removed). (a)–(c) Original, subsampled and recovered AFs, normalized to a unit peak. (d), (e) Zero-delay and zero-Doppler slices. (f), (g) Magnitude and phase of x^\hat{x} (red) and xx (blue), aligned over T(x)\mathcal{T}(x).

Complete AF: Figure 2(a) shows that the anchor has a median error of 1.4×10−21.4 \times10^{-2} and that wavex recovers 98 of the 100 pulses, with a median error of 1.4×10−61.4 \times10^{-6}. A recovery can be verified from the data alone, since the final misfit (6) of a recovered pulse is about 10−810^{-8}. The median run time per pulse on one CPU thread is 495 s.

Figure 2. Relative error of the anchor and of wavex. (a) Sorted errors of the 100 pulses from the complete AF; the dotted line marks the success threshold 10−310^{-3}. (b) Median error over 20 pulses versus SNR on the complete AF.

Incomplete AF: Table II uses 20 pulses (pulses 0, 5, . . . , 95) and removes delays or Doppler bins, as in Figure 1. When every LL-th delay is kept with LL coprime to NN, or the central half

of the delays or of the Doppler bins is kept (∣τ∣<N/4|\tau| < N/4 or ∣f∣<N/4|f| < N/4), wavex recovers every pulse. When LL divides NN (L=2,4,8L = 2, 4, 8 for N=128N = 128), the success rate drops to 55%, 25% and 0%. Keeping only the middle half of the delays or of the Doppler bins removes the origin rows, which the uniqueness proof of [20] requires, and recovery fails.

Noisy AF: We add Gaussian noise ee to the complete AF with SNR=10log⁡10(∥A∥F2/∥e∥22)\mathrm{SNR} = 10 \log_{10}(\lVert A \rVert_{F}^{2}/\lVert e \rVert_{2}^{2}). For noisy data wavex returns xLx_{\mathrm{L}}, because it splits with the noise. Figure 2(b) shows that its error degrades gracefully, with medians of 0.146, 0.077, 0.047 and 0.027 at 10, 20, 30 and 40 dB, about half those of the anchor (0.279, 0.144, 0.079 and 0.043).

Conclusion

This letter showed that radar waveform design from the magnitude of the conventional AF, so far addressed by non-convex solvers without global guarantees, admits a convex formulation. Lifting the problem to PSD matrices on the pulse band makes each AF sample the magnitude of a linear functional, and recovery becomes a convex program with a dual certificate as a sufficient condition for exactness. The proposed wavex combines an initialization by relaxed reflections, convex surrogate steps and a local polish. It accurately recovered band-limited pulses from complete AFs and from AFs with most samples removed, provided the remaining ones determine the pulse, and degraded gracefully with noise.

References

  1. [1]D. O. North, “An analysis of the factors which determine signal/noise discrimination in pulsed-carrier systems,” Proceedings of the IEEE, vol. 51, no. 7, pp. 1016–1027, Jul. 1963, (Reprint of RCA Laboratories Tech. Rep. PTR-6C, 1943).DOI
  2. [2]P. M. Woodward, Probability and Information Theory. With Applications to Radar. London, U.K.: Pergamon, 1953.
  3. [3]W. Siebert, “A radar detection philosophy,” IRE Transactions on Information Theory, vol. 2, no. 3, pp. 204–221, Sep. 1956.
  4. [4]R. Price and E. M. Hofstetter, “Bounds on the volume and height distributions of the ambiguity function,” IEEE Transactions on Information Theory, vol. 11, no. 2, pp. 207–214, Apr. 1965.DOI
  5. [5]E. Wigner, “On the quantum correction for thermodynamic equilibrium,” Physical Review, vol. 40, no. 5, pp. 749–759, Jun. 1932.
  6. [6]J. Ville, “Théorie et applications de la notion de signal analytique,” Câbles et Transmission, vol. 2A, no. 1, pp. 61–74, 1948. (in French).
  7. [7]W. Schempp, “Radar ambiguity functions, the Heisenberg group, and holomorphic theta series,” Proceedings of the American Mathematical Society, vol. 92, no. 1, pp. 103–110, Sep. 1984.DOI
  8. [8]L. Auslander and R. Tolimieri, “Radar ambiguity functions and group theory,” SIAM Journal on Mathematical Analysis, vol. 16, no. 3, pp. 577–601, May 1985.DOI
  9. [9]E. J. Kelly and R. P. Wishner, “Matched-filter theory for high-velocity, accelerating targets,” IEEE Transactions on Military Electronics, vol. 9, no. 1, pp. 56–69, 1965.DOI
  10. [10]J. Speiser, “Wide-band ambiguity functions,” IEEE Transactions on Information Theory, vol. 13, no. 1, pp. 122–123, Jan. 1967.DOI
  11. [11]G. San Antonio, D. R. Fuhrmann, and F. C. Robey, “MIMO radar ambiguity functions,” IEEE Journal of Selected Topics in Signal Processing, vol. 1, no. 1, pp. 167–177, Jun. 2007.
  12. [12]C. H. Wilcox, “The synthesis problem for radar ambiguity functions,” Mathematics Research Center, University of Wisconsin, Madison, WI, USA, MRC Technical Summary Report 157, 1960.
  13. [13]M. Jankiraman, Design of Multi-Frequency CW Radars. Raleigh, NC, USA: SciTech Publishing, 2007.DOI
  14. [14]A. W. Rihaczek, Principles of High-Resolution Radar. Norwood, MA, USA: Artech House, 1996.
  15. [15]R. de Buda, “Signals that can be calculated from their ambiguity function,” IEEE Transactions on Information Theory, vol. 16, no. 2, pp. 195–202, Mar. 1970.DOI
  16. [16]Y. Shechtman, Y. C. Eldar, O. Cohen, H. N. Chapman, J. Miao, and M. Segev, “Phase retrieval with application to optical imaging: A contemporary overview,” IEEE Signal Processing Magazine, vol. 32, no. 3, pp. 87–109, May 2015.DOI
  17. [17]P. Jaming, “The phase retrieval problem for the radar ambiguity function and vice versa,” in IEEE Radar Conference, 2010, pp. 230–235.DOI
  18. [18]T. Bendory, D. Edidin, and Y. C. Eldar, “On signal reconstruction from FROG measurements,” Applied and Computational Harmonic Analysis, vol. 48, no. 3, pp. 1030–1044, 2020.
  19. [19]S. Pinilla, T. Bendory, Y. C. Eldar, and H. Arguello, “Frequency-resolved optical gating recovery via smoothing gradient,” IEEE Transactions on Signal Processing, vol. 67, no. 23, pp. 6121–6132, Dec. 2019.DOI
  20. [20]S. Pinilla, K. V. Mishra, B. M. Sadler, and H. Arguello, “Phase retrieval for radar waveform design,” Information and Inference: A Journal of the IMA, vol. 13, no. 3, 2024, art. no. iaae015.arxiv.org/abs/2201.11384
  21. [21]———, “BanRaW: Band-limited radar waveform design via phase retrieval,” in IEEE International Conference on Acoustics, Speech and Signal Processing, 2021, pp. 5449–5453.
  22. [22]S. Pinilla, J. Bacca, and H. Arguello, “Phase retrieval algorithm via non-convex minimization using a smoothing function,” IEEE Transactions on Signal Processing, vol. 66, no. 17, pp. 4574–4584, Sep. 2018.DOI
  23. [23]S. Pinilla, J. Bacca, J.-Y. Tournier, and H. Arguello, “A smoothing stochastic phase retrieval algorithm for solving random quadratic systems,” in IEEE Statistical Signal Processing Workshop, 2018, pp. 278–282.DOI
  24. [24]S. Pinilla and J. Thiyagalingam, “Global optimality for non-linear constrained restoration problems via imvexity,” in International Conference on Learning Representations, 2024.
  25. [25]S. Pinilla, K. V. Mishra, and B. M. Sadler, “Unique bispectrum inversion for signals with finite spectral/temporal support,” in IEEE International Conference on Acoustics, Speech and Signal Processing, 2023, pp. 1–5.arxiv.org/abs/2111.06479
  26. [26]———, “Non-convex recovery from phaseless low-resolution blind deconvolution measurements using noisy masked patterns,” in 55th Asilomar Conference on Signals, Systems, and Computers, 2021, pp. 876–880.arxiv.org/abs/2111.13670
  27. [27]A. Jerez, S. Pinilla, and H. Arguello, “Fast target detection via template matching in compressive phase retrieval,” IEEE Transactions on Computational Imaging, vol. 6, pp. 934–944, 2020.DOI
  28. [28]K. V. Mishra, S. Pinilla, A. Pezeshki, and A. R. Calderbank, “Group-theoretic wideband radar waveform design,” in IEEE International Symposium on Information Theory, 2022, pp. 1821–1825.arxiv.org/abs/2207.00959
  29. [29]S. Pinilla, K. V. Mishra, and B. M. Sadler, “WaveMax: FrFT-based convex phase retrieval for radar waveform design,” in IEEE International Symposium on Information Theory, 2021, pp. 2387–2392.DOI
  30. [30]———, “WaveMax: Radar waveform design via convex maximization of FrFT phase retrieval,” IEEE Transactions on Signal Processing, vol. 73, pp. 4092–4107, 2025.arxiv.org/abs/2501.14164
  31. [31]E. J. Candès, T. Strohmer, and V. Voroninski, “PhaseLift: Exact and stable signal recovery from magnitude measurements via convex programming,” Communications on Pure and Applied Mathematics, vol. 66, no. 8, pp. 1241–1274, 2013.arxiv.org/abs/1109.4499
  32. [32]A. Guerrero, S. Pinilla, and H. Arguello, “Phase recovery guarantees from designed coded diffraction patterns in optical imaging,” IEEE Transactions on Image Processing, vol. 29, pp. 5687–5697, 2020.DOI
  33. [33]J. Bacca, S. Pinilla, and H. Arguello, “Super-resolution phase retrieval from designed coded diffraction patterns,” IEEE Transactions on Image Processing, vol. 29, pp. 2598–2609, 2020.DOI
  34. [34]S. Pinilla, K. V. Mishra, I. Shevkunov, M. Soltanalian, V. Katkovnik, and K. Egiazarian, “Unfolding-aided bootstrapped phase retrieval in optical imaging: Explainable AI reveals new imaging frontiers,” IEEE Signal Processing Magazine, vol. 40, no. 2, pp. 46–60, Mar. 2023.DOI
  35. [35]N. Levanon and E. Mozeson, Radar Signals. Hoboken, NJ, USA: Wiley, 2004.
  36. [36]S. Pinilla, “waveX: Convex radar waveform recovery from the narrow-band ambiguity function,” 2026. [Online]. Available: https://github.com/samuelpinilla/waveX
  37. [37]———, “invexapi: Operators, losses and solvers for structured inverse problems,” 2026. [Online]. Available: https://github.com/samuelpinilla/invexapi
  38. [38]D. R. Luke, “Relaxed averaged alternating reflections for diffraction imaging,” Inverse Problems, vol. 21, no. 1, pp. 37–50, 2005.
  39. [39]T. Goldstein, C. Studer, and R. Baraniuk, “A field guide to forward-backward splitting with a FISTA implementation,” arXiv:1411.3406, 2014.arxiv.org/abs/1411.3406
  40. [40]D. W. Marquardt, “An algorithm for least-squares estimation of nonlinear parameters,” Journal of the Society for Industrial and Applied Mathematics, vol. 11, no. 2, pp. 431–441, 1963.DOI

Paper details

vlnc:W_xe98awxm
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents