Source-linked AI summary
Fast Algorithms for Designing Multiple Unimodular Waveforms With Good Correlation Properties
Yongzhe Li, Sergiy A. Vorobyov
TL;DR
Large-scale, non-convex waveform-design problems make fast ISL/WISL optimization important, especially as code lengths and waveform counts grow. The paper formulates these objectives as quartic problems and uses majorization-minimization to simplify them. The authors report lower or comparable computational burden, faster convergence, and better correlation properties than existing algorithms.
Problem
ISL/WISL waveform-design problems can become large-scale as code lengths and waveform counts grow, yet are non-convex and require high design accuracy.
Source: §I · p. 3Method
The authors formulate ISL and WISL design as frequency-domain quartic optimization and simplify the problems using majorization-minimization and objective-function algebraic structure.
Source: §I · p. 4Results
The proposed algorithms have lower or comparable computational burden, faster convergence, and better correlation properties than state-of-the-art algorithms.
Source: §I · p. 4Takeaways & Limitations
The algorithms target real-time waveform design even when code lengths and waveform counts are large.
Source: §I · p. 4
Abstract
from arXiv · showhide
In this paper, we develop new fast and efficient algorithms for designing single/multiple unimodular waveforms/codes with good auto- and cross-correlation or weighted correlation properties, which are highly desired in radar and communication systems. The waveform design is based on the minimization of the integrated sidelobe level (ISL) and weighted ISL (WISL) of waveforms. As the corresponding optimization problems can quickly grow to large scale with increasing the code length and number of waveforms, the main issue turns to be the development of fast large-scale optimization techniques. The difficulty is also that the corresponding optimization problems are non-convex, but the required accuracy is high. Therefore, we formulate the ISL and WISL minimization problems as non-convex quartic optimization problems in frequency domain, and then simplify them into quadratic problems by utilizing the majorization-minimization technique, which is one of the basic techniques for addressing large-scale and/or non-convex optimization problems. While designing our fast algorithms, we find out and use inherent algebraic structures in the objective functions to rewrite them into quartic forms, and in the case of WISL minimization, to derive additionally an alternative quartic form which allows to apply the quartic-quadratic transformation. Our algorithms are applicable to large-scale unimodular waveform design problems as they are proved to have lower or comparable computational burden (analyzed theoretically) and faster convergence speed (confirmed by comprehensive simulations) than the state-of-the-art algorithms. In addition, the waveforms designed by our algorithms demonstrate better correlation properties compared to their counterparts.
I. INTRODUCTION
Waveform design seeks useful correlation properties while balancing constant-modulus hardware constraints and growing multiwaveform problems. This paper develops faster ISL- and WISL-based designs for matched-filter receivers using algebraic structure and majorization-minimization.
I. INTRODUCTION
- Good correlation properties support localization, resolution, and delay-Doppler ambiguity performance, while constant-modulus waveforms can reduce amplifier development costs.Perfect auto- and cross-correlation properties also help isolate targets after matched filtering.Source: §I · p. 2
- ISL measures accumulated sidelobes across time lags, and CAN and WeCAN use cyclic procedures for ISL and WISL design, respectively.These methods were extended to multiple-waveform design.Source: §I · p. 2
- Jointly optimizing a mismatched receive filter adds flexibility but trades signal-to-noise ratio for improved signal-to-interference-plus-noise ratio; this paper instead assumes a matched filter.With the receiver fixed, the focus is computationally efficient waveform design.Source: §I · p. 3
- Large code lengths and waveform counts make non-convex ISL/WISL problems costly, while CAN and WeCAN can take hours or days at scale.The paper targets faster convergence as well as lower computational burden, using frequency-domain quartic formulations, algebraic structure, and majorization-minimization; it reports lower or comparable burden, faster convergence, and better correlation properties than state-of-the-art algorithms.Source: §I · pp. 3–4
II. SIGNAL MODEL AND PROBLEM FORMULATION
The model represents a set of unimodular waveforms as a waveform matrix and formulates design through ISL or weighted ISL minimization. The weights control which time-lag sidelobes contribute to the objective.
II. SIGNAL MODEL AND PROBLEM FORMULATION
- The signal model uses an M-column waveform matrix of code length P, with each waveform represented by phase-valued samples of unit magnitude.The model describes the waveforms as mutually orthogonal; for M = 1, the matrix reduces to a column vector.Source: §II · p. 5
- ISL accumulates auto- and cross-correlation sidelobes across nonzero time lags for the waveform set.The objective’s first term represents auto-correlations and its second term cross-correlations.Source: §II · p. 5
- WISL uses real symmetric lag weights to control sidelobe levels, with zero-weighted lags excluded from consideration.When all controlling weights coincide, WISL reduces to ISL.Source: §II · p. 5
- The design problem seeks unimodular waveforms with desired correlation or weighted-correlation properties by minimizing ISL or WISL.The constraints impose unit magnitude, while the objective is stated to guarantee waveform orthogonality.Source: §II · pp. 5–6
III. FAST WAVEFORM DESIGN ALGORITHMS
The paper develops fast algorithms for ISL- and WISL-based unimodular waveform design, using majorization-minimization and algebraic structure in the objectives to reduce computational complexity.
III. FAST WAVEFORM DESIGN ALGORITHMS
- The section develops fast algorithms for both ISL- and WISL-minimization waveform design.The designs target unimodular waveforms.Source: §III · p. 6
- The algorithms use the majorization-minimization technique to address the design objectives.Source: §III · p. 6
- They exploit inherent algebraic structure in the objective functions to reduce computational complexity.Source: §III · p. 6
A. Fast ISL Minimization-Based Algorithm
The ISL algorithm rewrites the objective in the frequency domain as a quartic form, then uses successive quadratic majorizations to obtain waveform updates. Its implementation has O(MP log P) per-iteration complexity.
A. Fast ISL Minimization-Based Algorithm
- The frequency-domain ISL objective is rewritten as a quartic form in the vectorized waveform, using algebraic transformations of the correlation expression.The formulation relies on the desired waveforms’ orthogonality and constant modulus.Source: A. Fast ISL Minimization-Based Algorithm · pp. 6–7
- A quadratic majorant is applied to the transformed objective, and the majorization procedure yields a closed-form waveform update.The algorithm can also be accelerated with the SQUAREM scheme.Source: A. Fast ISL Minimization-Based Algorithm · pp. 8, 11
- The per-iteration complexity is O(MP log P), using FFT computations and the Toeplitz structure in the matrix-vector product.The direct calculation has complexity (3M + 2)P^2 + 2MP before these reductions.Source: A. Fast ISL Minimization-Based Algorithm · p. 12
B. Fast WISL Minimization-Based Algorithm
The WISL objective is reformulated into a proper quartic form so majorization-minimization can be applied. The resulting algorithm reduces the problem to a closed-form update and has complexity at most O((M −1)MP^2).
B. Fast WISL Minimization-Based Algorithm
- The WISL objective’s complex Frobenius-norm form is converted into a proper quartic form in y, enabling a MaMi-based algorithm.Directly expanding the squared norm does not yield a proper quartic form.Source: B. Fast WISL Minimization-Based… · pp. 13–14
- The quartic objective is majorized into a quadratic-form problem, whose unimodular update is solved in closed form.The algorithm then reshapes the updated vector into the designed waveform matrix.Source: B. Fast WISL Minimization-Based… · p. 19
- Algorithm 2 summarizes the proposed WISL minimization-based unimodular waveform design procedure.Source: B. Fast WISL Minimization-Based… · p. 19
- The algorithm’s complexity is at most O((M −1)MP^2), which the authors characterize as smaller than quadratic in problem size and suitable for large-scale optimization.The bound assumes the nonzero-weight index set Ω has NP elements, with 0 < NP ≤ P.Source: B. Fast WISL Minimization-Based… · pp. 19–20
IV. SIMULATION RESULTS
The simulations compare the proposed ISL and WISL algorithms with existing methods, including accelerated variants. They use common random-phase initializations and shared hardware and software, with two stopping criteria.
IV. SIMULATION RESULTS
- Algorithm 1 (ISLNew) is compared with CAN and ISLSong, while Algorithm 2 (WISLNew) is compared with WeCAN and WISLSong.Source: §IV · p. 21
- The simulations also test SQUAREM-accelerated versions of the MaMi-based ISLNew, WISLNew, ISLSong, and WISLSong algorithms.Source: §IV · p. 21
- All algorithms use the same random-phase initial sequences and computing platforms, and are evaluated with two stopping criteria.The criteria use normalized objective differences with tolerance 10^-8 or waveform-matrix/vector differences with tolerance 10^-3.Source: §IV · p. 21
A. ISL Minimization
Across the tested ISL algorithms, the accelerated ISLNew converges fastest, while the algorithms reach nearly the same final ISL values. The results also compare convergence and runtime under two stopping criteria.
A. ISL Minimization
- For M = 1 and P = 128, accelerated ISLNew requires the fewest iterations to meet tolerance under both stopping criteria; accelerated ISLSong is second fastest.All tested algorithms decrease ISL monotonically as iterations increase.Source: A. ISL Minimization · p. 22
- Without acceleration, ISLNew converges a little more slowly but achieves around 4 dB better ISL than CAN in the first example.Source: A. ISL Minimization · p. 22
- At P = 2048, accelerated ISLNew designs two waveforms in 56 seconds and 469 iterations, versus about 73 seconds and 6990 iterations for CAN.Accelerated ISLSong takes about 62 seconds and 491 iterations; the three algorithms obtain nearly the same minimum and average ISL across code lengths.Source: Table I · p. 22, A. ISL Minimization · p. 23
- Under stopping criterion (ii), the algorithms retain nearly the same minimum and average ISL values, but take longer and need more iterations than under criterion (i).For accelerated ISLSong at P = 2048, the worst time and iteration count increase about 10 and 7 times, respectively.Source: Table II · p. 22, A. ISL Minimization · p. 23
B. WISL Minimization
The WISL experiments compare convergence, final WISL, runtime, iterations, and correlation levels across design algorithms. Accelerated WISLNew generally performs best, with its advantage over WISLSong becoming more pronounced at larger code lengths.
B. WISL Minimization
- WISL values decrease monotonically with iterations, and accelerated WISLSong and WISLNew converge faster and reach lower values than their non-accelerated versions.In the tested example, WISLSong requires around twice as many iterations as WISLNew under either stopping criterion.Source: B. WISL Minimization · p. 24
- Accelerated WISLNew outperforms WISLSong and WeCAN across code lengths under criterion (i), and Table IV shows the same overall trends under criterion (ii).WeCAN performs worst across the evaluation characteristics; under criterion (ii), WISLNew takes around 3–7 times less time and 2–3 times fewer iterations than WISLSong.Source: Table III · p. 25, Table IV · p. 25, B. WISL Minimization · pp. 25, 27
- The fourth example averages minimum and average WISL, runtime, and iteration counts over 50 trials using the same waveform counts, code lengths, and weights as the second example.Results are reported for two stopping criteria.Source: B. WISL Minimization · p. 25
- For both designed waveform sets, WISLNew improves correlation levels by up to about 30 dB over WISLSong at the controlled lags.Autocorrelations are controlled at lags [−19, −1]∪ and cross-correlations at [−19, 19]; other lags are not controlled.Source: Figure 3 · p. 26, B. WISL Minimization · p. 27
- At P = 2048, WISLNew's largest minimum- and average-WISL advantages over WISLSong are 58.24 dB and 26.53 dB, respectively.WISLNew also uses less time and fewer iterations than WISLSong, with its superiority growing at larger code lengths.Source: B. WISL Minimization · pp. 26–27
V. CONCLUSION
The paper presents fast ISL- and WISL-minimization algorithms for unimodular waveform design, using majorization-minimization and objective-function algebraic structure. It reports computational burden at or below existing methods, faster convergence, and better waveform quality.
V. CONCLUSION
- The paper develops separate fast algorithms based on ISL and WISL minimization for single or multiple unimodular waveforms.The algorithms use the majorization-minimization framework and algebraic structures in the objective functions.Source: §V · p. 28
- The algorithms' computational complexity is suitable for large-scale optimization and is at least similar to or lower than that of existing algorithms.The paper also reports faster convergence to tolerance than existing state-of-the-art algorithms.Source: §V · p. 28
- The designed waveforms have better quality than those produced by existing state-of-the-art algorithms.The paper characterizes the target properties as good auto- and cross-correlation or weighted-correlation properties.Source: §V · p. 28