PaperlayerView exact revision on arXiv

Source-linked AI summary

Sequence Set Design With Good Correlation Properties via Majorization-Minimization

Junxiao Song, Prabhu Babu, Daniel P. Palomar

arXiv:1510.01899v1math.OC

TL;DR

The paper addresses the design of sequence sets with complementary or jointly good auto- and cross-correlation properties for sensing and communication systems. It formulates these tasks as optimization problems and develops FFT-implementable majorization-minimization algorithms. The algorithms converge to stationary points, are computationally efficient, and numerical experiments report near-lower-bound correlation performance and near-zero sidelobes in a zero-correlation-zone example.

  • Problem

    The paper asks how to design sequence sets with complementary autocorrelations or with both good auto- and cross-correlations, properties needed in active sensing and communication systems.

  • Method

    The paper formulates sequence-set design as unimodular optimization and develops algorithms based on successive majorization-minimization, with FFT implementations and an acceleration scheme.

  • Results

    The algorithms converge to stationary points; numerical experiments produce almost complementary sets and correlation performance close to the lower bound, with about -175 dB sidelobes in one zero-correlation-zone example.

  • Takeaways & Limitations

    FFT-based MM algorithms provide computationally efficient sequence-set design for very long sequences while addressing complementary and joint auto-/cross-correlation objectives.

Abstract

from arXiv · show

Sets of sequences with good correlation properties are desired in many active sensing and communication systems, e.g., multiple-input-multiple-output (MIMO) radar systems and code-division multiple-access (CDMA) cellular systems. In this paper, we consider the problems of designing complementary sets of sequences (CSS) and also sequence sets with both good auto- and cross-correlation properties. Algorithms based on the general majorization-minimization method are developed to tackle the optimization problems arising from the sequence set design problems. All the proposed algorithms can be implemented by means of the fast Fourier transform (FFT) and thus are computationally efficient and capable of designing sets of very long sequences. A number of numerical examples are provided to demonstrate the performance of the proposed algorithms.

I. INTRODUCTION

The paper formulates complementary-set and joint auto-/cross-correlation sequence design as optimization problems, then develops efficient MM algorithms implemented with FFT. These designs target sensing and communication settings where correlation properties support signal or user separation.

  • CSS Motivation: CSS design is motivated by the fact that a unimodular sequence has an autocorrelation sidelobe of 1 at lag N −1 regardless of its design.Complementary sets address this difficulty by combining sequence autocorrelations.
  • Motivation: Good autocorrelation and cross-correlation properties are important for active sensing and communication systems, including CDMA and MIMO radar.Autocorrelation concerns shifted versions of one sequence, while cross-correlation concerns shifted versions of different sequences.
  • Problem Scope: The paper designs complementary sets of sequences and sequence sets with both good auto- and cross-correlation properties.Its sequence-set formulations include single-sequence design problems as special cases.
  • Algorithms: The proposed algorithms successively majorize objective functions twice within the general MM framework and can be implemented using FFT operations.The paper also discusses convergence properties and an acceleration scheme, while prior CAN and WeCAN methods solved related formulations through almost-equivalent problems.
  • CSS Formulation: If the CSS optimization objective reaches zero, the resulting set is complementary; otherwise, the formulation can seek almost complementary sets when exact CSS does not exist.The optimization imposes unimodular constraints on every sequence element.
  • Correlation Criteria: The auto-/cross-correlation criterion cannot be made arbitrarily small because it is lower bounded by N 2M(M −1).The paper therefore introduces a weighted formulation that can emphasize selected time-lag intervals.

C. The MM Method

The paper uses majorization-minimization to replace difficult sequence-design objectives with successively simpler upper-bounded problems. The resulting updates support unimodular sequence constraints and FFT-based implementation for complementary-set design.

  • MM principle: The MM method transforms a difficult optimization problem into a sequence of simpler problems by minimizing majorizing surrogate functions.Each surrogate upper-bounds the original objective over the constraint set and equals it at the current iterate.
  • MM principle: The MM update makes the objective value nonincreasing at every iteration.The inequality chain follows from surrogate majorization, tangency, and minimization of the surrogate.
  • CSS formulation: For complementary-set design, the sequences are stacked into an auxiliary sequence whose autocorrelations represent the set's complementary structure.The reformulation uses Toeplitz shift matrices and imposes unit-modulus constraints on the original sequences.
  • CSS algorithm: Two successive majorization steps convert the CSS objective into a tractable update under the unimodular constraints.The second step uses an eigenvalue bound and the resulting elementwise problem has a closed-form phase update.
  • Implementation: The CSS algorithm can be implemented with FFT or inverse FFT operations because the relevant matrices have Hermitian Toeplitz structure.The Toeplitz decomposition enables fast matrix-vector products within each iteration.

IV. DESIGN OF SEQUENCE SET WITH GOOD AUTO- AND CROSS-CORRELATION PROPERTIES VIA MM

This section develops a weighted MM algorithm for sequence sets with good auto- and cross-correlation properties. It uses matrix reformulations, successive majorization, computable spectral bounds, and FFT-based products to obtain efficient unit-modulus updates.

  • Problem formulation: The weighted design problem jointly controls auto- and cross-correlations while allowing different weights for different lags.The formulation constrains every sequence entry to unit modulus.
  • Matrix reformulation: Stacking all sequences into one vector enables the correlation objective to be expressed through structured matrix operations.The construction uses Toeplitz matrices and Kronecker-product eigenvalue relations.
  • MM derivation: The algorithm applies two majorization steps, replacing the original objective first with a quadratic surrogate and then with a separable unit-modulus problem.A computable upper bound on the largest eigenvalue is used instead of repeatedly calculating it exactly.
  • MM update: The separable surrogate has an elementwise phase solution, updating each sequence entry from the argument of an intermediate quantity.The update is performed after computing the surrogate's intermediate vector.
  • Implementation: The weighted algorithm requires about 3M^2+4M+3 2N-point FFT (IFFT) operations per iteration and has complexity O(M^2N log N).Toeplitz block structure supports efficient matrix-vector multiplication and norm computation.

V. SIMPLIFIED MM FOR THE CASE WITHOUT WEIGHTS

Without lag weights, the paper derives a simplified MM algorithm for the auto- and cross-correlation objective. The simplification reduces the per-iteration FFT workload while retaining unit-modulus sequence updates.

  • Unweighted formulation: The unweighted problem is obtained from the weighted formulation by choosing equal weights for the considered correlation lags.The resulting algorithm targets sequence sets with both good auto- and cross-correlation properties.
  • Objective reformulation: The simplified derivation rewrites the objective using sequence covariance matrices at each lag.These covariance matrices organize the auto- and cross-correlation terms across sequence pairs.
  • MM derivation: Successive majorization converts the quartic and quadratic terms into a separable surrogate over the unit-modulus entries of the sequence matrix.The construction uses a quadratic upper bound for the first term and Cauchy-Schwarz-based majorization for the second.
  • MM update: The resulting elementwise update sets each entry to the unit-modulus phase of the negative intermediate matrix value.The update is X_i,j = e^jarg(-Y_i,j).
  • Implementation: 2M 2N-point FFT (IFFT) operations are needed at each iteration of the simplified algorithm.The matrix Y is computed efficiently through FFT-based reformulations.

A. Convergence Analysis

The proposed MM algorithms generate nonincreasing objective sequences bounded below by zero, so their objective values converge to finite limits. Their iterate sequences have stationary-point convergence guarantees.

  • Objective convergence: The objective values produced by the MM algorithms are nonincreasing at every iteration.This follows from the general MM construction.
  • Objective convergence: Because the objectives are bounded below by 0, the objective-value sequences converge to finite values.The statement applies to problems (4), (7), and (8).
  • Stationary-point convergence: The CSS algorithm's iterate sequence has at least one limit point, and every limit point is stationary for problem (4).The result concerns the sequence generated by Algorithm 1.
  • Stationary-point convergence: The sequences generated by Algorithms 2 and 3 converge to stationary points of problems (8) and (7), respectively.The convergence result is stated analogously for the two sequence-set algorithms.

B. Acceleration Scheme

The paper introduces SQUAREM to accelerate MM algorithms, addressing their simplicity and monotonicity but potentially slow convergence.

  • B. Acceleration Scheme: SQUAREM accelerates MM algorithms by approximating Newton’s method for finding a fixed point.The scheme was originally proposed for EM algorithms and can be applied to EM-type algorithms.
  • B. Acceleration Scheme: Modified SQUAREM schemes preserve monotonicity and solution feasibility after each iteration.
  • B. Acceleration Scheme: The proposed MM algorithms may converge slowly because their derivations use successive majorization steps.

VII. NUMERICAL EXPERIMENTS

The numerical experiments evaluate the proposed MM sequence-design algorithms across different design scenarios using Matlab implementations with acceleration.

  • VII. NUMERICAL EXPERIMENTS: The experiments evaluate MM-CSS, MM-Corr, and MM-WeCorr on sequence-design problems.These correspond to Algorithms 1, 3, and 2, respectively.
  • VII. NUMERICAL EXPERIMENTS: All experiments use Matlab on a PC with a 3.20 GHz i5-3470 CPU and 8 GB RAM.
  • VII. NUMERICAL EXPERIMENTS: The implementation applies the acceleration scheme described in Section VI-B to the proposed algorithms.

A. CSS Design

For unimodular CSS of length N = 128, increasing the number of sequences lowers complementary autocorrelation levels, with M = 3 producing nearly complementary behavior.

  • A. CSS Design: The MM-CSS experiment designs unimodular CSS of length N = 128 with M = 1, 2, and 3 sequences.
  • A. CSS Design: The initial sequence sets are generated randomly using independent phases uniformly distributed in [0, 1].
  • A. CSS Design: As M increases, the complementary autocorrelation level decreases because larger M provides more degrees of freedom for CSS design.
  • A. CSS Design: When M = 3, the autocorrelation sums are very close to zero, so the sequences can be viewed as complementary in practice.
  • A. CSS Design: Figure 1 reports autocorrelation levels for sequence sets with N = 128 and M = 1, 2, 3.

B. Approaching the Lower Bound of Ψ

Experiments compare MM-Corr, MM-WeCorr, and CAN on sequence sets of varied sizes, finding that all approach the lower bound while MM-Corr converges fastest.

  • B. Approaching the Lower Bound of Ψ: The experiments ask whether the lower bound N^2M(M−1) of Ψ can be achieved.
  • B. Approaching the Lower Bound of Ψ: MM-Corr and MM-WeCorr are compared with CAN for sequence sets having M ∈ {2, 3, 4} and N ∈ {256, 1024}.
  • B. Approaching the Lower Bound of Ψ: All three algorithms approach the lower bound of Ψ, producing almost optimal sequence sets for the considered (M, N) pairs.
  • B. Approaching the Lower Bound of Ψ: Average Ψ values over 10 random trials remain close to minimum values, indicating limited sensitivity to initialization.
  • B. Approaching the Lower Bound of Ψ: MM-Corr is fastest and CAN slowest for every (M, N) pair, with MM-Corr requiring far fewer iterations than CAN.Their per-iteration computational complexity is almost the same: 2M^2N-point FFT (IFFT) operations.

C. Sequence Set Design with Zero Correlation Zone

The zero-correlation-zone experiment targets low auto- and cross-correlations only at required lags and compares MM-WeCorr with WeCAN. MM-WeCorr reaches a far lower objective and suppresses required-lag sidelobes more effectively.

  • Runtime comparison: MM-WeCorr drives the objective to 10^-10 within 1 second, whereas WeCAN remains above 10^2 after 10000 seconds.The comparison uses the objective in (8) and the stated stopping conditions.
  • Correlation quality: MM-WeCorr suppresses required-lag correlation sidelobes to about -175 dB, while WeCAN produces much higher sidelobes.The correlations in Fig. 3 are normalized by N.
  • Correlation quality: WeCAN yields very low cross-correlations at lag 0 despite no attempted suppression there, because its lag-0 weight is required to be positive and sufficiently large.The weight helps ensure that WeCAN’s weight matrix is positive semidefinite.
  • Computational implication: The proposed algorithms are implemented via FFT and are reported as computationally efficient for sequence-set design.The paper’s conclusion also reports applications to almost complementary and jointly auto- and cross-correlated sequence sets.

APPENDIX A PROOF OF LEMMA 5

The appendix proves a technical lemma by embedding a Toeplitz matrix into a 2N-dimensional circulant matrix and using FFT diagonalization. It also establishes a quadratic majorization condition over a bounded interval.

  • Toeplitz embedding: An N × N Toeplitz matrix is embedded in a circulant matrix of dimension 2N × 2N.The circulant construction uses the Toeplitz entries and zero padding.
  • FFT representation: The circulant matrix is diagonalized by the FFT matrix, yielding an FFT-based representation of the Toeplitz matrix.The representation uses the first column of the circulant matrix and its diagonal spectrum.
  • Majorization condition: The majorization proof requires the surrogate to dominate the quadratic function throughout the interval [0, t] while matching it at x0.The construction begins with a quadratic surrogate whose curvature parameter satisfies a > 0.
  • Majorization condition: Monotonicity of the derivative-based auxiliary function reduces the verification to its maximum at x = t.The auxiliary function is shown to be nondecreasing on [0, t].
  • Proof completion: Rearranging the surrogate terms produces the function stated in the lemma.The appendix concludes the proof after this rearrangement.
Loading 1510.01899v1…