The RandNLA case study in VSCL: statements and proofs
Lean has checked proofs of the spectral-norm bound for element-wise sparsification, the structural bound for sketched low-rank approximation, the subspace embedding property and the relative-error least-squares bound of the subsampled randomized Hadamard transform, a sparse subspace embedding, and the relative-error least-squares bound with approximate leverage-score sampling, all in exact arithmetic. The bound for sparsification, the two results for the subsampled randomized Hadamard transform and the least-squares bound with leverage-score sampling rest on Lieb's concavity theorem, which the library proves. These results come from the survey by Drineas and Mahoney, RandNLA: Randomized Numerical Linear Algebra, Communications of the ACM 59(6), 2016, which this case study formalizes in VSCL. Lean reports that all 35 proofs use no axiom beyond its three standard ones (propext, Classical.choice and Quot.sound). Our paper discusses this case study.
Each statement is published apart from its proof, so that a reader can compare it with the survey without reading any proof. No expert outside our group has been asked to make this comparison. At commit 55a62f4 of 2026-11-16 the library publishes 47 statements from the survey, and 35 of them have a published proof. The subspace embedding for leverage-score sampling is among the 12 statements whose proof is not published.
The sparsification bound is proved for square matrices and a thresholded sampler. The low-rank bound adds a condition on the singular vectors and bounds the error rather than its square, which is weaker for the spectral and Frobenius norms. The sparse embedding, the two Hadamard results and the leverage-score least-squares bound fix choices that the survey leaves open. The two results for the subsampled randomized Hadamard transform take the number of rows to be a power of two, and no statement concerns running time. The library's notes on the groups of statements record each choice and change.
What the proofs depend on
For each of the six results above, the table gives its place in the survey and the number of theorems of the library that its proof depends on. We count a theorem if the proof refers to it directly or through a chain of references in Lean's elaborated statements and proofs, and leave out the theorems of Mathlib and the 57 further theorems in the case study's own files that the proofs reach.
| Result | Place in the survey | Library theorems |
|---|---|---|
| Spectral-norm bound for element-wise sparsification | Equation (2) | 430 |
| Structural bound for sketched low-rank approximation | Equation (9) | 184 |
| Subspace embedding of the subsampled randomized Hadamard transform | Algorithm 3 | 565 |
| Relative-error least squares with that transform | Page 87 | 589 |
| Relative-error least squares with approximate leverage-score sampling | Page 87 | 451 |
| Sparse subspace embedding | Algorithm 3 | 91 |
| All 35 published proofs | 1,053 |
The proofs share many theorems, so the rows add up to more than the last. Together, the 35 proofs depend on 1,053 theorems of the library. Among them, 771 of the 1,053 theorems, on RandNLA, matrix inequalities and finite probability, entered the library with this case study, including a proof of Lieb's concavity theorem. Of the other 282, on general linear algebra, a search of the source text finds 117 to 136 also in the library's files for Higham's Accuracy and Stability of Numerical Algorithms, depending on how repeated short names are counted. The proofs differ in size, and twelve of the 35 depend on at most three theorems outside the RandNLA modules.
How to check a statement
- Read the statement's Lean text and the definitions it uses. The name of each statement and of each definition below leads to it in the library.
- Compare it with the survey at the place given under "In the survey".
- Read the library's note on its group, which records where a statement differs from the printed claim or adds a condition.
- Lean checks each published proof. Anyone can rebuild the library at commit
55a62f4, and Lean's#print axiomslists the axioms that a proof uses, here only the three standard ones.
How to cite
Cite this record with the commit of the library that it describes.
| Field | Value |
|---|---|
| Title | The RandNLA case study in VSCL: statements and proofs |
| Library commit | 55a62f4 |
| Date | 2026-11-16 |
| Repository | https://github.com/the-numerical-proving-ground/lean-computational-mathematics |
The library itself carries its own citation, in its citation file.
The statements
The list holds the 47 statements, grouped by the file of the library that holds them, and the five definitions that some of them use, last in their file. Each group carries the title that the library gives its file, and the library's own note on the file where there is one.
Each entry gives the name of the statement in Lean, the library's own description of it, its place in the survey as the library names it, the definitions that its Lean text uses, its Lean text, and whether its proof is published. For six statements a few plain words come first, which say what the statement asserts and how it differs from the survey. For a published proof the entry gives the number of theorems of the library that the proof depends on, counted as in the table. The name leads to the statement, each definition to its place, and the words "Proof published" to the proof, in the library at commit 55a62f4 of 2026-11-16. We do not reproduce the text of the survey.
Proof-free contracts for subspace invariance and geometry
BasisGeometry.lean · 2 statements, each with a published proof
CACM 59(6), p. 85, Eq. (6) and the prose after Eq. (7). These targets isolate basis independence and the deterministic consequences of an embedding event; they do not replace the separate randomized Eq. (7) construction.
The normalized leverage law is independent of the orthonormal basis chosen for the same positive-dimensional column space. Frame widths may be supplied independently; orthonormality and equal ranges force consistency.
In the survey: Equation (6), page 85.
Uses:
Has,Orthonormal Columns leverage,Score leverageScore Prob Lean statement
def leverageBasisInvariance : Prop := ∀ (m n p : ℕ) (U : Matrix (Fin m) (Fin n) ℝ) (V : Matrix (Fin m) (Fin p) ℝ), 0 < n → 0 < p → HasOrthonormalColumns U → HasOrthonormalColumns V → Set.range U.mulVec = Set.range V.mulVec → (U * U.transpose = V * V.transpose) ∧ (∀ i, leverageScore U i = leverageScore V i) ∧ (∀ i, leverageScoreProb U i = leverageScoreProb V i)Proof published. It depends on 4 theorems of the library.
Eq. (7), with ε in (0,1), preserves all squared norms in the specified column space, is injective there, and preserves the rank of the original matrix.
Sacts on the original vectors andS*Uis its coordinate sketch.In the survey: Equation (7), page 85, and the text after it.
Uses:
Has,Orthonormal Columns id,Matrix op,Norm2Le row,Sketch Gram vecNorm2Sq Lean statement
def subspaceEmbeddingGeometry : Prop := ∀ (m n d r : ℕ) (A : Matrix (Fin m) (Fin n) ℝ) (U : Matrix (Fin m) (Fin d) ℝ) (S : Matrix (Fin r) (Fin m) ℝ), HasOrthonormalColumns U → Set.range A.mulVec = Set.range U.mulVec → ∀ ε : ℝ, 0 < ε → ε < 1 → opNorm2Le (fun j k => idMatrix d j k - rowSketchGram (S * U) j k) ε → (∀ y ∈ Set.range A.mulVec, (1 - ε) * vecNorm2Sq y ≤ vecNorm2Sq (S.mulVec y) ∧ vecNorm2Sq (S.mulVec y) ≤ (1 + ε) * vecNorm2Sq y) ∧ Set.InjOn S.mulVec (Set.range A.mulVec) ∧ (S * A).rank = A.rankProof published. It depends on 19 theorems of the library.
Covered-support entry-residual moment contract
EntryResidualMoments.lean · 1 statement, with a published proof
Original row016, p83, concerns zero mean and bounded variance of entries of the raw Algorithm1 residual. This conditional contract explicitly retains the nonzero-entry support coverage required by corrected unbiasedness. It does not silently repair the original unrestricted claim. The supplied distribution is normalized by its finite-probability type, and draws use its literal iid law. No truncation or independence between different residual coordinates is asserted.
Coordinate mean, exact variance, finite support bound and zero-atom branch for the original zero-initialized iid importance sketch on covered support.
In the survey: Page 83, Algorithm 1, the mean and variance of the entries of its error.
Uses:
Finite,Probability Finite,Probability.event Prob Finite,Probability.expectation Real Finite,Probability.iid Finite,Probability.prob Finite,Probability.variance Real entrySampling Residual Lean statement
def entryResidualMeanVariance : Prop := ∀ (m n s : ℕ) (A : Fin m → Fin n → ℝ) (P : FiniteProbability (Fin m × Fin n)), 0 < m → 0 < n → 0 < s → (∀ i j, A i j ≠ 0 → 0 < P.prob (i,j)) → ∀ i j, (P.iid s).expectationReal (fun ω => entrySamplingResidual A P ω i j) = 0 ∧ (0 < P.prob (i,j) → (P.iid s).varianceReal (fun ω => entrySamplingResidual A P ω i j) = A i j ^ 2 * (1 / P.prob (i,j) - 1) / (s : ℝ) ∧ 0 ≤ A i j ^ 2 * (1 / P.prob (i,j) - 1) / (s : ℝ) ∧ ∀ ω, 0 < (P.iid s).prob ω → |entrySamplingResidual A P ω i j| ≤ |A i j| * (1 + 1 / P.prob (i,j))) ∧ (P.prob (i,j) = 0 → A i j = 0 ∧ (P.iid s).eventProb {ω | entrySamplingResidual A P ω i j = 0} = 1 ∧ (P.iid s).varianceReal (fun ω => entrySamplingResidual A P ω i j) = 0)Proof published. It depends on 29 theorems of the library.
Corrected, thresholded entry-sparsification contract
EntrySparsification.lean · 1 statement, with a published proof
This is the square theorem supported by Drineas--Zouzias (survey reference18), with its explicit zero branch and upward-compatible integer sample condition. It is a correction to applying survey Equation(2) to the unchanged raw sampler. The strict-threshold convention is the printed algorithm-box convention.
corrected
Truncated Entry Guarantee In plain words: For a square n × n matrix A, the entries smaller than ε/(2n) in absolute value are set to zero, and s samples are drawn independently from the remaining entries, with probabilities proportional to their squares. If 14 n log(2n/δ) times the squared Frobenius norm of A is at most s ε², then with probability at least 1 − δ the error in the spectral norm is at most ε and the sketch has at most s nonzero entries. The survey states Equation (2) for the sampler without this threshold, and this is the thresholded form of its reference 18.
Corrected reference18 guarantee, including all matrices and at most
snonzero entries. The sample condition is multiplied by the positiveeps².In the survey: Equation (2), in the corrected form of the survey's reference 18.
Uses:
Elementwise,Sample Elementwise,Trace Finite,Probability.event Prob frob,Norm Sq Rect rect,Op Norm2Le truncated,Elementwise Probability truncatedElementwise Sketch Lean statement
def correctedTruncatedEntryGuarantee : Prop := ∀ (n s : ℕ) (A : Fin n → Fin n → ℝ) (eps δ : ℝ), 0 < n → 0 < s → 0 < eps → 0 < δ → δ < 1 → 14 * (n : ℝ) * frobNormSqRect A * Real.log ((2 * (n : ℝ)) / δ) ≤ (s : ℝ) * eps ^ 2 → 1 - δ ≤ (truncatedElementwiseProbability (s := s) (eps / (2 * (n : ℝ))) A).eventProb {outcome | rectOpNorm2Le (fun i j => A i j - truncatedElementwiseSketch (eps / (2 * (n : ℝ))) A outcome i j) eps ∧ (Finset.univ.filter (fun ij : Fin n × Fin n => truncatedElementwiseSketch (eps / (2 * (n : ℝ))) A outcome ij.1 ij.2 ≠ 0)).card ≤ s}Proof published. It depends on 430 theorems of the library.
Corrected entry sparsification on bounded accuracy
EntrySparsificationAccuracy.lean · 1 statement, with a published proof
This source-local contract selects strict thresholding, the actual squared-entry law with its deterministic zero branch, and accuracy and failure tolerance in (0,1). It states the support count for every output as well as the spectral error probability. The broader positive-accuracy contract remains unchanged.
corrected
Truncated Entry Guarantee Unit Accuracy Corrected finite sampling guarantee for
0 < eps < 1, with deterministic support size and the actual Option-valued thresholded sampling law.In the survey: Equation (2), in the corrected form of the survey's reference 18, for an accuracy below one.
Uses:
Elementwise,Sample Elementwise,Trace Finite,Probability.event Prob frob,Norm Sq Rect rect,Op Norm2Le truncated,Elementwise Probability truncatedElementwise Sketch Lean statement
def correctedTruncatedEntryGuaranteeUnitAccuracy : Prop := ∀ (n s : ℕ) (A : Fin n → Fin n → ℝ) (eps δ : ℝ), 0 < n → 0 < s → 0 < eps → eps < 1 → 0 < δ → δ < 1 → 14 * (n : ℝ) * frobNormSqRect A * Real.log ((2 * (n : ℝ)) / δ) ≤ (s : ℝ) * eps ^ 2 → (∀ outcome : Option (ElementwiseTrace n n s), (Finset.univ.filter (fun ij : Fin n × Fin n => truncatedElementwiseSketch (eps / (2 * (n : ℝ))) A outcome ij.1 ij.2 ≠ 0)).card ≤ s) ∧ 1 - δ ≤ (truncatedElementwiseProbability (s := s) (eps / (2 * (n : ℝ))) A).eventProb {outcome | rectOpNorm2Le (fun i j => A i j - truncatedElementwiseSketch (eps / (2 * (n : ℝ))) A outcome i j) eps ∧ (Finset.univ.filter (fun ij : Fin n × Fin n => truncatedElementwiseSketch (eps / (2 * (n : ℝ))) A outcome ij.1 ij.2 ≠ 0)).card ≤ s}Proof published. It depends on 430 theorems of the library.
Equation (7) as a success criterion
GramEmbeddingCriterion.lean · 1 statement, with a published proof
This is a condition on an arbitrary sketch, not a claim that a particular randomized construction succeeds. Its quadratic criterion holds simultaneously for every coefficient vector and includes zero coefficient dimension.
Eq. (7)'s identity-Gram equality and its exact all-vector interpretation.
In the survey: Equation (7).
Uses:
Has,Orthonormal Columns id,Matrix op,Norm2 row,Gram row,Sketch Gram vecNorm2Sq Lean statement
def gramEmbeddingCriterion : Prop := ∀ (m d t : ℕ) (U : Matrix (Fin m) (Fin d) ℝ) (B : Matrix (Fin t) (Fin d) ℝ), HasOrthonormalColumns U → ∀ ε : ℝ, 0 < ε → ε < 1 → opNorm2 (fun i j => rowGram U i j - rowSketchGram B i j) = opNorm2 (fun i j => idMatrix d i j - rowSketchGram B i j) ∧ (opNorm2 (fun i j => idMatrix d i j - rowSketchGram B i j) ≤ ε ↔ ∀ x : Fin d → ℝ, |vecNorm2Sq (B.mulVec x) - vecNorm2Sq x| ≤ ε * vecNorm2Sq x) ∧ (opNorm2 (fun i j => idMatrix d i j - rowSketchGram B i j) ≤ ε ↔ ∀ x : Fin d → ℝ, (1 - ε) * vecNorm2Sq x ≤ vecNorm2Sq (B.mulVec x) ∧ vecNorm2Sq (B.mulVec x) ≤ (1 + ε) * vecNorm2Sq x)Proof published. It depends on 18 theorems of the library.
Leading-subspace leverage distribution
LeadingSubspaceLeverage.lean · 1 statement, with a published proof
The footnote-e variant of equation (6) selects the first k left singular vectors of a supplied compatible ordered SVD. Thus the matrix A and the selected leading subspace are linked by reconstruction, rank and orthonormality, rather than by an unspecified leading-subspace predicate. Choices at a repeated singular value are fixed by the supplied SVD. An arbitrary orthonormal basis of that fixed subspace is allowed, specified by equality of actual matrix-vector image sets. Rank-deficient inputs are allowed.
leading
Subspace Leverage Distribution Equation (6), footnote e: normalized leverage probabilities of one chosen leading rank-
kleft singular subspace. The denominator isk.In the survey: Equation (6), footnote e.
Uses:
Has,Orthonormal Columns Is,Real Matrix SVD leading,Left Singular Columns leading,Left Singular Projector leverage,Score Prob rowSq Norm Prob Den Lean statement
def leadingSubspaceLeverageDistribution : Prop := ∀ (m n : ℕ) (A : Matrix (Fin m) (Fin n) ℝ), 0 < m → 0 < n → ∀ (k : ℕ) (_hkpos : 0 < k) (hk : k ≤ A.rank) (s : Fin n → ℝ) (u : Fin A.rank → EuclideanSpace ℝ (Fin m)) (v : Fin A.rank → EuclideanSpace ℝ (Fin n)), IsRealMatrixSVD A A.rank s u v → ∀ W : Matrix (Fin m) (Fin k) ℝ, HasOrthonormalColumns W → Set.range W.mulVec = Set.range (leadingLeftSingularColumns u hk).mulVec → rowSqNormProbDen W = (k : ℝ) ∧ (∀ i, 0 ≤ leverageScoreProb W i) ∧ (∑ i : Fin m, leverageScoreProb W i) = 1 ∧ (∀ i, leverageScoreProb W i = (∑ j : Fin k, W i j ^ 2) / (k : ℝ)) ∧ ∀ i, leverageScoreProb W i = leadingLeftSingularProjector u hk i i / (k : ℝ)Proof published. It depends on 10 theorems of the library.
Page-87 joint least-squares sketch constructions
LeastSquaresConstructions.lean · 2 statements, each with a published proof
Original claims026/027 specify constructions separately from their quantitative children. Scores in026 are supplied relative approximations, not silently exact scores. The Walsh realization in027 has 2^q rows; padding is not implicit. Neither contract asserts score-computation cost, running time or sketch quality.
relative
Leverage Least Squares Construction Original026 construction: normalize supplied relative scores, use an iid common A/b row sampler, and return actual sketch minimizers. Rank zero returns0 without introducing a leverage denominator.
In the survey: Page 87, the least-squares sketch, with approximate leverage scores.
Uses:
Finite,Probability Finite,Probability.event Prob Finite,Probability.iid Finite,Probability.prob Is,Least Squares Minimizer Relative,Leverage Scores Row,Trace augmented,Data Span ls,Column Space Basis Matrix ls,Residual row,Norm Sq row,Sample Sketch With Prob row,Sample Vector With Prob vecNorm2 Lean statement
def relativeLeverageLeastSquaresConstruction : Prop := ∀ (m n s : ℕ) (A : Fin m → Fin n → ℝ) (b : Fin m → ℝ) (a : Fin m → ℝ) (α : ℝ), 0 < m → 0 < n → 0 < s → 0 ≤ α → α < 1 → (∀ _hd : 0 < Module.finrank ℝ (augmentedDataSpan A (fun _ => 0)), RelativeLeverageScores (lsColumnSpaceBasisMatrix A) a α) → (Module.finrank ℝ (augmentedDataSpan A (fun _ => 0)) = 0 → IsLeastSquaresMinimizer A b (fun _ => 0)) ∧ ∀ _hd : 0 < Module.finrank ℝ (augmentedDataSpan A (fun _ => 0)), ∃ (P : FiniteProbability (Fin m)) (xHat : RowTrace m s → Fin n → ℝ), (∀ i, P.prob i = a i / ∑ j : Fin m, a j) ∧ (∀ i, ((1 - α) / (1 + α)) * (rowNormSq (lsColumnSpaceBasisMatrix A) i / (Module.finrank ℝ (augmentedDataSpan A (fun _ => 0)) : ℝ)) ≤ P.prob i) ∧ (∀ samples, (P.iid s).prob samples = ∏ t, P.prob (samples t)) ∧ (P.iid s).eventProb {samples | ∀ t, 0 < P.prob (samples t)} = 1 ∧ (∀ (samples : RowTrace m s) (t : Fin s) (j : Fin n), rowSampleSketchWithProb s A P.prob samples t j = A (samples t) j / Real.sqrt ((s : ℝ) * P.prob (samples t))) ∧ (∀ (samples : RowTrace m s) (t : Fin s), rowSampleVectorWithProb P.prob b samples t = b (samples t) / Real.sqrt ((s : ℝ) * P.prob (samples t))) ∧ ∀ samples, IsLeastSquaresMinimizer (rowSampleSketchWithProb s A P.prob samples) (rowSampleVectorWithProb P.prob b samples) (xHat samples) ∧ ∀ x, vecNorm2 (lsResidual (rowSampleSketchWithProb s A P.prob samples) (rowSampleVectorWithProb P.prob b samples) (xHat samples)) ≤ vecNorm2 (lsResidual (rowSampleSketchWithProb s A P.prob samples) (rowSampleVectorWithProb P.prob b samples) x)Proof published. It depends on 18 theorems of the library.
walsh
Uniform Least Squares Construction Original027 construction: independent signs then independent uniform row sampling, with the same HD transform and scale on A and b. All input ranks are allowed; minimizers are actual outputs rather than hypotheses.
In the survey: Page 87, the least-squares sketch, with a randomized Hadamard transform.
Uses:
Finite,Probability.prob Hadamard,Flat Is,Least Squares Minimizer Is,Orthogonal Rademacher,Trace Row,Sample Row,Trace least,Squares Walsh Matrix diag,Matrix ls,Residual mat,Mul mat,Mul Vec precondition,Rows rademacher,Sign Vector rademacher,Trace Probability row,Sample Sketch With Prob row,Sample Vector With Prob signed,Hadamard Uniform Row Trace Probability uniform,Row Prob uniform,Row Trace Probability vecNorm2 Lean statement
def walshUniformLeastSquaresConstruction : Prop := ∀ (q n s : ℕ) (A : Fin (2 ^ q) → Fin n → ℝ) (b : Fin (2 ^ q) → ℝ) (hm : 0 < 2 ^ q), 0 < n → 0 < s → let m := 2 ^ q let H := leastSquaresWalshMatrix q IsOrthogonal m H ∧ HadamardFlat m H ∧ ∃ xHat : RademacherTrace m × RowTrace m s → Fin n → ℝ, (∀ z, (signedHadamardUniformRowTraceProbability (m := m) (s := s) hm).prob z = (rademacherTraceProbability m).prob z.1 * (uniformRowTraceProbability (steps := s) hm).prob z.2) ∧ (∀ samples, (uniformRowTraceProbability (steps := s) hm).prob samples = ∏ _t : Fin s, ((m : ℝ)⁻¹)) ∧ ∀ (ω : RademacherTrace m) (samples : RowTrace m s), let T := matMul m H (diagMatrix (rademacherSignVector ω)) let B := preconditionRows T A let c := matMulVec m T b (∀ t j, rowSampleSketchWithProb s B uniformRowProb samples t j = Real.sqrt ((m : ℝ) / (s : ℝ)) * B (samples t) j) ∧ (∀ t, rowSampleVectorWithProb uniformRowProb c samples t = Real.sqrt ((m : ℝ) / (s : ℝ)) * c (samples t)) ∧ IsLeastSquaresMinimizer (rowSampleSketchWithProb s B uniformRowProb samples) (rowSampleVectorWithProb uniformRowProb c samples) (xHat (ω, samples)) ∧ ∀ x, vecNorm2 (lsResidual (rowSampleSketchWithProb s B uniformRowProb samples) (rowSampleVectorWithProb uniformRowProb c samples) (xHat (ω, samples))) ≤ vecNorm2 (lsResidual (rowSampleSketchWithProb s B uniformRowProb samples) (rowSampleVectorWithProb uniformRowProb c samples) x)Proof published. It depends on 49 theorems of the library.
The concrete normalized Walsh matrix used by original027.
Lean statement
noncomputable def leastSquaresWalshMatrix (q : ℕ) : Fin (2 ^ q) → Fin (2 ^ q) → ℝ := fun i k => Real.sqrt (((2 ^ q : ℕ) : ℝ)⁻¹) * sylvesterHadamardSignPattern q i kA definition that statements of this file use.
Least-squares existence and exact-leverage output contracts
LeastSquaresExistence.lean · 2 statements, 1 with a published proof
Equation (8), p. 86, has a minimizer for every finite real input, including rank-deficient and empty matrices. The separate page-87 exact-leverage case selects both an original minimizer and exact sketch minimizers and proves their relative residual guarantee. Classical selection makes no computational-cost or approximate-leverage-score assertion.
Equation (8): existence of a minimizer for both the squared library objective and the paper's unsquared Euclidean residual, without rank hypotheses.
In the survey: Equation (8), page 86.
Uses:
Is,Least Squares Minimizer ls,Residual vecNorm2 Lean statement
def leastSquaresMinimizerExists : Prop := ∀ (m n : ℕ) (A : Fin m → Fin n → ℝ) (b : Fin m → ℝ), ∃ xOpt : Fin n → ℝ, IsLeastSquaresMinimizer A b xOpt ∧ ∀ x, vecNorm2 (lsResidual A b xOpt) ≤ vecNorm2 (lsResidual A b x)Proof published. It depends on 4 theorems of the library.
exact
Leverage Least Squares Output Mathematical exact-leverage case of the page-87 algorithm: original and sampled minimizers exist and their returned residual satisfies the guarantee. No minimizer or final error bound is supplied as a premise. Positive input rank includes one; the all-rank minimizer-existence contract above includes rank zero.
In the survey: Page 87, the least-squares algorithm, with exact leverage scores.
Uses:
Finite,Probability.event Prob Is,Least Squares Minimizer Row,Sample Row,Trace augmented,Data Span leverage,Trace Probability ls,Column Space Basis Matrix ls,Residual row,Sample LSMatrix With Basis Scale row,Sample LSVector With Basis Scale vecNorm2 Lean statement
def exactLeverageLeastSquaresOutput : Prop := ∀ (m n s : ℕ) (A : Fin m → Fin n → ℝ) (b : Fin m → ℝ) (hd : 0 < Module.finrank ℝ (augmentedDataSpan A (fun _ => 0))) (η δ : ℝ), 0 < s → 0 < η → η < 1 → 0 < δ → δ < 1 → 10 * (Module.finrank ℝ (augmentedDataSpan A (fun _ => 0)) : ℝ) * Real.log ((4 * (Module.finrank ℝ (augmentedDataSpan A (fun _ => 0)) : ℝ)) / δ) ≤ (s : ℝ) → 8 * (Module.finrank ℝ (augmentedDataSpan A (fun _ => 0)) : ℝ) / (η * δ) ≤ (s : ℝ) → ∃ (xOpt : Fin n → ℝ) (xHat : RowTrace m s → Fin n → ℝ), IsLeastSquaresMinimizer A b xOpt ∧ (∀ samples, IsLeastSquaresMinimizer (rowSampleLSMatrixWithBasisScale s (lsColumnSpaceBasisMatrix A) A samples) (rowSampleLSVectorWithBasisScale s (lsColumnSpaceBasisMatrix A) b samples) (xHat samples)) ∧ 1 - δ ≤ (leverageTraceProbability (steps := s) (lsColumnSpaceBasisMatrix A) (hasOrthonormalColumns_lsColumnSpaceBasisMatrix A) hd).eventProb {samples | vecNorm2 (lsResidual A b (xHat samples)) ≤ (1 + η) * vecNorm2 (lsResidual A b xOpt)}No proof published.
Exact leverage sketching source contracts
LeverageSketching.lean · 5 statements, 1 with a published proof
Equation (7), p. 85, is instantiated by Algorithm 2 with the exact normalized leverage distribution of a positive-dimensional orthonormal basis. The stated sample budget is an explicit sufficient second-moment budget; the survey does not specify an equation-(7) sample count. Equation (8), p. 86, minimizes the unsquared Euclidean residual. Its page-87 sampling consequence is represented here for exact leverage probabilities and exact sketch minimizers, with the same sampled rows and scaling for A and b. Positive input rank includes one. Rank zero has a separate deterministic branch because the normalized leverage distribution is undefined there. These contracts concern mathematical guarantees. Approximate leverage-score construction, its computational cost, and the survey's running-time assertions are separate obligations and are not asserted by these contracts.
Equation (7), with a literal independent leverage row sketch and a sufficient sample budget, including the displayed identity-Gram equality.
In the survey: Equation (7), page 85, with Algorithm 2 and leverage-score sampling.
Uses:
Finite,Probability.event Prob Has,Orthonormal Columns Row,Sample Row,Trace id,Matrix leverage,Trace Probability op,Norm2 row,Gram rowSample Gram Lean statement
def leverageSubspaceEmbedding : Prop := ∀ (m n s : ℕ) (U : Fin m → Fin n → ℝ) (hU : HasOrthonormalColumns U) (hn : 0 < n) (ε δ : ℝ), 0 < s → 0 < ε → ε < 1 → 0 < δ → δ < 1 → 1 / ((s : ℝ) * (ε / (n : ℝ)) ^ 2) ≤ δ → 1 - δ ≤ (leverageTraceProbability (steps := s) U hU hn).eventProb {samples | opNorm2 (fun j k => rowGram U j k - rowSampleGram s U samples j k) = opNorm2 (fun j k => idMatrix n j k - rowSampleGram s U samples j k) ∧ opNorm2 (fun j k => idMatrix n j k - rowSampleGram s U samples j k) ≤ ε}No proof published.
Equation (8)'s residual-norm minimization agrees with the squared objective used by the library. Neither uniqueness nor exact solvability is required.
In the survey: Equation (8), page 86.
Uses:
Is,Least Squares Minimizer ls,Residual vecNorm2 Lean statement
def leastSquaresResidualMinimum : Prop := ∀ (m n : ℕ) (A : Fin m → Fin n → ℝ) (b : Fin m → ℝ) (xOpt : Fin n → ℝ), IsLeastSquaresMinimizer A b xOpt ↔ ∀ x, vecNorm2 (lsResidual A b xOpt) ≤ vecNorm2 (lsResidual A b x)Proof published. It depends on 3 theorems of the library.
Exact-leverage mathematical case of the page-87 LS guarantee, measured in squared residual objective. The sample count depends reciprocally on accuracy at fixed confidence. Basis dimension is the input rank, not augmented rank.
In the survey: Page 87, the least-squares guarantee, with exact leverage scores.
Uses:
Finite,Probability.event Prob Is,Least Squares Minimizer Row,Sample Row,Trace augmented,Data Span leverage,Trace Probability ls,Column Space Basis Matrix ls,Objective row,Sample LSMatrix With Basis Scale rowSample LSVector With Basis Scale Lean statement
def leverageLeastSquaresObjective : Prop := ∀ (m n s : ℕ) (A : Fin m → Fin n → ℝ) (b : Fin m → ℝ) (hd : 0 < Module.finrank ℝ (augmentedDataSpan A (fun _ => 0))) (xHat : RowTrace m s → Fin n → ℝ) (xOpt : Fin n → ℝ) (η δ : ℝ), 0 < s → 0 < η → η < 1 → 0 < δ → δ < 1 → IsLeastSquaresMinimizer A b xOpt → (∀ samples, IsLeastSquaresMinimizer (rowSampleLSMatrixWithBasisScale s (lsColumnSpaceBasisMatrix A) A samples) (rowSampleLSVectorWithBasisScale s (lsColumnSpaceBasisMatrix A) b samples) (xHat samples)) → 10 * (Module.finrank ℝ (augmentedDataSpan A (fun _ => 0)) : ℝ) * Real.log ((4 * (Module.finrank ℝ (augmentedDataSpan A (fun _ => 0)) : ℝ)) / δ) ≤ (s : ℝ) → 8 * (Module.finrank ℝ (augmentedDataSpan A (fun _ => 0)) : ℝ) / (η * δ) ≤ (s : ℝ) → 1 - δ ≤ (leverageTraceProbability (steps := s) (lsColumnSpaceBasisMatrix A) (hasOrthonormalColumns_lsColumnSpaceBasisMatrix A) hd).eventProb {samples | lsObjective A b (xHat samples) ≤ (1 + η) * lsObjective A b xOpt}No proof published.
leverage
Least Squares Residual Norm The same exact-leverage sampler and exact sketch solution, measured in Equation (8)'s unsquared Euclidean residual norm.
In the survey: Page 87, the least-squares guarantee, with exact leverage scores, measured as in Equation (8).
Uses:
Finite,Probability.event Prob Is,Least Squares Minimizer Row,Sample Row,Trace augmented,Data Span leverage,Trace Probability ls,Column Space Basis Matrix ls,Residual row,Sample LSMatrix With Basis Scale row,Sample LSVector With Basis Scale vecNorm2 Lean statement
def leverageLeastSquaresResidualNorm : Prop := ∀ (m n s : ℕ) (A : Fin m → Fin n → ℝ) (b : Fin m → ℝ) (hd : 0 < Module.finrank ℝ (augmentedDataSpan A (fun _ => 0))) (xHat : RowTrace m s → Fin n → ℝ) (xOpt : Fin n → ℝ) (η δ : ℝ), 0 < s → 0 < η → η < 1 → 0 < δ → δ < 1 → IsLeastSquaresMinimizer A b xOpt → (∀ samples, IsLeastSquaresMinimizer (rowSampleLSMatrixWithBasisScale s (lsColumnSpaceBasisMatrix A) A samples) (rowSampleLSVectorWithBasisScale s (lsColumnSpaceBasisMatrix A) b samples) (xHat samples)) → 10 * (Module.finrank ℝ (augmentedDataSpan A (fun _ => 0)) : ℝ) * Real.log ((4 * (Module.finrank ℝ (augmentedDataSpan A (fun _ => 0)) : ℝ)) / δ) ≤ (s : ℝ) → 8 * (Module.finrank ℝ (augmentedDataSpan A (fun _ => 0)) : ℝ) / (η * δ) ≤ (s : ℝ) → 1 - δ ≤ (leverageTraceProbability (steps := s) (lsColumnSpaceBasisMatrix A) (hasOrthonormalColumns_lsColumnSpaceBasisMatrix A) hd).eventProb {samples | vecNorm2 (lsResidual A b (xHat samples)) ≤ (1 + η) * vecNorm2 (lsResidual A b xOpt)}No proof published.
Zero input rank: every coefficient vector has the same residual objective; no normalized leverage sampler or probability law is introduced.
In the survey: Page 87, the least-squares guarantee, extended to an input of rank zero.
Uses:
augmented,Data Span ls,Objective ls,Residual vecNorm2 Lean statement
def zeroRankLeastSquares : Prop := ∀ (m n : ℕ) (A : Fin m → Fin n → ℝ) (b : Fin m → ℝ), Module.finrank ℝ (augmentedDataSpan A (fun _ => 0)) = 0 → ∀ (xHat xOpt : Fin n → ℝ) (η : ℝ), 0 ≤ η → lsObjective A b xHat ≤ (1 + η) * lsObjective A b xOpt ∧ vecNorm2 (lsResidual A b xHat) ≤ (1 + η) * vecNorm2 (lsResidual A b xOpt)No proof published.
Corrected source contract for the structural low-rank bound
LowRankApproximation.lean · 1 statement, with a published proof
The literal arbitrary-spanning-matrix wording preceding equation (9) on printed page 88 of Drineas--Mahoney (2016) is false. This proposed corrected contract requires compatible orthonormal right singular coordinates from one ordered SVD. It does not assert that the printed wording was already correct or that the correction has been admitted or independently reviewed. The orthonormal SVD convention is explicit in Boutsidis--Mahoney--Drineas, SODA09 §2.1 and corrected arXiv:0812.4293v2 §2.1. Mahoney--Drineas, Structural properties underlying high-quality Randomized Numerical Linear Algebra algorithms (2016), §§3.1--3.3, supplies the unsquared bound for every unitarily invariant norm and arbitrary sketch width. Its printed tail-dimension and undefined-Y defects are not adopted here. HMT11 Theorem 9.1 separately supports oversampling and the zero-tail case, but states only spectral/Frobenius bounds. The full right basis has n = k + q coordinates; left null coordinates are zero. Thus the tail includes the null singular directions even for wide matrices. All shapes use the same norm family, with exact isometric coherence. Full row rank of the sampled head is surjectivity of its matrix-vector map. The explicit k ≤ r retains the printed oversampling condition; it is also implied by that surjectivity. No rank or positive-leading-singular-value restriction is imposed.
corrected
Low Rank Approximation Structural Bound In plain words: For every unitarily invariant norm, ‖A − PA‖ ≤ ‖Σ⊥‖ + ‖Σ⊥ V⊥ᵀ Z (Vₖᵀ Z)⁺‖, where P is the orthogonal projector onto the range of AZ, Σ⊥ and V⊥ hold the trailing singular values and right singular vectors of one singular value decomposition of A, Z has at least k columns, and Vₖᵀ Z has full row rank. The bound is on the error itself, not on its square. For the spectral and Frobenius norms this is weaker, by a factor of at most √2, than the same bound on the square of the error. The library's note says that the wording before Equation (9), which allows any matrix spanning the same space as Vₖ, fails, and Lean does not check that remark.
Corrected equation (9): compatible orthonormal singular coordinates, arbitrary oversampling, and one coherent unitarily invariant norm family.
In the survey: Equation (9), page 88, in a corrected form.
Uses:
Ch14Ext.ch14ext_,rect Moore Penrose Pseudoinverse Complex,Matrix Unitary Invariant Norm Family Complex,Matrix Unitary Invariant Norm Family.real Norm Is,Real Full Right SVD column,Sketch Moore Penrose Projector finite,Transpose rect,Mat Mul rect,Mat Mul Vec square,SVDHead Right square,SVDTail Diagonal squareSVDTail Right Lean statement
def correctedLowRankApproximationStructuralBound : Prop := ∀ (m k q r : ℕ) (N : ComplexMatrixUnitaryInvariantNormFamily) (A Ufull : Matrix (Fin m) (Fin (k + q)) ℝ) (sigma : Fin (k + q) → ℝ) (Vfull : Matrix (Fin (k + q)) (Fin (k + q)) ℝ) (Z : Fin (k + q) → Fin r → ℝ), k ≤ r → IsRealFullRightSVD A Ufull sigma Vfull → Function.Surjective (rectMatMulVec (rectMatMul (finiteTranspose (squareSVDHeadRight Vfull)) Z)) → N.realNorm (fun i j => A i j - rectMatMul (columnSketchMoorePenroseProjector A Z) A i j) ≤ N.realNorm (squareSVDTailDiagonal sigma) + N.realNorm (rectMatMul (rectMatMul (squareSVDTailDiagonal sigma) (rectMatMul (finiteTranspose (squareSVDTailRight Vfull)) Z)) (Ch14Ext.ch14ext_rectMoorePenrosePseudoinverse (rectMatMul (finiteTranspose (squareSVDHeadRight Vfull)) Z)))Proof published. It depends on 184 theorems of the library.
Joint Walsh sketch geometry and actual sampled-system coherence
PreprocessingCoherence.lean · 4 statements, each with a published proof
These contracts instantiate the admitted real-Walsh realization. Rows are iid with replacement independently of the signs. The historical child identifier also mentions Fourier; no complex Fourier realization is asserted here. The actual sampled leverage is the normalized diagonal of W (WᵀW)⁻¹ Wᵀ, with its full-rank domain proved from sketch geometry. Ambient logarithms are retained; the d log d specialization has an explicit rank-versus-ambient-log regime. No running-time assertion is made.
In plain words: There is a constant C > 0 such that, for an orthonormal basis U of a d-dimensional subspace of R^m with m = 2^p and d ≤ m, 0 < ε < 1, 0 < δ < 1, and a sketch by random signs, the Walsh–Hadamard transform and at least C (d + log(2m/δ)) log(2d/δ)/ε² rows sampled uniformly, with probability at least 1 − δ the rows of the transformed basis have squared norms at most (√d + √(8 log(2m/δ)))²/m, the Gram matrix of the sketch is within ε of the identity in the spectral norm, and every squared length in the subspace is kept within a factor 1 ± ε. The statement asserts that some constant exists, and the proof takes C = 1000.
The full joint child022 guarantee, including simultaneous geometry for all vectors of the represented fixed subspace and the sharp row radius.
In the survey: Algorithm 3, the preprocessing with a randomized Hadamard transform and uniform sampling of rows.
Uses:
Finite,Probability.event Prob Has,Orthonormal Columns Rademacher,Trace Row,Sample Row,Trace walsh,Rotation finite,Id Matrix hadamard,Joint Row Radius op,Norm2 rect,Mat Mul Vec row,Gram row,Norm Sq signed,Hadamard Basis signed,Hadamard Uniform Row Trace Probability uniform,Scaled Row Sketch vecNorm2Sq Lean statement
def signedWalshJointEmbedding : Prop := ∃ C : ℝ, 0 < C ∧ ∀ (p d s : ℕ) (U : Fin (2 ^ p) → Fin d → ℝ), HasOrthonormalColumns U → 0 < d → d ≤ 2 ^ p → 0 < s → ∀ ε δ : ℝ, 0 < ε → ε < 1 → 0 < δ → δ < 1 → C / ε ^ 2 * ((d : ℝ) + Real.log ((2 * ((2 ^ p : ℕ) : ℝ)) / δ)) * Real.log ((2 * (d : ℝ)) / δ) ≤ (s : ℝ) → 1 - δ ≤ (signedHadamardUniformRowTraceProbability (m := 2 ^ p) (s := s) (pow_pos (by norm_num) p)).eventProb {z | let Q := signedHadamardBasis (walshRotation p) U z.1 let W := uniformScaledRowSketch Q z.2 (∀ i, rowNormSq Q i ≤ hadamardJointRowRadius (2 ^ p) d δ / ((2 ^ p : ℕ) : ℝ)) ∧ opNorm2 (fun j k => finiteIdMatrix j k - rowGram W j k) ≤ ε ∧ ∀ x : Fin d → ℝ, (1 - ε) * vecNorm2Sq (rectMatMulVec U x) ≤ vecNorm2Sq (rectMatMulVec W x) ∧ vecNorm2Sq (rectMatMulVec W x) ≤ (1 + ε) * vecNorm2Sq (rectMatMulVec U x)}Proof published. It depends on 565 theorems of the library.
sampled
Walsh Projector Coherence Actual sampled-projector coherence on every stated successful geometry event, rather than the unnormalized row norm of the sampled table.
In the survey: Algorithm 3, the same preprocessing, the leverage scores of the sampled rows.
Uses:
Has,Orthonormal Columns Rademacher,Trace Row,Trace walsh,Rotation finite,Id Matrix full,Rank Leverage Prob op,Norm2 row,Gram row,Norm Sq signed,Hadamard Basis uniformScaled Row Sketch Lean statement
def sampledWalshProjectorCoherence : Prop := ∀ (p d s : ℕ) (U : Fin (2 ^ p) → Fin d → ℝ), HasOrthonormalColumns U → 0 < d → 0 < s → ∀ δ : ℝ, 0 < δ → δ < 1 → ∀ (ω : RademacherTrace (2 ^ p)) (samples : RowTrace (2 ^ p) s), let Q := signedHadamardBasis (walshRotation p) U ω let W := uniformScaledRowSketch Q samples let L := (Real.sqrt (d : ℝ) + Real.sqrt (8 * Real.log (((2 ^ p : ℕ) : ℝ) / δ))) ^ 2 (∀ i, rowNormSq Q i ≤ L / ((2 ^ p : ℕ) : ℝ)) → opNorm2 (fun j k => finiteIdMatrix j k - rowGram W j k) ≤ (1 / 2 : ℝ) → Matrix.rank (W : Matrix (Fin s) (Fin d) ℝ) = d ∧ (∀ t, 0 ≤ fullRankLeverageProb W t) ∧ (∑ t : Fin s, fullRankLeverageProb W t) = 1 ∧ ∀ t, fullRankLeverageProb W t ≤ 2 * L / ((s : ℝ) * (d : ℝ))Proof published. It depends on 31 theorems of the library.
signed
Walsh Coherence Sample Scale Fixed-confidence joint geometry and actual sampled projector coherence at the general count, and its rank-dominates-log specialization. The same positive universal confidence and sample constant work for all fixed inputs.
In the survey: Algorithm 3, the same preprocessing, its number of sampled rows.
Uses:
Finite,Probability Finite,Probability.event Prob Has,Orthonormal Columns Rademacher,Trace Row,Sample Row,Trace walsh,Rotation finite,Id Matrix full,Rank Leverage Prob hadamard,Joint Row Radius op,Norm2 row,Gram row,Norm Sq signed,Hadamard Basis signed,Hadamard Uniform Row Trace Probability uniformScaled Row Sketch Lean statement
def signedWalshCoherenceSampleScale : Prop := ∃ C q0 : ℝ, 0 < C ∧ 0 < q0 ∧ q0 < 1 ∧ ∀ (p d s : ℕ) (U : Fin (2 ^ p) → Fin d → ℝ), HasOrthonormalColumns U → 0 < d → d ≤ 2 ^ p → 0 < s → let success := {z : RademacherTrace (2 ^ p) × RowTrace (2 ^ p) s | let Q := signedHadamardBasis (walshRotation p) U z.1 let W := uniformScaledRowSketch Q z.2 let L := hadamardJointRowRadius (2 ^ p) d (1 / 2) (∀ i, rowNormSq Q i ≤ L / ((2 ^ p : ℕ) : ℝ)) ∧ opNorm2 (fun j k => finiteIdMatrix j k - rowGram W j k) ≤ (1 / 2 : ℝ) ∧ Matrix.rank (W : Matrix (Fin s) (Fin d) ℝ) = d ∧ ∀ t, fullRankLeverageProb W t ≤ 2 * L / ((s : ℝ) * (d : ℝ))} let P := signedHadamardUniformRowTraceProbability (m := 2 ^ p) (s := s) (pow_pos (by norm_num) p) (C * ((d : ℝ) + Real.log (2 * ((2 ^ p : ℕ) : ℝ))) * Real.log (2 * (d : ℝ)) ≤ (s : ℝ) → q0 ≤ P.eventProb success) ∧ (Real.log (2 * ((2 ^ p : ℕ) : ℝ)) ≤ (d : ℝ) → (2 * C) * (d : ℝ) * Real.log (2 * (d : ℝ)) ≤ (s : ℝ) → q0 ≤ P.eventProb success)Proof published. It depends on 570 theorems of the library.
signed
Walsh Coherence Guarantees Complete selected row023 geometry, rotated spreading, actual sampled projector coherence, and quantified sample-scale contract.
In the survey: Algorithm 3, the preprocessing with a randomized Hadamard transform, its guarantees together.
Uses:
sampled,Walsh Projector Coherence signed,Walsh Coherence Sample Scale signed,Walsh Exact Geometry signedWalsh Mass Spreading Lean statement
def signedWalshCoherenceGuarantees : Prop := signedWalshExactGeometry ∧ signedWalshMassSpreading ∧ sampledWalshProjectorCoherence ∧ signedWalshCoherenceSampleScaleProof published. It depends on 583 theorems of the library.
Selected preprocessing geometry for Algorithm 3
PreprocessingGeometry.lean · 5 statements, 4 with a published proof
The survey's qualitative statement is instantiated by two distinct laws. The square Sylvester/Walsh transform preserves geometry exactly and spreads the leverage of a fixed positive-dimensional subspace. Its logarithmic constant comes from the primary signed-Hadamard row-norm bound, not from the survey. The signed-hash sparse family directly embeds a subspace and makes no claim that its output leverage is flattened. Zero-dimensional subspaces are handled without dividing a leverage score by zero.
Exact geometry for every realization of the actual independent sign law.
In the survey: Algorithm 3, the preprocessing with a randomized Hadamard transform.
Uses:
Has,Orthonormal Columns Rademacher,Trace walsh,Rotation diag,Matrix mat,Mul precondition,Rows rademacherSign Vector Lean statement
def signedWalshExactGeometry : Prop := ∀ (p d : ℕ) (U : Fin (2 ^ p) → Fin d → ℝ), HasOrthonormalColumns U → ∀ ω : RademacherTrace (2 ^ p), HasOrthonormalColumns (preconditionRows (matMul (2 ^ p) (walshRotation p) (diagMatrix (rademacherSignVector ω))) U)Proof published. It depends on 44 theorems of the library.
Sharp simultaneous row-norm and normalized-leverage bound for a fixed subspace. The two bounds hold on the same sign event.
In the survey: Algorithm 3, the preprocessing with a randomized Hadamard transform, with a constant from outside the survey.
Uses:
Finite,Probability.event Prob Has,Orthonormal Columns Rademacher,Trace walsh,Rotation diag,Matrix leverage,Score Prob mat,Mul precondition,Rows rademacher,Sign Vector rademacher,Trace Probability rowNorm Sq Lean statement
def signedWalshMassSpreading : Prop := ∀ (p d : ℕ) (U : Fin (2 ^ p) → Fin d → ℝ), HasOrthonormalColumns U → 0 < d → ∀ δ : ℝ, 0 < δ → δ < 1 → 1 - δ ≤ (rademacherTraceProbability (2 ^ p)).eventProb {ω | ∀ i : Fin (2 ^ p), let Q := preconditionRows (matMul (2 ^ p) (walshRotation p) (diagMatrix (rademacherSignVector ω))) U let L := (Real.sqrt (d : ℝ) + Real.sqrt (8 * Real.log (((2 ^ p : ℕ) : ℝ) / δ))) ^ 2 rowNormSq Q i ≤ L / ((2 ^ p : ℕ) : ℝ) ∧ leverageScoreProb Q i ≤ L / (((2 ^ p : ℕ) : ℝ) * (d : ℝ))}Proof published. It depends on 149 theorems of the library.
sparse
Signed Hash Subspace Geometry In plain words: For an orthonormal basis U of a d-dimensional subspace, 0 < ε < 1 and 0 < δ < 1, and a sparse sign-and-hash sketch with at least (d² + d)/(ε² δ) rows, with probability at least 1 − δ the sketch keeps every squared length in the subspace within a factor 1 ± ε. The threshold is the library's, and the survey states this kind of result qualitatively.
Signed-hash sparse preprocessing directly embeds a fixed subspace. Each input coordinate has an independent uniform hash and independent unbiased sign. The same event gives the spectral Gram bound and geometry for every subspace vector, with the dimension threshold
(d²+d)/(ε²δ).In the survey: Algorithm 3, the preprocessing with a sparse sign-and-hash transform.
Uses:
Count,Sketch Hash Finite,Probability.event Prob Has,Orthonormal Columns Rademacher,Trace count,Sketch Probability count,Sketch Rows id,Matrix op,Norm2 precondition,Rows rademacher,Sign Vector rect,Mat Mul Vec row,Gram vecNorm2Sq Lean statement
def sparseSignedHashSubspaceGeometry : Prop := ∀ (m d t : ℕ) (ht : 0 < t) (U : Fin m → Fin d → ℝ), 0 < m → HasOrthonormalColumns U → ∀ ε δ : ℝ, 0 < ε → ε < 1 → 0 < δ → δ < 1 → ((d : ℝ) ^ 2 + (d : ℝ)) / (ε ^ 2 * δ) ≤ (t : ℝ) → 1 - δ ≤ (countSketchProbability (r := t) (m := m) ht).eventProb {x | let Pi := countSketchRows x.1 (rademacherSignVector x.2) opNorm2 (fun j k => idMatrix d j k - rowGram (preconditionRows Pi U) j k) ≤ ε ∧ ∀ v : Fin m → ℝ, (∃ z : Fin d → ℝ, v = rectMatMulVec U z) → (1 - ε) * vecNorm2Sq v ≤ vecNorm2Sq (rectMatMulVec Pi v) ∧ vecNorm2Sq (rectMatMulVec Pi v) ≤ (1 + ε) * vecNorm2Sq v}Proof published. It depends on 91 theorems of the library.
Combined parent contract for the two selected preprocessing families: exact signed-Walsh geometry, its mass spreading, and sparse signed-hash subspace geometry with its own law and dimension threshold.
In the survey: Algorithm 3, the preprocessing with either transform.
Uses:
signed,Walsh Exact Geometry signed,Walsh Mass Spreading sparseSigned Hash Subspace Geometry Lean statement
def preprocessingGeometry : Prop := signedWalshExactGeometry ∧ signedWalshMassSpreading ∧ sparseSignedHashSubspaceGeometryProof published. It depends on 216 theorems of the library.
zero
Subspace Preprocessing Geometry Every linear preprocessing map preserves the zero subspace exactly. This branch has no normalized leverage probability or division by its dimension.
In the survey: Algorithm 3, the preprocessing, for a subspace of dimension zero.
Uses:
rect,Mat Mul Vec vecNorm2Sq Lean statement
def zeroSubspacePreprocessingGeometry : Prop := ∀ (m t : ℕ) (Pi : Fin t → Fin m → ℝ) (v : Fin m → ℝ), v = 0 → rectMatMulVec Pi v = 0 ∧ vecNorm2Sq (rectMatMulVec Pi v) = vecNorm2Sq vNo proof published.
The concrete normalized Sylvester/Walsh matrix in dimension
2^p.Lean statement
noncomputable def walshRotation (p : ℕ) : Fin (2 ^ p) → Fin (2 ^ p) → ℝ := fun i k => Real.sqrt (((2 ^ p : ℕ) : ℝ)⁻¹) * sylvesterHadamardSignPattern p i kA definition that statements of this file use.
Quantitative children of supplied-score leverage least squares
RelativeLeverageLeastSquaresRate.lean · 4 statements, 1 with a published proof
The score tolerance α is separate from residual tolerance ε. Its unavoidable factor β⁻¹ is explicit. Bounded score tolerance α≤1/2 gives β⁻¹≤3, hence the source scale with an absolute constant. No score-computation cost is asserted.
relative
Leverage Least Squares Relative Error In plain words: There is a constant C ≥ 1 such that, for an m × n matrix A, a vector b, row scores a with (1 − α) ℓᵢ ≤ aᵢ ≤ (1 + α) ℓᵢ for the leverage scores ℓᵢ of the column space of A and some 0 ≤ α < 1, 0 < ε < 1, and at least C n log(2m)/(((1 − α)/(1 + α)) ε) rows of A and b sampled independently with probabilities proportional to the scores, every exact solution of the sketched problem has a residual at most (1 + ε) times the least residual, with probability at least 1/2. The statement asserts that some constant exists, and the proof takes C = 4096.
Original026-relative-error: every sufficient integer sample count for the actual normalized approximate scores, with reciprocal accuracy dependence.
In the survey: Page 87, the least-squares sketch with approximate leverage scores, its relative-error bound.
Uses:
Relative,Leverage Scores Relative,Leverage Least Squares Quality augmented,Data Span lsColumn Space Basis Matrix Lean statement
def relativeLeverageLeastSquaresRelativeError : Prop := ∃ C : ℝ, 1 ≤ C ∧ ∀ (m n s : ℕ) (A : Fin m → Fin n → ℝ) (b : Fin m → ℝ) (a : Fin m → ℝ) (α ε : ℝ) (hα : α < 1) (ha : ∀ _hd : 0 < Module.finrank ℝ (augmentedDataSpan A (fun _ => 0)), RelativeLeverageScores (lsColumnSpaceBasisMatrix A) a α), 0 < m → 0 < n → 0 < s → 0 ≤ α → 0 < ε → ε < 1 → C * (n : ℝ) * Real.log (2 * (m : ℝ)) / (((1 - α) / (1 + α)) * ε) ≤ (s : ℝ) → RelativeLeverageLeastSquaresQuality s A b a α hα ha εProof published. It depends on 451 theorems of the library.
relative
Leverage Least Squares Samples Original026-samples: the ceiling of a dimension/accuracy/score-tolerance budget gives successful actual outputs, and remains at most twice its scale.
In the survey: Page 87, the least-squares sketch with approximate leverage scores, its sample count.
Uses:
Relative,Leverage Scores Relative,Leverage Least Squares Quality augmented,Data Span lsColumn Space Basis Matrix Lean statement
def relativeLeverageLeastSquaresSamples : Prop := ∃ C : ℝ, 1 ≤ C ∧ ∀ (m n : ℕ) (A : Fin m → Fin n → ℝ) (b : Fin m → ℝ) (a : Fin m → ℝ) (α ε : ℝ) (hα : α < 1) (ha : ∀ _hd : 0 < Module.finrank ℝ (augmentedDataSpan A (fun _ => 0)), RelativeLeverageScores (lsColumnSpaceBasisMatrix A) a α), 0 < m → 0 < n → 0 ≤ α → 0 < ε → ε < 1 → ∃ s : ℕ, s = ⌈C * (n : ℝ) * Real.log (2 * (m : ℝ)) / (((1 - α) / (1 + α)) * ε)⌉₊ ∧ 0 < s ∧ (s : ℝ) ≤ 2 * C * (n : ℝ) * Real.log (2 * (m : ℝ)) / (((1 - α) / (1 + α)) * ε) ∧ RelativeLeverageLeastSquaresQuality s A b a α hα ha εNo proof published.
relative
Leverage Least Squares Source Relative Error Source-scale relative-error child with a uniformly bounded internal score approximation tolerance. In particular α=min(ε,1/2) is permitted.
In the survey: Page 87, the least-squares sketch with approximate leverage scores, its relative-error bound at the survey's sample scale.
Uses:
Relative,Leverage Scores Relative,Leverage Least Squares Quality augmented,Data Span lsColumn Space Basis Matrix Lean statement
def relativeLeverageLeastSquaresSourceRelativeError : Prop := ∃ C : ℝ, 1 ≤ C ∧ ∀ (m n s : ℕ) (A : Fin m → Fin n → ℝ) (b : Fin m → ℝ) (a : Fin m → ℝ) (α ε : ℝ) (hα : α < 1) (ha : ∀ _hd : 0 < Module.finrank ℝ (augmentedDataSpan A (fun _ => 0)), RelativeLeverageScores (lsColumnSpaceBasisMatrix A) a α), 0 < m → 0 < n → 0 < s → 0 ≤ α → α ≤ 1 / 2 → 0 < ε → ε < 1 → C * (n : ℝ) * Real.log (2 * (m : ℝ)) / ε ≤ (s : ℝ) → RelativeLeverageLeastSquaresQuality s A b a α hα ha εNo proof published.
relative
Leverage Least Squares Source Samples Source-scale samples child for bounded supplied-score tolerance. Its integer witness depends only on dimensions and residual accuracy.
In the survey: Page 87, the least-squares sketch with approximate leverage scores, its sample count at the survey's sample scale.
Uses:
Relative,Leverage Scores Relative,Leverage Least Squares Quality augmented,Data Span lsColumn Space Basis Matrix Lean statement
def relativeLeverageLeastSquaresSourceSamples : Prop := ∃ C : ℝ, 1 ≤ C ∧ ∀ (m n : ℕ) (A : Fin m → Fin n → ℝ) (b : Fin m → ℝ) (a : Fin m → ℝ) (α ε : ℝ) (hα : α < 1) (ha : ∀ _hd : 0 < Module.finrank ℝ (augmentedDataSpan A (fun _ => 0)), RelativeLeverageScores (lsColumnSpaceBasisMatrix A) a α), 0 < m → 0 < n → 0 ≤ α → α ≤ 1 / 2 → 0 < ε → ε < 1 → ∃ s : ℕ, s = ⌈C * (n : ℝ) * Real.log (2 * (m : ℝ)) / ε⌉₊ ∧ 0 < s ∧ (s : ℝ) ≤ 2 * C * (n : ℝ) * Real.log (2 * (m : ℝ)) / ε ∧ RelativeLeverageLeastSquaresQuality s A b a α hα ha εNo proof published.
Is
Relative Leverage Least Squares Output Exact outputs of the literal shared A/b importance-sampling sketch.
Lean statement
def IsRelativeLeverageLeastSquaresOutput {m n s : ℕ} (A : Fin m → Fin n → ℝ) (b : Fin m → ℝ) (P : FiniteProbability (Fin m)) (xHat : RowTrace m s → Fin n → ℝ) : Prop := ∀ samples, IsLeastSquaresMinimizer (rowSampleSketchWithProb s A P.prob samples) (rowSampleVectorWithProb P.prob b samples) (xHat samples)A definition that statements of this file use.
Relative
Leverage Least Squares Quality Rank-complete quality of the actual supplied-score law, including existence of actual outputs. Rank zero returns0 without dividing by a zero score sum.
Lean statement
def RelativeLeverageLeastSquaresQuality {m n : ℕ} (s : ℕ) (A : Fin m → Fin n → ℝ) (b : Fin m → ℝ) (a : Fin m → ℝ) (α : ℝ) (hα : α < 1) (ha : ∀ _hd : 0 < Module.finrank ℝ (augmentedDataSpan A (fun _ => 0)), RelativeLeverageScores (lsColumnSpaceBasisMatrix A) a α) (ε : ℝ) : Prop := (Module.finrank ℝ (augmentedDataSpan A (fun _ => 0)) = 0 → IsLeastSquaresMinimizer A b (fun _ => 0) ∧ ∀ xOpt : Fin n → ℝ, IsLeastSquaresMinimizer A b xOpt → vecNorm2 (lsResidual A b (fun _ => 0)) ≤ (1 + ε) * vecNorm2 (lsResidual A b xOpt)) ∧ ∀ hd : 0 < Module.finrank ℝ (augmentedDataSpan A (fun _ => 0)), let P := relativeLeverageScoreProbability (lsColumnSpaceBasisMatrix A) (hasOrthonormalColumns_lsColumnSpaceBasisMatrix A) hd a hα (ha hd) (∃ xHat : RowTrace m s → Fin n → ℝ, IsRelativeLeverageLeastSquaresOutput A b P xHat) ∧ ∀ (xHat : RowTrace m s → Fin n → ℝ) (xOpt : Fin n → ℝ), IsRelativeLeverageLeastSquaresOutput A b P xHat → IsLeastSquaresMinimizer A b xOpt → (1 / 2 : ℝ) ≤ (P.iid s).eventProb {samples | vecNorm2 (lsResidual A b (xHat samples)) ≤ (1 + ε) * vecNorm2 (lsResidual A b xOpt)}A definition that statements of this file use.
Proof-free contract for preservation of represented-subspace rank
RepresentedSubspaceRank.lean · 1 statement, with a published proof
The deterministic rank consequence of successful Eq. (7), CACM 59(6), p. 85. Only the actual represented subspace is claimed to be preserved.
Successful Eq. (7) preserves the dimension of the represented subspace. The same linear sketch is injective throughout col(U); its application to U has rank d; and it preserves the rank of every matrix spanning exactly col(U). This includes the zero-dimensional case and rank-deficient input matrices.
In the survey: Equation (7), page 85, its consequence for rank.
Uses:
Has,Orthonormal Columns id,Matrix op,Norm2Le rowSketch Gram Lean statement
def representedSubspaceRank : Prop := ∀ (m d t : ℕ) (U : Matrix (Fin m) (Fin d) ℝ) (T : Matrix (Fin t) (Fin m) ℝ), HasOrthonormalColumns U → ∀ ε : ℝ, 0 < ε → ε < 1 → opNorm2Le (fun j k => idMatrix d j k - rowSketchGram (T * U) j k) ε → (T * U).rank = d ∧ Set.InjOn T.mulVec (Set.range U.mulVec) ∧ ∀ (n : ℕ) (A : Matrix (Fin m) (Fin n) ℝ), Set.range A.mulVec = Set.range U.mulVec → (T * A).rank = A.rankProof published. It depends on 20 theorems of the library.
Source contracts for norm-squared and leverage sampling
RowSampling.lean · 3 statements, 2 with a published proof
Proof-free statements for equations (4)--(6) of Drineas--Mahoney (2016). The positive denominator in equation (4) excludes the undefined norm-squared distribution of the zero matrix. Equation (6) uses a positive-dimensional orthonormal basis and the paper's normalized leverage probabilities.
Equation (4): norm-squared row probabilities form the stated distribution.
In the survey: Equation (4).
Uses:
row,Sq Norm Prob rowSq Norm Prob Den Lean statement
def rowNormDistribution : Prop := ∀ (m n : ℕ) (A : Fin m → Fin n → ℝ), 0 < rowSqNormProbDen A → (∀ i, 0 ≤ rowSqNormProb A i) ∧ (∑ i : Fin m, rowSqNormProb A i) = 1 ∧ ∀ i, rowSqNormProb A i = (∑ j : Fin n, A i j ^ 2) / (∑ r : Fin m, ∑ j : Fin n, A r j ^ 2)Proof published. It depends on 3 theorems of the library.
Equation (6): normalized leverage probabilities are squared row norms divided by the dimension, equivalently the diagonal of
UUᵀdivided by it.In the survey: Equation (6).
Uses:
Has,Orthonormal Columns leverageScore Prob Lean statement
def leverageDistribution : Prop := ∀ (m n : ℕ) (U : Fin m → Fin n → ℝ), 0 < n → HasOrthonormalColumns U → (∀ i, 0 ≤ leverageScoreProb U i) ∧ (∑ i : Fin m, leverageScoreProb U i) = 1 ∧ (∀ i, leverageScoreProb U i = (∑ j : Fin n, U i j ^ 2) / (n : ℝ)) ∧ ∀ i, leverageScoreProb U i = (∑ j : Fin n, U i j * U i j) / (n : ℝ)Proof published. It depends on 5 theorems of the library.
Equation (5) is an expectation bound, as specified by its following prose. The norm on the Gram difference is Frobenius and sampling is with replacement.
In the survey: Equation (5) and the text after it.
Uses:
Finite,Probability.expectation Real Row,Sample Row,Trace frob,Norm row,Gram row,Sample Gram row,Sq Norm Prob Den rowSq Norm Trace Probability Lean statement
def expectedGramError : Prop := ∀ (m n s : ℕ) (A : Fin m → Fin n → ℝ) (hA : 0 < rowSqNormProbDen A), 0 < s → (rowSqNormTraceProbability (steps := s) A hA).expectationReal (fun samples => frobNorm (fun j k => rowSampleGram s A samples j k - rowGram A j k)) ≤ rowSqNormProbDen A / Real.sqrt (s : ℝ)No proof published.
Algorithm contracts for Drineas--Mahoney (2016)
SamplingAlgorithms.lean · 5 statements, each with a published proof
Algorithms 1 and 2 use a supplied finite distribution and exactly s independent samples with replacement. Zero-probability outcomes are excluded almost surely. The unbiasedness claims require the distribution to cover every nonzero entry or row; without this support condition those claims are false. Algorithm 3 specifies products once its random preprocessing matrices have been drawn. As in the source meta-algorithm, these preprocessing matrices preserve dimensions.
Algorithm 1 and equation (1): iid sampling and the accumulated exact update.
In the survey: Algorithm 1 and Equation (1).
Uses:
Elementwise,Trace Finite,Probability Finite,Probability.event Prob Finite,Probability.iid Finite,Probability.prob elementwiseTrace Sketch With Prob Lean statement
def elementwiseSamplingAlgorithm : Prop := ∀ (m n s : ℕ) (A : Fin m → Fin n → ℝ) (P : FiniteProbability (Fin m × Fin n)), 0 < s → (∀ ω, (P.iid s).prob ω = ∏ t, P.prob (ω t)) ∧ (P.iid s).eventProb {ω | ∀ t, 0 < P.prob (ω t)} = 1 ∧ ∀ (ω : ElementwiseTrace m n s) i j, elementwiseTraceSketchWithProb s A (fun _ _ => 0) (fun r c => P.prob (r,c)) ω i j = ∑ t : Fin s, if (ω t).1 = i ∧ (ω t).2 = j then (1 / ((s : ℝ) * P.prob (i,j))) * A i j else 0Proof published. It depends on 4 theorems of the library.
Algorithm 2 and equation (3): iid row sampling with the prescribed scale.
In the survey: Algorithm 2 and Equation (3).
Uses:
Finite,Probability Finite,Probability.event Prob Finite,Probability.iid Finite,Probability.prob Row,Trace rowSample Sketch With Prob Lean statement
def rowSamplingAlgorithm : Prop := ∀ (m n s : ℕ) (A : Fin m → Fin n → ℝ) (P : FiniteProbability (Fin m)), 0 < s → (∀ ω, (P.iid s).prob ω = ∏ t, P.prob (ω t)) ∧ (P.iid s).eventProb {ω | ∀ t, 0 < P.prob (ω t)} = 1 ∧ ∀ (ω : RowTrace m s) t j, rowSampleSketchWithProb s A P.prob ω t j = (1 / Real.sqrt ((s : ℝ) * P.prob (ω t))) * A (ω t) jProof published. It depends on 4 theorems of the library.
random
Projection Preconditioning Algorithm Algorithm 3: the exact left, right and two-sided matrix products. The meta-algorithm does not prescribe a unique law for the preprocessing maps.
In the survey: Algorithm 3.
Uses:
precondition,Columns precondition,Elements preconditionRows Lean statement
def randomProjectionPreconditioningAlgorithm : Prop := ∀ (m n : ℕ) (L : Fin m → Fin m → ℝ) (A : Fin m → Fin n → ℝ) (R : Fin n → Fin n → ℝ), (∀ i j, preconditionRows L A i j = ∑ k : Fin m, L i k * A k j) ∧ (∀ i j, preconditionColumns A R i j = ∑ k : Fin n, A i k * R k j) ∧ (∀ i j, preconditionElements L A R i j = ∑ k : Fin m, ∑ l : Fin n, L i k * A k l * R l j)Proof published. It depends on no theorems of the library.
The elementwise sketch is unbiased when the supplied law covers
A's support.In the survey: Algorithm 1, the claim that its output is unbiased.
Uses:
Finite,Probability Finite,Probability.expectation Real Finite,Probability.iid Finite,Probability.prob elementwiseTrace Sketch With Prob Lean statement
def elementwiseSamplingUnbiased : Prop := ∀ (m n s : ℕ) (A : Fin m → Fin n → ℝ) (P : FiniteProbability (Fin m × Fin n)), 0 < s → (∀ i j, P.prob (i,j) = 0 → A i j = 0) → ∀ i j, (P.iid s).expectationReal (fun ω => elementwiseTraceSketchWithProb s A (fun _ _ => 0) (fun r c => P.prob (r,c)) ω i j) = A i jProof published. It depends on 6 theorems of the library.
The row sketch's Gram matrix is unbiased when the law covers every nonzero row.
In the survey: Algorithm 2, the claim that the Gram matrix of its output is unbiased.
Uses:
Finite,Probability Finite,Probability.expectation Real Finite,Probability.iid Finite,Probability.prob row,Gram rowSample Sketch With Prob Lean statement
def rowSamplingGramUnbiased : Prop := ∀ (m n s : ℕ) (A : Fin m → Fin n → ℝ) (P : FiniteProbability (Fin m)), 0 < s → (∀ i, P.prob i = 0 → ∀ j, A i j = 0) → ∀ j k, (P.iid s).expectationReal (fun ω => rowGram (rowSampleSketchWithProb s A P.prob ω) j k) = rowGram A j kProof published. It depends on 5 theorems of the library.
Column sampling, output sparsity, and the explicit Eq. (5) Markov consequence
SamplingConsequences.lean · 3 statements, each with a published proof
These contracts retain separate selected child claims. The Gram tail has the visible confidence-dependent threshold dictated by Markov's inequality.
Algorithm 2 transposed back samples columns, retaining one column per trial.
In the survey: Algorithm 2, applied to columns.
Uses:
Finite,Probability Finite,Probability.event Prob Finite,Probability.iid Finite,Probability.prob rowSample Sketch With Prob Lean statement
def columnSamplingAlgorithm : Prop := ∀ (m n s : ℕ) (A : Fin m → Fin n → ℝ) (P : FiniteProbability (Fin n)), 0 < s → (∀ ω, (P.iid s).prob ω = ∏ t, P.prob (ω t)) ∧ (P.iid s).eventProb {ω | ∀ t, 0 < P.prob (ω t)} = 1 ∧ ∀ (ω : Fin s → Fin n) i t, (Matrix.transpose (rowSampleSketchWithProb s (Matrix.transpose A) P.prob ω)) i t = (1 / Real.sqrt ((s : ℝ) * P.prob (ω t))) * A i (ω t)Proof published. It depends on 4 theorems of the library.
At most
sdistinct entries of the zero-initialized Algorithm 1 output are nonzero. Repeated samples and sampled zero entries can make this strict.In the survey: Algorithm 1, the number of nonzero entries of its output.
Uses:
Elementwise,Trace Finite,Probability Finite,Probability.prob elementwiseTrace Sketch With Prob Lean statement
def elementwiseSamplingSparsity : Prop := ∀ (m n s : ℕ) (A : Fin m → Fin n → ℝ) (P : FiniteProbability (Fin m × Fin n)), 0 < s → ∀ (ω : ElementwiseTrace m n s), (∀ t, 0 < P.prob (ω t)) → (Finset.univ.filter (fun ij : Fin m × Fin n => elementwiseTraceSketchWithProb s A (fun _ _ => 0) (fun i j => P.prob (i,j)) ω ij.1 ij.2 ≠ 0)).card ≤ sProof published. It depends on no theorems of the library.
The direct high-probability consequence of the unsquared Eq. (5) expectation: the threshold is enlarged by
1/δ, with the literal nonzero-input norm law.In the survey: Equation (5), as a bound that holds with high probability.
Uses:
Finite,Probability.event Prob Row,Sample Row,Trace frob,Norm row,Gram row,Sample Gram row,Sq Norm Prob Den rowSq Norm Trace Probability Lean statement
def gramErrorHighProbability : Prop := ∀ (m n s : ℕ) (A : Fin m → Fin n → ℝ) (hA : 0 < rowSqNormProbDen A), 0 < s → ∀ δ : ℝ, 0 < δ → δ < 1 → 1 - δ ≤ (rowSqNormTraceProbability (steps := s) A hA).eventProb {ω | frobNorm (fun j k => rowSampleGram s A ω j k - rowGram A j k) ≤ rowSqNormProbDen A / (δ * Real.sqrt (s : ℝ))}Proof published. It depends on 35 theorems of the library.
Total norm-squared row-sampling extension contracts
TotalRowSampling.lean · 3 statements, 1 with a published proof
The printed Eq4 distribution has no zero-input normalization rule. These contracts explicitly extend it by a deterministic none outcome with zero sketch and Gram output. On nonzero inputs they agree with the literal original iid sampler, and Eq5's expected error formula then extends to every finite matrix. This is an explicit mathematical convention, not a claim that the source printed a zero-input branch. Existing nonzero source contracts remain unchanged.
Exact agreement with the existing independent row law on positive-weight inputs. The extra
noneoutcome has zero probability in this branch.In the survey: Equation (4), extended to the zero matrix.
Uses:
Finite,Probability Finite,Probability.on Some Row,Sample Row,Trace row,Sq Norm Prob Den row,Sq Norm Trace Probability totalRow Sq Norm Trace Probability Lean statement
def totalRowSamplingAgrees : Prop := ∀ (m n s : ℕ) (A : Fin m → Fin n → ℝ) (hA : 0 < rowSqNormProbDen A), totalRowSqNormTraceProbability (s := s) A = FiniteProbability.onSome (rowSqNormTraceProbability (steps := s) A hA)No proof published.
Chosen zero-input rule: return
nonewith explicit zero sketch and Gram.In the survey: Equation (4), extended to the zero matrix.
Uses:
Finite,Probability.event Prob Row,Sample Row,Trace row,Sq Norm Prob Den total,Row Sample Gram total,Row Sample Sketch totalRow Sq Norm Trace Probability Lean statement
def totalRowSamplingZeroOutput : Prop := ∀ (m n s : ℕ) (A : Fin m → Fin n → ℝ), rowSqNormProbDen A = 0 → (totalRowSqNormTraceProbability (s := s) A).eventProb {outcome | outcome = none ∧ totalRowSampleSketch A outcome = (fun _ _ => 0) ∧ totalRowSampleGram A outcome = (fun _ _ => 0)} = 1No proof published.
Eq5's error formula for the explicit total sampler, for every finite input. The norm is Frobenius, the quantity is an expectation, and the sample count is positive. Empty row/column dimensions and the zero matrix are included.
In the survey: Equation (5), with the sampler of Equation (4) extended to the zero matrix.
Uses:
Finite,Probability.expectation Real Row,Sample Row,Trace frob,Norm row,Gram row,Sq Norm Prob Den total,Row Sample Gram totalRow Sq Norm Trace Probability Lean statement
def totalExpectedGramError : Prop := ∀ (m n s : ℕ) (A : Fin m → Fin n → ℝ), 0 < s → (totalRowSqNormTraceProbability (s := s) A).expectationReal (fun outcome => frobNorm (fun j k => totalRowSampleGram A outcome j k - rowGram A j k)) ≤ rowSqNormProbDen A / Real.sqrt (s : ℝ)Proof published. It depends on 38 theorems of the library.
Quantitative children of the joint Walsh least-squares construction
WalshLeastSquaresRate.lean · 2 statements, each with a published proof
The source's rough sample scale is represented by existence of a universal constant. Success1/2 is a concrete sufficient interpretation of qualitative positive success probability. Neither contract asserts fast execution or an implicit extension to row dimensions other than powers of two.
walsh
Uniform Least Squares Relative Error In plain words: There is a constant C ≥ 1 such that, for A with 2^q rows and n columns, 0 < ε < 1, and a sketch by random signs, a Walsh–Hadamard transform and at least C n log(2 · 2^q)/ε rows sampled uniformly, every exact solution of the sketched problem has a residual at most (1 + ε) times the least residual, with probability at least 1/2. The statement asserts that some constant exists, and the proof takes C = 4096.
Original027-relative-error: every sufficient integer budget controls the original unsquared residual for every exact sketch minimizer. Actual outputs exist; no minimizer, embedding or final quality is postulated as source input.
In the survey: Page 87, the least-squares sketch with a randomized Hadamard transform, its relative-error bound.
Uses:
Finite,Probability.event Prob Is,Least Squares Minimizer Rademacher,Trace Row,Sample Row,Trace Is,Walsh Least Squares Output ls,Residual signed,Hadamard Uniform Row Trace Probability vecNorm2 Lean statement
def walshUniformLeastSquaresRelativeError : Prop := ∃ C : ℝ, 1 ≤ C ∧ ∀ (q n s : ℕ) (A : Fin (2 ^ q) → Fin n → ℝ) (b : Fin (2 ^ q) → ℝ) (hm : 0 < 2 ^ q) (ε : ℝ), 0 < n → 0 < s → 0 < ε → ε < 1 → C * (n : ℝ) * Real.log (2 * ((2 ^ q : ℕ) : ℝ)) / ε ≤ (s : ℝ) → (∃ xHat : RademacherTrace (2 ^ q) × RowTrace (2 ^ q) s → Fin n → ℝ, IsWalshLeastSquaresOutput A b xHat) ∧ ∀ (xHat : RademacherTrace (2 ^ q) × RowTrace (2 ^ q) s → Fin n → ℝ) (xOpt : Fin n → ℝ), IsWalshLeastSquaresOutput A b xHat → IsLeastSquaresMinimizer A b xOpt → (1 / 2 : ℝ) ≤ (signedHadamardUniformRowTraceProbability (m := 2 ^ q) (s := s) hm).eventProb {z | vecNorm2 (lsResidual A b (xHat z)) ≤ (1 + ε) * vecNorm2 (lsResidual A b xOpt)}Proof published. It depends on 589 theorems of the library.
walsh
Uniform Least Squares Samples Original027-samples: a dimension/accuracy-only integer budget at the source scale comes with actual joint sketch outputs and the fixed-probability original residual guarantee. This asserts algorithm success, not just an arithmetic count.
In the survey: Page 87, the least-squares sketch with a randomized Hadamard transform, its sample count.
Uses:
Finite,Probability.event Prob Is,Least Squares Minimizer Rademacher,Trace Row,Sample Row,Trace Is,Walsh Least Squares Output ls,Residual signed,Hadamard Uniform Row Trace Probability vecNorm2 Lean statement
def walshUniformLeastSquaresSamples : Prop := ∃ C : ℝ, 1 ≤ C ∧ ∀ (q n : ℕ) (A : Fin (2 ^ q) → Fin n → ℝ) (b : Fin (2 ^ q) → ℝ) (hm : 0 < 2 ^ q) (ε : ℝ), 0 < n → 0 < ε → ε < 1 → ∃ s : ℕ, s = ⌈C * (n : ℝ) * Real.log (2 * ((2 ^ q : ℕ) : ℝ)) / ε⌉₊ ∧ 0 < s ∧ (s : ℝ) ≤ 2 * C * (n : ℝ) * Real.log (2 * ((2 ^ q : ℕ) : ℝ)) / ε ∧ ∃ xHat : RademacherTrace (2 ^ q) × RowTrace (2 ^ q) s → Fin n → ℝ, IsWalshLeastSquaresOutput A b xHat ∧ ∀ xOpt : Fin n → ℝ, IsLeastSquaresMinimizer A b xOpt → (1 / 2 : ℝ) ≤ (signedHadamardUniformRowTraceProbability (m := 2 ^ q) (s := s) hm).eventProb {z | vecNorm2 (lsResidual A b (xHat z)) ≤ (1 + ε) * vecNorm2 (lsResidual A b xOpt)}Proof published. It depends on 589 theorems of the library.
Actual exact minimizers of the common HD/uniform-row sketch of A and b.
Lean statement
def IsWalshLeastSquaresOutput {q n s : ℕ} (A : Fin (2 ^ q) → Fin n → ℝ) (b : Fin (2 ^ q) → ℝ) (xHat : RademacherTrace (2 ^ q) × RowTrace (2 ^ q) s → Fin n → ℝ) : Prop := ∀ ω samples, let T := matMul (2 ^ q) (leastSquaresWalshMatrix q) (diagMatrix (rademacherSignVector ω)) IsLeastSquaresMinimizer (rowSampleSketchWithProb s (preconditionRows T A) uniformRowProb samples) (rowSampleVectorWithProb uniformRowProb (matMulVec (2 ^ q) T b) samples) (xHat (ω, samples))A definition that statements of this file use.