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 , the conventional AF is
with and indices modulo . 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 leave (1) unchanged:
T1 Rotated signal for some .
T2 Translated signal for some .
T3 Reflected signal .
T4 Modulated signal for some .
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 ; (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. denotes the Hermitian matrices, , , and the Frobenius, nuclear and spectral norms of a matrix, the entrywise product, (with ), and with the scaled leading eigenvector of .
Problem Formulation
Let be the pulse. A delay by is applied by the operator , where $F is the unitary DFT and indexes its frequencies. For integer it is the cyclic shift of (1), , and for real it defines the translation in T2. With the matrices , , the sum in (1) is the quadratic form , so that
where is the lifted pulse and is the set of measured delay-Doppler pairs. Every AF sample is thus the squared magnitude of a linear functional of .
Let stack the functionals for , and let stack the amplitudes . Unlike classical lifting, where is linear in [31], the AF is quartic in , so the lifted problem is still a PR problem, now over the positive semidefinite (PSD) cone: find of rank one with .
Let occupy at most contiguous DFT bins; because a modulation is trivial (T4), the band can be taken centered. Let hold the DFT columns for , so that with and with . The band-limited lift has unknowns instead of , and exactly when .
The trivial ambiguities T1–T4 of are collected in the set . For almost all pulses with , AF samples determine up to [20 Prop. 1]. We take , the widest band covered by this uniqueness result. Since , the origin sample fixes the trace: for every exact fit.
Convex Program and Recovery Guarantees
Let denote the lifted pulse in the band. The convex program takes as input an anchor , a rank-one estimate of computed from the data by the initialization of Section III-A. Given the anchor, and following [30], we relax the equalities to inequalities and, among the matrices that satisfy them, recover as the one best aligned with the anchor:
The objective is linear and the constraints are convex, so (P) is convex [30 Lemma 1]. The lift of every member of that remains in the band is feasible with all constraints active, so the anchor is what singles out .
To state when is the unique solution of (P), let hold the phases of the AF samples, and define on the real-linear map , with adjoint . Since , with equality at the pulse, every feasible satisfies .
Moving the pulse from to changes , to first order, by ; these matrices form the tangent space of the rank-one matrices at [30 Sec. IV-C]. Its orthogonal complement holds the Hermitian matrices whose range is orthogonal to , with projection , . We write , and likewise for the other subspaces.
The map cannot be injective on all of : a continuous trivial ambiguity, such as a fractional translation, moves along a curve of rank-one matrices on which is constant, so the tangent of this curve lies in . Injectivity is therefore required only on , the orthogonal complement of in :
In the opposite direction, gives for every .
Theorem 1. Assume (A1) ; (A2) there are with and such that satisfies and ; and (A3) the anchor is aligned, . If and , then is the unique solution of (P).
Proof. Let be feasible and . Feasibility gives and . Since , we bound the two terms. First, as and ,
Second, because the range of is orthogonal to , so (A3) gives and, by (A2) and ,
Hence , which is negative unless . In that case with ; writing with , the compression of to has determinant , so and with real. Then forces , a contradiction. ▪
Conditions (A1) and (A2) are the restricted injectivity and approximate dual certificate of [30 Thm. 2], stated modulo the kernel that the continuous ambiguities create; (A3) is the first-order optimality of the alignment between the anchor and the orbit of . When an exact certificate is available, the injectivity and alignment conditions are not needed:
Proposition 1. If there is such that satisfies , and , then is the unique solution of (P).
Proof. For a feasible , , using , and . Equality forces , so with because the null space of is spanned by , and forces . ▪
Since , the smallest singular value of on bounds from below; Section IV evaluates it numerically (Table I).
The Algorithm
recovers the pulse in three steps, summarized in Algorithm 1: an initialization that computes the anchor 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 belongs to two sets, the matrices that reproduce the measured magnitudes, , and the rank-one PSD matrices, and the initialization looks for a common point by moving between them. Let fit the measured magnitudes while keeping the current phases, with the minimum-norm pseudoinverse, and let be the best rank-one PSD approximation. Alternating them, , 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:
with and 300 steps, from a single random start scaled to . Applying by ten conjugate-gradient steps from zero keeps the correction in the range of , so the pulse remains a fixed point even where has a null space. The anchor is .
Convex Surrogate Steps
Problem (P) has real unknowns and up to 16384 second-order cone constraints, which is costly for interior-point solvers. instead applies the fast adaptive shrinkage/thresholding algorithm (FASTA) [39], started at , to the penalized form
The fit penalizes violations of the constraints of (P), and the slack , refreshed between rounds as , 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 on exact fits, it does not change the set of exact solutions, and its bias is removed by continuation, over three rounds, from .
With and at the iterate , the convex quadratic majorizes the fit, because for , and touches it with the same gradient at . The forward–backward step of FASTA at is therefore a step on the convex semidefinite program of minimizing over , a majorization–minimization scheme, whose proximal map soft-thresholds the eigenvalues. FASTA chooses the step adaptively [39], and each iteration costs one Hermitian eigendecomposition and two applications of . The lifted estimate is .
Algorithm 1 : estimate from AF samples on
Require: on ; ;
; , random,
Initialization
for 300 steps do
— fit magnitudes, keep phases
end for
— anchor
Convex surrogate steps
for 3 rounds do
repeat
— eigendecomposition
until the residual falls below of its maximum
end for
— lifted estimate
Polish
LM iterations on in (6), started at
return (noiseless data) or (noisy data)
Polish
The lifted estimate need not be the pulse itself: every member of 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 by decreasing the intensity misfit
with at most 150 Levenberg–Marquardt (LM) iterations [40] started at ; the result is the estimate .
Numerical Experiments
Following [20], we build 100 unit-norm pulses with samples on ( ns), each as the inverse DFT of a Gaussian-shaped amplitude spectrum multiplied by a uniformly random phase. The centered band of bins holds all but of the energy of each pulse, so the pulses are band-limited with up to the Gaussian tail. The error is , with the distance of [20 Def. 2] taken over with continuous shifts and modulations, and a trial succeeds when it is below . 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 on ; the smallest on is a lower bound for
| Delays kept | On (shift) | Smallest on | Next on | |
| All | 16384 | – | – | |
| Every 2nd | 8192 | – | – | |
| Every 3rd | 5504 | – | – | |
| Every 5th | 3328 | – | – | |
| Every 7th | 2432 | – | – | |
| Every 8th | 2048 | – | – |
Table 1. Numerical validation of (A1) on pulses 1, 6 and 11: singular values of on (range over the pulses).
| Measured | Removed | Median error | Success |
| All delays | 0% | 100% | |
| Every 3rd delay | 66% | 100% | |
| Every 5th delay | 80% | 100% | |
| Every 7th delay | 86% | 100% | |
| Every 2nd delay | 50% | 55% | |
| Every 4th delay | 75% | 25% | |
| Every 8th delay | 88% | 0% | |
| 50% | 100% | ||
| 50% | 100% | ||
| Middle half of delays | 50% | 10% | |
| Middle half of Doppler | 50% | 5% |
Table 2. Median error and success rate of wavex for incomplete AF.
. In every case : is one-dimensional (the fractional shift), and 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 matches the original over the whole delay-Doppler plane, including the unmeasured delays, and overlaps after alignment over , with a relative error of ( 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 (red) and (blue), aligned over .
Complete AF: Figure 2(a) shows that the anchor has a median error of and that wavex recovers 98 of the 100 pulses, with a median error of . A recovery can be verified from the data alone, since the final misfit (6) of a recovered pulse is about . 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 . (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 -th delay is kept with coprime to , or the central half
of the delays or of the Doppler bins is kept ( or ), wavex recovers every pulse. When divides ( for ), 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 to the complete AF with . For noisy data wavex returns , 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]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]P. M. Woodward, Probability and Information Theory. With Applications to Radar. London, U.K.: Pergamon, 1953.
- [3]W. Siebert, “A radar detection philosophy,” IRE Transactions on Information Theory, vol. 2, no. 3, pp. 204–221, Sep. 1956.
- [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]E. Wigner, “On the quantum correction for thermodynamic equilibrium,” Physical Review, vol. 40, no. 5, pp. 749–759, Jun. 1932.
- [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]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]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]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]J. Speiser, “Wide-band ambiguity functions,” IEEE Transactions on Information Theory, vol. 13, no. 1, pp. 122–123, Jan. 1967.DOI
- [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]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]M. Jankiraman, Design of Multi-Frequency CW Radars. Raleigh, NC, USA: SciTech Publishing, 2007.DOI
- [14]A. W. Rihaczek, Principles of High-Resolution Radar. Norwood, MA, USA: Artech House, 1996.
- [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]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]P. Jaming, “The phase retrieval problem for the radar ambiguity function and vice versa,” in IEEE Radar Conference, 2010, pp. 230–235.DOI
- [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]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]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]———, “BanRaW: Band-limited radar waveform design via phase retrieval,” in IEEE International Conference on Acoustics, Speech and Signal Processing, 2021, pp. 5449–5453.
- [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]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]S. Pinilla and J. Thiyagalingam, “Global optimality for non-linear constrained restoration problems via imvexity,” in International Conference on Learning Representations, 2024.
- [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]———, “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]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]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]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]———, “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]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]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]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]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]N. Levanon and E. Mozeson, Radar Signals. Hoboken, NJ, USA: Wiley, 2004.
- [36]S. Pinilla, “waveX: Convex radar waveform recovery from the narrow-band ambiguity function,” 2026. [Online]. Available: https://github.com/samuelpinilla/waveX
- [37]———, “invexapi: Operators, losses and solvers for structured inverse problems,” 2026. [Online]. Available: https://github.com/samuelpinilla/invexapi
- [38]D. R. Luke, “Relaxed averaged alternating reflections for diffraction imaging,” Inverse Problems, vol. 21, no. 1, pp. 37–50, 2005.
- [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]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

