Source-linked AI summary
Joint-sparse recovery from multiple measurements
Ewout van den Berg, Michael P. Friedlander
TL;DR
The paper studies recovery of jointly sparse matrices from multiple compressed measurements, extending the single-measurement-vector setting. It compares sum-of-norm and sequential ℓ1 methods and analyzes ReMBo with ℓ1 through its generated sign patterns. The main conclusions are that sum-of-norm uniform recovery cannot exceed sequential ℓ1, while ReMBo improves recovery with more measurements only up to the number of nonzero rows.
Problem
Joint-sparse recovery extends compressed-sensing recovery from one sparse vector to a matrix whose nonzero entries are restricted to common rows.
Method
The paper compares sum-of-norm and sequential ℓ1 recovery, then analyzes boosted-ℓ1 and ReMBo by reducing multiple measurements to weighted single-measurement problems.
Results
Uniform recovery with sum-of-norm minimization cannot exceed sequential ℓ1, while ℓ1,2 and ℓ1,1 can each succeed on instances where the other fails.
Takeaways & Limitations
ReMBo-ℓ1 has higher potential recovery rates than boosted-ℓ1, but its theoretical performance does not increase after the number of observations reaches the number of nonzero rows.
Takeaways & Limitations
Uniform recovery for ℓ1,1 and sum-of-norm approaches does not improve with additional observations, and ReMBo analysis depends on structured sign patterns and unknown geometric distributions.
Abstract
from arXiv · showhide
The joint-sparse recovery problem aims to recover, from sets of compressed measurements, unknown sparse matrices with nonzero entries restricted to a subset of rows. This is an extension of the single-measurement-vector (SMV) problem widely studied in compressed sensing. We analyze the recovery properties for two types of recovery algorithms. First, we show that recovery using sum-of-norm minimization cannot exceed the uniform recovery rate of sequential SMV using $\ell_1$ minimization, and that there are problems that can be solved with one approach but not with the other. Second, we analyze the performance of the ReMBo algorithm [M. Mishali and Y. Eldar, IEEE Trans. Sig. Proc., 56 (2008)] in combination with $\ell_1$ minimization, and show how recovery improves as more measurements are taken. From this analysis it follows that having more measurements than number of nonzero rows does not improve the potential theoretical recovery rate.
1 Introduction
The paper extends sparse recovery from single measurement vectors to jointly sparse matrices and compares mixed-norm, sequential ℓ1, and ReMBo-based approaches. It studies when these methods recover matrices whose nonzero entries occupy common rows.
- SMV background: ℓ1 relaxation replaces combinatorial sparsity minimization with an efficiently solvable convex problem that can recover the same solution under suitable conditions.The ℓ0 formulation is impractical except for small problems because it is combinatorial.
- Problem setting: MMV recovery seeks X0 from B = AX0 when the columns share nonzero locations and X0 is nonzero in only a few rows.This generalizes the SMV problem from one measurement vector to a set of measurements.
- Paper scope: The paper compares sum-of-norms recovery with sequential ℓ1,1 recovery for uniform recovery of all matrices sharing a fixed row support.It also constructs instances where ℓ1,2 succeeds while ℓ1,1 fails, and vice versa.
- Paper scope: The study analyzes how sequential ℓ1,1 changes with more measurements and proposes boosted-ℓ1 as an improvement based on individual observations.The paper places these approaches alongside ReMBo, which reduces MMV recovery to sequential SMV problems.
- Notation and assumptions: The notation assumes a full-rank A and an s row-sparse X0 in R^n×r, with columns and rows represented explicitly for the MMV analysis.Vectors are treated as column vectors throughout.
2 Existing results for ℓ1 recovery
This section reviews geometric, kernel, and optimality-based conditions under which ℓ1 recovery succeeds. It characterizes recovery through faces of a mapped cross-polytope and null-space inequalities.
- Analytical approaches: Restricted isometry, polytope geometry, kernel properties, and dual optimality conditions provide complementary analyses of when ℓ1 recovers sparse vectors.The paper focuses mainly on geometric and kernel conditions while recalling related results for context.
- Geometry of ℓ1 recovery: The unit ℓ1-ball is the cross-polytope C, and applying A maps it to the polytope P = AC.Faces of C are formed from convex hulls of signed identity columns, while P contains their mapped counterparts.
- Geometry of ℓ1 recovery: ℓ1 recovery succeeds exactly when the face containing x0 maps to a face of P, so recovery depends only on x0’s sign pattern.The geometric view interprets the solution as the first contact when P is inflated until it reaches b.
- Support-restricted recovery: For a fixed support, uniform recovery requires every vector supported there to be recoverable, and the relevant probability compares faces generated by that support in C and AC.The support-restricted face count uses FI(C) = 2^|I| and FI(AC).
- Null-space conditions: Basis pursuit uniformly recovers all vectors supported on I if and only if every nonzero null-space vector has strictly smaller ℓ1 mass on I than on its complement.This is the null-space characterization for the fixed index set I.
- Optimality conditions: KKT conditions yield dual certificates for ℓ1 recovery, with uniqueness additionally requiring full rank on the active columns and strict off-support inequalities.For matrices in general position, the dual condition becomes necessary and sufficient because the solution is always unique.
3 Recovery using sums-of-row norms
The paper characterizes uniform recovery for sum-of-norms methods, showing that they cannot surpass uniform ℓ1,1 recovery while still exhibiting different instance-specific behavior. It derives ℓ1,2 optimality conditions and constructs examples where either ℓ1,2 or ℓ1,1 succeeds exclusively.
- Uniform recovery: Uniform recovery by any sum-of-norms formulation implies uniform recovery by ℓ1,1 on the same fixed row support.The result holds for any vector norm used within the row-wise sum.
- Uniform recovery: Therefore, analyses of uniform sum-of-norms recovery cannot yield stronger conditions than uniform ℓ1 recovery.This follows from the equivalence between ℓ1,1 and independent columnwise ℓ1 recovery.
- ℓ1,2 recovery: ℓ1,2 can recover some matrices that ℓ1,1 cannot, even though its uniform recovery guarantee is no better.For random signals, Figure 1 reports higher individual-signal recovery probability for ℓ1,2.
- ℓ1,2 recovery: The paper derives necessary and sufficient primal-dual optimality conditions and uses them to obtain sufficient conditions for unique ℓ1,2 recovery.The conditions establish optimality and uniqueness through a dual certificate and support constraints.
- ℓ1,2 recovery: The ℓ1,2 recovery conditions depend on the magnitudes of nonzero entries as well as their row support and sign pattern.Thus, matrices with the same support and signs can have different recovery outcomes.
- Experiments: Experiments construct weighted combinations of individually recoverable and nonrecoverable vectors, revealing regions where ℓ1,2 succeeds despite ℓ1 failure.The weighting matrix has nonnegative diagonal entries with unit trace, and recovery is assessed by maximum absolute error below 10^-5.
4 Boosted ℓ1
This section develops boosted ℓ1 as a way to exploit partially recovered columns, contrasting its recovery behavior with sequential ℓ1,1 and validating theoretical rates experimentally.
- Recovery behavior: ℓ1,1 recovers X0 only when every individual column xk is successfully recovered by ℓ1.Its recovery rate therefore compounds the single-column recovery requirement across observations.
- Algorithm: Boosted ℓ1 uses sequential SMV solutions and tests sufficiently sparse supports before reconstructing and verifying the full matrix.A zero residual after solving on the candidate support is used to declare success.
- Figures: The complete boosted-ℓ1 procedure is presented in Figure 3, while Figure 4 compares its theoretical and experimental performance across the three support sizes.The figure uses dashed curves for theoretical performance and solid curves for experimental performance.
- Recovery behavior: Boosted ℓ1 fails only when all individual columns fail under ℓ1, giving recovery properties opposite to ℓ1,1.A single correctly recovered column reveals the common row support, which can then be used to recover the nonzero part of X0.
- Experiments: Theoretical and experimental boosted-ℓ1 recovery rates were evaluated for a 20 × 80 Gaussian matrix at row supports s = 8, 9, 10.The empirical rate averages 1,000 trials with normally distributed nonzero coefficients, and the rates are plotted in Figure 4.
5 Recovery using ReMBo
ReMBo-ℓ1 reduces joint-sparse recovery to repeated SMV ℓ1 problems by generating sign patterns through random linear combinations. Its theoretical recovery model depends on orthant intersections and is limited in practice by structured sampling and feasible iteration counts.
- ReMBo-ℓ1 algorithm: ReMBo combines the observations with a random weight vector, solves one SMV ℓ1 problem, and repeats when the candidate is not sufficiently sparse.The algorithm stops after a maximum number of trials or when a sufficiently sparse solution is found.
- Geometric interpretation: Each weight vector creates an s-sparse SMV whose ℓ1 recovery depends on its support and sign pattern.More generated sign patterns can increase recovery probability because each pattern corresponds to a face that may or may not survive the geometric mapping.
- Performance model: The theoretical recovery model treats sign patterns as sampled from possible patterns, but actual patterns are structured by orthant intersections and may be unevenly distributed.The authors note that the model would bound average performance under random sampling, whereas structured clustering of perishing faces could yield higher recovery.
- Maximum orthant intersections: C(n, d) gives the maximum number of orthant interiors intersected by a hyperplane generated by d vectors, with C(n, 1) = 2 and C(n, d) = 2^n for d ≥ n.For d ≤ n, the analysis also gives C(n, d) = 2^n − C(n, n − d).
- Maximum orthant intersections: A hyperplane reaches the maximum orthant count when its generating vectors have full rank or when no coordinate vector e_i lies in their range.The construction and equality argument use recursive orthant counting and orthogonal vectors associated with non-intersected orthants.
- Practical limitations: All possible C(|I|, r)/2 sign patterns are generally infeasible to generate, so practical recovery uses the patterns actually sampled and their reach probabilities.After t trials, recovery probability depends on the sampling distribution over patterns that correspond to recoverable faces.
- Practical sampling: 7.3 × 10^6 versus 4 observations shows strong sampling bias across orthants under normally distributed weights.The efficiency of ReMBo depends on how quickly new sign patterns are encountered, not only on the total number theoretically available.
- Practical sampling: The choice of basis for the nonzero part of X0 influences which orthants are sampled, even though the maximum possible orthant count is basis-independent.The paper compares independently normal entries with repeated-column constructions perturbed by random noise.
6 Conclusions
The paper establishes distinct uniform and individual recovery properties for sum-of-norm methods and ℓ1,1, then analyzes how ReMBo-ℓ1 changes with additional observations. It concludes that ReMBo-ℓ1 offers no further theoretical performance increase once observations reach the number of nonzero rows, while comparison with ℓ1,2 remains outside scope.
- Uniform and individual recovery: Uniform recovery using sums of norms cannot exceed uniform recovery using ℓ1,1, although individual instances can favor either method.The paper constructs cases where ℓ1,2 succeeds while ℓ1,1 fails and vice versa.
- Uniform and individual recovery: Relative coefficient magnitudes affect ℓ1,2 recovery, unlike ℓ1,1 recovery, which depends only on support and sign patterns.This difference removes the usefulness of face-based analysis for the relevant ℓ1,2 behavior.
- ReMBo-ℓ1: ReMBo repeatedly samples random observation combinations, giving higher potential recovery rates than boosted-ℓ1 and allowing compatibility with alternative SMV solvers.The paper also notes that ReMBo is easily parallelized.
- ReMBo-ℓ1: Once observations reach the number of nonzero rows, ReMBo-ℓ1 theoretically gains no further performance from additional observations.The accompanying simplified model could be improved using distributions of mapped faces and external cone angles.
- Scope: A direct comparison between ℓ1,2 and ReMBo-ℓ1 is identified as interesting but remains beyond the paper’s scope.The numerical experiments and generated figures are reported as reproducible.