Pipeline-generated

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

Stable compressed sensing with noise — Examples and Counterexamples

1 · Prerequisites

2 · Logical flowchart

3 · Definitions, theorems and proofs

None yet.

4 · Examples, counterexamples and false statements

ExampleConstruction: AI-generatedVerification: AI-generatedjudge pass (gpt-6-luna)verified 2026-10-22 (gpt-6.1-sol)Open item page →

Bounded noise, compressible truth, and a large nullspace component

Example

In the first two cases take $A = I_{2} : R^{2} \to R^{2}$ , $s = 1$ , $ρ = \frac{1}{2}$ , and $τ = 1$ . This matrix satisfies the robust nullspace property for every vector: for each $S \subseteq {1, 2}$ with $∣ S ∣ \leq 1$ , $∥ h_{S} ∥_{2} \leq ∥ h ∥_{2} = ∥ A h ∥_{2}$ , while the other term on the right side of the robust inequality is nonnegative.

Bounded noise. Let $x^{†} = (1, 0)$ , $e = (0, \frac{1}{10})$ , $y = (1, \frac{1}{10})$ , and $ϵ = \frac{1}{10}$ . The truth is feasible, the noise bound is attained, and $σ_{1} (x^{†})_{1} = 0$ . Every minimizer therefore obeys the recovery bounds with $C_{1} = 8$ , $C_{2} = 12$ , $C_{3} = 6$ , and $C_{4} = 8$ .
Compressible truth. Let $x^{†} = (1, \frac{1}{5})$ , $e = (0, \frac{1}{100})$ , $y = (1, \frac{21}{100})$ , and $ϵ = \frac{1}{100}$ . The truth is feasible and $σ_{1} (x^{†})_{1} = \frac{1}{5}$ . Every minimizer obeys the same constants and hence $∥ \hat{x} - x^{†} ∥_{2} \leq \frac{43}{25}, ∥ \hat{x} - x^{†} ∥_{1} \leq \frac{32}{25} .$
A large nullspace component outside the theorem's hypothesis. Let $A_{0} : R^{2} \to R$ be $A_{0} (z_{1}, z_{2}) = z_{1}$ , take $s = 1$ , $x^{†} = (0, M)$ for any $M > 0$ , $e = 0$ , $ϵ = 0$ , and $y = 0$ . The only minimum- $ℓ^{1}$ feasible vector is $\hat{x} = (0, 0)$ , so $∥ \hat{x} - x^{†} ∥_{2} = M$ while $σ_{1} (x^{†})_{1} = 0$ . The robust nullspace property fails for $A_{0}$ , witnessed by $h = (0, 1)$ and $S = {2}$ ; this case is outside the theorem and shows why its matrix hypothesis cannot be omitted.

Example references

Robust nullspace noisy recovery bound

Robust nullspace hypothesis

Best s-term ℓ1 error

Certified BPDN procedure and its conditional success status

Foucart and Rauhut, A Mathematical Introduction to Compressive Sensing, §4.3

Mendelson, Rauhut, and Ward, Improved Bounds for Sparse Recovery from Subsampled Random Convolutions, §2.1

Facts & Assumptions

Given: The three finite-dimensional examples in the Example section and the constants and conclusions stated there.

[F1]

The ℓ2 robust nullspace property: the inequality must hold for every vector and every coordinate set of size at most $s$ .

[F2]

Best s-term ℓ1 approximation error and The largest coordinates attain the best s-term ℓ1 error: $σ_{s} (x)_{1}$ is the least coordinate-tail $ℓ^{1}$ error and is obtained by retaining the largest $s$ coordinates.

[F3]

Robust nullspace property gives stable noisy recovery: under the robust property, every BPDN minimizer obeys the two displayed error bounds with the stated constants.

[F4]

The $p$ -norms $∥ x ∥_{p}$ for rational $p \geq 1$ , and $∥ x ∥_{\infty}$ : for $s = 1$ , the scalar $\sqrt{s} = 1$ and the displayed coordinate norms are the usual absolute-value and Euclidean norms.

[F5]

Cauchy-Schwarz $∣ ⟨ x, y ⟩ ∣ \leq ∥ x ∥_{2} ∥ y ∥_{2}$ with its equality case, the triangle inequality for $∥ \cdot ∥_{2}$ , the parallelogram law and polarisation and Laws of finite sums and finite products: Euclidean norms are nonnegative, and finite coordinate sums preserve the stated inequalities.

Verification

1.1F1F2F4F5algebra

For $A = I_{2}$ and any $h, S$ in the first two cases, coordinate restriction gives $∥ h_{S} ∥_{2} \leq ∥ h ∥_{2}$ , and $A h = h$ . Since $ρ ∥ h_{S^{c}} ∥_{1} \geq 0$ , the robust inequality holds with $ρ = 1 / 2, τ = 1$ . The best-term lemma gives $σ_{1} (1, 0)_{1} = 0$ and $σ_{1} (1, 1 / 5)_{1} = 1 / 5$ .

1.2F2F3givenalgebra

In case 1, $y - x^{†} = e$ and $∥ e ∥_{2} = 1 / 10 = ϵ$ . The theorem constants evaluate to $(8, 12, 6, 8)$ ; with $σ_{1} = 0$ its bounds are $∥ \hat{x} - x^{†} ∥_{2} \leq 12 / 10 = 6 / 5$ and $∥ \hat{x} - x^{†} ∥_{1} \leq 8 / 10 = 4 / 5$ . In case 2, $∥ e ∥_{2} = 1 / 100 = ϵ$ and $y = x^{†} + e$ . The theorem gives $8 (1 / 5) + 12 (1 / 100) = 43 / 25, 6 (1 / 5) + 8 (1 / 100) = 32 / 25,$ for the two respective bounds.

2.1F1F2givenalgebra∎

In case 3, feasibility at radius zero is $z_{1} = 0$ . Its objective is then $∣ z_{2} ∣$ , whose unique minimum is zero at $z = (0, 0)$ . For $h = (0, 1)$ and $S = {2}$ , $∥ h_{S} ∥_{2} = 1$ , $∥ h_{S^{c}} ∥_{1} = 0$ , and $A_{0} h = 0$ , so the robust inequality would require $1 \leq 0$ ; it fails for every $0 < ρ < 1$ and every $τ > 0$ . The reconstruction error and best one-term tail have the stated values.