TheoremStatement: Literature-sourcedProof: AI-generatedPipeline-generatedprecheck passjudge pass (gpt-6-luna)

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.

Strong-RRQR interpolative decomposition error and coefficient bounds

Statement

Let $A \in F^{m \times n}$ over $F \in {R, C}$ , with $m \geq n \geq 1$ , and let $0 \leq k \leq n$ , $f \geq 1$ . The spectral norm is $∥ M ∥_{2} = \sup_{∥ x ∥_{2} = 1} ∥ M x ∥_{2}$ , and $σ_{j} (M)$ is the $j$ th singular value in decreasing order. The procedure Strong-RRQR interpolative decomposition with explicit statuses returns the exact zero approximation for $k = 0$ and the exact reconstruction for $k = n$ . For $1 \leq k < n$ , assume $rank (A) = n$ and its exact-arithmetic strong-RRQR call returns success, and write $g = (1 + f^{2} k (n - k))^{1 / 2}$ for the returned blocks. Then $T (:, J) = I_{k}$ , $\max_{i, j} ∣ T_{i j} ∣ \leq f$ , and

$∥ A - A (:, J) T ∥_{2} = ∥ R_{22} ∥_{2} \leq g σ_{k + 1} (A) .$

No decomposition or error conclusion is asserted when the procedure returns a rank-loss or budget status. This theorem gives no finite-precision error bound for a returned candidate; such a bound requires verified score bounds and a reconstruction certificate for the actual returned interpolative decomposition.

Facts & Assumptions

Given: A matrix $A \in F^{m \times n}$ , the factor $f \geq 1$ , and the exact-arithmetic procedure with $1 \leq k < n$ .

[F1]

Strong-RRQR interpolative decomposition with explicit statuses: on exact-arithmetic success, the first $k$ permuted columns are $J$ , $T Π = [I_{k} X]$ , and $X = R_{11}^{- 1} R_{12}$ .

[F2]

Strong rank-revealing QR with finite swaps and explicit statuses: in exact arithmetic the procedure returns success only when every coefficient score and combined trailing-residual score is at most $f$ .

[F3]

Strong RRQR block singular values compare to the full matrix spectrum: for an exact-arithmetic successful factorization, $σ_{j} (R_{22}) \leq g σ_{k + j} (A)$ for $1 \leq j \leq n - k$ , where $g = (1 + f^{2} k (n - k))^{1 / 2}$ .

[F4]

The operator norm is 0 on the zero domain and otherwise equals the largest singular value, attained at a right-singular vector: on a nonzero finite-dimensional domain, the operator norm is the largest singular value.

Proof

1.1givenF1algebra

If $k = 0$ , the algorithm returns $T$ with zero rows, so $A (:, J) T = 0$ and the residual is $A$ . If $k = n$ , it returns $J = (1, \dots, n)$ and $T = I_{n}$ , so the residual is zero. Assume henceforth $1 \leq k < n$ and exact-arithmetic success.

1.2F1F2algebra

With $X = R_{11}^{- 1} R_{12}$ , [F1] gives $T Π = [I_{k} X]$ , so the first $k$ columns of $T Π$ are $I_{k}$ and therefore $T (:, J) = I_{k}$ . By [F2], $∣ X_{i j} ∣^{2} \leq ∣ X_{i j} ∣^{2} + (ω_{i} γ_{j})^{2} \leq f^{2}$ , hence $∣ X_{i j} ∣ \leq f$ . Since $f \geq 1$ , the identity entries also obey the same coefficient bound.

1.3F1algebra

Put $C = A (:, J)$ , the first $k$ columns of $A Π$ . Then $C = Q [\begin{array}{c} R_{11} \\ 0 \end{array}]$ and $C (T Π) = Q [\begin{array}{cc} R_{11} & R_{11} X \\ 0 & 0 \end{array}] = Q [\begin{array}{cc} R_{11} & R_{12} \\ 0 & 0 \end{array}]$ . Subtracting from $A Π$ gives $(A - C T) Π = Q [\begin{array}{cc} 0 & 0 \\ 0 & R_{22} \end{array}]$ . A unitary matrix preserves vector norms, and a permutation maps the unit sphere onto itself; the definition of the operator norm therefore gives $∥ A - C T ∥_{2} = ∥ R_{22} ∥_{2}$ .

2.1F3F4step 1.3∎

The domain of $R_{22}$ has dimension $n - k > 0$ , so [F4] gives $∥ R_{22} ∥_{2} = σ_{1} (R_{22})$ . Apply [F3] with $j = 1$ and combine with step 1.3 to obtain the stated residual bound.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

12 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

Ming Gu and Stanley C. Eisenstat, Efficient Algorithms for Computing a Strong Rank-Revealing QR Factorization, Theorem 3.2 (standard reference, not scraped)
Per-Gunnar Martinsson and Joel A. Tropp, Randomized Numerical Linear Algebra: Foundations & Algorithms, §13.3 (standard reference, not scraped)
Nathan Halko, Per-Gunnar Martinsson, and Joel A. Tropp, Finding Structure with Randomness, §3.3.2 (standard reference, not scraped)