PaperlayerView exact revision on arXiv

Source-linked AI summary

Designing Unimodular Codes via Quadratic Optimization is not Always Hard

Mojtaba Soltanalian, Petre Stoica

arXiv:1303.0152v1eess.SYcs.IT

TL;DR

The paper studies quadratic-form optimization for radar code design and develops a cone-based approach to identifying global optimizers. Its results characterize the relevant matrix cone and establish rapid convergence and eigenvector conditions for associated UQPs.

  • Problem

    Radar code design includes optimizing a quadratic form to design codes for SNR or CRLB objectives.

  • Method

    The paper characterizes the cone K(s), the set of matrices for which a given unimodular vector s is a global optimizer of UQP.

  • Results

    Theorem 4 establishes convergence of {R(t)} in at most two iterations, while Theorems 6 and 7 give hyper-point and dominant-eigenvector conditions for associated matrices.

  • Takeaways & Limitations

    The cone characterization and eigenvector conditions provide a basis for tackling UQP through structured matrix transformations.

Abstract

from arXiv · show

The NP-hard problem of optimizing a quadratic form over the unimodular vector set arises in radar code design scenarios as well as other active sensing and communication applications. To tackle this problem (which we call unimodular quadratic programming (UQP)), several computational approaches are devised and studied. A specialized local optimization scheme for UQP is introduced and shown to yield superior results compared to general local optimization methods. Furthermore, a \textbf{m}onotonically \textbf{er}ror-bound \textbf{i}mproving \textbf{t}echnique (MERIT) is proposed to obtain the global optimum or a local optimum of UQP with good sub-optimality guarantees. The provided sub-optimality guarantees are case-dependent and generally outperform the $π/4$ approximation guarantee of semi-definite relaxation. Several numerical examples are presented to illustrate the performance of the proposed method. The examples show that for cases including several matrix structures used in radar code design, MERIT can solve UQP efficiently in the sense of sub-optimality guarantee and computational time.

I. INTRODUCTION

Unimodular quadratic programming (UQP) captures code-design problems in active sensing, radar, beamforming, and communication systems. The introduction motivates UQP through several applications, including SNR and CRLB optimization, cross-ambiguity-function synthesis, steering-vector estimation, and unimodular-code detection.

  • Unimodular codes are used in active sensing and communication systems because they have unity peak-to-average-power ratio.
  • Designing unimodular codes is formulated as optimizing a quadratic form over vectors whose entries lie on the unit circle.The paper denotes this problem UQP.
  • Designing codes that optimize the SNR or the CRLB: SNR optimization and CRLB minimization for radar code design can both be formulated as UQPs.The CRLB provides a lower bound on the variance of any unbiased target Doppler-frequency estimator.
  • Synthesizing cross ambiguity functions (CAFs): Synthesizing a desired cross-ambiguity function is difficult because few code and filter variables must satisfy many two-dimensional matching constraints.The design targets a specified magnitude |χ(τ, f)| over delay and Doppler coordinates.
  • Estimating an unknown unimodular steering vector and detecting unimodular symbols by maximum likelihood also lead to UQP-type formulations.The steering-vector formulation can incorporate prior phase-sector information.

B. Related Work

Related work establishes UQP as NP-hard and surveys polynomial-time relaxations and discrete variants. Semi-definite relaxation offers a π/4 sub-optimality guarantee, while rank-based algorithms do not directly apply to the continuous unimodular problem.

  • UQP is NP-hard, with its hardness established through a reduction from an NP-complete matrix partitioning problem.
  • The m-UQP variant restricts decision variables to m-th roots of unity and coincides with UQP as m approaches infinity.
  • When rank(R) behaves as O(1) with problem dimension, m-UQP admits a polynomial-time algorithm with O((mn/2)2d) complexity.
  • These rank-based algorithms are not applicable to UQP because UQP corresponds to infinitely many possible phases.
  • Semi-definite relaxation converts UQP into a polynomial-time solvable semi-definite program by removing rank and unimodularity constraints.Solutions can be approximated using rank-one or randomized procedures.
  • π/4 is the SDR randomized-approximation sub-optimality guarantee, and the coefficient can be arbitrarily close to π/4.

C. Contributions of this Work

The paper develops a specialized local optimization scheme and MERIT for UQP, combining computational efficiency with case-dependent sub-optimality guarantees. Numerical evidence indicates that MERIT efficiently solves several UQPs, particularly those arising in active sensing code design.

  • A computationally efficient local optimization approach is proposed for UQP and for improving solutions obtained by methods such as SDR.
  • MERIT is introduced to obtain a global or local UQP optimum with good sub-optimality guarantees.
  • MERIT provides case-dependent sub-optimality guarantees that were not previously known for UQP.
  • The proposed guarantees generally outperform analytical worst-case guarantees such as SDR's π/4 approximation guarantee.
  • The guarantees are practically important for judging whether solutions from SDR or other optimization methods are sufficiently good to trust.
  • Numerical evidence shows that several UQPs, particularly active-sensing code-design instances, can be solved efficiently without sacrificing solution quality.
  • The paper suggests that its general ideas may extend to m-UQP, while detailed study of the finite-alphabet case remains outside scope.

B. Analytical Solutions to UQP

The paper identifies analytical conditions yielding global UQP optima and studies a cyclic local-optimization procedure. These results characterize useful solution structures while clarifying limits from nonuniqueness, saddle points, and incomplete cone characterization.

  • Analytical global optima are easy to obtain in certain UQP cases.
  • When the phase-adjusted matrix is rank one, the corresponding unimodular vector is a global UQP optimizer.
  • If a unimodular vector lies in the span of eigenvectors associated with identical largest eigenvalues, it is a global optimizer.
  • The UQP solution need not be unique; a matrix can be constructed so several unimodular vectors are global optimizers.
  • Because UQP is generally highly multimodal, cyclic optimization is used to find local optima and improve approximate solutions.
  • The method may not converge to every local optimum, and the analysis assumes positive-definite R while allowing saddle points in the candidate set.
  • The cyclic iterations increase a bounded objective and therefore converge in associated objective value.
  • The local method can bypass some lower-objective local optima and, for some initializations, reach the global optimum.

IV. RESULTS ON THE CONE K(s)

The section develops an approximate characterization of K(s), despite the inability to fully characterize it under UQP's NP-hardness. Its iterative construction converges rapidly and supports explicit sub-optimality guarantees.

  • Approximate characterization: Theorem 3 constructs K(s) using cone families C(Vs) and Cs, where Cs contains matrices having s as a dominant eigenvector.The resulting characterization can be used to tackle UQP, and its accuracy is measured by the minimal α0.
  • Approximate characterization: The proposed construction can satisfy the required condition even when s is only a hyper point of UQP.This extends the construction beyond cases where s is already known to be globally optimal.
  • Iterative construction: The hyper point s is preserved through R(1) and R(2), and becomes an eigenvector of R(2).Theorem 6 establishes preservation across the generated UQPs and identifies s as an eigenvector at convergence.
  • Dominant-eigenvector condition: For any ρ ≥ µ/n, s is a dominant eigenvector of R(2), provided ρ is sufficiently large and satisfies the construction criterion.Here µ is the largest eigenvalue of R(2) associated with an eigenvector other than s.
  • Sub-optimality guarantee: The construction yields an explicit sub-optimality guarantee for UQP solutions based on the approximation of K(s).The subsequent method decreases an upper bound on the obtained solution's sub-optimality during each iteration.

V. MERIT FOR UQP

MERIT reformulates UQP through a sequence of nearby matrices with known global optima, then alternates optimizations over auxiliary matrix components and the unimodular vector. The method maintains positive definiteness and can return a global or locally optimal solution with a sub-optimality bound.

  • Global optimization: MERIT builds matrices whose known global optima approach a target matrix, enabling iterative solution of the original UQP.The matrix sequence is constructed using a one-to-one mapping and an approximation of K(s).
  • Global optimization: The method can obtain a global optimum or a local optimum with an upper bound on solution sub-optimality.The bound decreases monotonically across iterations.
  • Algorithmic optimization: MERIT optimizes the auxiliary variables Q1 and P1 and the unimodular vector s in separate steps.The Q1 and P1 updates exploit convex-cone structure, while the s update uses power-method-like iterations to obtain a local optimum.
  • Algorithmic optimization: The optimization over s remains non-convex, so the corresponding update provides a local optimum rather than a guaranteed global solution.The algorithm summarizes these alternating updates in Table I.
  • Algorithmic optimization: Positive diagonal loading preserves the relevant transformed structure while ensuring that the iterates remain positive definite.A loading λI is absorbed into P1, and the loading threshold is chosen using the smallest eigenvalue of R.

B. Achieving a Local Optimum of UQP (the Case of α0 > 0)

When the zero-loading case does not converge, MERIT increases α0 and solves a modified problem that can still yield a local UQP optimum with a corresponding guarantee.

  • Local optimum for α0 > 0: MERIT solves the modified problem with R′ = R + α0ssH for increasing α0 to obtain a local optimum.Increasing α0 decreases the objective in (67).
  • Local optimum for α0 > 0: The modified optimization uses the same tools as the α0 = 0 case, including optimization over Q1, P1, and s.The resulting solution can initialize the corresponding problem for other α0 values.
  • Local optimum for α0 > 0: A bisection approach obtains α0, focusing on small values of α0, and the resulting local-optimum procedure is summarized in Table I-B.The positive-definiteness condition must hold for the loaded matrix.

C. Sub-optimality Analysis

MERIT derives case-dependent sub-optimality guarantees from the gap between the target matrix and its approximation. When that approximation error vanishes, the guarantee reaches γ = 1 and certifies global optimality.

  • Guarantee construction: MERIT provides a sub-optimality guarantee γ based on the optimization of the approximating matrix problem.The guarantee is derived from the relationship between the true matrix R and the approximated matrix Rs.
  • Global-optimum certification: When α0 = 0 and ∥E∥F converges to zero, the bounds imply that s is globally optimal for the UQP associated with R.The approximation error is ∥E∥F = ∥R − Rs∥F.
  • Guarantee construction: Solving the auxiliary optimization problem exactly is not necessary for the resulting solution to be optimal.The method can therefore certify optimality even when the auxiliary problem is not solved exactly.
  • Guarantee comparison: The derived guarantee generally gives tighter sub-optimality bounds than the π/4 approximation guarantee of SDR.The paper presents empirical evidence for this comparison in the numerical section.
  • Guarantee visualization: Figure 1 tracks the true and approximated UQP objectives, their upper and lower bounds, and ∥E∥F across iterations.The bounds are updated using (71)–(72).

VI. NUMERICAL EXAMPLES

Numerical experiments evaluate MERIT on random full-rank and rank-deficient matrices, radar-oriented matrix structures, and a thumbtack CAF design problem. The reported results show accurate solutions, favorable behavior on rank-deficient cases, and effective sidelobe suppression.

  • Illustrative UQP: For a random positive definite matrix with n = 16, MERIT achieved γ = 1 and therefore obtained the global optimum in 3.653 sec.The objective values and sub-optimality bounds are shown against iteration number in Figure 1.
  • Random matrices: MERIT and SDR are compared on 20 random positive definite matrices across sizes n ∈ {8, 16, 32, 64}.The experiments include both full-rank and rank-deficient matrices and allocate SDR the same computational time.
  • Random matrices: Rank-deficient UQPs appear to be solved more efficiently by MERIT than full-rank UQPs.The rank-deficient matrices use d ≪ n, and their performance is reported in Table II.
  • Comparison with SDR: When SDR solves the UQPs within the same time, its objective values are nearly identical to MERIT's.MERIT additionally supplies a case-dependent sub-optimality guarantee that can be used to assess SDR solutions.
  • Structured radar matrices: For three radar-related matrix structures, MERIT obtains solutions with sub-optimality guarantees close to one across sizes and random initializations.The cases include exponential disturbance, clutter-plus-noise, and discrete-scatterer disturbance structures.
  • CAF design: In the thumbtack CAF design example, MERIT efficiently suppresses sidelobes in the region of interest despite the unimodular transmit-vector constraint.The synthesis cyclically minimizes the CAF objective and uses MERIT to obtain a unimodular x at each iteration.

VII. CONCLUDING REMARKS

The paper develops specialized and iterative approaches for UQP, including MERIT, and reports favorable sub-optimality guarantees and efficient solutions for some active-sensing code-design matrices.

  • UQP applications include cases where accurate global optima can be obtained efficiently, and the solution need not be unique.
  • A specialized local optimization scheme for relaxed UQP yields superior results compared to general local optimization methods.
  • MERIT uses an approximate characterization of K(s) to iteratively address UQP.
  • MERIT provides case-dependent sub-optimality guarantees that available numerical evidence indicates are generally better than SDR’s π/4 approximation guarantee.
  • Numerical examples show that MERIT can efficiently obtain UQP solutions for certain matrices used in active-sensing code design.
  • No theoretical efficiency assessment of MERIT was provided, and characterizing the portion of K(s) covered by the approximation remains future work.

APPENDIX

The appendix establishes structural and convergence properties of the iterative matrix sequence, including closure, phase alignment, and a dimension-independent entrywise convergence argument.

  • Matrices sharing a common global optimizer form a set closed under positive linear combinations.
  • The appendix uses a one-to-one transformation between cones associated with different unimodular solutions to transfer global-optimality structure.
  • Each matrix entry is analyzed independently, so the convergence argument does not depend on the problem dimension n.
  • When the initial phase is farther than π/2 from the target, the update moves it toward the target and can bring it within π/2 in one iteration.
  • When an entry’s phase is within π/2 of the target phase, the sequence converges in one iteration; every matrix entry converges in at most two iterations.

D. Proof of Theorem 5

The proof shows that the iterative update preserves a given hyper point under suitable nonnegativity conditions and leads to an eigenvector relation after two iterations.

  • The derivation relies on the phase conditions and update relations established for the iterative sequence.
  • A hyper point s satisfies Rs = v ⊙s for a non-negative real-valued vector v.
  • The recursive update is rewritten to track the vector v(t) associated with the preserved hyper point across iterations.
  • The proof verifies preservation by showing that the updated vector v(t+1) remains componentwise nonnegative.
  • After the update, s is an eigenvector of R(2) with eigenvalue nρ.
Loading 1303.0152v1…