Source-linked AI summary
Estimating Unknown Sparsity in Compressed Sensing
Miles E. Lopes
TL;DR
Compressed sensing theory commonly assumes the signal’s sparsity is known, though it is typically unknown in practice, and the exact nonzero count can be unstable or uninformative. The paper proposes estimating a stable soft sparsity measure from measurements. It provides a dimension-independent confidence-interval width and extends the approach to a soft matrix-rank measure.
Problem
Compressed sensing analyses commonly assume ||x||_0 is known even though it is typically unknown in practice, and exact sparsity can be an unstable or uninformative measure for real signals.
Source: §1 · p. 2, §1.2 · p. 4Method
The paper identifies s(x) as a stable soft sparsity measure and proposes an efficient estimator with provable guarantees.
Source: §1.2 · p. 4, §1.4 · p. 5Results
The confidence-interval width for estimating s(x) does not depend on signal dimension p, and the approach extends to estimating a soft matrix-rank measure.
Source: §3.3 · p. 9, §3.4 · p. 10Takeaways & Limitations
The paper concludes that randomized measurements are essential for estimating s(x) in a minimax sense, while deterministic measurements have large minimax risk when n is much smaller than p.
Source: §4 · p. 12The paper does not pursue estimating ||x||_0 as a limit of ||x||_q^q, because it regards ||x||_0 as less meaningful for natural signals.
Source: §3.2 · p. 8
Abstract
from arXiv · showhide
In the theory of compressed sensing (CS), the sparsity ||x||_0 of the unknown signal x\in\R^p is commonly assumed to be a known parameter. However, it is typically unknown in practice. Due to the fact that many aspects of CS depend on knowing ||x||_0, it is important to estimate this parameter in a data-driven way. A second practical concern is that ||x||_0 is a highly unstable function of x. In particular, for real signals with entries not exactly equal to 0, the value ||x||_0=p is not a useful description of the effective number of coordinates. In this paper, we propose to estimate a stable measure of sparsity s(x):=||x||_1^2/||x||_2^2, which is a sharp lower bound on ||x||_0. Our estimation procedure uses only a small number of linear measurements, does not rely on any sparsity assumptions, and requires very little computation. A confidence interval for s(x) is provided, and its width is shown to have no dependence on the signal dimension p. Moreover, this result extends naturally to the matrix recovery setting, where a soft version of matrix rank can be estimated with analogous guarantees. Finally, we show that the use of randomized measurements is essential to estimating s(x). This is accomplished by proving that the minimax risk for estimating s(x) with deterministic measurements is large when n<<p.
1 Introduction
Compressed sensing theory often treats signal sparsity as known, although it is usually unknown in practice and the exact nonzero count can be uninformative for real-valued signals. The paper motivates a stable soft sparsity measure and an efficient estimator, with applications to measurement and recovery choices.
1 Introduction
- The exact sparsity level is typically unknown in practice, despite its role in compressed sensing theory, leaving estimation and uncertainty quantification relatively underexplored.A direct plug-in count from a recovered signal may fail when the sparsity assumptions behind that recovery method are invalid.Source: §1 · p. 2, §1.1 · p. 2
1.1 Motivations and the role of sparsity
- A sparsity estimate can inform whether sparse modeling is supported, measurement counts, measurement-matrix certificates, and recovery-algorithm tuning.For example, it can restrict OMP iteration counts or Lasso parameter choices; for matrix certificates, the presumed sparsity bound must be consistent with the signal.Source: §1.1 · pp. 2–3
1.2 An alternative measure of sparsity
- For real signals with nonzero entries, ||x||_0=p can fail to describe the effective number of coordinates, motivating a stable soft alternative.The numerical sparsity s(x) is a soft sparsity measure, and its ratio is bounded between 1 and p for nonzero x.Source: §1.2 · pp. 3–4
- s(x) is a sharp, scale-invariant lower bound on ||x||_0; equality holds when the nonzero coordinates have equal magnitude.The paper notes that a continuous upper bound on ||x||_0 over an open set can only be the trivial bound p.Source: §1.2 · p. 4
- When a signal has k large and p−k small coordinates, s(x) can be approximately k even though ||x||_0=p.The Figure 1 vectors illustrate how s(x) reflects different coordinate-decay profiles as an effective coordinate count.Source: §1.2 · p. 4, Figure 1 · p. 4
1.3 Related work.
- Prior CV/ERM approaches tune parameters through candidate solutions, but had not addressed estimating soft sparsity such as s(x) with guarantees of closeness to its true value.The paper contrasts those optimization-based approaches with its estimator, which requires no optimization and uses a small set of preliminary measurements.Source: §1.3 · p. 5
1.4 Our contributions.
- The paper’s contributions are a stable sparsity measure relevant to compressed sensing, an efficient estimator with guarantees, and a distinction between randomized and deterministic measurements for unknown-sparsity estimation.The paper also frames recovery conditions directly in terms of s(x), then develops an estimator and confidence interval.Source: §1.4 · p. 5
2 Recovery conditions in terms of s(x)
This section links s(x) to Basis Pursuit recovery conditions, showing how it can guide the number of measurements. Its approximation-error bounds make T ≳ s(x) necessary and T ≳ s(x) log(p) sufficient.
2 Recovery conditions in terms of s(x)
- The standard Basis Pursuit result assumes bounded noise, a suitable measurement-matrix ensemble, and n ≳ T log(p/T), and gives a high-probability error bound.The reference bound applies to all signals, not only k-sparse ones.Source: §2 · p. 6
- The section studies relative ℓ2 error so the measurement choice does not depend on signal scale.The relative error is invariant to scaling x by any nonzero constant.Source: §2 · p. 6
- T ≳ s(x) is necessary and T ≳ s(x) log(p) is sufficient for the approximation error to be small.The bounds apply to all non-zero signals.Source: §2 · pp. 6–7
- Choosing n = 2⌈bs(x)⌉log(p/⌈bs(x)⌉) from an estimate bs(x) leads to accurate reconstruction across many sparsity levels in simulations.Source: §2 · p. 7
3 Estimation results for s(x)
Section 3 estimates s(x) from randomized linear measurements and extends the approach to an effective-rank measure for semidefinite matrices. It provides confidence guarantees whose widths do not depend on signal dimension or matrix rank.
3 Estimation results for s(x)
- The vector estimator uses few linear measurements, makes no sparsity assumptions, and requires little computation; those measurements may also be reused to recover the signal.Source: §3 · p. 7
3.2 Estimation procedure for s(x)
- The procedure uses Cauchy and Gaussian measurement sets to estimate ||x||1 and ||x||2^2 separately, then combines those estimates to form s(x).The first set uses Cauchy measurements and the second Gaussian measurements.Source: §3.1 · p. 7, §3.2 · pp. 8–9
3.1 Sketching with stable laws
- Stable-law sketches make randomized projections informative about ℓq norms by turning them into samples from a stable distribution with scale determined by the corresponding norm.The procedure estimates ||x||1 and ||x||2 from separate measurement sets.Source: §3.1 · pp. 7–8
3.3 Confidence interval.
- The confidence-interval width for s(x) does not depend on signal dimension or sparsity, so fixed-precision estimation needs O(1) measurements with respect to problem size.When δn and ηn are small, the relative error is of order n^-1/2 + ρ with high probability.Source: §3.3 · p. 9
3.4 Estimating rank and sparsity of matrices
- For matrix recovery, the sparsity analogue s(X)=||X||1^2/||X||F^2 extends directly, so the paper focuses on the distinct problem of estimating robust rank.The paper notes that rank(X) and ||X||0 are sensitive to perturbations.Source: §3.4 · p. 10
3.4.1 The rank of semidefinite matrices
- For nonzero semidefinite X, effective rank tracks k when k eigenvalues are large and the remaining p−k are small, whereas rank(X)=p; its estimator combines separate trace and Frobenius-norm estimates.The resulting confidence interval has width independent of rank and dimension.Source: §3.4.1 · pp. 10–11
- For matrices, confidence-interval width is independent of rank and dimension, and relative error is O(n^-1/2 + ϱ) with high probability when ζn is small.The width depends on the noise-to-signal ratio ϱ.Source: §3.4.1 · p. 11
4 Deterministic measurement matrices
The section contrasts randomized and deterministic measurements for estimating s(x): a deterministic matrix lets an adversary choose a signal that is difficult to estimate. Theorem 3 establishes a large worst-case relative-error lower bound for deterministic measurements.
4 Deterministic measurement matrices
- With a fixed matrix, nature can choose an ill-suited signal; randomizing the matrix leaves nature less information for selecting a bad signal.The section frames this contrast as a game between the statistician and nature.Source: §4 · pp. 11–12
- For noiseless deterministic measurements, every estimation rule has worst-case relative error much larger than n^-1/2, unlike the randomized rule's high-probability O(n^-1/2) error.Theorem 3 gives a minimax lower bound; the comparison with the randomized procedure is stated for the particular estimator bs(x).Source: §4 · p. 12
- When n/p approaches a constant in (0,1), the deterministic minimax error remains much larger than n^-1/2.This is the high-dimensional regime highlighted in the theorem's remarks.Source: §4 · p. 12
5 Simulations
The simulations examine how bs(x)'s relative error varies with signal and measurement parameters, and illustrate reconstruction using a measurement count chosen from bs(x). They report error patterns consistent with the theory and qualitative agreement between true and reconstructed signals.
Relative error of bs(x)
- The relative error shows no noticeable dependence on p or s(x), grows moderately with ρ at fixed n1+n2, and tracks the theoretical bound well at low noise ρ = 10^-2.Figure 2 reports these patterns across the tested settings.Source: §5 · p. 12, Figure 2 · p. 13
Reconstruction of x based on bs(x)
- The reconstructions show good qualitative agreement for three power-law signals, using estimated measurement counts of 4108, 590, and 150.The signal profiles have ν = 0.7, 1.0, and 1.3, respectively.Source: §5 · p. 13, Figure 3 · p. 13
Settings for relative error of bs(x) (Figure 2)
- Relative-error curves average 100 instances per setting, with n1 = n2 and signals normalized to ||x||2 = 1.The measurement matrix follows equations (7) and (9), with γ = 1 and uniformly distributed noise.Source: §5 · p. 13
Settings for reconstruction (Figure 3)
- Reconstructions use Basis Pursuit with ϵ0 = σ0; each plotted profile represents the median reconstruction error over 25 runs.The reconstruction noise has σ0 = 0.001.Source: §5 · p. 14
6 Appendix
The appendix proves Proposition 1 and Theorems 1–3. Its proofs use inequalities and asymptotic distribution arguments, and establish the deterministic lower bound through indistinguishable signals and a two-point decision rule.
6.1 Proof of Proposition 1
- For Proposition 1, an ε bound on the left-hand side implies T ≥ s(x)(1 + ε)^2, proving part (i).The proof also invokes majorization of the uniform probability vector by the normalized absolute signal entries for part (ii).Source: §6.1 · pp. 14–15
6.2 Proof of Theorem 1.
- Theorem 1's proof combines bounds on its statistics using Cauchy sample-median asymptotics and a chi-square delta-method argument.The proof works with noiseless versions of the statistics before accounting for bounded measurement noise.Source: §6.2 · pp. 15–16
6.3 Proof of Theorem 2.
- Theorem 2's probability bound is 1 − 2α, versus (1 − 2α)^2 for Theorem 1, because its corresponding first-statistic condition holds with probability 1.For Theorem 1, the analogous condition holds with probability 1 − 2α.Source: §6.3 · p. 16
6.4 Proof of Theorem 3.
- Theorem 3's proof uses indistinguishable signals for a fixed matrix, then an equal-mass two-point Bayes rule to establish a constant-risk minimax lower bound.A null-space construction supplies a signal with the same measurements but a different sparsity level.Source: §6.4 · pp. 17, 20