PaperlayerView exact revision on arXiv

Source-linked AI summary

A Coordinate-Descent Framework to Design Low PSL/ISL Sequences

M. Alaee, A. Aubry, A. De Maio, M. M. Naghsh, M. Modarres-Hashemi

arXiv:1612.05880v1cs.IT

TL;DR

The paper asks how to design phase sequences with low aperiodic PSL and ISL under continuous or discrete phase constraints. It formulates the task as Pareto optimization and solves it with coordinate descent, using bisection or FFT-based subproblem methods. The proposed procedures outperform some literature counterparts, with gains increasing as the constellation size decreases.

  • Problem

    The paper addresses the difficult design of unimodular phase sequences that jointly achieve low aperiodic PSL and ISL under continuous or discrete phase constraints.

  • Method

    A coordinate-descent framework solves scalarized non-convex problems, using global bisection for continuous phases, FFT-based updates for discrete phases, and lp-norm heuristic initialization.

  • Results

    The synthesized sequences provide better PSL and ISL than some open-literature counterparts, with larger gains as constellation size decreases.

  • Takeaways & Limitations

    The framework is especially effective for discrete-phase and binary sequence design, where it can outperform existing methods.

Abstract

from arXiv · show

This paper is focused on the design of phase sequences with good (aperiodic) autocorrelation properties in terms of Peak Sidelobe Level (PSL) and Integrated Sidelobe Level (ISL). The problem is formulated as a bi-objective Pareto optimization forcing either a continuous or a discrete phase constraint at the design stage. An iterative procedure based on the coordinate descent method is introduced to deal with the resulting optimization problems which are non-convex and NP-hard in general. Each iteration of the devised method requires the solution of a non-convex min-max problem. It is handled either through a novel bisection or an FFT-based method for the continuous and the discrete phase constraint, respectively. Additionally, a heuristic approach to initialize the procedures employing the lp-norm minimization technique is proposed. Simulation results illustrate that the proposed methodologies can outperform some counterparts providing sequences with good autocorrelation features especially in the discrete phase/binary case.

I. INTRODUCTION

The paper targets phase-coded sequences with low aperiodic PSL and ISL under continuous or discrete phase constraints. It addresses the resulting Pareto optimization and proposes coordinate-descent procedures for both settings.

  • I. INTRODUCTION: Low correlation sidelobes support synchronization, reduce multi-access interference, prevent weak-target masking, and mitigate distributed clutter in communication and radar systems.PSL is emphasized for range compression, while ISL addresses clutter near the target of interest.
  • I. INTRODUCTION: Fixed conventional waveforms offer easy generation and possible Doppler tolerance but can limit adaptivity and increase vulnerability to electronic attacks.This motivates designing multiple adaptable phase-coded waveforms.
  • A. Background and Previous Works: Binary phase waveforms are simple to implement, but Barker codes stop at length 13 and several established sequence families lack aperiodic-sidelobe guarantees.Aperiodic correlation design is generally harder than periodic correlation design.
  • A. Background and Previous Works: Prior methods include ITROX, simulated-annealing heuristics, cyclic ISL algorithms, and majorization-minimization, but discrete-phase and exact PSL design remain difficult.Generalized Barker codes from prior heuristics are reported only up to length 77, while some cyclic methods optimize ISL approximations or locally optimize ISL.
  • II. PROBLEM FORMULATION: The paper formulates simultaneous PSL and ISL minimization as a bi-objective Pareto problem for unimodular sequences with continuous or finite phase alphabets.Scalarization uses a weighted sum of the two metrics, and a Pareto solution is sought because simultaneous minimization may not exist.
  • B. Contribution and Organization: Its coordinate-descent framework optimizes one code entry at a time, using bisection for continuous phases, FFT-based updates for discrete phases, and lp-norm initialization.The framework targets non-convex, generally NP-hard scalarized problems; the weighted objective decreases under the stated convergence rule and has polynomial per-iteration complexity.

III. CD CODE OPTIMIZATION

The paper applies coordinate descent to optimize the phase-code objective one code entry at a time. The resulting iterative procedure generates successive radar codes and has convergence support through monotonic objective decrease and, with MBI updating, stationary-point guarantees.

  • Coordinate descent minimizes the multivariable objective along one code-entry direction at a time, producing univariate optimization problems in a loop.At each iteration, one code entry is selected while the remaining entries are fixed.
  • Starting from an initial code x(0), the procedure iteratively produces a sequence of radar codes x(1), x(2), x(3), … until its stopping condition is met.The algorithm cycles through code entries and stops when the objective improvement falls below ε.
  • Monotonic objective behavior and a lower bound ensure convergence of the objective values, while MBI updating can ensure convergence to a stationary point.The paper distinguishes objective-value convergence from the stronger stationary-point guarantee associated with MBI.
  • The scalarized objective combines ISL- and PSL-based metrics through a Pareto weight θ, with different weights corresponding to Pareto-optimal solutions.Scalarization uses a convex combination of the original figures of merit.
  • Each coordinate update leads to a constrained, non-convex min-max problem with a non-homogeneous quadratic objective in one complex variable.The paper identifies solving these subproblems as its main optimization-theory challenge.

A. Continuous Phase Code Design

For continuous phase design, each coordinate subproblem is transformed into a feasibility problem and solved globally through bisection. The method exploits quartic-polynomial structure to perform feasibility checks and has polynomial computational complexity.

  • The squared autocorrelation magnitude as a function of one phase entry can be represented as a ratio of two quartic functions of a real variable.The phase entry is parameterized as xd = e^jφd with φd ∈ [0, 2π].
  • Bisection tests whether the optimal min-max value is below a candidate γ̄ by solving a corresponding feasibility problem.A feasible test implies an objective value no greater than γ̄, while infeasibility indicates that the optimum exceeds γ̄.
  • Each bisection step halves the current uncertainty interval, and the procedure terminates when its width is at most the prescribed accuracy ε1.The initial interval is bounded by w(0) = 0 and u(0) = fθ(x(n)).
  • Feasibility checking reduces to finding roots of quartic polynomials and checking gaps in unions of resulting intervals.The real roots can be obtained in closed form using Cardano’s procedure.
  • The overall continuous-phase optimization has complexity O(KN log2(N)), where K is the number of bisection iterations.The interval-root processing contributes O(N log2(N)) per feasibility evaluation.

B. Discrete Phase Code Design

For discrete phase design, the coordinate update evaluates candidate constellation phases efficiently using discrete Fourier transforms. A binary specialization reduces the representation to real coefficients, while quantizing a continuous solution is not generally sufficient.

  • The discrete coordinate subproblem is reformulated in terms of the phase φd = arg(xd) and solved using the Discrete Fourier Transform.The optimal phase is selected from the finite constellation by comparing the resulting candidate objectives.
  • For M ≥ 3, squared autocorrelation magnitudes across the discrete phase candidates are obtained elementwise from the M-point DFT of a coefficient vector ζdk.The vector contains the coordinate-dependent coefficients used by the lemma underlying the update.
  • Quantizing a good continuous-phase sequence does not generally guarantee a good discrete-phase sequence.Discrete design therefore requires its own optimization procedure rather than simple post-design quantization.
  • The binary case restricts the phase to {0, π}, allowing the coordinate-dependent coefficient vector to be represented using two real components.This requires a slight modification of the general discrete-phase update.
  • The discrete algorithm evaluates N − 1 different M-point DFTs, each computable with an FFT, giving complexity O(NM log2 M).The stated complexity applies to the discrete phase-entry optimization procedure.

C. lp-norm Minimization for Algorithm Initialization

Because coordinate-descent solutions depend on their initial sequence, the paper proposes lp-norm minimization to generate higher-quality starting points. Increasing p provides a controllable trade-off between ISL and PSL, with PSL reached as p tends to infinity.

  • The optimized sequence depends on the initial sequence, motivating a heuristic procedure for producing high-quality starting points.Initialization is treated as valuable because different starts can affect the obtained solution.
  • Minimizing the autocorrelation vector’s lp-norm trades off ISL and PSL as p increases.The procedure is designed to obtain phase-only codes with low autocorrelation lp-norm.
  • The PSL equals the limit of the autocorrelation vector lp-norm as p approaches infinity.This motivates using lp-norm minimization as an initialization strategy for PSL-oriented design.
  • The initialization framework applies coordinate-wise surrogate optimization to the H∞,p and HM,p problems.Each variable block corresponds to one code entry.

1) Starting Point for the Continuous Phase Code Design:

The continuous-phase design starting point is formulated through quartic-function lemmas and a resulting non-convex optimization problem. These steps support an efficient solution procedure for the continuous-phase case.

  • Continuous-phase formulation: Lemma III.1 recasts d,x(n) as a ratio of two quartic polynomials.The reformulation supplies the polynomial structure used in the subsequent optimization analysis.
  • Continuous-phase formulation: The derivation invokes additional lemmas and equations to construct Problem H∞,p.The cited development combines Lemmas III.1 and III.3 with equations (15) and (14).
  • Continuous-phase solution: βd,eγ can be efficiently solved using a simplified version of Algorithm 2 for a single fractional quartic function.The simplification follows from the special form of the associated objective.
  • Discrete-phase counterpart: The discrete phase code design problem is cast explicitly before applying the discrete optimization construction.This establishes the counterpart formulation for phase values restricted to a finite alphabet.

2) Starting Point for Discrete Phase Code Design:

The proposed methods are evaluated against established algorithms for PSL and ISL design under continuous and discrete phase constraints. Results emphasize strong discrete-phase performance, particularly for binary sequences.

  • Experimental setup: CPM and DPM denote the continuous and discrete phase methods derived from Algorithm 1, with heuristic initialization used unless otherwise stated.CPM solves P ∞,θ through Algorithm 2, while DPM solves P M,θ through Algorithm 3.
  • Experimental setup: All algorithms use common starting codes and terminate when |obj(x(n)) −obj(x(n−1))| ≤10^-5.The comparison includes Golomb and Frank codes plus five random sequences, unless a different initialization is specified.
  • PSL minimization: For N = 400, CPM outperforms CAN, CAN(D), MM-PSL, and DPM in PSL as constellation size varies.DPM outperforms CAN(D) and surpasses CAN and MM-PSL when the alphabet is sufficiently dense.
  • PSL minimization: DPM’s PSL approaches CPM’s lower bound as M increases, while smaller alphabets converge faster but obtain worse PSL.The convergence comparison is reported for M = 64 and M = 256 after heuristic initialization.
  • Discrete PSL comparison: DPM exceeds CAN(D) by maximum gains of 3.98 dB, 1.47 dB, and 1.65 dB for M = 2, M = 8, and M = 16, respectively.The comparison uses the same five uniformly drawn random initial sequences for each alphabet size.
  • Binary PSL performance: For binary sequences, DPM significantly outperforms ITROX and approaches the global optimum of MPS sequences with lower computational complexity and no maximum code-length restriction.DPM sometimes coincides with the MPS optimum.
  • Binary PSL performance: At sequence length 126, DPM achieves PSL 8, while the genetic-algorithm result reported in is PSL 11.Only 10% of DPM trials are higher than or equal to 11, and 4% reach PSL 8.

B. ISL Minimization

For ISL minimization, DPM is evaluated against continuous- and discrete-phase counterparts across constellation sizes and sequence lengths. The results show especially large gains for discrete and binary phase codes, while θ controls the PSL–ISL trade-off.

  • ISL versus constellation size: At N = 400, continuous-phase strategies have nearly identical ISL performance, whereas DPM requires a smaller constellation than CAN(D) for the same ISL.The comparison includes DPM, CAN(D), CAN, WISL-Diag, and CPM.
  • ISL versus sequence length: For N-dependent ISL comparisons, Figs. 7(a)–(c) evaluate M = 2, M = 8, and M = 16 using five random starting sequences.The best resulting code is selected for each case.
  • ISL versus constellation size: DPM outperforms CAN(D) in ISL minimization, with the largest reported gain for binary phase codes.The maximum gains are 5.99 dB for M = 2, 1.73 dB for M = 8, and 1.4 dB for M = 16.
  • Pareto trade-off: The Pareto weight θ trades PSL against ISL: increasing θ improves PSL while worsening ISL.The Pareto curves compare CPM and DPM for M = 64 and M = 256 with N = 400.
  • Overall findings: The proposed coordinate-descent procedures design constant-modulus sequences with improved autocorrelation properties relative to some literature counterparts, with larger gains at smaller constellation sizes.The framework handles continuous and discrete phase constraints and includes binary synthesis.

APPENDIX A PROOF OF LEMMA III.1

The appendix uses trigonometric relationships and algebraic transformations to recast the relevant expressions in a form suitable for the lemma’s proof.

  • Transformation: The proof applies trigonometric relationships to transform the expression involving the phase variable.The transformed form follows from the stated trigonometric identities.
  • Algebraic recasting: Standard algebra is then used to recast the resulting expression into the required form.A similar procedure is applied to Bdk.

APPENDIX B DERIVATION OF THE FEASIBILITY SET

The feasibility-set derivation analyzes a quartic polynomial through its real roots and derivative behavior, then combines the resulting intervals using a union procedure.

  • Quartic representation: The polynomial is represented as a quartic ¯p(x) = ax4 + bx3 + cx2 + dx + e over real coefficients.The coefficient vector is required to be nonzero.
  • Root analysis: The procedure first finds and orders the distinct real roots of ¯p(x), whose number satisfies L ≤ 4.If there are no roots, the constant term determines the immediate exit condition.
  • Interval construction: Derivative signs determine which intervals around each root belong to the feasibility set.Positive, negative, and stationary derivative cases update Ak differently; second- and fourth-order derivatives classify stationary points.
  • Set union: A union-find procedure merges the interval sets and identifies disjoint portions of the resulting feasibility set.Sorted lower and upper endpoints are scanned with a counter to detect completed unions.
  • Interval construction: The construction includes intervals extending beyond the first and last roots, with x0 = −∞ and xL+1 = +∞.These boundary conventions support the interval updates at the ends of the real line.

APPENDIX C PROOF OF LEMMA III.2

The appendix derives an equivalent transformed expression using a phase substitution and explicitly defined real and imaginary components.

  • Magnitude relation: The resulting expression preserves magnitude under multiplication by the unit-modulus factor e−jφ̄m.Equation (48) uses |e−jφ̄m| = 1 in the magnitude relation.
  • Variable substitution: The derivation uses cos(φd) as a change of variable to reformulate the phase-dependent expression.This substitution is introduced by reference to Appendix A.
  • Coefficient definitions: The transformed terms are expressed through real-valued combinations of the real and imaginary parts of adk, bdk, and cdk.The definitions of eµdk, eκdk, eξdk, eηdk, and eρdk collect these components.
Loading 1612.05880v1…