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

Two-stage ℓ2 sampling controls Gram matrices

Statement

Let $M \in R^{a \times b}$ be nonzero, let $q_{1}, \dots, q_{a}$ be a probability distribution satisfying $q_{i} \geq α ∥ M_{i, *} ∥_{2}^{2} / ∥ M ∥_{F}^{2}$ for some $0 < α \leq 1$ , and let $p$ be a positive integer. Draw $p$ independent row indices $I_{1}, \dots, I_{p}$ from this distribution and form $N \in R^{p \times b}$ with row $t$ equal to $M_{I_{t}, *} / \sqrt{p q_{I_{t}}}$ ; a zero row with $q_{i} = 0$ is never sampled. Then $E ∥ M^{T} M - N^{T} N ∥_{F}^{2} \leq \frac{∥ M ∥_{F}^{4}}{α p},$ and for every $θ > 0$ , $P (∥ M^{T} M - N^{T} N ∥_{F} \geq θ ∥ M ∥_{F}^{2}) \leq \frac{1}{α p θ^{2}} .$ For column sampling, assume the analogous probability lower bound on columns and apply the result to $M^{T}$ .

In particular, let $A \in R^{m \times n}$ be nonzero with $F = ∥ A ∥_{F}$ , and use $p$ samples at each of two stages. First draw independent $I_{r}$ with probabilities $d_{i} = ∥ A_{i, *} ∥_{2}^{2} / F^{2}$ and set $S_{r, *} = A_{I_{r}, *} / \sqrt{p d_{I_{r}}}$ . Conditional on $S$ , draw independent $J_{c}$ with probabilities $f_{j} = ∥ S_{*, j} ∥_{2}^{2} / F^{2}$ and set $W_{*, c} = S_{*, J_{c}} / \sqrt{p f_{J_{c}}}$ . These are the exact normalized two-stage sketches; zero-probability indices are never selected. Then $∥ S ∥_{F} = ∥ W ∥_{F} = F$ , both Gram estimators are unbiased (the second conditional on $S$ ), and $E ∥ A^{T} A - S^{T} S ∥_{F}^{2} \leq F^{4} / p, E [∥ S S^{T} - W W^{T} ∥_{F}^{2} ∣ S] \leq F^{4} / p .$ For every $θ > 0$ , the probability that either Gram error is at least $θ F^{2}$ is at most $2 / (p θ^{2})$ ; the two errors need not be independent.

Facts & Assumptions

Given: The finite matrices, sampling probabilities, positive sample count, and independent samples within each stage in the Statement; second-stage sampling is conditional on the realized first stage.

[F1]

Finite probability spaces, outcome weights, events, and event probabilities: a finite probability law assigns nonnegative weights summing to one; here the assumed row law assigns weight $q_{i}$ to index $i$ .

[F2]

Pairwise and mutual independence of finite-valued random variables: independent sampled indices make their entrywise matrix-valued contributions independent.

[F3]

The Frobenius norm $∥ A ∥_{F} = (\sum_{i, j} ∣ a_{i j} ∣^{2})^{1 / 2}$ on real or complex matrices: $∥ X ∥_{F}^{2}$ is the finite sum of squared entry moduli.

[F4]

Markov's inequality on a finite probability space: for nonnegative $Y$ and $c > 0$ , $P (Y \geq c) \leq E [Y] / c$ .

Proof

1.1givenF1algebra

The assumed lower bound on $q_{i}$ forces $M_{i, *} = 0$ whenever $q_{i} = 0$ . For one sampled row $I$ , define the random matrix $X = M_{I, *}^{T} M_{I, *} / q_{I}$ when $q_{I} > 0$ , and $X = 0$ on zero-probability zero rows. For each matrix entry $(r, s)$ , $E X_{r s} = \sum_{i : q_{i} > 0} q_{i} \frac{M_{i r} M_{i s}}{q_{i}} = \sum_{i} M_{i r} M_{i s} = (M^{T} M)_{r s} .$ Thus $N^{T} N = p^{- 1} \sum_{t = 1}^{p} X_{t}$ is unbiased.

1.2givenF1F3algebra

The squared Frobenius norm of one contribution is $∥ X ∥_{F}^{2} = ∥ M_{I, *} ∥_{2}^{4} / q_{I}^{2}$ . Therefore $E ∥ X ∥_{F}^{2} = \sum_{i : q_{i} > 0} \frac{∥ M_{i, *} ∥_{2}^{4}}{q_{i}} \leq \frac{∥ M ∥_{F}^{2}}{α} \sum_{i} ∥ M_{i, *} ∥_{2}^{2} = \frac{∥ M ∥_{F}^{4}}{α},$ using the lower bound on each $q_{i}$ .

2.1step 1.1step 1.2F2algebra

Expand $∥ p^{- 1} \sum_{t} (X_{t} - E X_{t}) ∥_{F}^{2}$ entrywise. For distinct $s, t$ , independence [F2] and zero means make each cross expectation zero. Hence its expectation is $p^{- 1} E ∥ X - E X ∥_{F}^{2} \leq p^{- 1} E ∥ X ∥_{F}^{2} \leq ∥ M ∥_{F}^{4} / (α p)$ by step 1.2.

3.1step 2.1F3F4algebra

Apply [F4] to the nonnegative random variable $Y = ∥ M^{T} M - N^{T} N ∥_{F}^{2}$ with threshold $θ^{2} ∥ M ∥_{F}^{4} > 0$ . Step 2.1 yields the probability bound. Transposing $M$ interchanges rows and columns, proving the column assertion.

4.1givenF1F3step 1.1step 2.1step 3.1algebra

In the exact two-stage construction every sampled row of $S$ has squared norm $F^{2} / p$ , so $∥ S ∥_{F}^{2} = F^{2}$ and $\sum_{j} f_{j} = 1$ . Every sampled column of $W$ likewise has squared norm $F^{2} / p$ , giving $∥ W ∥_{F} = F$ . Apply steps 1.1–2.1 with $M = A$ , $α = 1$ , and row law $d$ for the first Gram estimator. For each fixed $S$ , apply the transposed result with $M = S^{T}$ , $α = 1$ , and row law $f$ for the second estimator. This proves both unbiasedness assertions and both second-moment bounds, with the second conditional on $S$ .

5.1F1step 3.1step 4.1algebra∎

Step 3.1 bounds the first-stage tail by $1 / (p θ^{2})$ and bounds the second-stage tail by the same number conditional on every $S$ . Averaging the latter bound over the finite first-stage histories gives the same unconditional bound. Pointwise the indicator of either failure is at most the sum of the two failure indicators, so summing their finite probability weights gives $2 / (p θ^{2})$ . No independence between the stages' errors is used.

Depends on

Used by

Dependency tree · two levels

21 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

Alan Frieze, Ravi Kannan, and Santosh Vempala, Fast Monte-Carlo Algorithms for Finding Low-Rank Approximations, full author manuscript (standard reference, not scraped)
Ewin Tang, A quantum-inspired classical algorithm for recommendation systems, version 3 (standard reference, not scraped)