Abstract
Traditional approaches to the Multiple Measurement Vector (MMV) problem often treat it as a collection of independent Single Measurement Vector (SMV) problems, failing to exploit the diversity across channels. This paper reveals that the rank of the signal matrix is a critical "hidden superpower" in joint sparse recovery. By introducing "rank-aware" techniques inspired by array signal processing, the authors demonstrate that signals can be perfectly recovered from significantly fewer measurements than previously thought possible, provided the signal matrix has high rank.
Introduction
In compressed sensing, the goal is typically to recover a sparse vector from a limited set of linear measurements (the SMV problem). The Multiple Measurement Vector (MMV) problem extends this to recovering a matrix $\mathbf{X}$ where all columns share a common sparsity pattern, known as joint sparsity.
Prior to this work, the prevailing wisdom suggested that MMV did not offer significantly better worst-case guarantees than SMV because, in the worst case, all channels might be identical (rank 1). The authors argue that this "rank-blind" perspective ignores a massive opportunity: if the channels are diverse (high rank), we should be able to recover much denser signals with fewer measurements. This paper bridges the gap between compressed sensing and array signal processing to provide the theoretical and algorithmic tools necessary to exploit this rank diversity.
Theoretical Foundations of Rank Awareness
The authors derive new necessary and sufficient conditions for uniqueness that explicitly incorporate the rank of the signal matrix. A key breakthrough is the shift from the standard $2k$ rule to a $k+1$ rule. In standard compressed sensing, one generally needs $m \ge 2k$ measurements to guarantee the unique recovery of a $k$-sparse signal. However, this paper proves that if the signal matrix $\mathbf{X}$ is full rank (i.e., $rank(\mathbf{X}) = k$), unique recovery is possible with only $m = k+1$ measurements.
This theoretical advancement is supported by analyzing specific matrix structures, such as the one illustrated in Figure 1, to identify the fundamental limits of recovery when rank and sparsity interact. Furthermore, the authors mathematically prove that popular methods like Simultaneous Orthogonal Matching Pursuit (SOMP) and mixed-norm ($\ell_{1,q}$) minimization are fundamentally "rank-blind," as their performance is bottlenecked by the rank-1 case regardless of actual channel diversity.
Proposed Methods
To leverage rank diversity, the authors propose two primary algorithms:
- Rank-Aware Thresholding (RA-Thresholding): This method adapts the MUSIC (MUltiple SIgnal Classification) algorithm from array signal processing into a discrete thresholding method. It uses a Singular Value Decomposition (SVD) of the measurements to identify the signal subspace and select the most likely atoms from the dictionary. It is extremely efficient, requiring only a single SVD.
- RA-ORMP (Rank-Aware Order Recursive Matching Pursuit): This is the flagship algorithm of the paper. Standard greedy pursuits like SOMP suffer from "rank degeneration," where the rank of the residual signal drops after each step, losing the rank advantage. RA-ORMP fixes this by projecting and renormalizing the dictionary at each step, maintaining rank awareness throughout the pursuit.
Key Results and Insights
The paper validates these concepts through synthetic numerical experiments using random Gaussian dictionaries.
- Performance Gap: In tests with 32 measurements ($m=32$) and 32 channels ($l=32$), RA-ORMP achieved perfect recovery for sparsity levels up to $k=31$. In contrast, SOMP's performance plateaued at $k \approx 11$, failing to improve even as more channels were added.
- Subspace Geometry: The core insight is that high-rank measurements provide a "view" of the entire signal subspace. If the subspace is known, finding the sparse support becomes a matter of identifying which dictionary atoms lie within that subspace.
Conclusion and Future Work
This research demonstrates that rank awareness is essential for optimal joint sparse recovery. While the current analysis focuses on the noiseless case, the robustness of MUSIC-based methods suggests potential for practical applications in noisy environments. Future work includes quantifying noise sensitivity and attempting to formulate a convex optimization problem that can naturally interpolate between the rank-1 and full-rank regimes.
Summary updated