TheoremStatement: Literature-sourcedProof: AI-adaptedPipeline-generatedprecheck pass

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.

Leverage-score row sampling embeds the column space

Statement

Let $Q \in K^{n \times d}$ , $d \geq 1$ , have orthonormal columns, and let $ℓ_{i} = ∥ e_{i}^{*} Q ∥_{2}^{2}$ . Let $π$ be a probability vector with $π_{i} \geq β ℓ_{i} / d$ for $0 < β \leq 1$ , and draw $S$ by With-replacement leverage-score row sampling and rescaling with replacement. For $0 < ε, δ < 1$ , if

m \geq \frac{8 d}{β ε^{2}} \log (\frac{2 d}{δ}),

then with probability at least $1 - δ$ ,

∥ Q^{*} S^{*} S Q - I_{d} ∥_{2} \leq ε .

Equivalently, $S$ is an $ε$ -subspace embedding for $Ran (Q)$ . In the usual confidence range $0 < δ \leq 1 / 2$ , the simpler sufficient condition

m \geq \frac{16 d}{β ε^{2}} \log (\frac{d}{δ})

follows. For a matrix $A$ of rank $d$ , any orthonormal basis $Q$ of $Ran (A)$ gives the corresponding embedding guarantee on $Ran (A)$ .

Facts & Assumptions

Given: An orthonormal $Q$ , the stated sampling probabilities and parameters, and the with-replacement sketch draw.

[F1]

The leverage scores are basis-independent, sum to $d$ , and satisfy $0 \leq ℓ_{i} \leq 1$ (Row leverage scores of a finite-dimensional subspace, Leverage scores are basis-independent and sum to the dimension).

[F2]

Each draw independently samples row $i$ with probability $π_{i}$ and puts $e_{i}^{*} / \sqrt{m π_{i}}$ in the corresponding row; a zero-probability row has zero leverage and is not sampled (With-replacement leverage-score row sampling and rescaling).

[F3]

If independent centered Hermitian matrices $B_{j}$ satisfy $∥ B_{j} ∥_{2} \leq R$ and $∥ E B_{j}^{2} ∥_{2} \leq v$ , then $\Pr {∥ \sum_{j = 1}^{m} B_{j} ∥_{2} > \sqrt{2 m v a} + 2 R a / 3} \leq 2 d e^{- a}$ for every $a > 0$ (Bounded independent matrix Bernstein bound from the trace exponential).

[F4]

An $ε$ -embedding has the squared-norm inequality on every vector of the specified subspace (Oblivious squared-norm subspace embeddings).

[F5]

For Hermitian matrices, write $X ⪯ Y$ when $v^{*} (Y - X) v \geq 0$ for every vector $v$ ; the operator norm is $\max_{∥ v ∥_{2} = 1} ∥ M v ∥_{2}$ on a nonzero finite-dimensional domain (The operator norm is zero on the zero domain and otherwise is max_{||v||=1} ||Tv||).

[F6]

The inner product satisfies Cauchy--Schwarz over both fields (Cauchy–Schwarz: $∣ ⟨ u, v ⟩ ∣ \leq ∥ u ∥ ∥ v ∥$ , with equality exactly for linearly dependent vectors).

Proof

Given: The hypotheses in the Statement.

1.1F1F2algebra

Write $z_{i} = Q^{*} e_{i} \in K^{d}$ , so $∥ z_{i} ∥_{2}^{2} = ℓ_{i}$ . For draw $j$ , let $J_{j}$ be its sampled index and define $Y_{j} = z_{J_{j}} z_{J_{j}}^{*} / π_{J_{j}}$ . By [F2], the $Y_{j}$ are independent and $E Y_{j} = \sum_{i : π_{i} > 0} z_{i} z_{i}^{*} = Q^{*} Q = I_{d}$ ; terms with $π_{i} = 0$ have $z_{i} = 0$ by [F1] and contribute zero.

2.1F1step 1.1F3algebra

Put $R = d / β \geq 1$ and $B_{j} = Y_{j} - I_{d}$ . The rank-one identity $(z_{i} z_{i}^{*})^{2} = ℓ_{i} z_{i} z_{i}^{*}$ and $π_{i} \geq β ℓ_{i} / d$ give $∥ Y_{j} ∥_{2} = ℓ_{J_{j}} / π_{J_{j}} \leq R$ and $Y_{j}^{2} ⪯ R Y_{j}$ . Thus $∥ B_{j} ∥_{2} \leq \max (1, R - 1) \leq R$ , $E B_{j} = 0$ , and $0 ⪯ E B_{j}^{2} = E Y_{j}^{2} - I_{d} ⪯ (R - 1) I_{d} ⪯ R I_{d}$ . Hence [F3] applies with both bounds equal to $R$ .

3.1F3step 2.1givenalgebra

Set $a = \log (2 d / δ)$ . By [F3], $\Pr {∥ \sum_{j = 1}^{m} B_{j} ∥_{2} > \sqrt{2 m R a} + 2 R a / 3} \leq 2 d e^{- a} = δ$ . Under the first sample-size condition, $m ε^{2} \geq 8 R a$ , so $\sqrt{2 m R a} \leq m ε / 2$ . Also $m ε / 2 \geq 4 R a / ε \geq 2 R a / 3$ , since $0 < ε < 1$ . Thus the Bernstein threshold is at most $m ε$ .

4.1F2F4F5F6step 2.1step 3.1algebra

From the sampled-row definition in [F2], $Q^{*} S^{*} S Q = m^{- 1} \sum_{j} Y_{j}$ , so $Q^{*} S^{*} S Q - I_{d} = m^{- 1} \sum_{j} B_{j}$ . Step 2.1 therefore proves $∥ Q^{*} S^{*} S Q - I_{d} ∥_{2} \leq ε$ with probability at least $1 - δ$ . For nonzero $y$ , [F5] and [F6] imply $∣ y^{*} (Q^{*} S^{*} S Q - I_{d}) y ∣ \leq ∥ y ∥_{2} ∥ (Q^{*} S^{*} S Q - I_{d}) y ∥_{2} \leq ε ∥ y ∥_{2}^{2}$ ; the same holds for zero $y$ . Thus $(1 - ε) ∥ y ∥_{2}^{2} \leq ∥ S Q y ∥_{2}^{2} \leq (1 + ε) ∥ y ∥_{2}^{2}$ , and because $Q$ is an isometry onto its range, this is the embedding property in [F4].

5.1givenstep 4.1algebra∎

If $0 < δ \leq 1 / 2$ and $d \geq 1$ , then $d / δ \geq 2$ , hence $\log (2 d / δ) = \log (d / δ) + \log 2 \leq 2 \log (d / δ)$ . Therefore the second stated sample-size condition implies the first. For any rank- $d$ matrix $A$ , its range is $Ran (Q)$ , so the same embedding statement applies to $A$ 's column space.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

20 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

David P. Woodruff, Sketching as a Tool for Numerical Linear Algebra, §2.4, Theorem 17 (standard reference, not scraped)
David Woodruff, 15-859T Lecture 4.2, Leverage Score Sampling gives a Subspace Embedding, Claims 2–3 (standard reference, not scraped)
Joel A. Tropp, An Introduction to Matrix Concentration Inequalities, §6.6 (standard reference, not scraped)