PaperlayerView exact revision on arXiv

Source-linked AI summary

Reduce and Boost: Recovering Arbitrary Sets of Jointly Sparse Vectors

Moshe Mishali, Yonina C. Eldar

arXiv:0802.1311v1nlin.CG

TL;DR

Recovering an infinite set of jointly sparse vectors is difficult because existing methods target finite vector collections. The paper reduces the task to finite-dimensional MMV recovery and then to single-vector sparse recovery, with exact recovery for countable and uncountable sets and improved empirical performance from boosting.

  • Problem

    Existing sparse-recovery methods do not directly address possibly infinite sets of jointly sparse vectors, making recovery of their common support difficult.

  • Method

    The paper reduces infinite-set recovery to a finite-dimensional MMV problem, then randomly combines measurement vectors to obtain a single sparse-vector problem and applies empirical boosting.

  • Results

    The approach exactly recovers countable and uncountable sets without discretization, while experiments report higher recovery rates and faster or superior performance than comparison methods.

  • Takeaways & Limitations

    The framework provides a direct reduction for arbitrary jointly sparse sets and improves practical sparse-vector recovery through boosting.

Abstract

from arXiv · show

The rapid developing area of compressed sensing suggests that a sparse vector lying in an arbitrary high dimensional space can be accurately recovered from only a small set of non-adaptive linear measurements. Under appropriate conditions on the measurement matrix, the entire information about the original sparse vector is captured in the measurements, and can be recovered using efficient polynomial methods. The vector model has been extended to a finite set of sparse vectors sharing a common non-zero location set. In this paper, we treat a broader framework in which the goal is to recover a possibly infinite set of jointly sparse vectors. Extending existing recovery methods to this model is difficult due to the infinite structure of the sparse vector set. Instead, we prove that the entire infinite set of sparse vectors can recovered by solving a single, reduced-size finite-dimensional problem, corresponding to recovery of a finite set of sparse vectors. We then show that the problem can be further reduced to the basic recovery of a single sparse vector by randomly combining the measurement vectors. Our approach results in exact recovery of both countable and uncountable sets as it does not rely on discretization or heuristic techniques. To efficiently recover the single sparse vector produced by the last reduction step, we suggest an empirical boosting strategy that improves the recovery ability of any given sub-optimal method for recovering a sparse vector. Numerical experiments on random data demonstrate that when applied to infinite sets our strategy outperforms discretization techniques in terms of both run time and empirical recovery rate. In the finite model, our boosting algorithm is characterized by fast run time and superior recovery rate than known popular methods.

I. INTRODUCTION

The paper extends jointly sparse recovery from finite MMV sets to countable or uncountable IMV sets, using exact reductions rather than discretization. It then reduces MMV recovery to SMV recovery and adds boosting to improve practical recovery performance.

  • I. INTRODUCTION: The paper introduces infinite measurement vectors (IMV), an infinite set of jointly sparse vectors that generalizes the finite MMV model.The set may be countable or uncountable and can arise in recovery problems involving analog signals.
  • I. INTRODUCTION: Discretizing an infinite vector set cannot guarantee perfect recovery, motivating a reduced finite-dimensional formulation.The formulation infers the common non-zero location set exactly without discretizing the model or solution.
  • I. INTRODUCTION: For every IMV problem, the paper constructs an MMV counterpart with the same non-zero location set without discretization or heuristic techniques.This reduction permits, in principle, exact recovery of the entire sparse-vector set and allows MMV recovery results to be applied.
  • I. INTRODUCTION: A second theoretical reduction randomly combines MMV measurement vectors into an SMV problem while preserving the non-zero location set with probability one.The random coefficients merge the measurement vectors into a sparse vector suitable for SMV recovery.
  • I. INTRODUCTION: The ReMBo algorithm repeatedly samples random combinations because sub-optimal SMV recovery depends on exact coefficient values, not only locations.Empirically, each boost iteration improves the overall recovery rate of the non-zero location set.
  • I. INTRODUCTION: Numerical experiments report advantages over familiar MMV techniques in empirical recovery rate and run time, including an advantage over discretization for IMV reduction.The paper presents a complete flow from IMV or MMV recovery through SMV recovery and boosting.

II. INFINITE-MEASUREMENT-VECTORS MODEL

The IMV model seeks to recover an arbitrary finite or infinite set of jointly sparse vectors from their measurements. Joint sparsity supplies the prior needed to address the underdetermined linear system.

  • Model formulation: Because m < n, each measurement vector has fewer equations than unknowns, so an additional prior is required for unique recovery.The prior resolves the non-uniqueness of the unconstrained linear system.
  • Model formulation: The IMV model recovers x(Λ) from y(Λ) when Λ may be finite, countably infinite, or uncountable.The parameter may index a discrete set or vary over a continuous interval.
  • Model formulation: Each vector is sparse, and all vectors share a common non-zero location set of size at most K.This is the joint sparsity prior used throughout the IMV model.
  • Model formulation: The IMV system is the infinite-Λ version of the parametric linear system, while the single-element case is the SMV model.The finite multi-vector case is called MMV when the joint sparsity prior holds.
  • Notation and SMV background: A K-sparse vector has at most K non-zero entries, and its support records the locations of those entries.The Kruskal-rank σ(A) is defined as the largest number of columns that are always linearly independent.

B. Uniqueness in IMV Models

The IMV uniqueness result uses the measurement-set span dimension and can require a lower Kruskal-rank than the standard SMV condition. The resulting guarantee applies to the entire jointly sparse solution set.

  • Definitions: The support of a vector set is the union of the supports of its individual vectors.A jointly K-sparse set therefore has a common non-zero location set of size no more than K.
  • Uniqueness condition: Proposition 1 gives a sufficient Kruskal-rank condition for a K-sparse IMV solution set to be unique.The proposition extends uniqueness results for finite multiple-measurement-vector systems.
  • Proof idea: The span of y(Λ) has finite dimension, and selecting a finite linearly independent subset converts the corresponding measurements into an MMV system.The proof then establishes uniqueness for the selected subset and extends it to the full solution set.
  • Uniqueness condition: The required Kruskal-rank can generally be lower than 2K, the sufficient bound for separately treating each vector as an SMV problem.Joint sparsity is what permits exploiting structure shared across vectors.
  • Implication: The uniqueness guarantee is useful for recovery design, but its condition depends on dim(span(y(Λ))), which is not known a priori.Guaranteeing uniqueness for every K-sparse solution set reverts to the 2K-type condition.

III. DIMENSION REDUCTION FOR INFINITE Λ

The infinite-dimensional IMV optimization problem is difficult because it contains infinitely many unknowns and equations. The paper avoids discretization by reducing it exactly to finite MMV recovery.

  • Optimization viewpoint: The IMV optimization formulation has infinitely many unknowns and equations and was not analyzed in the existing optimization literature.Related semi-infinite formulations instead have infinite constraints but finite optimization variables.
  • Dimension reduction: The joint sparsity prior converts the IMV problem into an MMV-form problem with finite-dimensional variables and constraints.This transformation addresses the intrinsic difficulty of the infinite formulation.
  • Discretization baseline: Discretization selects a finite grid, solves the resulting MMV problem, and interpolates the partial solution to approximate x(Λ).The finite problem can be relaxed using known compressed-sensing techniques.
  • Discretization baseline: A discretized solution can differ from the unique solution and typically fails to satisfy the original system between grid points.This issue occurs for parameter values outside the selected grid.
  • Exact reduction: The exact method transforms the infinite structure into a single MMV system without losing information, avoiding grid-density-dependent complexity.The paper includes a numerical experiment comparing the exact method with discretization.

B. Paradigm

The recovery framework reduces jointly sparse vector sets to finite-dimensional problems, ultimately identifying the common support through a single sparse-recovery task. It applies to finite and infinite models, including countable and uncountable sets, under stated uniqueness and energy conditions.

  • Reduction paradigm: The method separates support identification from signal reconstruction, recovering the finite support set S before inverting the corresponding linear system.Once S is known, the restricted system can be inverted exactly using the Moore–Penrose pseudoinverse.
  • Finite reduction: Every r linearly independent measurement vectors form an MMV system with a unique K-sparse solution matrix whose support equals S.The construction uses r independent columns from the measurement set and the corresponding sparse vectors.
  • Finite reduction: Theorem 2 avoids the infinite structure by recovering S through a single finite MMV system, provided a frame V spans span(y(Λ)).This converts recovery over the full set into a reduced finite-dimensional support-recovery problem.
  • Frame construction: A matrix V with the required span can be constructed from Q when the integral defining Q exists, with bounded-energy conditions for countable or uncountable parameter sets.Because Q is positive semidefinite, a factorization Q = VVH exists; its columns span span(y(Λ)).
  • Framework improvements: The reduction flow is organized into two independent stages with separate proofs, removing the earlier orthogonality restriction on V.The stages can use alternative operations with equivalent functionality, including other constructions of a frame for span(y(Λ)).

A. Objective

The objective is to recover jointly sparse vectors sharing a common support while reducing the MMV optimization dimension. Randomly merging measurement vectors converts the problem to SMV recovery without losing the support with probability one.

  • Objective: The paper seeks to reduce the optimization variable of finite MMV recovery before applying tractable relaxation methods.The MMV unknown has dimensions n × d, whereas the target SMV formulation uses an n-dimensional variable.
  • Objective: The common support S contains the crucial information because the sparse solution matrix can be reconstructed by inverting the relevant columns of A.The assumed unique K-sparse solution matrix has at most K nonzero rows.
  • Random reduction: Randomly merging Y as y = Ya and X̄ as x̄ = X̄a produces an SMV system y = Ax while preserving the sparse support with probability one.For every realization of a, x̄ is the unique K-sparse SMV solution, and I(x̄) = I(X̄) with probability one.
  • Random reduction: Absolutely continuous randomness is essential because deterministic merging can fail to preserve support, including ordinary summation when nonzero row entries cancel.The theorem guarantees support preservation for arbitrary finite d without a stochastic prior on X̄.
  • Comparison: Unlike an earlier OSGA result requiring Gaussian entries and d tending to infinity, this reduction holds for arbitrary finite and fixed d.The paper states that its method does not assume a stochastic prior on the solution set.

V. THE REMBO ALGORITHM

ReMBo repeatedly reduces an MMV system to SMV problems by random column merging and applies a chosen sparse-recovery method. It boosts recovery empirically by retrying unsuccessful reductions with new random combinations.

  • Algorithm: ReMBo draws a random vector a, forms y = Ya, solves the resulting SMV problem, and tests the estimated support and residual.The algorithm accepts a candidate when its support size is at most K and its residual norm is at most ε.
  • Boosting: If a candidate is not sparse enough or poorly aligned with the measurements, ReMBo repeats the reduction with another random draw.These additional iterations are the algorithm’s boosting step, bounded by MaxIters.
  • Boosting: Theorem 3 guarantees that each reduced SMV system has a sparse solution preserving S with probability one, while iterations change its nonzero values.Changing the nonzero values improves the chances that a sub-optimal SMV method recovers S.
  • Parameterization: Approximation methods that fix sparsity to K can make the acceptance condition always true, preventing boosting from occurring.The paper therefore recommends avoiding that method group when only K is constrained.
  • Complexity: The reduction lowers computational complexity because SMV has fewer unknowns, while the reduction itself requires only one matrix multiplication.The paper describes this multiplication as negligible relative to typical compressed-sensing runtimes.
  • Performance: A single reduction can outperform direct MMV recovery for some parameter choices, whereas other choices require boosting.ReMBo-based techniques remain comparably fast even when boosting is used.

VI. NUMERICAL EXPERIMENTS

The numerical experiments evaluate ReMBo for MMV systems with sub-optimal SMV solvers and compare representative ReMBo-derived techniques with popular MMV methods. They also test the IMV reduction flow against discretization.

  • MMV evaluation: The experiments demonstrate ReMBo when the produced SMV problem is solved using a sub-optimal method.
  • MMV evaluation: Two representative MMV techniques derived from Algorithm 1 are compared with other popular MMV techniques.
  • IMV evaluation: A separate experiment examines the benefits of the IMV reduction flow over discretization.

A. Evaluating ReMBo

The experiments evaluate ReMBo-derived and other MMV techniques on repeated random sparse-recovery instances, comparing empirical recovery rates and run times. Recovery correctness requires exact reconstruction up to machine precision, with SMV and MMV curves plotted on the same scale because both recover the finite support set.

  • Experimental setup: Experiments repeat recovery of K-sparse 30 × 5 solution matrices from 20 × 30 Gaussian measurement systems 500 times for each K.The measurement matrix and non-zero solution entries are drawn from zero-mean, unit-variance Gaussian distributions.
  • ReMBo configuration: ReMBo techniques use an independently and identically distributed uniform random matrix P with entries in [−1, 1]^d.The techniques are evaluated as reductions to sparse-vector recovery methods.
  • Evaluation criteria: A solution is counted as correct only when the entire matrix is recovered exactly up to machine precision.The empirical recovery rate is the percentage of correct solutions for each K.
  • Scope and robustness: The study qualitatively compares run times, while rigorous complexity analysis is outside the paper’s scope.The authors also report similar empirical recovery rates when non-zero entries follow a non-Gaussian distribution.
  • Evaluation criteria: SMV and MMV recovery curves are plotted on the same scale because both tasks amount to recovering the finite support set.MMV success requires all vectors in the matrix to be recovered, whereas SMV requires one vector.

B. Results

The results compare ReMBo-derived methods with convex-relaxation and greedy MMV techniques across recovery rate and run time. ReMBo methods often improve recovery, and boosting iterations can substantially increase recovery in difficult regimes.

  • Convex-relaxation methods: ReMBo-BP improves on BP through boosting and has lower average run time than M-BP(ℓ1) and M-BP(ℓ∞).The reduction also avoids selecting an additional row norm before the final column-vector ℓ1 norm.
  • Greedy methods: Greedy matching-pursuit and FOCUSS methods are typically faster than basis-pursuit methods, while joint sparsity improves their recovery rate.FOCUSS is not paired with ReMBo because it is designed to produce a K-sparse approximation and cannot exploit boosting.
  • Greedy methods: ReMBo-OMP outperforms M-OMP and M-FOCUSS for 1 ≤K ≤13, reaching approximately 10% higher recovery for 10 ≤K ≤13.Its run time is not far from that of the direct greedy approaches.
  • Boosting iterations: 54% recovery at K = 10 with one ReMBo-BP iteration rises to 74% with two iterations and 91% with five.Additional iterations produce only minor further improvement, supporting MaxIters = rank(Y) as an intuitive default.
  • Boosting iterations: For K > 10, repeating the reduction beyond rank(Y) can help; ReMBo-BP[20] reaches 56% rather than 25% at K = 14.The condition K ≤10 is sufficient, while empirical recovery remains possible to some extent above it.

C. IMV Reduction vs. Discretization

The IMV reduction preserves the support information needed to recover an entire solution set without discretizing its parameter domain. In the reported comparison, it achieves similar or better recovery with lower run time than discretization, while reducing the problem to a bounded-size MMV system.

  • Reduction and discretization: Discretization uses g evenly spaced columns of Y to form an MMV system, while the IMV flow recovers the entire solution set from the support estimated on the chosen grid.Because the non-zero values are random, missing columns are not interpolated; the support is used instead.
  • Empirical comparison: A discretization grid with g = 200 still has a recovery rate below the IMV flow’s rate.The grid density also affects discretization run time.
  • Empirical comparison: IMV is faster than discretization while achieving a similar recovery rate in the reported example.Discretization with g = 200 creates an MMV system with 200 columns, whereas V can be chosen with no more than K ≤20 columns.
  • Reduction and discretization: Discretization may miss the entire solution-set information when its grid cannot synchronize with non-zero locations, whereas the IMV flow preserves the support set for exact recovery.The paper identifies the non-zero location set as the necessary information for reconstructing the solution set.
  • Theoretical reduction: The reduction theorems convert recovery of an arbitrary number of jointly sparse vectors into recovery of a single sparse vector, covering finite MMV and the introduced IMV model.The approach recovers the support from a low-dimensional problem rather than directly from the original high-dimensional setting.
  • Boosting and tunability: ReMBo makes recovery tunable by trading run time against overall recovery rate, and simulations report that its methods outperform other known techniques.The reduction method also uses randomness during reconstruction while preserving deterministic reconstruction in the stated framework.
Loading 0802.1311v1…