PaperlayerView exact revision on arXiv

Source-linked AI summary

Optimization Methods for Designing Sequences with Low Autocorrelation Sidelobes

Junxiao Song, Prabhu Babu, Daniel P. Palomar

arXiv:1501.02252v1math.OCcs.ITstat.ME

TL;DR

Low-autocorrelation unimodular sequences are important for radar and CDMA, but direct ISL minimization is difficult. The paper develops MISL, an MM-based algorithm with FFT implementation, acceleration schemes, and a spectral-constraint variant. The proposed methods are reported to improve sequence quality and computational efficiency over existing algorithms.

  • Problem

    The paper addresses efficient design of unimodular sequences with low autocorrelation sidelobes, a property used in radar detection and CDMA synchronization.

  • Method

    MISL applies majorization-minimization to directly minimize ISL, with FFT implementation, acceleration schemes, and a spectral-MISL extension for spectral constraints.

  • Results

    Numerical results report larger merit factors than CAN for aperiodic autocorrelations, virtually zero periodic sidelobes, and low sidelobes with suppressed power in arbitrary frequency bands.

  • Takeaways & Limitations

    The proposed algorithms provide computationally efficient unimodular sequence design that can simultaneously address autocorrelation and spectral requirements.

Abstract

from arXiv · show

Unimodular sequences with low autocorrelations are desired in many applications, especially in the area of radar and code-division multiple access (CDMA). In this paper, we propose a new algorithm to design unimodular sequences with low integrated sidelobe level (ISL), which is a widely used measure of the goodness of a sequence's correlation property. The algorithm falls into the general framework of majorization-minimization (MM) algorithms and thus shares the monotonic property of such algorithms. In addition, the algorithm can be implemented via fast Fourier transform (FFT) operations and thus is computationally efficient. Furthermore, after some modifications the algorithm can be adapted to incorporate spectral constraints, which makes the design more flexible. Numerical experiments show that the proposed algorithms outperform existing algorithms in terms of both the quality of designed sequences and the computational complexity.

I. INTRODUCTION

The paper formulates unimodular sequence design as minimizing integrated sidelobe level for aperiodic or periodic autocorrelations, motivated by radar and CDMA applications. It introduces MISL, an efficient MM-based approach that directly targets this objective under unit-modulus constraints.

  • Low autocorrelation sidelobes support weak-target detection in radar and synchronization in CDMA systems.
  • The design variable is a complex unimodular sequence whose aperiodic or periodic autocorrelation sidelobes should be minimized.
  • ISL measures aperiodic autocorrelation sidelobe energy, while periodic ISL is defined similarly and relates closely to merit factor.
  • The paper develops MISL to directly minimize both aperiodic and periodic ISL monotonically using majorization-minimization.
  • The formulation imposes |x_n| = 1 for every sequence element while minimizing the selected autocorrelation ISL.
  • The optimization is difficult because its objective is quartic and its unit-modulus constraints are nonconvex.

B. The Periodic Autocorrelation

The paper reviews frequency-domain formulations and existing CAN-type methods for periodic and aperiodic ISL design. These methods are FFT-efficient but may optimize surrogate criteria rather than the original ISL problem, motivating direct minimization.

  • B. The Periodic Autocorrelation: Periodic ISL minimization can be rewritten in the frequency domain using periodic steering vectors and unit-modulus constraints.
  • B. The Periodic Autocorrelation: For periodic autocorrelations, unimodular sequences with zero ISL exist for every length N, unlike exact impulse-like aperiodic autocorrelations.
  • B. The Periodic Autocorrelation: CAN’s surrogate is not exactly equivalent to the original ISL problem, so its limit point need not be a local minimum or stationary point of that problem.
  • B. The Periodic Autocorrelation: CAN and PeCAN use criteria related to ISL, and PeCAN can numerically generate almost perfect periodic sequences from random initializations.
  • B. The Periodic Autocorrelation: Because the surrogate approaches can differ from direct ISL minimization, the paper seeks an equally efficient algorithm that minimizes the original metric.

III. ISL MINIMIZATION VIA MAJORIZATION-MINIMIZATION

The MM framework replaces a difficult objective with iteratively minimized majorizing functions that touch the objective at the current iterate. This construction yields monotonic objective decrease and a stable optimization procedure.

  • A. The MM Method: MM transforms a difficult optimization problem into a sequence of simpler problems using objective functions that majorize the original function.
  • A. The MM Method: A majorization function upper-bounds the objective over the feasible set and coincides with it at the current iterate.
  • A. The MM Method: Each MM iteration finds a feasible starting point, constructs a majorizer, minimizes it, and repeats until a convergence criterion is met.
  • A. The MM Method: The objective value decreases monotonically at every iteration according to f(x^(k+1)) ≤ f(x^(k)).
  • A. The MM Method: This monotonicity is identified as making MM algorithms very stable in practice.

B. MISL

MISL applies majorization-minimization twice to the ISL problem, producing a closed-form unimodular update that preserves monotonicity and extends to periodic autocorrelations.

  • Derivation: MISL constructs a majorization function for the quartic ISL objective and then applies majorization-minimization again under unit-modulus constraints.The first reformulation makes the objective quadratic, while the second yields a tractable constrained problem.
  • Alternative approach: An SDP relaxation is possible, but its tightness is unproved and solving it at every iteration is computationally unsuitable for large N.The paper instead uses the second majorization to obtain a simple algorithm.
  • Closed-form update: The second majorization reduces each iteration to minimizing a squared Euclidean distance over the unit-modulus constraint set.This constrained subproblem has a closed-form solution obtained element-wise.
  • Properties and scope: MISL preserves the MM algorithm’s monotonicity and is named the Monotonic minimizer for Integrated Sidelobe Level.The derivation can also be adapted to periodic autocorrelation by replacing the aperiodic matrix with its periodic counterpart.

C. Convergence Analysis

The convergence analysis shows that MISL’s objective values decrease monotonically to a finite limit, and every limit point of its iterates is a stationary point.

  • Objective convergence: The sequence of MISL objective values is nonincreasing and bounded below by 0, so it converges to a finite value.This follows from the MM descent relation.
  • Optimality condition: A stationary point is defined through the first-order optimality condition for minimizing a smooth function over the constraint set.The analysis uses this condition after establishing that a limit point minimizes the corresponding majorization function.
  • Stationary-point convergence: Every limit point of the sequence generated by MISL is a stationary point of the constrained ISL problem.The proof converts the complex problem to an equivalent real formulation and applies a first-order optimality condition.

D. Computational Complexity of MISL

MISL’s dominant matrix-vector products can be implemented with FFT and IFFT operations, making the algorithm computationally efficient for very long sequences.

  • Aperiodic implementation: MISL’s per-iteration cost is dominated by two matrix-vector multiplications involving A.These products are computed using FFT operations on zero-padded vectors and inverse FFT operations followed by truncation.
  • Periodic implementation: In the periodic case, multiplication by ˆA^H and ˆA is exactly an FFT and IFFT of the vector.The periodic matrix ˆA^H is the N × N DFT matrix.
  • Scalability: N ∼ 10^6 is identified as a sequence length for which MISL can be used.The FFT/IFFT implementation is cited as the basis for this efficiency.

IV. ACCELERATION SCHEMES

The paper accelerates MISL with fixed-point and backtracking strategies because double majorization can make convergence slow, especially for large N.

  • Motivation: For large N, MISL can converge very slowly, possibly because double majorization produces a loose approximation of the original objective.This motivates acceleration schemes that improve the iteration process or the objective approximation.
  • Fixed-point acceleration: SQUAREM accelerates MISL by treating its MM update as a nonlinear fixed-point iteration and applying an off-the-shelf fixed-point accelerator.The accelerated algorithm projects wayward points back to the feasible unit-modulus region.
  • Algorithmic safeguard: The accelerated-MISL procedure uses a backtracking loop that reduces the step parameter until ISL descent is restored.The algorithm includes initialization, fixed-point updates, step-length computation, and an ISL-based acceptance test.
  • Backtracking acceleration: Backtracking-MISL chooses the smallest L satisfying the descent condition, ensuring monotonicity even though the resulting function is not guaranteed to be a global upper bound.The method searches L over a prescribed sequence at each iteration.

V. ISL MINIMIZATION WITH SPECTRAL CONSTRAINTS

The paper adapts MISL to minimize ISL while enforcing spectral-power constraints, producing the spectral-MISL algorithm. The derivation preserves the unimodular sequence constraint and can use the same acceleration schemes as MISL.

  • V. ISL MINIMIZATION WITH SPECTRAL CONSTRAINTS: Spectral-MISL is listed as Algorithm 5, while Algorithm 4 provides a backtracking-MISL procedure used in the surrounding development.The section states that the resulting spectral-MISL algorithm follows the same derivation framework as MISL.
  • V. ISL MINIMIZATION WITH SPECTRAL CONSTRAINTS: Spectral-MISL adapts MISL to design sequences with low autocorrelation sidelobes and suppressed spectral power in specified frequency bands.The method addresses applications where correlation quality and spectral constraints must be satisfied simultaneously.
  • V. ISL MINIMIZATION WITH SPECTRAL CONSTRAINTS: Spectral constraints require power over an index set Ω to remain below a prescribed threshold, while the sequence remains unimodular.The constrained formulation uses |x_n| = 1 for n = 1, . . . , N.
  • V. ISL MINIMIZATION WITH SPECTRAL CONSTRAINTS: For a given threshold ǫ > 0, a parameter λ transforms the constrained ISL problem into an equivalent penalized problem.This parameter controls the tradeoff between correlation minimization and spectral-power restriction.
  • V. ISL MINIMIZATION WITH SPECTRAL CONSTRAINTS: The spectral-MISL derivation follows MISL’s majorization steps and yields an algorithm with the same problem form as the earlier MISL update.The acceleration schemes described for MISL can also be applied to spectral-MISL.

VI. NUMERICAL EXPERIMENTS

The numerical experiments compare the proposed MISL algorithms with existing methods to evaluate sequence quality and computational performance across the paper’s design settings.

  • VI. NUMERICAL EXPERIMENTS: Experiments compare the proposed MISL algorithms with existing methods to assess their performance in sequence design.All experiments were performed on a PC with a 3.20GHz i5-3470 CPU and 8GB RAM.

A. ISL Minimization

The experiments evaluate MISL and accelerated-MISL against CAN for aperiodic design, examine convergence and periodic autocorrelation, and test spectral-MISL under frequency-band constraints. The reported results show stronger merit factors, lower running times for the accelerated method, near-zero periodic sidelobes, and simultaneous spectral suppression with low autocorrelation sidelobes.

  • A. ISL Minimization: MISL experiments compare unimodular-sequence quality and efficiency with the computationally efficient CAN algorithm.Quality is measured using merit factor, where larger values are better.
  • A. ISL Minimization: The proposed backtracking-MISL and accelerated-MISL algorithms generate consistently larger MF than CAN across tested sequence lengths.Each algorithm was repeated 100 times for lengths N = 25, 26, . . . , 2^13.
  • A. ISL Minimization: Accelerated-MISL is faster than CAN across the tested lengths, especially for longer sequences.The average running times are reported from the same 100-trial experiment.
  • A. ISL Minimization: When initialized with accelerated-MISL output, CAN increases ISL, whereas MISL retains monotonic behavior; different initializations can lead to different convergence points.The comparison uses two random trials with N = 32.
  • A. ISL Minimization: For periodic autocorrelation, accelerated-MISL produces correlation levels lower than -200dB at nonzero lags for sequences of lengths N = 256 and N = 1024.The paper notes that exact zero-ISL periodic sequences exist for any length N.
  • A. ISL Minimization: For N = 1000 and λ = 10^4, spectral-MISL suppresses power in specified frequency bands while maintaining low autocorrelation sidelobes.The frequency-band index set Ω is selected to represent the prescribed bands, and λ adjusts the tradeoff.
  • A. ISL Minimization: The conclusion reports that MISL converges to a stationary point, while all proposed algorithms can be implemented with FFT operations for computational efficiency.The conclusion also reports larger MF than the state-of-the-art method for aperiodic autocorrelations.

APPENDIX

The appendix establishes structural properties of the matrix Φ and proves its largest eigenvalue through a nonnegative quadratic-form argument with attainable equality.

  • Φ is a real matrix.
  • The proof establishes λmax(Φ) = 2N^2 by showing the associated quadratic form is nonnegative for every real x.
  • Equality in the quadratic-form bound is attainable for nonzero vectors with the specified index structure.
Loading 1501.02252v1…