Recovering linear images of sparse signals from indirect observations

1 Introduction

• The target is a linear form or image of an s-sparse signal in a known convex compact set, observed indirectly with noise.The paper considers both g^T x and Bx.Source: §1 · p. 1
• The introduction's illustrative setting uses an ℓ1-minimization estimate for sparse signals with sub-Gaussian observation noise.The paper also considers other noise families and observation models.Source: §1 · p. 1
• Classical performance guarantees often require RIP, RE, compatibility, or nullspace conditions that are difficult to verify for an individual sensing matrix.Known verifiable alternatives such as mutual incoherence are described as conservative.Source: §1 · p. 2
• The proposed approach builds a computationally tractable outer approximation of the recovery-error set, then uses it to compute error bounds and optimize contrasts.The same approximation supports guarantees for recovery of the sparse signal and its image.Source: §1 · p. 2
• Without specific assumptions on the sensing matrix or signal-set geometry, contrast parameters and risk bounds are computed rather than given as closed-form rates.The paper describes these outputs as readily available from the problem data through computation.Source: §1 · p. 2

2.1 Observation schemes

• The observation model assumes tail bounds for noise projections through a family of norms, with uncertain-bounded, Gaussian, and sub-Gaussian noise among the listed schemes.The norm bounds are nonincreasing in the confidence parameter.Source: §2.1 · p. 3
• Mixture and Poisson observations fit the observation framework, while repeated observations can be aggregated into a single-observation scheme.Discrete observations are represented by basis vectors with probabilities determined by Ax; aggregation also applies to repeated Poisson observations.Source: §2.1 · pp. 3–4

2.2 Polyhedral estimates

• The estimation setup extends to signals in a convex compact set and to recovering a linear image, with performance measured by a risk bound.Prior polyhedral-estimation results provide efficiently computable upper bounds that can be optimized over admissible contrasts.Source: §2.2 · p. 4, Polyhedral estimates · p. 5

Polyhedral estimates.

• An admissible contrast matrix yields a polyhedral estimate of the signal and an associated estimate of its linear image, with the observation event holding with probability at least 1 − ϵ.The estimate is defined through the nonempty feasible set V[ω].Source: Polyhedral estimates · p. 5

2.3.1. Notation.

• For sparse signals under an admissible contrast matrix, the signal estimate is well defined and its recovery error lies in a localized set with a bounded contrast residual.The error is also constrained by the signal-set difference and sparsity relations described in the preliminaries.Source: §2.3.1 · p. 6

3.1 Risk analysis

• For an admissible contrast matrix, the section bounds the risk of the associated polyhedral estimate of a sparse signal's linear functional.The risk analysis relies on a localized set for the recovery error.Source: §3.1 · p. 8

3.2 Designing the estimate

• The contrast-design procedure optimizes the stated risk upper bound over admissible matrices, and the resulting design is optimal for that bound under the paper's stated performance criterion.The authors qualify this comparison as applying when performance is measured by the efficiently computable upper bound, rather than the actual risk.Source: §3.2 · p. 9

3.3 Linearly corrected (debiased) estimation

• For a linearly corrected estimate, minimizing ψ_g(f) produces a computable upper bound on its (s, ϵ)-risk.The correction is linear in the observation and targets the bias of the plug-in estimate; the construction is presented as a counterpart of debiased estimation [5] [23].Source: §3.3 · pp. 9–10

4 Recovering linear image of a sparse signal

• Polyhedral estimates extend recovery from linear functionals to linear images, with estimates formed by applying G to the estimated signal and confidence bounds targeting image loss.Source: §4 · p. 10, §4.1.1 · p. 10

4.1.1 Preliminaries

• For general G, coordinate error bounds yield risk bounds under any absolute norm when an (ℓ, ±) case occurs.The coordinate bounds are given by r(ℓ)[G, H].Source: §4.1.1 · p. 11

4.1.2 Recovering the sparse signal y = Cx

• For Cx, the propositions bound the image error Cζ and derive corresponding recovery-risk bounds.Source: §4.1.2 · pp. 11–12

4.1.3 Recovering w = Bx

• When B = FC, bounds for Cζ and F^T Bζ support a Euclidean-risk bound for estimating Bx, with admissibility ensured when δ ≤ ϵ/(4p^2m).Source: §4.1.3 · pp. 12–13

4.2 Reducing complexity of the estimate

• The alternative error localizer yields coordinatewise and risk bounds for Gx and a Euclidean-risk bound for Bx; iterated contrasts reduce rows from 2p^2 to p without degrading Cx risk.Source: §4.2 · pp. 14–15

• The approach assumes the symmetrized signal set belongs to a basic ellitope.Source: §5 · p. 16
• Here a basic ellitope is described through quadratic constraints indexed by a monotone, convex compact parameter set.Source: §5 · p. 16
• The unit ball of the dual error norm is also assumed to be a basic ellitope.Source: §5 · p. 16

5.1.1 Initial risk bound

• An initial risk bound uses Optℓ[H], but these quantities are difficult to compute and optimize directly over H.Source: §5.1.1 · p. 16, §5.1.2 · p. 17

5.1.2 Efficiently computable relaxation of (48)

• The relaxation replaces difficult Optℓ[H] values with efficiently computable upper bounds, using a construction based on quadratic constraints and semidefinite optimization.Source: §5.1.2 · p. 17

5.1.3 Designing the estimate

• The next design step optimizes the risk bound over the contrast matrix H.Source: §5.1.3 · p. 18

5.1.4 The case of sub-Gaussian/Gaussian observation scheme

• For Gaussian or sub-Gaussian observations, the recommended H*[δ] is (1−ϵ)-admissible at δ = ϵ/M and minimizes the risk bound among contrasts with column πδ-norms at most 1.Source: §5.1.4 · pp. 18–19

5.1.5 Poisson and Discrete observation schemes

• The contrast-design construction is extended to discrete and Poisson observations, assuming respectively column-stochastic A with X in the probabilistic simplex, or nonnegative A and X.Source: §5.1.5 · pp. 19–20

5.2 Putting things together

• The section combines techniques from Sections 4.1 and 5.1.4 to obtain polyhedral estimates with improved risk bounds.It assumes the signal set satisfies (45) and uses Gaussian or sub-Gaussian observations.Source: §5.2 · p. 20

5.2.1 Preliminaries

• For each ℓ, the preliminaries define efficiently computable convex optimization quantities and use their solutions to form component contrast matrices Hℓ[U,δ].The matrices are built by scaling eigenvector columns to have unit πδ-norm.Source: §5.2.1 · p. 20

5.2.2 The construction

• The construction selects G, U, and ς through convex master problems, then builds contrast matrices from eigenvectors scaled to unit πδ-norm.The stated risk bound applies when the designed matrices are included in the contrast matrix.Source: §5.2.2 · p. 21
• The construction yields a polyhedral estimate of Bx with a stated θ-risk bound after concatenating designed contrast matrices.The construction uses M = p(4p+n) and δ = ϵ/M.Source: §5.2.2 · p. 22

5.2.3 Bounding the estimation error for a fixed H

• For a fixed admissible H, Proposition 5.3 gives a risk bound for recovering Bx using an optimization-based signal-decomposition bound.The associated quantities are described as efficiently computable convex functions.Source: §5.2.3 · pp. 22–23

6 Testing sparse hypotheses

• The task is to distinguish whether x belongs to X_s or Y_s from ω = Ax + ξ, where each hypothesis imposes a sparse transform constraint.The sets X and Y are nonempty, convex, and compact, and X_s ∩ Y_s = ∅.Source: §6 · p. 23

6.1 Building bricks

• For two convex compact sets A and B, a detector-based test thresholds h^Tω to accept one hypothesis, with correct acceptance probability at least 1−δ.The test defines risk as the maximal probability of a wrong decision over x in A ∪ B.Source: §6.1 · p. 24

6.2 Testing hypotheses about sparse signals

• The sparse-hypothesis procedure tests signed component sets pairwise, accepts a side when one component passes against every opposing component, and otherwise fails to decide.The component tests use δ = ϵ/(2 max[p_X,p_Y]).Source: §6.2 · pp. 24–25
• When the good case holds, the composite test T has risk at most ϵ.The guarantee does not extend to the bad case, including when AX_i and AY_j share a point.Source: §6.2 · p. 25
• If any AX_i and AY_j share a point, the good case is impossible regardless of the number of repeated observations.Proposition 6.1 does not apply beyond the good case.Source: §6.2 · p. 25

7.1 Estimating linear functionals

• The entry-recovery experiment evaluates four bounds, including Dantzig Selector, reduced-complexity, Simple Polyhedral, and full Polyhedral estimates.The signals are sparse, observations use Gaussian noise with σ=0.01, and the risk reliability parameter is ε=0.05.Source: §7.1 · p. 26
• For s=4, upper ∥·∥2-risk bounds were 54.9092 (Dantzig Selector), 9.2918 (reduced complexity polyhedral), and 7.6836 (full polyhedral).For s=3, the corresponding bounds were 6.6966 (Dantzig Selector), 0.7581 (reduced complexity polyhedral), and 0.7458 (full polyhedral); for s=2, they were 0.7727, 0.2514, and 0.2500, respectively.Source: §7.1 · p. 26
• A second experiment compares bounds for Enhanced DS and Simple Polyhedral estimates with bounds for Debiased DS and Debiased Polyhedral estimates at s=3 and s=2.The comparison is presented for the setup of the first experiment in Figure 3.Source: §7.1 · p. 26, Figure 3 · p. 27
• For random unit-norm functionals and Gaussian sensing matrices, the experiments compare risk-bound distributions at s=s(A[k]) and s=s(A[k])−1.Figures 4 and 5 show cumulative distributions and distributions of risk-bound ratios; the setting uses σ=0.01 and reliability ε=0.05.Source: §7.1 · p. 27, Figure 4 · p. 28, Figure 5 · p. 28

7.2 Sparse signal recovery

• For s=3 and s=5, 1,000-trial boxplots compare recovery errors with upper risk bounds; the nonsparse all-X optimal-polyhedral ∥·∥2-risk bound is 91.709 at ε=0.05.The boxplots cover ℓ2 and ℓ1 errors for random sparse signals; the red bars indicate risk bounds where specified.Source: §7.2 · p. 28, Figure 6 · p. 29, Figure 7 · p. 30

7.3 Testing sparse hypotheses

• The testing example contrasts hypotheses whose sets have a large intersection with the sparse-signal setting, where the reported tests can distinguish them.The sets intersect in a box, so no nontrivial test distinguishes membership without the sparsity assumption, regardless of the number of observations.Source: §7.3 · p. 29
• At ε=0.01, testing needed K=1 (n=100, s=10), 17 (s=40), and 26 (n=10,000, s=4,900); at ε=10^-4, K=35 yielded zero errors in 1,000 simulations.The zero-error result is reported for the n=10,000, s=4,900 setting.Source: §7.3 · p. 29

Miscellaneous proofs

• Figures 8 and 9 compare ℓ2- and ℓ1-estimation errors with upper risk bounds for random 5-sparse signals.Source: Figure 8 · p. 31, Figure 9 · p. 32
• A mixture of the centered random variables ξ_i−μ with coefficients x_i is sub-Gaussian with parameters 0 and [σ^2+ϱ^2]I_m.The passage defines ϱ using the maximum pairwise distance between the means μ_i.Source: A Miscellaneous proofs · p. 31