PaperlayerView exact revision on arXiv

Source-linked AI summary

Robust Recovery of Signals From a Structured Union of Subspaces

Yonina C. Eldar, Moshe Mishali

arXiv:0807.4581v2nlin.CGcs.ITnlin.SI

TL;DR

The paper addresses robust recovery when a signal lies in an unknown structured union of subspaces rather than a known subspace. It reformulates the problem as block-sparse recovery and proposes a mixed ℓ2/ℓ1 convex program. Block-RIP conditions guarantee exact recovery and stability under noise and modelling errors, with extensions to MMV signals.

  • Problem

    The paper studies recovery when x lies in a sum of k subspaces selected from m possibilities, with the active subspaces unknown.

  • Method

    The approach converts structured-union recovery into block-sparse recovery and uses a mixed ℓ2/ℓ1 convex program, formulated as an SOCP.

  • Results

    Block-RIP conditions guarantee exact recovery and stability in the presence of noise and modelling errors.

  • Takeaways & Limitations

    The framework provides efficient and robust recovery algorithms for finite structured unions of subspaces and extends to MMV signals with joint sparsity.

  • Takeaways & Limitations

    The analysis assumes a finite union of subspaces and finite-dimensional underlying spaces.

Abstract

from arXiv · show

Traditional sampling theories consider the problem of reconstructing an unknown signal $x$ from a series of samples. A prevalent assumption which often guarantees recovery from the given measurements is that $x$ lies in a known subspace. Recently, there has been growing interest in nonlinear but structured signal models, in which $x$ lies in a union of subspaces. In this paper we develop a general framework for robust and efficient recovery of such signals from a given set of samples. More specifically, we treat the case in which $x$ lies in a sum of $k$ subspaces, chosen from a larger set of $m$ possibilities. The samples are modelled as inner products with an arbitrary set of sampling functions. To derive an efficient and robust recovery algorithm, we show that our problem can be formulated as that of recovering a block-sparse vector whose non-zero elements appear in fixed blocks. We then propose a mixed $\ell_2/\ell_1$ program for block sparse recovery. Our main result is an equivalence condition under which the proposed convex algorithm is guaranteed to recover the original signal. This result relies on the notion of block restricted isometry property (RIP), which is a generalization of the standard RIP used extensively in the context of compressed sensing. Based on RIP we also prove stability of our approach in the presence of noise and modelling errors. A special case of our framework is that of recovering multiple measurement vectors (MMV) that share a joint sparsity pattern. Adapting our results to this context leads to new MMV recovery methods as well as equivalence conditions under which the entire set can be determined efficiently.

Union of Subspaces

The paper develops efficient, robust recovery for signals in finite-dimensional structured unions of subspaces by converting the problem into block-sparse recovery. A mixed ℓ2/ℓ1 method and block-RIP conditions provide exact and stable recovery, including MMV extensions.

  • Problem setting: The framework targets signals in a sum of k unknown subspaces selected from m finite-dimensional possibilities.The subspaces comprising the sum are not known in advance.
  • Block-sparse formulation: Recovery over the structured union is cast as sparse recovery with nonzero coefficients appearing in fixed blocks.Exploiting this block structure can permit recovery under more general conditions than standard sparsity.
  • Convex recovery: The proposed block-sparse algorithm minimizes a mixed ℓ2/ℓ1 norm and can be formulated as a convex second order cone program.The resulting SOCP can be solved efficiently using standard software packages.
  • Recovery guarantees: Block-RIP conditions guarantee recovery by the convex algorithm and provide stability under noise and modelling errors.The results also establish stable approximation to the best block-k sparse solution when noise or modelling errors are present.
  • Random measurements: Random measurement matrices satisfy block-RIP with overwhelming probability, with a substantially larger probability than standard RIP.Thus finite structured unions can be recovered efficiently and stably from suitable random measurements.
  • MMV extension: For MMV signals with a shared sparsity pattern, the block-sparse formulation yields RIP-based conditions and sampling methods with superior recovery rates.The MMV equivalence condition is stronger than in the single-measurement setting.

II. UNION OF SUBSPACES

Sampling measurements may not uniquely determine a signal when the sampling vectors fail to span the ambient space. Prior subspace information can restore uniqueness under an appropriate intersection condition.

  • Sampling model: Linear samples are inner products with sampling functions and can be written as y = S^T x in finite-dimensional spaces.A set-transformation notation extends this representation to abstract Hilbert spaces.
  • Nonuniqueness: If the sampling vectors do not span the entire space, multiple signals can produce the same measurements.Adding any vector in the orthogonal complement of the sampling space leaves the samples unchanged.
  • Subspace prior: Prior knowledge that x lies in a subspace can guarantee uniqueness despite incomplete sampling.When the subspace and sampling space have equal finite dimension and intersect orthogonally only at zero, exact recovery follows.

B. Union of Subspaces

The paper specializes union-of-subspaces recovery to sums of disjoint subspaces and connects this model to block sparsity. It then develops efficient convex recovery with block-RIP-based uniqueness, stability, and robustness guarantees.

  • Union model: The model represents x as belonging to a union of subspaces, while the particular subspace containing x is unknown.The union is generally not itself a subspace.
  • Structured model: Each union element is formed by summing k subspaces from a finite set of m disjoint subspaces with finite dimensions.This structured subclass is the setting analyzed for stable recovery algorithms.
  • Block-sparse connection: The recovery task is equivalent to recovering a block-sparse coefficient vector whose active blocks identify the component subspaces.The signal is reconstructed from the recovered block coefficients.
  • Special cases: The framework includes standard compressed sensing, block sparsity, and MMV with jointly sparse rows as special cases.For MMV, vectorizing the transposed coefficient matrix produces a k-block sparse vector.
  • Recovery objectives: The paper addresses sampling conditions, uniqueness, and efficient stable recovery through convex algorithms under appropriate conditions on sampling functions and subspaces.These algorithms fill the gap between prior invertibility results and concrete recovery procedures.
  • Guarantees: Block-RIP ensures uniqueness and stability, while the proposed optimization exactly recovers block-sparse coefficients and approximates the best block-k sparse solution under errors.The method remains meaningful in the presence of noise and modelling errors.

III. CONNECTION WITH BLOCK SPARSITY

The union-of-subspaces model is equivalent to recovering a vector whose nonzero coefficients occupy at most k fixed blocks. This correspondence enables block-sparse formulations of sampling, uniqueness, and stability.

  • Union model and block representation: Any signal in a sum of k selected subspaces can be represented as x = Ac with at most k nonzero coefficient blocks.The selected subspaces determine which coefficient blocks are active, but their indices are unknown in advance.
  • Union model and block representation: The nonzero elements of c occur in blocks, distinguishing this model from arbitrary sparsity patterns.Block lengths are determined by the dimensions of the candidate subspaces.
  • Recovery formulation: There is a one-to-one correspondence between signals in the union and block-sparse coefficient vectors, so recovery can be posed as recovering c from y = Dc.Changing the bases within subspaces preserves the block-sparsity pattern.
  • Uniqueness and stability: A unique block-k-sparse vector is determined by y = Dc exactly when no nonzero block-2k-sparse vector lies in the nullspace of D.The difference between two block-k-sparse candidates is block-2k-sparse, yielding the uniqueness condition.
  • Uniqueness and stability: Stability requires uniform lower and upper norm bounds on D over block-2k-sparse vectors, which imply both invertibility and stability.The ratio of these bounds measures the stability of the sampling operator.

A. Block RIP

Block RIP restricts isometry requirements to vectors whose nonzero entries follow the known block structure. This can produce weaker conditions than standard RIP while supporting uniqueness and efficient recovery.

  • Definition and implications: Block RIP requires norm preservation for every block-k-sparse vector over the prescribed block partition.The paper abbreviates the block-RIP constant δk|I as δk when the context is clear.
  • Definition and implications: If D satisfies block RIP with δ2k < 1, the measurements uniquely determine the block-sparse vector.This follows because the condition excludes nonzero block-2k-sparse vectors from the nullspace.
  • Comparison with standard RIP: Block RIP examines only structured supports, whereas standard RIP also includes sparse vectors whose nonzero entries do not align with blocks.Consequently, the block-RIP constant can be smaller than the corresponding standard-RIP requirement.
  • Comparison with standard RIP: For a three-block example with two columns per block, standard RIP gives δ2 = 0.866, while block RIP gives δ1|I = 0.289 for one-block supports.The example illustrates the tighter constant obtained by exploiting support structure.
  • Comparison with standard RIP: For four nonzero entries restricted to two blocks, standard RIP fails for every δ4 < 1, while δ2|I = 0.966 still guarantees unique block-sparse recovery.Thus structured measurements can remain identifiable even when unrestricted sparse recovery is not.
  • Efficient recovery condition: Under a stronger condition on δ2k, the proposed approach recovers the coefficient vector in a stable and efficient manner instead of using exponential search.The exhaustive search is conceptually valid but computationally inefficient.

V. CONVEX RECOVERY ALGORITHM

The paper replaces exhaustive block-support search with a mixed ℓ2/ℓ1 convex program formulated as an SOCP. Under a suitable block-RIP condition, the program uniquely and exactly recovers the block-sparse coefficients.

  • Convex formulation: The convex method minimizes the sum of the ℓ2 energies of coefficient blocks, yielding a mixed ℓ2/ℓ1 recovery objective.Introducing ti = ∥c[i]∥2 converts the problem into a second-order cone program solvable with standard software.
  • Recovery guarantee: The theorem establishes three linked facts: a unique block-k-sparse vector exists, the SOCP has a unique solution, and that solution equals c0.These conclusions hold under the theorem’s block-RIP hypothesis.
  • Comparison with standard recovery: The SOCP exploits fixed block locations, unlike standard ℓ1 recovery, which treats all individual coefficient positions as interchangeable.The block-aware condition can therefore be less stringent than the corresponding standard compressed-sensing condition.
  • Proof strategy: The proof exploits block decompositions of the error and mixed-norm inequalities before applying block RIP to force the recovery error to zero.This adapts standard compressed-sensing arguments to blocks of potentially different sizes.

B. Robust Recovery

The robust formulation modifies the convex program to handle noisy measurements and signals that are not exactly block-k-sparse. It bounds recovery error and approaches the best block-k-sparse approximation under block RIP.

  • Robust formulation: The robust setting considers bounded measurement noise together with coefficient vectors that may violate exact block-k-sparsity.The modified SOCP remains feasible for noisy observations.
  • Approximation guarantee: The best block-k-sparse approximation ck minimizes ∥c0 − d∥2,I over all block-k-sparse d.This approximation is the target when c0 is not exactly block-k-sparse.
  • Error sources: The recovery error contains separate contributions from model mismatch and measurement noise.The first term reflects the failure of exact block-k-sparsity, while the second quantifies noise-induced error.
  • Approximation guarantee: Under block RIP, the modified SOCP approximates the best block-k-sparse solution even with noisy measurements and model mismatch.The paper summarizes this as stability with recovery error bounded by the noise level, together with approximation of non-block-sparse signals.

C. Advantage of Block Sparsity

Block-sparsity structure can make recovery succeed when standard sparsity information is insufficient. Experiments show that the mixed ℓ2/ℓ1 method exploits this structure to outperform standard ℓ1 minimization.

  • Block sparsity restricts non-zero entries to predefined regions, unlike standard sparsity, which permits them anywhere.
  • RIP-based analysis provides finite-dimensional uniqueness and equivalence conditions, whereas prior block-sparse analysis focused on asymptotic noise-free recovery.
  • The mixed ℓ2/ℓ1 program explicitly incorporates block structure, unlike standard basis pursuit.
  • The mixed method recovers a block-sparse signal exactly in an example where standard ℓ1 minimization fails.The signal is 4-sparse with non-zeros known to occur in blocks of length 2; standard ℓ1 returns an incorrect vector.
  • Across 500 random experiments, incorporating block structure improves recovery over standard basis pursuit.The experiment uses a 25 × 50 Gaussian matrix, block length 5, and 1 ≤ k ≤ 25 non-zero entries.
  • Block-sparse recovery remains roughly constant over block length, explaining its advantage over standard sparse recovery in the example.

VI. APPLICATION TO MMV MODELS

The paper specializes block-sparse recovery and equivalence results to MMV problems with jointly sparse measurement vectors. It derives RIP-based results and a measurement strategy whose performance can improve over conventional MMV methods, including in worst-case analysis.

  • The MMV specialization yields an RIP-based equivalence result for a mixed-norm recovery algorithm.
  • A new MMV measurement strategy improves performance over conventional methods in simulations and under an RIP-based equivalence condition.
  • The proposed strategy guarantees improved performance over single-measurement recovery even for the worst possible X.

A. Equivalence Results

MMV recovery can be recast as block-sparse recovery by vectorizing the unknown matrix and forming consecutive blocks. This yields RIP-based equivalence conditions, while the separable measurement model limits worst-case gains from additional measurement vectors.

  • MMV recovery models Y = MX with at most k non-zero rows in X, corresponding to block sparsity after vectorization.
  • The vectorized measurements satisfy y = Dc with D = M^T ⊗ I_d, linking the MMV model to the block-sparse recovery program.
  • For block-sparse vectors, the matrix inequality in (65) is equivalent to the standard RIP condition for 2k-sparse vectors.
  • If M satisfies conventional RIP, the mixed-norm MMV program recovers X, under a condition also sufficient for separate column-wise ℓ1 recovery.
  • Joint processing improves practical recovery, but known equivalence conditions do not capture that gain because D = M^T ⊗ I_d has separable structure.
  • In the worst case, choosing every x_i equal makes all observation vectors equal, so separable MMV measurements cannot improve over the single-measurement setting.

B. Improved MMV Recovery

The paper proposes dense, unstructured measurements for MMV recovery because block-RIP conditions can be weaker than standard RIP. This measurement redesign improves practical and worst-case performance, but increases computational complexity.

  • Dense measurements can improve worst-case MMV behavior over single-channel measurements without relying on randomness in the unknown vectors.
  • The alternative measurement design changes the measurement process rather than introducing a new recovery algorithm.
  • Average-case analysis predicts improved performance as the number of measurement vectors increases because equal unknown vectors have zero probability.
  • For arbitrary unstructured D, block-RIP requirements are weaker than standard RIP requirements for recovering k-sparse vectors.
  • The tradeoff is increased computational complexity because each measurement depends on all input vectors.

VII. RANDOM MATRICES

The section analyzes block-RIP constants for random matrices, establishing probabilistic guarantees and comparing block structure with standard RIP. It shows that block structure can improve recovery conditions and reduce the required number of measurements, while theoretical sparsity predictions remain pessimistic.

  • Probabilistic guarantees: A sufficiently small block-RIP constant δ2k|I guarantees exact recovery under the paper’s convex recovery conditions.The random-matrix analysis bounds the probability that δk|I exceeds a threshold and shows exponential decay.
  • Unequal block lengths: For unequal block lengths, the probability bound is governed by the maximal block length and becomes less stringent as max(di)/min(di) grows.The equal-length assumption simplifies the proof; the unequal-length extension uses d = max(di).
  • Block-RIP advantage: For fixed problem dimensions and d > 1, block-RIP constants are smaller than standard RIP constants.The improvement follows from the additional block-structure exponent in the bound.
  • Block-RIP advantage: Block structure lets a wider range of sparsity ratios satisfy Theorem 1 than standard RIP.The comparison uses d = 1 as the standard-RIP case and evaluates several sampling rates and block structures.
  • Empirical comparison: Theoretical absolute sparsity ratios are pessimistic, although brute-force Gaussian experiments qualitatively find block-RIP constants more likely to be smaller than standard RIP constants.The empirical comparison averages results over random Gaussian matrix instances and remains qualitative for relatively small dimensions.
  • Measurement requirements: For block-sparse signals with nonzero fraction r = kd/N, roughly n ≈ k log(m/k) = −k log(r) measurements are needed.The corresponding standard-RIP requirement is larger: n ≈ −kd log(r).

VIII. CONCLUSION

The paper develops efficient, robust recovery for signals in a structured union of subspaces by reducing the problem to block-sparse recovery and using convex optimization with block-RIP guarantees. The framework provides stable recovery under noise and mismodeling, extends to MMV systems, and is limited by its finite-dimensional assumptions.

  • Problem formulation: Recovery over a structured union of subspaces is reduced to recovering a block-sparse vector from linear measurements.The nonzero entries are grouped into fixed blocks, reflecting the subspace structure.
  • Recovery method: The measurement matrix is formed as D = S* A, and the coefficient vector is recovered with a mixed ℓ2/ℓ1 SOCP.A corresponds to a basis for the sum of the component subspaces.
  • Guarantees: Block-RIP conditions guarantee perfect recovery and stable approximation under noise, while also controlling recovery when the signal is not exactly block-sparse.The same conditions support approximation to the best block-sparse representation.
  • Guarantees: Random measurement matrices satisfy the recovery conditions with high probability, and the results ensure stable recovery under signal mismodeling.The guarantees are non-asymptotic.
  • MMV extension: Specializing the framework to MMV systems yields a sampling method that can improve recovery rates and equivalence results for RIP-based MMV algorithms.The MMV problem is treated through block-sparse recovery with a joint sparsity structure.
  • Scope and future work: The framework assumes finite unions of finite-dimensional subspaces, motivating future work on possibly infinite unions and infinite-dimensional spaces.The authors propose combining this framework with prior infinite-dimensional sparse-recovery results.
Loading 0807.4581v2…