PaperlayerView exact revision on arXiv

Source-linked AI summary

Enhancing Sparsity and Resolution via Reweighted Atomic Norm Minimization

Zai Yang, Lihua Xie

arXiv:1408.5750v3cs.IT

TL;DR

Existing atomic-norm methods enable gridless recovery but retain a frequency-separation resolution limit. The paper introduces a nonconvex sparse metric and a locally convergent reweighted ANM algorithm, RAM, and numerical simulations report enhanced sparsity and resolution, including in DOA estimation.

  • Problem

    Atomic-norm recovery for continuous compressed sensing is computationally efficient but suffers a resolution limit when frequencies are insufficiently separated.

  • Method

    RAM combines a sparse metric bridging the atomic ℓ0 norm and atomic norm with a locally convergent iterative algorithm that repeatedly applies reweighted ANM.

  • Results

    RAM significantly enlarges the successful sparsity-separation phase relative to ANM and is reported to enhance sparsity and resolution in numerical simulations.

  • Takeaways & Limitations

    The method provides a gridless approach for signal and frequency recovery in CCS, with application to DOA estimation and reported advantages over ANM.

Abstract

from arXiv · show

The mathematical theory of super-resolution developed recently by Candès and Fernandes-Granda states that a continuous, sparse frequency spectrum can be recovered with infinite precision via a (convex) atomic norm technique given a set of uniform time-space samples. This theory was then extended to the cases of partial/compressive samples and/or multiple measurement vectors via atomic norm minimization (ANM), known as off-grid/continuous compressed sensing (CCS). However, a major problem of existing atomic norm methods is that the frequencies can be recovered only if they are sufficiently separated, prohibiting commonly known high resolution. In this paper, a novel (nonconvex) sparse metric is proposed that promotes sparsity to a greater extent than the atomic norm. Using this metric an optimization problem is formulated and a locally convergent iterative algorithm is implemented. The algorithm iteratively carries out ANM with a sound reweighting strategy which enhances sparsity and resolution, and is termed as reweighted atomic-norm minimization (RAM). Extensive numerical simulations are carried out to demonstrate the advantageous performance of RAM with application to direction of arrival (DOA) estimation.

I. INTRODUCTION

The paper addresses continuous compressed sensing for recovering signals and frequencies from partial samples when frequencies lie on a continuous dictionary. It proposes RAM, a reweighted atomic-norm method intended to enhance sparsity and resolution beyond ANM's separation-limited recovery.

  • Problem setting: Continuous compressed sensing recovers sinusoidal signals whose frequencies vary continuously rather than lying on a finite grid.The setting includes partial samples indexed by Ω and supports both line spectral estimation and array-processing applications.
  • Problem setting: In array processing, each continuous frequency corresponds uniquely to a source direction, making CCS applicable to DOA estimation with sparse linear arrays.A smaller antenna index set Ω means fewer retained antennas in the sparse linear array.
  • Prior methods: Atomic-norm methods provide gridless recovery but suffer a resolution limit when frequencies are insufficiently separated.The cited theory guarantees infinite-precision recovery in the noiseless case under a sufficient separation condition, while the condition is not necessary.
  • Proposed method: RAM uses a novel sparse metric between the atomic ℓ0 norm and atomic norm, then solves a nonconvex recovery problem with a locally convergent iterative algorithm.The algorithm repeatedly performs ANM using reweighting based on the latest frequency estimate.
  • Proposed method: The reweighting strategy favors frequencies near those from the current iteration, thereby enhancing sparsity and resolution in the continuous setting.The paper reports numerical evaluation of RAM against existing methods, including DOA estimation.

III. ENHANCING SPARSITY AND RESOLUTION VIA A NOVEL SPARSE METRIC

The paper introduces a logarithmic sparse metric that bridges the atomic norm and atomic ℓ0 norm as ϵ varies, targeting enhanced sparsity and resolution. Its limiting behavior also characterizes the optimizer’s eigenvalues and atomic decomposition.

  • The logarithmic penalty ln|λ + ϵ| approaches the ℓ1 norm for large ϵ and the ℓ0 norm as ϵ approaches zero.The plotted curves use ϵ values from 10 to 10^-6, with translations and scaling only for illustration.
  • As ϵ approaches zero, the smallest N−r eigenvalues of T(u*ϵ) are zero or approach zero at least as fast as ϵ, where r = ∥Y∥A,0.The paper also states that simulations consistently observe these eigenvalues becoming zero when ϵ is sufficiently small.
  • The optimizer’s cluster points admit an atomic decomposition whose limiting Toeplitz structure reflects the number of frequency components.The supplied theorem statements introduce this cluster-point characterization and its associated atomic decomposition.
  • Theorem 1 and Theorem 2 establish that Mϵ(Y) matches the atomic norm as ϵ approaches infinity and approaches the atomic ℓ0 norm as ϵ approaches zero.These limits support the expectation that the metric enhances sparsity and resolution relative to the atomic norm.

A. A Locally Convergent Iterative Algorithm

The proposed nonconvex metric is optimized through majorization–minimization, replacing its concave term with tangent planes and repeatedly solving weighted atomic-norm problems. This produces RAM, whose weights adapt to the latest estimate and thereby promote sparsity and finer spectral resolution.

  • A. A Locally Convergent Iterative Algorithm: The proposed optimization is nonconvex because ln |T(u) + ϵI| is concave, so global optimality cannot be guaranteed by efficient algorithms.
  • A. A Locally Convergent Iterative Algorithm: Majorization–minimization replaces the logarithmic term with its tangent plane at the current iterate, yielding a sequence of tractable subproblems.
  • A. A Locally Convergent Iterative Algorithm: The objective decreases monotonically across iterations and converges to a local minimum.
  • B. Interpretation as RAM: A weighted atomic norm assigns frequency-dependent preference to atoms, with larger weights making corresponding atoms more likely to be selected.
  • B. Interpretation as RAM: RAM updates its weighting function from the latest solution; its first iteration uses a constant weighting function and therefore coincides with ANM.
  • B. Interpretation as RAM: The reweighting strategy favors frequencies found in the current iteration, enhancing sparsity and providing finer spectral details around those frequencies.

V. COMPUTATIONALLY EFFICIENT IMPLEMENTATIONS

The implementation solves RAM through semidefinite programming, with both standard SDP and ADMM-based approaches. Dimension reduction limits the PSD-matrix order using the rank of the observations, while dual SDP solving can improve efficiency.

  • A. Optimization Using Standard SDP Solver: Each RAM iteration solves the semidefinite program with W = (T(u^j) + ϵI)^−1, and its dual can be more efficient than the primal with SDPT3.
  • B. A First-order Algorithm via ADMM: ADMM reformulates the SDP and updates the optimization variables and multipliers in closed-form iterations until convergence.
  • C. Dimension Reduction for Large L: The reduction applies to settings with L measurement vectors by using a rank-r representation, with r bounded by min(L, M).
  • C. Dimension Reduction for Large L: The dimension-reduction approach does not require the model order K and produces a dimension-reduced equivalent problem.
  • C. Dimension Reduction for Large L: When L > M, dimension reduction lowers the PSD-matrix order from N + L to N + r ≤ N + M, making problem size depend only on M and N.
  • C. Dimension Reduction for Large L: The implementation is practical when M and N are small, although SDPT3 and ADMM may lack good scalability, especially SDPT3.

D. Remarks on Algorithm Implementation

RAM is initialized with ANM and iteratively refines its weighting function, using progressively smaller ϵ values and stopping based on solution stability or an iteration limit. An illustrative five-spike example shows successive resolution gains until all frequencies are recovered.

  • D. Remarks on Algorithm Implementation: RAM can start with u0 = 0, making its first iteration coincide with ANM; a Capon-inspired weight can accelerate convergence when L is large.
  • D. Remarks on Algorithm Implementation: The implementation gradually decreases ϵ and defines each weighting function from the latest solution to avoid local minima.
  • D. Remarks on Algorithm Implementation: The default implementation starts with ϵ = 1 and halves ϵ between iterations until reaching 1/2^10 or a specified threshold.
  • D. Remarks on Algorithm Implementation: When η = 0, RAM terminates after relative solution change falls below 10^-6 or after 20 iterations.
  • B. An Illustrative Example: In the five-spike example, RAM identifies all frequencies after successive reweighting and converges in four SDPT3 iterations.
  • B. An Illustrative Example: After three iterations, T(u*) becomes rank-5 and the remaining eigenvalues are zero within numerical precision.

C. Sparsity-Separation Phase Transition

The experiments compare ANM and RAM across sparsity, frequency separation, measurement-vector, and DOA settings. RAM enlarges the successful recovery region and improves sparse frequency and source recovery, including correlated-source scenarios.

  • Illustrative RAM behavior: Only 5 eigenvalues remain nonzero after 3 RAM iterations in the illustrative N = 64, M = 30, K = 5 example.The first iteration uses a constant weighting function and coincides with ANM.
  • Sparsity-separation phase transition: RAM significantly enlarges the success phase and enhances sparsity and resolution compared with ANM in the L = 1 phase-transition experiment.Success is defined by relative signal MSE and frequency MSE below 10^-12 over 20 Monte Carlo runs.
  • Application to DOA estimation: In DOA simulations, RAM correctly detects 4 sources near their true locations, whereas ANM produces spurious sources and fails to separate the closest pair.The sources include two separated by only 0.2 N^-1, and both uncorrelated and correlated cases are considered.
  • Application to DOA estimation: RAM requires more computation than ANM in the reported DOA experiment, taking 7.31 s versus 0.87 s with SDPT3 and 2.65 s versus 0.20 s with ADMM.These are average computational times for the respective implementations.

APPENDIX

The appendix proves properties of the proposed metric through eigenvalue asymptotics and rank arguments. As the regularization parameter vanishes, the metric exhibits behavior associated with low-rank atomic representations.

  • Rank argument: A rank contradiction shows that T(u*) retains at most r − 1 frequencies only if Y admits an atomic decomposition of order at most r − 1.This contradicts the assumption that the atomic ℓ0 norm of Y equals r.
  • Asymptotic metric behavior: The proof establishes that M_ϵ(Y) behaves asymptotically as (N − r) ln ϵ as ϵ → 0.Here r is the number of nonzero eigenvalues in the relevant decomposition.
  • Eigenvalue bounds: The proof shows that λ_ϵ,k = O(ϵ) for k = r + 1, . . . , N.These eigenvalues correspond to the components beyond the first r terms.

C. Proof of Theorem 3

The proof concludes its argument by combining Vandermonde-decomposition equalities and observing that the result does not depend on the decomposition order.

  • Proof conclusion: The conclusion follows by combining the stated equalities, with the first using the Vandermonde decomposition and the second using the referenced equality.The proof applies to any possible Vandermonde decomposition, whether T(u) is invertible or not.

D. Lagrangian Analysis of the Dual Problem (21)

The dual problem is obtained by minimizing the Lagrangian over the primal variables and identifying the resulting dual objective and constraints.

  • Dual derivation: Minimizing the Lagrangian over (u, X, Y) yields a dual objective involving −λ^-1∥V_Ω∥_2 or −∞, depending on feasibility.The adjoint operator T*(·) is used to obtain the dual formulation in (21).

E. Proof of Proposition 1

The proof considers an optimization problem related to equations (15) and (13).

  • The proof introduces an optimization problem associated with equations (15) and (13).

Y HCY

The derivation applies a unitary change of variables to reduce the optimization problem while preserving its optimal value, then maps the reduced optimizer back to the original variables.

  • The optimization variable Y is replaced by Z = YQ using a unitary matrix Q.The transformed problem is expressed in terms of Z_j = YQ_j for j = 1, 2.
  • The second component of the optimizer is zero, yielding a dimension-reduced problem with the same optimal function value.
  • Given the reduced optimizer, the optimizer in the original variables is recovered through Y* = Z*Q^H.
Loading 1408.5750v3…