Source-linked AI summary
Various thresholds for $\ell_1$-optimization in compressed sensing
Mihailo Stojnic
TL;DR
The paper addresses recovery of sparse vectors from under-determined linear systems using polynomial ℓ1-optimization. It develops an alternative theoretical performance analysis based on geometric and null-space characterizations, obtaining threshold bounds that are comparable to the best known results. The authors also note a limitation for signed vectors, where their strong-threshold results trail prior work except near α → 1.
Problem
The central problem is recovering sparse solutions of under-determined linear systems when the measurement matrix is given.
Method
The paper analyzes ℓ1-optimization through null-space and projected-cross-polytope characterizations of recovery.
Results
The authors derive lower bounds for the strong, weak, and sectional recoverable thresholds, with values comparable to the best currently known ones.
Takeaways & Limitations
The threshold results provide an alternative performance analysis of polynomial ℓ1-optimization for sparse recovery.
Takeaways & Limitations
For signed vectors, the strong-threshold results trail those of prior work except in a very narrow range near α → 1.
Abstract
from arXiv · showhide
Recently, \cite{CRT,DonohoPol} theoretically analyzed the success of a polynomial $\ell_1$-optimization algorithm in solving an under-determined system of linear equations. In a large dimensional and statistical context \cite{CRT,DonohoPol} proved that if the number of equations (measurements in the compressed sensing terminology) in the system is proportional to the length of the unknown vector then there is a sparsity (number of non-zero elements of the unknown vector) also proportional to the length of the unknown vector such that $\ell_1$-optimization succeeds in solving the system. In this paper, we provide an alternative performance analysis of $\ell_1$-optimization and obtain the proportionality constants that in certain cases match or improve on the best currently known ones from \cite{DonohoPol,DT}.
1 Introduction
The introduction frames compressed sensing as recovery of a sparse vector from an under-determined linear system, emphasizing polynomial ℓ1-optimization when the measurement matrix is given. It positions the paper as an alternative threshold analysis whose bounds are comparable to leading prior results.
- Problem formulation: Finding the sparsest solution of an under-determined linear system is a crucial compressed sensing problem.When A is fixed rather than designed, the recovery problem becomes NP-hard.
- Problem formulation: Compressed sensing seeks a k-sparse x from y = Ax, where A is m × n with m < n.The linear regime sets k = βn and m = αn, with α and β independent of n.
- Prior ℓ1 results: For random matrices satisfying RIP, prior work established recovery of vectors with k = βn nonzero elements through ℓ1-optimization.The RIP is sufficient rather than necessary, motivating geometric characterizations based on projected cross-polytopes.
- Paper contribution: A necessary and sufficient condition for ℓ1 recovery is that the cross-polytope projected by A is k-neighborly.The paper determines strong, sectional, and weak threshold values across the full range 0 ≤ α ≤ 1.
2 Key theorems
This section states null-space criteria for when ℓ1 minimization recovers sparse solutions and introduces probabilistic tools for analyzing random measurement matrices. It also reformulates the criterion using ordered magnitudes and invokes escape-through-a-mesh results.
- Null-space characterization: Theorem 1 gives a null-space characterization for ℓ1 recovery of a general k-sparse vector with signed nonzero components.The criterion is stated for an m × n matrix A, y = Ax, and subsets K of k coordinates.
- Equivalent formulation: The null-space test can be simplified by sorting the magnitudes of a null-space vector and comparing sums of its ordered entries.This formulation is used in the subsequent analysis alongside the theorem’s original form.
- Null-space characterization: A sufficient matrix condition makes the ℓ1 and sparsest-solution problems coincide.The paper notes that constructing deterministic matrices satisfying this condition is difficult when m and k scale linearly with n.
- Random matrices: Random matrices with null spaces uniformly distributed in the Grassmannian provide a convenient alternative to difficult deterministic constructions.The analysis uses the relation between such random subspaces and the escape-through-a-mesh theorem.
- Probabilistic tool: Gordon’s escape-through-a-mesh theorem bounds how a uniformly random subspace interacts with a subset of the unit sphere.The section records that a constant of 2.5 replaced the original 3.5 in a later version, with both constants considered suitable here.
3 Probabilistic analysis of the null-space characterizations – general x
The paper probabilistically analyzes the null-space characterization for general sparse vectors. This analysis is used to obtain strong, weak, and sectional recovery thresholds.
- General x: The section probabilistically analyzes validity of the null-space characterization from Theorem 1.The analysis concerns the general signed-vector setting.
- Strong threshold: The strong threshold βs is obtained over the entire range 0 ≤ α ≤ 1.The paper then extends the strong-threshold analysis to the weak and sectional thresholds.
3.1 Strong threshold
The paper estimates the strong threshold for ℓ1-optimization by upper-bounding a Gaussian width through dual optimization and asymptotic analysis. The resulting thresholds are comparable to prior results across much of the measurement range and slightly better near α=1, where β≈.24 is optimal.
- Geometric condition: A uniformly distributed null-space Y will miss Ss with a probability bounded below whenever w(Ss) satisfies the stated threshold condition.Here Y is the null-space of A, and missing Ss ensures condition (3).
- Strong-threshold estimation: The analysis estimates the strong threshold by obtaining a fairly precise estimate of w(Ss), using upper bounds on w(h, Ss) and its expectation.The expected upper bound E(Bs) bounds w(Ss), and tighter bounds yield better strong-threshold values.
- Dual upper bound: Lagrange duality supplies an upper bound wup(h, Ss) on w(h, Ss), with feasible values of ν and λ sufficient for the analysis.The paper notes that strong duality in fact gives equality, although only the upper-bound relation is needed.
- Asymptotic calculation: The asymptotic analysis determines θ̂s from equation (53), then sets δs=1−θ̂s and cs=δsn=(1−θ̂s)n.This completes the first step of the strong-threshold calculation.
- Threshold guarantee: Theorem 3 states that under the specified measurement-matrix and null-space conditions, the solutions of (1) and (2) coincide with overwhelming probability.The theorem follows by combining the preceding geometric, width, and asymptotic bounds.
- Comparison with prior thresholds: For α near 1, the threshold values from Theorem 3 are slightly better than prior results, and as α→1, β≈.24, matching an optimal value.Across a large portion of the α range, the results are comparable to those from.
3.2 Weak threshold
The section defines the weak threshold for ℓ1-optimization and derives it probabilistically for sparse vectors with fixed support and signs. The resulting threshold curve matches the best currently known results.
- For fixed α, βw is the maximum sparsity proportion for which ℓ1-optimization recovers every βn-sparse vector with fixed support and signs.
- The analysis reduces recovery to bounding the Gaussian width of a set associated with the null-space characterization.The expected value of an upper bound on the random support function is used to upper-bound the Gaussian width.
- The derivation first bounds w(h, Sw) using sorted Gaussian magnitudes and duality, then computes the expected bound through two sequential steps.The first step determines cw; the second evaluates the corresponding expectation for large n.
- Under the theorem’s Grassmannian null-space assumptions, the solutions of (1) and (2) coincide with overwhelming probability.
- The obtained weak-threshold results match the best currently known results from.The comparison is presented in Figure 3.
3.3 Sectional threshold
The section defines the sectional threshold for vectors with a fixed support location and derives an upper-bound analysis based on Gaussian width. The resulting thresholds slightly improve on the best currently known ones.
- For fixed α, βsec is the maximum sparsity proportion for which ℓ1-optimization recovers every vector with a fixed support location.
- The recovery condition is specialized to a k-sparse vector whose nonzero components occupy a fixed location.The exposition assumes the first n−k components are zero without loss of generality.
- The analysis bounds the Gaussian width of Ssec by first controlling w(h, Ssec) and then computing the expectation of an upper bound Bsec.The random vector h has independent standard Gaussian components, and the bound uses sorted magnitudes and duality.
- Under a uniformly Grassmannian null space and large dimensions, the theorem gives coincidence of the two optimization solutions with overwhelming probability.
- The sectional-threshold results slightly improve on the best currently known results from.The comparison is presented in Figure 4.
4 Probabilistic analysis of the null-space characterizations – signed x
This section extends the probabilistic null-space analysis to recovery when the signs of the nonzero components are known. It derives weak-threshold results that match prior best results.
- The analysis considers k-sparse vectors whose nonzero components are known to be positive, using a modified ℓ1 formulation.The support location is treated as arbitrarily chosen but fixed.
- A null-space characterization provides the recovery condition for the non-negative formulation.
- The probabilistic analysis bounds the Gaussian width of S+w through a support-function bound, duality, and expectations over Gaussian variables.The derivation adapts the earlier weak-threshold analysis to the known-sign setting.
- The weak-threshold results for a priori known signs match the best currently known results from.The comparison is presented in Figure 5.
5 Discussion
The paper derives lower bounds for strong, weak, and sectional recovery thresholds in the linear sparsity regime, with results comparable to the best known values. Its framework also extends toward other signal and measurement settings and has connections to geometric neighborliness.
- 5 Discussion: The analysis assumes that the measurement matrix has a uniformly distributed basis for its null-space.
- 5 Discussion: Lower bounds for strong, weak, and sectional thresholds are derived when recoverable sparsity is proportional to signal length.This is the paper’s linear regime of compressed sensing recovery.
- 5 Discussion: The obtained threshold results are comparable to the best currently known ones.
- 5 Discussion: The framework can be extended to approximately sparse signals and noisy measurements.
- 5 Discussion: The paper focuses mainly on ℓ1-optimization, while analogous ℓq-optimization results are deferred to future work.The stated range is 0 < q < 1.
- 5 Discussion: The results can also determine neighborliness thresholds for projected cross-polytopes, regular simplices, and positive orthants.