Source-linked AI summary
New Bounds for Restricted Isometry Constants
T. Tony Cai, Lie Wang, Guangwu Xu
TL;DR
Compressed sensing must recover high-dimensional sparse signals from considerably fewer measurements, but direct sparse optimization is computationally infeasible. This paper derives new RIP conditions using norm and restricted-orthogonality inequalities, showing that δ_k < 0.307 guarantees exact noiseless recovery and stable noisy estimation, while an example limits guaranteed recovery beyond 0.5.
Problem
Sparse recovery needs a tractable alternative to NP-hard ℓ0 minimization, together with sharp RIP-based conditions for ℓ1 recovery.
Method
The paper derives general RIP bounds using ℓ1–ℓ2 norm inequalities and a square root lifting inequality for restricted orthogonality.
Results
δ_k < 0.307 guarantees exact recovery of k-sparse signals without noise and stable estimation with noise via ℓ1 minimization.
Takeaways & Limitations
The recovery bound cannot be substantively improved: δ_k = (k−1)/(2k−1) < 0.5 can still make certain k-sparse signals unrecoverable.
Takeaways & Limitations
At δ_k = (k−1)/(2k−1), the model is not generally identifiable, so not all k-sparse signals can be recovered exactly in the noiseless case.
Abstract
from arXiv · showhide
In this paper we show that if the restricted isometry constant $δ_k$ of the compressed sensing matrix satisfies \[ δ_k < 0.307, \] then $k$-sparse signals are guaranteed to be recovered exactly via $\ell_1$ minimization when no noise is present and $k$-sparse signals can be estimated stably in the noisy case. It is also shown that the bound cannot be substantively improved. An explicitly example is constructed in which $δ_{k}=\frac{k-1}{2k-1} < 0.5$, but it is impossible to recover certain $k$-sparse signals.
1 Introduction
Compressed sensing seeks to recover high-dimensional sparse signals from substantially fewer linear measurements, using ℓ1 minimization as a tractable alternative to NP-hard ℓ0 minimization. The paper introduces a condition on δ_k guaranteeing exact noiseless recovery and stable noisy estimation, and argues its bound is nearly unimprovable.
- Compressed sensing reconstructs high-dimensional sparse signals from considerably fewer linear measurements.
- ℓ1 minimization provides a convex, computationally feasible relaxation of NP-hard ℓ0 minimization for sparse recovery.The feasible set is constrained by a bounded noise set B, with B = {0} in the noiseless case.
- RIP requires subsets of matrix columns to approximately behave like an orthonormal system, but verifying RIP conditions for a given matrix is difficult.Random matrix constructions are commonly used to obtain RIP with high probability instead.
- The paper establishes, to the authors’ knowledge, the first recovery condition stated directly on δ_k.
- Under the new condition, k-sparse signals are recovered exactly by ℓ1 minimization without noise and estimated stably with noise.The results can also extend to signals that are not exactly k-sparse.
- The paper derives a more general RIP result and uses norm inequalities for ℓ1 and ℓ2 together with a square root lifting inequality for restricted orthogonality.These ingredients support the new RIP conditions and include the stated δ_k condition as a special case.
2 Some Properties of Restricted Isometry Constants
This section introduces notation and elementary properties for restricted isometry and restricted orthogonality constants. It collects monotonicity, conversion, and square root lifting tools used to derive simplified recovery conditions.
- The section defines vmax(k) by retaining the k largest entries of a vector and v−max(k) by removing them.
- The ℓq-norm is denoted by ∥v∥q = (Σ_i=1^p |vi|^q)^1/q.
- For a subset T, Φ_T is the submatrix formed from columns indexed by T, while Λmin(k) and Λmax(k) summarize extreme singular values over supports of size at most k.
- The condition defining the restricted isometry constant can be viewed as a condition on Λmin(k) and Λmax(k).
- The section collects monotone properties and inequalities relating restricted isometry and restricted orthogonality constants.These properties are used to simplify recovery conditions.
- The square root lifting inequality bounds θk,ak′ in terms of θk,k′ and generalizes an earlier inequality for restricted orthogonality constants.
3 A Norm Inequality for ℓ1 and ℓ2
This section develops a sharper inequality connecting ℓ1- and ℓ2-norms, including its equality cases. The inequality is intended to support finer analysis of sparse recovery.
- The section develops a useful inequality for converting between the ℓ1-norm and ℓ2-norm.
- Cauchy–Schwarz gives a baseline relation between ∥x∥2 and ∥x∥1, with equality when all coordinate magnitudes are equal.
- The derived bound characterizes when the norm-related quantity reaches equality.One equality family has all absolute coordinate values equal.
- A second equality case occurs when n = 4m, with m nonzero coordinates having equal magnitudes and the remaining coordinates zero.
- The proof analyzes the extremum by ordering nonnegative coordinates and showing the maximizing vector has at most two constant coordinate levels.
4 New RIP Bounds of Compressed Sensing Matrices
The paper develops new RIP conditions for sparse recovery, using square root lifting and related RIP properties to obtain exact noiseless and stable noisy recovery under δ_k < 0.307.
- Scope extension: The analysis extends beyond exactly k-sparse signals when the true signal has a good k-term approximation.For general signals, the paper states that error bounds involve β−max(k).
- Proof strategy: The proof combines a square root lifting inequality with norm inequalities for ℓ1 and ℓ2 and other properties of RIP constants.The proof is presented concisely for k ≡ 0 (mod 9), with the complete proof deferred to the appendix.
- Contribution: The authors identify the result as, to their knowledge, the first sparse-recovery condition involving only δ_k.Different choices of auxiliary parameters k_1 and k_2 yield different conditions, with integrality assumptions handled using ceiling notation when needed.
- Main recovery bound: δ_k < 0.307 also suffices for stable recovery of k-sparse signals when the error satisfies the Dantzig Selector constraint.The bounded error set is B_DS = {z : ∥Φ′z∥∞ ≤ λ}.
5 Upper Bounds of δk
This section constructs a matrix showing that the δ_k recovery bound cannot be substantively improved. At δ_k=(k−1)/(2k−1)<0.5, certain k-sparse signals are not identifiable or exactly recoverable.
- δ_k=(k−1)/(2k−1)<0.5, yet certain k-sparse signals cannot be recovered exactly.Thus a guarantee for all k-sparse signals cannot extend to this boundary.
- A (2k−1)×2k matrix exists with restricted isometry constant δ_k=(k−1)/(2k−1).
- Two nonzero k-sparse vectors with disjoint supports produce the same measurements, Φβ1=Φβ2.The construction therefore makes the k-sparse model non-identifiable.
- Under δ_k=(k−1)/(2k−1), the model is not identifiable and not all k-sparse signals can be exactly recovered in the noiseless case.In sufficiently small noise, no estimator can be close to both indistinguishable vectors.
- The construction starts from a positive-semidefinite 2k×2k matrix Γ with rank 2k−1 and factors it as Γ=Φ′Φ.A nonzero null vector of Φ is then used to construct the indistinguishable sparse vectors.
A-1 Proof of Lemma 1
The proof of Lemma 1 partitions a (k+k′)-sparse vector into disjoint components and bounds their norms using monotonicity of restricted isometry constants.
- A (k+k′)-sparse vector is arranged so its nonzero entries occupy the first k+k′ coordinates.
- The proof assumes k≤k′ and splits c into c1 containing the first k entries and c2 equal to c−c1.
- The resulting norm bounds use δ_k≤δ_k′ together with the relation between the component norm and the full vector norm.
- A second arrangement instead places the first k′ entries in c2 and defines c1=c−c2, yielding the corresponding upper and lower bounds.
A-2 Proof of Corollary 1
The proof of Corollary 1 combines an earlier relation with the square root lifting inequality to bound the restricted orthogonality term by restricted isometry constants.
- The proof begins by applying the relation from equation (10) together with the square root lifting inequality.
- 2θ_k,k+δ_2k≤3δ_2k, converting the mixed restricted-orthogonality expression into a δ_2k-only bound.
- Lemma 1 supplies the next bound used in completing the corollary.
A-3 Completion of the Proof of Theorem 2
The proof completes the theorem by selecting parameters and estimating the resulting coefficient A_k. Direct calculations establish the needed numerical bounds for different k values.
- The argument concludes after applying the square root lifting inequality and carrying out the associated calculations.
- For general k, k2 is selected using the residue r_k≡4k (mod 9), with a case-dependent choice involving ceil(9k/4).
- A4=A6=f(0.5)=3.25, while A5=f(0.4)<3.246.
- The proof uses the relation h(k1+(i−1)k2+1)=h(k1+ik2) for i>0 to obtain the required estimate.
- For k=2,3, the proof sets k2=1 and estimates A_kδ_k by a numerical upper bound.