LemmaStatement: Literature-sourcedProof: 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.

A block-tail estimate for the largest coordinates

Statement

Let $n, s \in N$ with $n \geq 1$ and $1 \leq s \leq n$ , and let $h \in R^{n}$ use one-based coordinate labels $[n] = {1, \dots, n}$ , with label $j$ corresponding to library coordinate $j - 1$ . In real scalar expressions, a natural number denotes its canonical real image. Order the coordinates by decreasing $∣ h_{j} ∣$ , breaking ties by increasing $j$ . Let $S$ consist of the first $s$ indices, and partition $S^{c}$ in this same order into consecutive nonempty blocks $T_{1}, \dots, T_{q}$ of size $s$ , with only the last block possibly smaller; if $S^{c} = \emptyset$ , take $q = 0$ . Then $∥ h_{S^{c}} ∥_{2} \leq ∥ h_{S} ∥_{2} + \frac{∥ h_{S^{c}} ∥_{1}}{\sqrt{s}} .$

Statement references

One-based finite coordinate restrictions

Finite-dimensional one- and two-norms

Canonical real image of the natural scalar $s$

Triangle inequality for the finite-dimensional two-norm

Positivity and strict increase of canonical natural scalars

Foucart and Rauhut, A Mathematical Introduction to Compressive Sensing, §4.3, proof of Theorem 4.25, printed pp. 89–90

Mendelson, Rauhut, and Ward, Improved Bounds for Sparse Recovery from Subsampled Random Convolutions, §2.1, Theorem 2.2, printed p. 6

Facts & Assumptions

Given: Integers $n \geq 1$ , $1 \leq s \leq n$ , a vector $h \in R^{n}$ , the deterministic ordered coordinate list $j_{1}, \dots, j_{n}$ , its first- $s$ set $S = {j_{1}, \dots, j_{s}}$ , and the finite successive tail blocks $T_{1}, \dots, T_{q}$ .

[F1]

The strict nullspace property: $h_{S}$ agrees with $h$ on $S$ and is zero on $S^{c}$ ; the coordinate labels are one-based with label $j$ identified with library coordinate $j - 1$ .

[F2]

The $p$ -norms $∥ x ∥_{p}$ for rational $p \geq 1$ , and $∥ x ∥_{\infty}$ : $∥ v ∥_{1} = \sum_{j} ∣ v_{j} ∣$ and $∥ v ∥_{2} = (\sum_{j} ∣ v_{j} ∣^{2})^{1 / 2}$ on finite-dimensional real coordinate spaces.

[F3]

Each $∥ \cdot ∥_{p}$ is a norm on $R^{n}$ , and the induced metrics are exactly $d_{1}$ , $d_{2}$ and $d_{\infty}$ of the published metric-spaces page: $∥ \cdot ∥_{2}$ is a norm and obeys the triangle inequality.

[F4]

Laws of finite sums and finite products: finite sums preserve termwise inequalities and a sum of nonnegative terms is nonnegative.

[F5]

Squaring is monotone on the nonnegatives: for nonnegative $a, b$ , $a^{2} \leq b^{2}$ implies $a \leq b$ .

[F6]

The canonical natural $ι (n) = n \cdot 1_{F}$ of a field: a natural number used as a real scalar denotes its canonical real image.

[F7]

Canonical naturals are positive and strictly increasing: the canonical real image of $s$ is positive for $s \geq 1$ ; if $k_{r} \leq s$ as natural numbers, then their canonical real images satisfy $k_{r} \leq s$ .

Proof

1.1givenF1F2F4F5algebra

If $q = 0$ , then $S^{c} = \emptyset$ and the conclusion is $0 \leq ∥ h_{S} ∥_{2}$ . If $q \geq 1$ , write $r = ∣ T_{1} ∣ \leq s$ . The order gives $T_{1} = {j_{s + 1}, \dots, j_{s + r}}$ and $S = {j_{1}, \dots, j_{s}}$ , with $∣ h_{j_{s + k}} ∣ \leq ∣ h_{j_{k}} ∣$ for every $1 \leq k \leq r$ . Termwise squaring and finite-sum monotonicity therefore give $∥ h_{T_{1}} ∥_{2}^{2} = \sum_{k = 1}^{r} ∣ h_{j_{s + k}} ∣^{2} \leq \sum_{k = 1}^{r} ∣ h_{j_{k}} ∣^{2} \leq \sum_{k = 1}^{s} ∣ h_{j_{k}} ∣^{2} = ∥ h_{S} ∥_{2}^{2} .$ Both norms are nonnegative, so [F5] gives $∥ h_{T_{1}} ∥_{2} \leq ∥ h_{S} ∥_{2}$ .

2.1givenF2F3F4F5F6F7step 1.1algebra∎

For each $2 \leq r \leq q$ , the preceding block $T_{r - 1}$ has size $s$ . Its last ordered coordinate has magnitude no greater than any earlier entry, hence no greater than the average magnitude on $T_{r - 1}$ . Every entry of $T_{r}$ is no greater than that last entry. Put $c = ∥ h_{T_{r - 1}} ∥_{1} / s$ . Then each entry of $T_{r}$ has magnitude at most $c$ . If $k_{r} = ∣ T_{r} ∣$ , termwise comparison gives $∥ h_{T_{r}} ∥_{2}^{2} = \sum_{j \in T_{r}} ∣ h_{j} ∣^{2} \leq k_{r} c^{2} \leq s c^{2} = \frac{∥ h_{T_{r - 1}} ∥_{1}^{2}}{s},$ using $k_{r} \leq s$ as natural numbers: padding the sum of $k_{r}$ copies of the nonnegative number $c^{2}$ by the remaining nonnegative copies gives the sum of $s$ copies, by [F4]; [F6,F7] interpret these counts as real scalars. Since both sides are nonnegative, [F5] gives $∥ h_{T_{r}} ∥_{2} \leq \frac{∥ h_{T_{r - 1}} ∥_{1}}{\sqrt{s}} .$ The blocks are disjoint and finite. By [F6], [F7], the triangle inequality, step 1.1, and this block bound, $∥ h_{S^{c}} ∥_{2} = ∥ \sum_{r = 1}^{q} h_{T_{r}} ∥_{2} \leq \sum_{r = 1}^{q} ∥ h_{T_{r}} ∥_{2} \leq ∥ h_{S} ∥_{2} + \frac{1}{\sqrt{s}} \sum_{r = 1}^{q - 1} ∥ h_{T_{r}} ∥_{1} \leq ∥ h_{S} ∥_{2} + \frac{∥ h_{S^{c}} ∥_{1}}{\sqrt{s}} .$ This proves the claimed estimate, including a final block smaller than $s$ .

Remarks

The tie-breaking rule makes the block partition deterministic. The proof uses only finite coordinate comparisons and the Euclidean triangle inequality; no choice axiom is used.

Depends on

Used by

Robust nullspace property gives stable noisy recovery Theorem

Dependency tree · two levels

46 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 proof of Theorem 4.25 (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)