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.

An embedded QR right preconditioner has controlled singular values

Statement

Let $n, m, d \geq 1$ with $n, m \geq d$ , let $A \in K^{n \times d}$ have full column rank, and let $0 < ε < 1$ , and suppose the particular matrix $S$ is an $ε$ -subspace embedding for $Ran (A)$ . A reduced QR factorization $S A = Q R$ exists and has nonsingular $R$ , so the preconditioner $P_{S} = R^{- 1}$ of Right preconditioner from the reduced QR factor of a sketch is defined. Its right-preconditioned matrix satisfies

\frac{1}{\sqrt{1 + ε}} \leq σ_{\min} (A P_{S}) \leq σ_{\max} (A P_{S}) \leq \frac{1}{\sqrt{1 - ε}}, κ_{2} (A P_{S}) : = \frac{σ_{\max} (A P_{S})}{σ_{\min} (A P_{S})} \leq \sqrt{\frac{1 + ε}{1 - ε}} .

Facts & Assumptions

Given: Full-column-rank $A$ , an $ε$ -embedding $S$ on $Ran (A)$ , and $0 < ε < 1$ .

[F1]

On the embedded subspace, $(1 - ε) ∥ x ∥_{2}^{2} \leq ∥ S x ∥_{2}^{2} \leq (1 + ε) ∥ x ∥_{2}^{2}$ for every $x \in Ran (A)$ (Oblivious squared-norm subspace embeddings).

[F2]

A reduced QR factorization has $S A = Q R$ , $Q^{*} Q = I_{d}$ , and upper-triangular $R$ ; Householder or Givens steps construct one for every finite $S A$ (Full, reduced, and column-pivoted computational QR factorisations, Successive Householder or Givens transformations produce full and reduced QR factorisations with the standard dense operation counts).

[F3]

Singular values give the minimum and maximum expansion of a finite matrix on unit vectors, and condition number here is defined as their positive ratio (Every linear map between finite-dimensional real or complex inner product spaces admits a singular value decomposition, Spectral and Frobenius norms are unitarily invariant, are given by singular values, and satisfy the sharp rank comparison).

Proof

Given: The hypotheses in the Statement.

1.1F1F2givenalgebra

If $y \in K^{d}$ is nonzero, full column rank gives $A y \neq 0$ ; then [F1] gives $∥ S A y ∥_{2}^{2} \geq (1 - ε) ∥ A y ∥_{2}^{2} > 0$ . Thus $S A$ has full column rank. The reduced QR factorization in [F2] exists. If $R v = 0$ , then $S A v = Q R v = 0$ ; injectivity of $S A$ forces $v = 0$ , so $R$ is nonsingular and $P_{S} = R^{- 1}$ is defined.

2.1F1F2step 1.1algebra

For any $y \in K^{d}$ , $S A P_{S} y = Q R R^{- 1} y = Q y$ , so $∥ S A P_{S} y ∥_{2}^{2} = ∥ Q y ∥_{2}^{2} = ∥ y ∥_{2}^{2}$ by [F2]. Since $A P_{S} y \in Ran (A)$ , [F1] yields $(1 - ε) ∥ A P_{S} y ∥_{2}^{2} \leq ∥ y ∥_{2}^{2} \leq (1 + ε) ∥ A P_{S} y ∥_{2}^{2}$ .

3.1F3step 2.1algebra

For every unit $y$ , step 2.1 implies $1 / \sqrt{1 + ε} \leq ∥ A P_{S} y ∥_{2} \leq 1 / \sqrt{1 - ε}$ . By [F3], the minimum and maximum of these values over the unit sphere are $σ_{\min} (A P_{S})$ and $σ_{\max} (A P_{S})$ , respectively. This proves both singular-value bounds.

4.1step 3.1algebra∎

The lower bound in step 3.1 is positive, so the ratio defining $κ_{2}$ is valid. Dividing the upper singular-value bound by the lower one gives $κ_{2} (A P_{S}) \leq \sqrt{(1 + ε) / (1 - ε)}$ .

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

22 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.6 (standard reference, not scraped)
Michael W. Mahoney, Randomized Algorithms for Matrices and Data, §4.3 (standard reference, not scraped)