TL;DR
This paper introduces SPARROW, a more computationally efficient reformulation of the mixed-norm minimization problem for jointly sparse signal reconstruction from multiple measurement vectors. SPARROW significantly reduces the problem size by focusing on row-norms, leading to faster estimation and enabling gridless parameter estimation.
What Problem Does This Paper Address?
Many real-world applications, such as radar and communications, involve analyzing signals captured by multiple sensors over time, often referred to as Multiple Measurement Vectors (MMVs). A common challenge is to reconstruct a signal that is "jointly sparse," meaning it has a similar sparse structure across these multiple measurements. Traditional methods for this, like the $\ell_{2,1}$ mixed-norm minimization, become computationally very expensive as the number of measurements or the desired signal resolution increases. This paper aims to tackle this computational bottleneck by developing a more compact and efficient formulation for jointly sparse signal reconstruction.
Methods
The core contribution is the development of the SPARROW (SPARse ROW-norm reconstruction) formulation. Instead of directly estimating the large, jointly sparse signal matrix, SPARROW reformulates the problem to estimate the row-norms of this matrix. This is achieved by leveraging a compact parameterization.
Key methodological aspects include:
- Compact Reformulation: The $\ell_{2,1}$ mixed-norm minimization problem is transformed into an equivalent problem that operates on a much smaller set of variables (the row-norms).
- Closed-Form Reconstruction: Once the sparse row-norms are estimated, the original jointly sparse signal matrix can be reconstructed in closed-form.
- Gridless Estimation: For uniform linear arrays, SPARROW is extended to enable gridless parameter estimation using semidefinite programming (SDP). This means it doesn't require pre-defined frequency grids, which can lead to spectral leakage.
- Coordinate Descent Implementation: For scenarios with a large number of sensors, a low-complexity grid-based implementation using the coordinate descent method is proposed. This avoids the computational burden of SDPs.
- Equivalence Proofs: The paper rigorously proves the equivalence between the proposed SPARROW formulation and existing methods like atomic norm minimization and SPICE, providing theoretical links and insights.
Datasets
Not discussed in the paper. The paper focuses on theoretical development and simulation-based evaluation using synthetic data generated according to the described signal model.
Key Insights and Ideas
- Row-Norms as Key: The crucial insight is that the support (the locations of non-zero rows) of the jointly sparse signal is fully encoded in the row-norms. Estimating these row-norms directly is far more efficient than estimating the entire signal matrix.
- Covariance Matrix Suffices: SPARROW demonstrates that the support of the signal matrix can be recovered using only the sample covariance matrix, rather than the instantaneous MMVs themselves. This is a significant advantage when the number of MMVs is large.
- Unification of Methods: The paper establishes clear theoretical links and equivalences between SPARROW, atomic norm minimization, and SPICE, offering a unified perspective on these different sparse recovery techniques.
- Computational Advantage: The compact formulation leads to a substantial reduction in computational complexity, particularly for scenarios with many measurement vectors.
Key Results
- Computational Speedup: Simulations show that SPARROW significantly outperforms existing methods (like $\ell_{2,1}$ mixed-norm and atomic norm minimization) in terms of computation time, especially for a large number of MMVs. For gridless methods, SPARROW is up to 2x faster than ANM.
- Gridless Performance: The gridless SPARROW (GL-SPARROW) method demonstrates competitive performance in terms of estimation bias and variance, particularly for closely spaced sources.
- Resolution Capability: GL-SPARROW achieves high resolution percentages, comparable to root-MUSIC, and outperforms other sparse methods in resolving closely spaced sources.
- Bias Trade-off: While SPARROW offers computational advantages and good resolution, it can exhibit a larger bias for very closely spaced frequencies, a trade-off common in sparse estimation methods.
Limitations and Future Work
- Regularization Parameter Selection: The paper acknowledges that the optimal selection of the regularization parameter ($\lambda$) for SPARROW is an open research problem. The study uses a heuristic approach for parameter selection.
- Bias Mitigation: For gridless estimation, the inherent bias for closely spaced frequencies can be addressed by bias mitigation techniques or a final maximum likelihood estimation step, which are mentioned as potential future directions.
- General Array Geometries: While the paper presents gridless SPARROW for uniform linear arrays (ULAs), extensions to arbitrary array geometries are discussed, but the primary focus remains on ULAs for gridless aspects.
- Rank Awareness: The paper briefly mentions that rank awareness can improve MMV-based SSR performance, a concept not fully explored within the SPARROW framework itself.
Summary updated