Ferkans — Interactive Telecom Tutor

From Random to Structured Compressed Sensing

In FSI Ch 13, compressed sensing theory provides powerful recovery guarantees: if the sensing matrix satisfies the Restricted Isometry Property (RIP), then sparse signals can be recovered from far fewer measurements than the ambient dimension. The catch is that these guarantees are proven for random matrices (Gaussian, sub-Gaussian, random partial Fourier). Our physical sensing matrix $\mathbf{A}$ is highly structured, and the standard RIP results do not apply directly. This section examines what coherence and RIP-like properties $\mathbf{A}$ actually possesses, and what this means for sparse reconstruction in RF imaging.

Definition:
Mutual Coherence

The mutual coherence of a matrix $\mathbf{A} \in \mathbb{C}^{M \times N}$ with columns $\mathbf{A}_{1}, \ldots, \mathbf{A}_{N}$ is

$\mu(\mathbf{A}) = \max_{p \neq q} \frac{|\langle \mathbf{A}_{p}, \mathbf{A}_{q} \rangle|}{\|\mathbf{A}_{p}\| \|\mathbf{A}_{q}\|} = \max_{p \neq q} \frac{|[\mathbf{A}^{H}\mathbf{A}]_{pq}|}{\sqrt{[\mathbf{A}^{H}\mathbf{A}]_{pp} [\mathbf{A}^{H}\mathbf{A}]_{qq}}}.$

The coherence satisfies $\mu \in [0, 1]$ , with $\mu = 0$ meaning all columns are orthogonal and $\mu = 1$ meaning two columns are collinear (indistinguishable).

The Welch bound provides a lower limit:

$\mu(\mathbf{A}) \geq \sqrt{\frac{N - M}{M(N - 1)}}.$

For the overcomplete case $N > M$ (typical in imaging), the Welch bound is approximately $1/\sqrt{M}$ . Equiangular tight frames achieve this bound, but physical sensing matrices generally do not.

Theorem: Coherence-Based Recovery Guarantee

If $\mathbf{c}$ is $s$ -sparse and the mutual coherence satisfies

$s < \frac{1}{2}\left(1 + \frac{1}{\mu(\mathbf{A})}\right),$

then both Basis Pursuit (the $\ell_1$ relaxation) and OMP recover $\mathbf{c}$ exactly from $\mathbf{y} = \mathbf{A}\mathbf{c}$ in the noiseless case.

Low coherence means that no two columns of $\mathbf{A}$ point in nearly the same direction, so the contribution of any sparse component can be distinguished from every other. For RF imaging, this translates to the requirement that no two voxels produce nearly identical measurement signatures --- which fails when two voxels are too close together (within the resolution cell) or when grating lobes create ambiguities.

Proof

Connection to the exact recovery condition

The proof proceeds by showing that the coherence bound implies a diagonal dominance condition on the sub-matrix of $\mathbf{A}$ restricted to the support of $\mathbf{c}$ . Specifically, for any support set $S$ with $|S| = s$ , the sub-matrix $\mathbf{A}_{S}^{H}\mathbf{A}_{S}$ satisfies

$\sigma_{\min}(\mathbf{A}_{S}^{H}\mathbf{A}_{S}) \geq 1 - (s-1)\mu > 0$

when $s < 1 + 1/\mu$ , guaranteeing that $\mathbf{A}_{S}$ has full column rank and the sparse signal is identifiable. $\blacksquare$

Definition:
Restricted Isometry Property (RIP)

A matrix $\mathbf{A}$ satisfies the Restricted Isometry Property of order $s$ with constant $\delta_s \in [0, 1)$ if for all $s$ -sparse vectors $\mathbf{c}$ :

$(1 - \delta_s)\|\mathbf{c}\|_2^2 \leq \|\mathbf{A}\mathbf{c}\|_2^2 \leq (1 + \delta_s)\|\mathbf{c}\|_2^2.$

Equivalently, every $M \times s$ sub-matrix formed by selecting $s$ columns of $\mathbf{A}$ has all singular values in $[\sqrt{1 - \delta_s}, \sqrt{1 + \delta_s}]$ .

The RIP guarantees that $\mathbf{A}$ approximately preserves the $\ell_2$ norm of every sparse vector --- a far stronger condition than low coherence, which only controls pairwise column correlations. RIP with $\delta_{2s} < \sqrt{2} - 1$ is sufficient for exact recovery of $s$ -sparse signals via Basis Pursuit.

Example: Coherence of a ULA Sensing Matrix

A ULA with $N_{\text{virt}} = 32$ virtual elements at half-wavelength spacing images a scene of $N = 64$ angular bins uniformly spaced over $[-90^\circ, 90^\circ]$ . Compute the mutual coherence $\mu(\mathbf{A})$ .

Solution

Form the sensing matrix

The columns of $\mathbf{A}$ are steering vectors evaluated at the grid angles $\theta_q$ :

$[\mathbf{A}]_{n, q} = \frac{1}{\sqrt{N_{\text{virt}}}} e^{-j\pi n \sin\theta_q}, \quad n = 0,\ldots,31.$

This is a partial DFT matrix with non-uniform frequency sampling (due to the $\sin\theta_q$ mapping).

Compute pairwise coherence

The inner product between columns $p$ and $q$ is

$\langle \mathbf{A}_{p}, \mathbf{A}_{q} \rangle = \frac{1}{N_{\text{virt}}} \sum_{n=0}^{31} e^{j\pi n(\sin\theta_p - \sin\theta_q)} = \frac{1}{32} \cdot \frac{\sin(16\pi\Delta_u)}{\sin(\frac{\pi}{2}\Delta_u)}$

where $\Delta_u = \sin\theta_p - \sin\theta_q$ . The coherence is maximized by adjacent bins with $\Delta_u = 2/N = 1/32$ , giving

$\mu \approx \frac{|\sin(16\pi/32)|}{32|\sin(\pi/64)|} = \frac{|\sin(\pi/2)|}{32 \cdot \pi/64} \approx \frac{1}{32 \cdot 0.049} \approx 0.637.$

Interpretation

The coherence $\mu \approx 0.64$ is high compared to a random Gaussian matrix of the same size (which would have $\mu \approx 1/\sqrt{32} \approx 0.18$ ). This means the coherence-based sparsity bound allows recovery of at most $s < \frac{1}{2}(1 + 1/0.64) \approx 1.3$ --- essentially only a single scatterer can be guaranteed. In practice, algorithms perform much better than this worst-case bound suggests, because the high-coherence pairs are localized (adjacent bins only).

Theorem: RIP for Kronecker-Structured Matrices

Let $\mathbf{A} = \mathbf{A}_{2} \otimes \mathbf{A}_{1}$ where $\mathbf{A}_{k} \in \mathbb{C}^{m_k \times n_k}$ . If each factor satisfies the RIP of order $s_k$ with constant $\delta_{s_k}^{(k)}$ , then the Kronecker product satisfies the RIP of order $s_1 s_2$ with constant

$\delta_{s_1 s_2} \leq \delta_{s_1}^{(1)} + \delta_{s_2}^{(2)} + \delta_{s_1}^{(1)}\delta_{s_2}^{(2)}.$

In particular, if both factors have $\delta_{s_k} \leq \delta$ , then $\delta_{s_1 s_2} \leq 2\delta + \delta^2$ .

This result (Jokar and Mehta, 2009) shows that Kronecker products inherit RIP from their factors, with the sparsity level being multiplicative: if each factor handles $s_k$ -sparse signals, the product handles $s_1 s_2$ -sparse signals. The constant degrades additively, which is acceptable for moderate individual RIP constants.

Proof

Norm preservation bound

For any $(s_1 s_2)$ -sparse vector $\mathbf{c}$ reshaped as a matrix $\mathbf{C} \in \mathbb{C}^{n_1 \times n_2}$ with at most $s_1 s_2$ non-zeros:

$\|\mathbf{A}\mathbf{c}\|^2 = \|\mathbf{A}_{2} \mathbf{C} \mathbf{A}_{1}^{T}\|_F^2.$

The RIP of $\mathbf{A}_{1}$ applied column-wise and $\mathbf{A}_{2}$ applied row-wise gives upper and lower bounds that factor into the product of individual RIP constants. $\blacksquare$

Common Mistake: RIP Is Practically Unverifiable for Physical Matrices

Mistake:

Attempting to verify the RIP of the physical sensing matrix $\mathbf{A}$ by checking the condition number of all $\binom{N}{s}$ sub-matrices.

Correction:

RIP verification is NP-hard in general. For random matrices, RIP is proven probabilistically (all sub-matrices are well-conditioned with high probability). For the structured physical $\mathbf{A}$ , no such probabilistic argument is available. Instead, use the restricted eigenvalue condition (REC) or the compatibility condition, which are weaker but sufficient for LASSO recovery, and can be estimated numerically for specific geometries. Alternatively, the Kronecker RIP bound (Theorem 7.3.3) provides a constructive guarantee when the individual factors have verifiable RIP.

Random vs. Physical Sensing Matrix Properties

Property	Random Gaussian	Physical (Kronecker DFT)
Coherence $\mu$	$O(1/\sqrt{M})$ (near Welch bound)	$O(1/\sqrt[4]{M})$ or worse (high for nearby voxels)
RIP order $s$	$O(M/\log(N/s))$	Difficult to bound; depends on geometry
Condition number $\kappa$	$(\sqrt{N/M}+1)/(\sqrt{N/M}-1)$	Product of factor $\kappa$ values; can be very large
AMP convergence	Guaranteed (state evolution holds)	Can diverge; use OAMP instead (Ch 17)
Storage	$O(MN)$	$O(\sum m_k n_k)$ via Kronecker
Matvec cost	$O(MN)$	$O(N^{4/3})$ or $O(N\log N)$ via FFT

Quick Check

A sensing matrix has mutual coherence $\mu = 0.5$ . The coherence-based guarantee ensures exact sparse recovery for sparsity up to what level?

$s < 1.5$ (i.e., only $s = 1$ )

$s < 3$

$s < 10$

No guarantee exists

Correction:

s < 1.5

(i.e., only

s = 1

)

$s < \frac{1}{2}(1 + 1/\mu) = \frac{1}{2}(1 + 2) = 1.5$ , so the guarantee holds for $s = 1$ only.

Restricted Isometry Property (RIP)

A property of a matrix requiring that it approximately preserves the $\ell_2$ norm of every $s$ -sparse vector, with distortion bounded by a constant $\delta_s < 1$ . The RIP is a sufficient condition for stable sparse recovery via $\ell_1$ minimization and other compressed sensing algorithms.

Mutual coherence

The maximum absolute normalized inner product between any two distinct columns of a matrix. Low coherence ( $\mu \ll 1$ ) indicates that the measurement signatures of different voxels are distinct, which is favorable for sparse recovery.

Related: {{Ref:Gloss Rip}}

Historical Note: Compressed Sensing Meets Imaging

2007--present

The application of compressed sensing to imaging was pioneered independently by Lustig, Donoho, and Pauly (2007) for MRI and by Baraniuk and Steeghs (2007) for radar. The key insight was that natural images are sparse in some transform domain (wavelets, total variation), and structured sensing matrices arising from physics (partial Fourier, steering vectors) can satisfy weakened forms of the RIP. However, the gap between the theoretical guarantees (derived for random matrices) and practical performance (on structured matrices) remains significant. Bridging this gap for RF imaging is an active area of CommIT research.

Key Takeaway

The physical sensing matrix $\mathbf{A}$ has high mutual coherence (DFT-like columns) compared to random matrices. Standard compressed sensing guarantees based on coherence or RIP are pessimistic for structured operators. For Kronecker products, the RIP constant degrades additively while the sparsity level multiplies across factors. Algorithms designed for random matrices (AMP) can fail on $\mathbf{A}$ ; use OAMP or other structure-aware methods instead.

Coherence and RIP for Structured Sensing Matrices