PaperlayerView exact revision on arXiv

Source-linked AI summary

Exact Joint Sparse Frequency Recovery via Optimization Methods

Zai Yang, Lihua Xie

arXiv:1405.6585v2cs.IT

TL;DR

The paper addresses recovery of continuous frequencies shared across multiple measurement vectors, a setting arising in array processing and joint sparse recovery. It proposes atomic ℓ0 and convex atomic-norm formulations, showing that MMVs can improve recoverability while the practical relaxation is solvable by semidefinite programming. Theoretical guarantees and simulations support exact recovery and improved performance under appropriate conditions.

  • Problem

    The central problem is recovering shared continuous frequencies from MMVs without grid mismatch while exploiting their joint sparsity.

  • Method

    The paper studies an MMV atomic ℓ0 formulation and introduces a convex MMV atomic-norm relaxation solvable by semidefinite programming.

  • Results

    Theoretical results establish exact frequency recovery under appropriate conditions, while simulations show the proposed method performs well for uncorrelated and coherent sources.

  • Takeaways & Limitations

    MMV atomic-norm recovery can exploit joint sparsity through a single convex optimization problem and may improve recovery performance, including with coherent sources.

Abstract

from arXiv · show

Frequency recovery/estimation from discrete samples of superimposed sinusoidal signals is a classic yet important problem in statistical signal processing. Its research has recently been advanced by atomic norm techniques which exploit signal sparsity, work directly on continuous frequencies, and completely resolve the grid mismatch problem of previous compressed sensing methods. In this work we investigate the frequency recovery problem in the presence of multiple measurement vectors (MMVs) which share the same frequency components, termed as joint sparse frequency recovery and arising naturally from array processing applications. To study the advantage of MMVs, we first propose an $\ell_{2,0}$ norm like approach by exploiting joint sparsity and show that the number of recoverable frequencies can be increased except in a trivial case. While the resulting optimization problem is shown to be rank minimization that cannot be practically solved, we then propose an MMV atomic norm approach that is a convex relaxation and can be viewed as a continuous counterpart of the $\ell_{2,1}$ norm method. We show that this MMV atomic norm approach can be solved by semidefinite programming. We also provide theoretical results showing that the frequencies can be exactly recovered under appropriate conditions. The above results either extend the MMV compressed sensing results from the discrete to the continuous setting or extend the recent super-resolution and continuous compressed sensing framework from the single to the multiple measurement vectors case. Extensive simulation results are provided to validate our theoretical findings and they also imply that the proposed MMV atomic norm approach can improve the performance in terms of reduced number of required measurements and/or relaxed frequency separation condition.

I. INTRODUCTION

The paper studies joint sparse frequency recovery from multiple measurement vectors sharing frequencies, motivated by direction-of-arrival estimation and the need to exploit temporal redundancy. It develops atomic-norm methods that extend continuous-frequency recovery to the MMV setting.

  • Problem formulation: Joint sparse frequency recovery estimates shared frequency components from multiple measurement vectors generated by sinusoidal signals.The shared frequencies are recovered first; amplitudes and full data can then be obtained by least squares.
  • Applications: Direction-of-arrival estimation is a natural JSFR application in which each frequency represents a source direction and each measurement vector is one sensor-array snapshot.Multiple snapshots assume static sources during a time window, creating temporal redundancy that can be exploited when array size is physically or economically limited.
  • Prior methods: Conventional subspace methods require covariance estimation, sufficient snapshots, and can degrade when source signals are correlated.Their Toeplitz structure cannot generally be exploited through the sample covariance.
  • Prior methods: Grid-based sparse methods impose an on-grid frequency assumption, whereas atomic-norm techniques recover continuous frequencies and resolve grid mismatch.Prior continuous-frequency results established exact recovery under frequency separation and, for compressive data, sufficient random samples.
  • Contributions: The paper proposes an MMV atomic ℓ0 approach to characterize joint-sparsity gains and an MMV atomic norm relaxation that is solvable by semidefinite programming.The atomic ℓ0 formulation shows increased recoverable frequencies except in a trivial case, while the convex method provides exact-recovery guarantees under appropriate conditions.

A. Preliminary: Vandermonde Decomposition

The section connects shared-frequency signal models with Vandermonde decomposition and introduces atomic sparsity formulations for recovery. Joint sparsity can increase recoverable frequencies, but the direct atomic ℓ0 formulation becomes rank minimization, motivating a convex atomic-norm relaxation.

  • Vandermonde decomposition: Under uncorrelated sources, the covariance matrix is rank-K, positive semidefinite, and Toeplitz, enabling unique frequency recovery through Vandermonde decomposition when K < N.The decomposition can also be computed using a subspace method such as ESPRIT.
  • Atomic representation: The MMV signal is represented as a linear combination of atoms sharing frequencies while carrying vector-valued amplitudes across measurement vectors.An atomic decomposition of order K requires positive coefficients and distinct frequencies.
  • Joint-sparsity formulation: The atomic ℓ0 norm is the smallest number of continuous-frequency atoms needed to express the MMV signal.It generalizes joint sparse recovery's ℓ2,0 perspective to a continuous dictionary.
  • Joint-sparsity formulation: The proposed optimization uses the frequencies in its solution as frequency estimates.This extends a sparse-frequency recovery method from the single-measurement-vector setting to MMVs.
  • Recovery guarantee: If rank(Y_Ω^o) > 1, MMVs can increase the number of recoverable frequencies compared with the SMV case, except when the vectors are identical up to scaling.Exact recovery holds when the sparsity is sufficiently small relative to the sampling index set and observed data.
  • Computational limitation: The atomic ℓ0 formulation equals a rank minimization problem and therefore cannot be practically solved globally.This nonconvex formulation motivates the later convex atomic-norm relaxation.

C. Frequency Recovery via Convex Relaxation

The MMV atomic norm provides a convex relaxation of an intractable rank-minimization formulation for joint sparse frequency recovery. Its SDP representation enables practical optimization, with theoretical guarantees for exact recovery under stated conditions.

  • Convex relaxation: The MMV atomic norm is a convex relaxation of the nonconvex rank-minimization problem motivated by joint sparsity.The rank formulation cannot be globally solved with a practical algorithm, whereas the atomic norm is convex.
  • Convex relaxation: The atomic norm is defined as the gauge function of the convex hull of the atom set.This extends the joint-sparse formulation through a continuous atomic representation.
  • Convex relaxation: The proposed recovery program minimizes the MMV atomic norm subject to matching the observed samples.The formulation corresponds to the convex optimization problem introduced for joint sparse frequency recovery.
  • Semidefinite implementation: An SDP formulation makes the atomic norm practically computable despite its original semi-infinite representation.The resulting SDP can be solved using an off-the-shelf SDP solver.
  • Semidefinite implementation: The recovered frequencies and atomic decomposition are obtained from the Vandermonde decomposition of the optimal Toeplitz matrix.The decomposition uses the optimal solution u* of the SDP.
  • Recovery guarantees: Under the stated separation and sampling conditions, the original signal is the unique optimizer and its atomic decomposition is unique.The compressive-data guarantee assumes uniformly random sampling and includes a technical requirement N ≥257.

D. Discussions

The paper contrasts atomic ℓ0 and atomic norm approaches for JSFR, showing that MMVs can improve recoverable-frequency counts generally, while convex recovery remains computationally practical. Theoretical guarantees are worst-case, so simulations are needed to expose MMV benefits for general source positions.

  • Optimization approaches: The atomic ℓ0 approach exploits joint sparsity most directly but produces an NP-hard rank-minimization problem.The atomic norm approach instead relaxes this problem convexly, admits an SDP formulation, and supports polynomial-time solution.
  • MMV advantage: MMVs generally increase the number of recoverable frequencies, making the result practically relevant to array-processing applications.This improvement disappears when all sources are coherent and the observation matrix has rank one.
  • Open questions: Sensor-array geometry remains an open design issue because selecting the sampling set to improve spark is identified as an interesting future topic.In the full-data case, spark reaches N + 1 because any N atoms are linearly independent.
  • Theoretical guarantees: Theorem 4 extends an SMV result to MMVs, but its guarantee cannot improve uniformly because it includes the trivial coherent-source case.Theorem 5 likewise generalizes a compressive SMV guarantee to MMVs and is characterized as worst-case analysis.
  • Theoretical guarantees: A single convex optimization can confidently recover frequencies from MMVs by exploiting their joint sparsity.Simulations indicate significantly better recovery for sources at general positions, while average-case analysis remains future work.

III. CONNECTIONS TO PRIOR ART

The paper places its gridless JSFR method among continuous sparse-recovery approaches and connects it to SPA. It also explains that the proofs extend prior SMV and scalar-polynomial arguments to MMVs and vector-valued dual polynomials.

  • Gridless recovery: Grid-based joint sparse recovery cannot generally achieve exact frequency recovery because true frequencies typically do not lie on the assumed grid.Atomic ℓ0 and atomic norm are continuous counterparts of the grid-based ℓ2,0 and ℓ2,1 norms.
  • Prior gridless method: SPA was the only previously identified discretization-free JSFR technique and uses a weighted covariance-fitting criterion from a statistical perspective.The paper compares this approach with its atomic norm formulation.
  • Connection to SPA: The paper shows that SPA computes an atomic norm of modified source signals.In the SMV case, where V is a positive scalar, SPA and the atomic norm technique are exactly equivalent; a similar connection holds for compressive data.
  • Proof strategy: The proofs generalize results from SMV to MMV and from discrete to continuous settings, requiring vector-valued rather than scalar-valued dual polynomials.The proof of Theorem 4 also forms the basis for Theorem 5, and an inaccuracy in prior work is corrected.

A. Proof of Theorem 2

The proof establishes that the atomic ℓ0 quantity equals the rank of an optimal positive semidefinite Toeplitz matrix. It does so by deriving matching inequalities from Vandermonde decompositions and atomic representations.

  • Setup: The proof defines K as the atomic ℓ0 quantity and K∗ as the rank of the optimal Toeplitz matrix, then aims to show K = K∗.This equality links the continuous sparse representation to the rank-minimization formulation.
  • First inequality: A Vandermonde decomposition of the optimal Toeplitz matrix places Y in its range and yields an atomic representation with K∗ frequencies, proving K ≤ K∗.The representation uses atoms a(fj) and coefficient vectors sj.
  • Second inequality: Conversely, any atomic decomposition with K terms constructs a feasible solution whose Toeplitz matrix has rank K, proving K∗ ≤ K.Thus every atomic representation supplies a feasible rank bound.
  • Technical tools: The proof handles rank-deficient matrices using a limiting inverse definition and a minimum-norm representation lemma.The lemma rewrites y^H R^-1 y as a constrained minimum over coefficient vectors when R = AA^H is positive semidefinite.
  • Remaining argument: The semidefinite constraint implies T(u) ≥ 0 and W ≥ Y^H[T(u)]^-1Y, reducing the remaining argument to the required matrix inequality.A Vandermonde decomposition T(u) = APA^H and the lemma are then applied columnwise to Y.

C. Proof of Theorem 1

The proof of Theorem 1 uses spark and null-space arguments to establish uniqueness of the atomic decomposition under the stated condition. It then rules out an alternative decomposition by contradiction.

  • Contradiction: The nullity and rank relations imply K + K̃ − K12 ≥ spark(A_Ω), contradicting condition (9).This contradiction excludes the alternative decomposition and completes the uniqueness argument.
  • Uniqueness: The condition in (9) implies K < spark(A_Ω) ≤ K, which is used to establish uniqueness.The proof invokes the definition of spark and linear independence of selected atoms.
  • Uniqueness: Any K atoms in A1_Ω are linearly independent, so the atomic decomposition is unique once the frequency set T is fixed.This is the central uniqueness step of the theorem proof.
  • Contradiction: An alternative decomposition would produce a nonzero coefficient difference whose image under A_Ω is zero.The proof partitions the competing decompositions and obtains Y^o − Ỹ = AΥ̸ = 0.
  • Contradiction: The proof applies the same argument after separating the competing decomposition into additional components, provided the relevant second atom set is nonempty.The remaining steps are stated to follow from the preceding argument.

D. Proof of Theorem 4

The proof constructs a vector-valued dual polynomial for the MMV setting and establishes its required interpolation and boundedness properties. This extends the scalar dual-certificate strategy to multiple measurement vectors.

  • Dual certificate: Theorem 4 is linked to a vector-valued dual polynomial whose coefficient matrix is constructed under the theorem’s assumptions.The polynomial is Q(f) = a^H(f)V, with coefficients chosen to satisfy the required constraints.
  • Coefficient construction: The polynomial coefficients are determined by combining interpolation and derivative constraints into a linear system.The system uses coefficient vectors α_j and β_j associated with the frequency locations.
  • Norm bounds: The induced ℓ2,∞ operator norm equals the ℓ∞ norm for the operators used in the proof.This equality permits existing ℓ∞ bounds to control the MMV coefficient terms.
  • Certificate verification: Away from all true frequencies, the constructed polynomial has norm at most 0.99992.Near each true frequency, strict concavity of the squared norm gives a unique maximum of 1 at that frequency.

E. Proof of Theorem 5

The proof extends the dual-certificate analysis to randomly sampled MMV data. It combines concentration of random sampling operators with vector-valued probabilistic bounds to establish exact recovery conditions.

  • Dual certificate: Theorem 5 uses a vector-valued dual polynomial satisfying interpolation, boundedness, and an additional constraint required for the compressive-data case.The proof also requires linear independence of the sampled frequency atoms for uniqueness.
  • Random observations: Random sampling is modeled with independent Bernoulli variables, whose observed indices define the sampling set.The observation probability is tied to the sample size and ambient index-set size.
  • Random kernel: The random kernel is constructed as an analogue of the full-data kernel and has expectation equal to the sampling probability times that kernel.The same relationship applies to the kernel derivatives.
  • Concentration: Concentration events control the random dual polynomial and its derivatives on a discrete grid and then extend the bounds to the whole unit circle.The argument uses a vector-form Hoeffding inequality for independently sampled rows on a complex hypersphere.
  • Recovery guarantee: The resulting dual certificate proves that the atomic decomposition is the unique optimizer under the stated assumptions.The proof verifies the required norm bound by combining concentration with local concavity around each true frequency.

A. Full Data

Full-data simulations test the atomic norm method under varying frequency separation, source correlation, and numbers of measurement vectors. They support the theoretical recovery guarantee and show that MMVs can improve recovery except when sources are fully coherent.

  • Experimental setup: The experiments vary N = 128 and the minimum frequency separation from approximately 1.05N^-1 to 2N^-1 for equispaced frequencies.Random-frequency experiments use a lower starting separation of 0.9N^-1.
  • Experimental setup: The study compares L = 1, 3, and 5 measurement vectors using 20 Monte Carlo runs for each separation and frequency type.Recovery is performed with the proposed atomic norm method using the first L columns of the generated data.
  • Uncorrelated sources: The results verify exact recovery under a frequency separation condition and indicate that more measurement vectors permit weaker separation conditions.For equispaced frequencies, more frequencies require stronger separation.
  • Coherent sources: As the coherent-source percentage τ increases, success rates decrease and stronger frequency separation is required.At τ = 100%, the curves approximately match the L = 1 case because all source signals are coherent.
  • Computation: Each semidefinite program takes about 11 seconds on average, with only slight CPU-time differences across the tested values of L.Generating the data for Figs. 1 and 2 required about 22 hours in total.

B. Compressive Data

Compressive-data experiments examine phase transitions and noisy recovery. MMVs improve recovery across correlation levels, while the noisy simulations show good performance but leave theoretical noise analysis for future work.

  • Compressive data: The compressive-data study fixes N = 128, L = 5, and Δmin = 1.2N^-1 while varying the sample count M and frequency count K.The phase transition is evaluated in the (M, K) plane using 20 Monte Carlo runs and recovery-error thresholds.
  • Compressive data: The simulations exhibit a phase transition from perfect recovery to complete failure in every subfigure.More samples allow recovery of more frequencies.
  • Compressive data: As MMV correlation increases, the successful-recovery phase decreases, yet MMVs substantially improve frequency recovery relative to the SMV case even under strong temporal correlations.The SMV case corresponds to the subfigure with completely correlated snapshots.
  • Compressive data: Successful recoveries occur above the sufficient-condition lines K = 1/2(M + L) for MMVs and K = 1/2(M + 1) for SMV.These lines are upper bounds associated with the atomic ℓ2,0 norm theorem.
  • The noisy case: In noisy simulations, ANM identifies the three frequencies in the SMV case and remains successful with uncorrelated and coherent MMVs, whereas MUSIC fails in the SMV and coherent-source cases.Spurious ANM components have about 0.4% of total power in the SMV case and on the order of 10^-6 in the two MMV cases.
  • The noisy case: The noisy simulations suggest robustness, but theoretical analysis of the noisy case is left for future studies.The proposed method takes about 1.5 seconds in each noisy scenario.
Loading 1405.6585v2…