Signal Recovery in Unions of Subspaces with Applications to Compressive Imaging

Nikhil Rao, Robert D. Nowak, Nowak, RobertarXiv 2012 · DOI · arXiv

Abstract

In applications ranging from communications to genetics, signals can be modeled as lying in a union of subspaces. Under this model, signal coefficients that lie in certain subspaces are active or inactive together. The potential subspaces are known in advance, but the particular set of subspaces that are active (i.e., in the signal support) must be learned from measurements. We show that exploiting knowledge of subspaces can further reduce the number of measurements required for exact signal recovery, and derive universal bounds for the number of measurements needed. The bound is universal in the sense that it only depends on the number of subspaces under consideration, and their orientation relative to each other. The particulars of the subspaces (e.g., compositions, dimensions, extents, overlaps, etc.) does not affect the results we obtain. In the process, we derive sample complexity bounds for the special case of the group lasso with overlapping groups (the latent group lasso), which is used in a variety of applications. Finally, we also show that wavelet transform coefficients of images can be modeled as lying in groups, and hence can be efficiently recovered using group lasso methods.

What Problem Does This Paper Address?

In the world of Compressed Sensing (CS), the golden rule is that you can recover a high-dimensional signal from very few measurements if the signal is "sparse" (mostly zeros). Standard CS theory tells us we need roughly $O(s \log p)$ measurements to recover a signal of length $p$ with $s$ non-zero entries.

However, real-world signals aren't just randomly sparse; they have structure. In genetics, genes in the same pathway often turn on or off together. In image processing, if a wavelet coefficient is large, its "children" in the wavelet tree are likely large too. While researchers have developed "Group Lasso" and "Union of Subspace" methods to exploit this, we lacked a rigorous, non-asymptotic understanding of exactly how many measurements are needed when these groups overlap. This paper fills that gap, providing a mathematical guarantee for structured recovery.

A signal modeled as a union of subspaces $S_1, S_2, S_3$, where $S_1$ is a plane and $S_2, S_3$ are lines.

Methods

The authors approach the problem using Atomic Norm Minimization. Instead of just using the standard $\ell_1$ norm (which treats every coefficient as independent), they define a new "atomic norm" based on the specific subspaces the signal is expected to inhabit.

To find the measurement bounds, they use a sophisticated geometric tool called Gaussian Widths. By calculating the width of the "tangent cone" of their atomic norm ball, they can determine the minimum number of random Gaussian measurements ($n$) required to ensure the recovery algorithm finds the unique, correct signal.

Key technical highlights include:

  • Generalizing the Latent Group Lasso: They show that the popular "latent group lasso" (used for overlapping groups) is actually a special case of their broader union-of-subspaces framework.
  • Wavelet Tree Modeling: They propose a novel way to group wavelet coefficients into parent-child pairs, allowing them to use convex optimization to recover images more efficiently than standard methods.

Key Insights and Ideas

  • The "Universal" Bound: The most striking finding is that the degree of overlap between subspaces does not affect the measurement bound. Whether your groups are perfectly distinct or heavily overlapping, the "price" you pay for recovery remains the same.
  • Orientation Matters, Not Composition: The number of measurements depends on the number of subspaces and their relative angles to one another (captured by the condition number $\kappa(K)$). If subspaces are nearly aligned, they are harder to distinguish, requiring more measurements. This is reflected in the geometry of the norm balls.
Norm balls for (a) perpendicular and (b) non-perpendicular subspaces, illustrating how orientation affects the geometry of the recovery problem.
  • Linearity in $k$ and $B$: The required measurements scale linearly with the number of active subspaces ($k$) and the maximum dimension of those subspaces ($B$). This mirrors the linear dependence on sparsity ($s$) in standard Lasso but offers a much tighter bound when the group structure is known.
  • Overlap is a "Recovery" Cost, Not a "Sampling" Cost: While overlapping groups don't require more measurements to capture the signal, they do make the reconstruction math harder, often requiring coefficient replication or more complex primal-dual solvers.

Key Results

  • Theoretical Efficiency: For a signal with $s$ non-zeros partitioned into groups of size $B$, the authors show their method requires roughly $(2s/B) \log(M) + s$ measurements. Compared to the standard Lasso's $2s \log(p)$, this represents a significant reduction, especially as the group size $B$ increases.
  • Empirical Superiority: In 1D tests, their "Glasso" (Latent Group Lasso) achieved exact recovery with ~380 measurements, while standard Lasso failed completely at the same level.
  • Imaging Performance: On the Microsoft image database, the proposed method consistently achieved lower Normalized Mean Square Error (NMSE) than standard CS tools (like SPGL1 or CoSaMP) and performed comparably to highly specialized, non-convex "Turbo" algorithms, while maintaining the reliability of a convex approach.
  • Noise Robustness: The method showed significantly better stability than standard Lasso when measurements were corrupted by noise, particularly when recovering piecewise constant signals.

Limitations and Future Work

  • Computational Complexity: The authors acknowledge that while their bounds are "universal," the actual recovery process for overlapping subspaces is more computationally expensive than standard sparse recovery.
  • Grouping Heuristics: For the imaging experiments, the authors used a simple parent-child pairing for wavelets. They note that finding the "best" way to group coefficients remains an open research question.
  • Gaussian Assumption: The current proof relies on i.i.d. Gaussian measurement matrices. While they mention this can be extended to "subgaussian" cases, the exact bounds for other common sensing matrices (like scrambled Fourier) aren't explicitly derived here.

Summary updated

Abstract

In applications ranging from communications to genetics, signals can be modeled as lying in a union of subspaces. Under this model, signal coefficients that lie in certain subspaces are active or inactive together. The potential subspaces are known in advance, but the particular set of subspaces that are active (i.e., in the signal support) must be learned from measurements. We show that exploiting knowledge of subspaces can further reduce the number of measurements required for exact signal recovery, and derive universal bounds for the number of measurements needed. The bound is universal in the sense that it only depends on the number of subspaces under consideration, and their orientation relative to each other. The particulars of the subspaces (e.g., compositions, dimensions, extents, overlaps, etc.) does not affect the results we obtain. In the process, we derive sample complexity bounds for the special case of the group lasso with overlapping groups (the latent group lasso), which is used in a variety of applications. Finally, we also show that wavelet transform coefficients of images can be modeled as lying in groups, and hence can be efficiently recovered using group lasso methods.
BibTeX
@misc{rao2012signal,
  author = {Nikhil Rao and Robert D. Nowak and Nowak, Robert},
  title = {{Signal Recovery in Unions of Subspaces with Applications to Compressive Imaging}},
  year = {2012},
  eprint = {1209.3079},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1209.3079},
}
Figure