PaperlayerView exact revision on arXiv

Source-linked AI summary

Sequence Design to Minimize the Weighted Integrated and Peak Sidelobe Levels

Junxiao Song, Prabhu Babu, Daniel P. Palomar

arXiv:1506.04234v1math.OC

TL;DR

The paper addresses weighted autocorrelation-sidelobe minimization for unit-modulus sequences, motivated by sensing and communications applications. It develops MM algorithms with FFT implementations and extends them to ℓp-based PSL minimization, obtaining low or virtually zero sidelobes and improved long-sequence PSL results.

  • Problem

    The paper studies how to design unit-modulus sequences with low weighted integrated or peak autocorrelation sidelobes for active sensing and communication applications.

  • Method

    The authors develop two majorization-minimization algorithms for WISL, implement them with FFT operations, add acceleration, and extend them to ℓp-norm sidelobe minimization.

  • Results

    The algorithms converge to stationary points and efficiently generate sequences with virtually zero sidelobes in selected lag intervals and smaller PSL for long sequences than Frank and Golomb sequences.

  • Takeaways & Limitations

    FFT-based MM optimization provides a computationally efficient approach to designing unit-modulus sequences with targeted correlation zones and low peak sidelobes.

Abstract

from arXiv · show

Sequences with low aperiodic autocorrelation sidelobes are well known to have extensive applications in active sensing and communication systems. In this paper, we consider the problem of minimizing the weighted integrated sidelobe level (WISL), which can be used to design sequences with impulse-like autocorrelation and zero (or low) correlation zone. Two algorithms based on the general majorization-minimization method are developed to tackle the WISL minimization problem and the convergence to a stationary point is guaranteed. In addition, the proposed algorithms can be implemented via fast Fourier transform (FFT) operations and thus are computationally efficient, and an acceleration scheme has been considered to further accelerate the algorithms. Moreover, the proposed methods are extended to optimize the $\ell_{p}$-norm of the autocorrelation sidelobes, which lead to a way to minimize the peak sidelobe level (PSL) criterion. Numerical experiments show that the proposed algorithms can efficiently generate sequences with virtually zero autocorrelation sidelobes in a specified lag interval and can also produce very long sequences with much smaller PSL compared with some well known analytical sequences.

I. INTRODUCTION

The paper formulates weighted integrated sidelobe level minimization for unit-modulus sequences and develops efficient MM-based algorithms with convergence guarantees.

  • I. INTRODUCTION: Low aperiodic autocorrelation sidelobes support synchronization, channel estimation, sonar, radar, and cryptographic applications.Unit-modulus sequences are especially relevant because of their maximum energy efficiency under hardware amplitude limitations.
  • I. INTRODUCTION: The WISL metric includes ISL minimization and can target zero or low correlation zones through larger weights on selected sidelobes.The sequence design remains subject to unit-modulus constraints.
  • I. INTRODUCTION: Two MM algorithms directly minimize WISL, use FFT operations, converge to stationary points, and can be accelerated.The approach transforms the difficult optimization into simpler majorized problems solved iteratively.
  • I. INTRODUCTION: The paper extends the approach from WISL to the ℓp-norm of autocorrelation sidelobes, providing a route toward PSL minimization.As p tends toward infinity, the ℓp metric approaches the ℓ∞ metric associated with PSL.
  • I. INTRODUCTION: The proposed methods address limitations of WeCAN by directly minimizing WISL rather than an almost equivalent criterion and reducing large-N computational cost.WeCAN requires an N × N matrix square root initially and N FFTs per iteration.

B. WISL Minimization via MM

The first WISL algorithm applies successive majorization steps to obtain a unit-modulus phase update, with FFT-based implementation and monotonic objective decrease.

  • B. WISL Minimization via MM: The MM construction replaces the quadratic WISL objective with an upper-bounding function that coincides with it at the current iterate.A scalar maximum-eigenvalue bound provides a simple majorizer for the first step.
  • B. WISL Minimization via MM: The second majorization reduces the constrained subproblem to minimizing Euclidean distance to an auxiliary vector under unit-modulus constraints.The resulting closed-form update sets each sequence element to the phase of the corresponding auxiliary-vector element.
  • B. WISL Minimization via MM: Autocorrelations and the required Hermitian Toeplitz matrix-vector products are computed through FFT and inverse-FFT operations.A circulant embedding diagonalized by the FFT enables the Toeplitz decomposition.
  • B. WISL Minimization via MM: Each iteration of MWISL is dominated by four FFT or inverse-FFT operations, making the algorithm computationally efficient.The algorithm preserves MM monotonicity while using the FFT-based structure of the problem.

IV. WISL MINIMIZATION WITH AN IMPROVED MAJORIZATION FUNCTION

The improved MM algorithm uses a diagonal majorization function tailored to the problem structure, retaining FFT efficiency while tightening the surrogate construction.

  • IV. WISL MINIMIZATION WITH AN IMPROVED MAJORIZATION FUNCTION: A diagonal majorizer makes the quadratic term constant over the unit-modulus constraint set, removing a higher-order term from the subproblem.This design is intended to produce a tighter majorization function than the simpler scalar-bound construction.
  • IV. WISL MINIMIZATION WITH AN IMPROVED MAJORIZATION FUNCTION: The improved construction selects a diagonal matrix by minimizing the sum of eigenvalues of its difference from the WISL matrix.For the relevant symmetric nonnegative matrix, the diagonal choice is available in closed form.
  • IV. WISL MINIMIZATION WITH AN IMPROVED MAJORIZATION FUNCTION: The diagonal-majorizer design begins from a semidefinite program that has no closed-form solution in general.The paper obtains a closed-form solution here because of the symmetry and nonnegativity of the matrix involved.
  • IV. WISL MINIMIZATION WITH AN IMPROVED MAJORIZATION FUNCTION: Hadamard multiplication with xx^H preserves the eigenvalues of the associated matrix when the sequence has unit-modulus entries.This property supports the eigenvalue bound used in the improved majorization derivation.
  • IV. WISL MINIMIZATION WITH AN IMPROVED MAJORIZATION FUNCTION: The improved algorithm computes its main quantities with FFT operations and requires four FFT or inverse-FFT operations per iteration.Its per-iteration complexity is O(N log N), and a reusable matrix term is computed only once.

A. Convergence Analysis

The proposed MM algorithms generate nonincreasing weighted-ISL objective values bounded below by zero, and every limit point of MWISL is a stationary point.

  • Convergence of objective values: The weighted-ISL objective values generated by MWISL and MWISL-Diag are nonincreasing and converge to a finite value.The lower bound is zero.
  • Stationarity definition: A stationary point is characterized through a first-order optimality condition for minimizing a smooth function over the feasible constraint set.
  • Convergence to stationarity: MM stationarity analysis uses a real-valued reformulation equivalent to the original complex WISL problem under unit-modulus constraints.
  • Convergence to stationarity: Every limit point generated by MWISL is a stationary point of the weighted-ISL minimization problem.
  • Convergence to stationarity: The proof establishes stationarity by showing that a limit point globally minimizes its limiting majorization function and satisfies the first-order condition.

B. Acceleration Scheme

The paper accelerates its MM fixed-point iterations with SQUAREM because successive majorization steps can make convergence slow, while preserving feasibility and monotonicity through projection and backtracking.

  • Acceleration motivation: SQUAREM accelerates MM algorithms by adapting a fixed-point acceleration scheme originally developed for EM algorithms.MM updates are treated as nonlinear fixed-point iterations.
  • Accelerated update: The accelerated scheme projects wayward iterates back onto the feasible region, using element-wise e^jarg(·) for unit-modulus constraints.
  • Monotonicity control: Backtracking maintains the descent property, and only a few backtracking steps are usually needed in practice.
  • Accelerated update: Algorithm 3 applies the acceleration scheme after initializing the iteration index and starting point.

VI. MINIMIZING THE ℓp-NORM OF AUTOCORRELATION SIDELOBES

The paper extends weighted-ISL minimization to ℓp-norm optimization of autocorrelation sidelobes, approaching PSL minimization as p tends to infinity while maintaining unit-modulus sequence constraints.

  • Metric formulation: The unweighted ISL is the squared ℓ2-norm of autocorrelation sidelobes, while the generalized metric uses 2 ≤ p < ∞.
  • Metric formulation: As p → +∞, the ℓp-norm of autocorrelation sidelobes tends to the ℓ∞-norm, known as the peak sidelobe level.
  • Metric formulation: Choosing p = 2 recovers ISL minimization, and weights can be incorporated to form a weighted ℓp-norm objective.
  • MM construction: For p > 2, each |r_k|^p term is locally majorized by a quadratic function because a global quadratic majorization is unavailable.
  • MM construction: The resulting majorized problems retain unit-modulus constraints and are solved through successive majorization steps in closed form at each iteration.
  • Algorithmic procedure: Algorithm 4 summarizes the monotonic minimizer for the ℓp-metric, using normalized weights to avoid numerical issues.

VII. NUMERICAL EXPERIMENTS

The numerical section evaluates the proposed MWISL algorithms and variants against existing methods, using an FFT-oriented implementation on a standard desktop platform.

  • Experimental setup: The experiments compare MWISL and its variants with existing algorithms across sequence-design scenarios.
  • Algorithm evaluated: Algorithm 4 is the monotonic minimizer for the autocorrelation-sidelobe ℓp-metric with p ≥ 2.
  • Algorithm evaluated: The implementation initializes l = 0 and x^(0) before iterating the algorithm.
  • Algorithm evaluated: The algorithm computes λ_L from the maximum of a_k(N − k) over k = 1, …, N − 1.
  • Algorithm evaluated: The iteration forms a vector using autocorrelation-related quantities and normalized weights before updating the sequence.

A. Weighted ISL Minimization

The proposed weighted-ISL algorithms efficiently design length-100 sequences with low correlations at selected lags. They reach a weighted ISL of 10^-10 and suppress required-lag sidelobes to about -160 dB.

  • A. Weighted ISL Minimization: The experiment targets length N = 100 sequences with small correlations at lags 1–20 and 51–70 using weights that select those lags.The design has 99 free phases and matches 80 real correlation components, so the weighted ISL can be driven to 0 in principle.
  • A. Weighted ISL Minimization: All algorithms reach weighted ISL 10^-10 when enough iterations are allowed, but the proposed algorithms require far fewer iterations than WeCAN.The accelerated variants are especially efficient, and MWISL-Diag converges somewhat faster than the corresponding MWISL method.
  • A. Weighted ISL Minimization: Accelerated MWISL and MWISL-Diag take 0.07 and 0.06 seconds, respectively, whereas WeCAN takes more than 1000 seconds.The proposed methods use four FFT operations per iteration; WeCAN uses N computations of 2N-point FFTs per iteration.
  • A. Weighted ISL Minimization: The accelerated MWISL-Diag sequence suppresses autocorrelation sidelobes to about -160 dB at the required lags.The corresponding correlation level is shown for the length-100 sequence designed with the selected weights.
  • A. Weighted ISL Minimization: Figures 1 and 2 track weighted ISL against iterations and elapsed time, while Figure 3 reports correlation level for the accelerated MWISL-Diag output.The time plot includes a zoomed view of the interval [0, 10] seconds.

B. PSL Minimization

The paper extends its MM framework to PSL minimization through ℓp-norm optimization of autocorrelation sidelobes. Smaller p values converge faster initially, while increasing p can produce lower final PSL and outperform Frank and Golomb sequences.

  • B. PSL Minimization: The accelerated ℓp-based algorithm evaluates PSL evolution for p values after 5×10^4 iterations.The experiment examines how the choice of p affects convergence and final peak sidelobe levels.
  • B. PSL Minimization: Smaller p values converge faster, but p = 100 ultimately gives lower PSL than p = 10.Larger p values approximate the ℓ∞-norm more closely, motivating a gradually increasing p strategy.
  • B. PSL Minimization: Figure 4 shows the evolution curves of the peak sidelobe level for the tested p settings.The curves support comparison of convergence speed and later-stage PSL behavior across p values.

VIII. CONCLUSION

The paper develops FFT-efficient algorithms for WISL and ℓp-norm sidelobe minimization, with convergence to stationary points and strong numerical performance on long sequences.

  • VIII. CONCLUSION: The algorithms minimize WISL for unit-modulus sequences and extend to minimizing the ℓp-norm of autocorrelation sidelobes.The extension provides a route toward minimizing the peak sidelobe level criterion.
  • VIII. CONCLUSION: FFT implementation makes all proposed algorithms computationally efficient, and an acceleration scheme further speeds them up.
  • VIII. CONCLUSION: The WISL algorithms generate sequences with virtually zero autocorrelation sidelobes in specified lag intervals at lower computational cost than the state-of-the-art.
  • VIII. CONCLUSION: The ℓp-metric algorithm produces long sequences with more uniform autocorrelation sidelobes and smaller PSL than Frank and Golomb sequences.

APPENDIX A PROOF OF LEMMA 10

The appendix proves the majorization lemma by constructing a quadratic upper bound and showing its auxiliary difference is increasing over the relevant interval.

  • APPENDIX A PROOF OF LEMMA 10: A quadratic function g(x|x0) is constructed to majorize f(x) at a given point x0.The construction requires equality at x0 and an upper-bound condition elsewhere on [0, t].
  • APPENDIX A PROOF OF LEMMA 10: The proof reduces the majorization condition to verifying nonnegativity of an auxiliary function A(x|x0).
  • APPENDIX A PROOF OF LEMMA 10: Because A(x|x0) is increasing, its maximum occurs at x = t, determining the smallest admissible quadratic coefficient.
  • APPENDIX A PROOF OF LEMMA 10: Substituting this coefficient into g(x|x0) and rearranging yields the majorization function used in the paper.
Loading 1506.04234v1…