ExampleConstruction: AI-generatedVerification: AI-generatedPipeline-generatedjudge pass (gpt-6-luna)verified 2026-10-22 (gpt-6.1-sol)

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.

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.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

61 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

Simon Foucart and Holger Rauhut, A Mathematical Introduction to Compressive Sensing, §4.3 (standard reference, not scraped)
Shahar Mendelson, Holger Rauhut, and Rachel Ward, Improved Bounds for Sparse Recovery from Subsampled Random Convolutions, §2.1 (standard reference, not scraped)