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.
A fully converged LSQR solve can amplify a small singular-direction error
Statement refuted
There is a constant independent of the matrix such that continuing the LSQR projected solves to zero residual always gives an estimate within that constant times the data-noise level of the exact solution.
Concrete instance
For each integer , let , exact solution , exact datum , and noisy datum . The noise level is . The un-stopped projected LSQR solve takes one Golub–Kahan step and returns with zero residual. Thus the error is , which is not bounded by a fixed multiple of . With the assigned discrepancy-stopped procedure and zero initial guess, the initial residual already satisfies ; the procedure returns at index zero. The example concerns continuing to a full solve and shows why early stopping matters.
Facts & Assumptions
Given: The diagonal matrix, exact and noisy data, and zero initial guess.
Exact-arithmetic LSQR with Golub–Kahan bidiagonalization and explicit statuses: The un-stopped version uses the stated LSQR initialization and first projected solve; the assigned procedure itself may return earlier at its discrepancy check.
Rectangular matrix multiplication and the identity matrix , including zero-sized shapes: Matrix-vector multiplication is the coordinate sum of each row against the vector.
The Euclidean inner product on : on real coordinate vectors.
The natural numbers (von Neumann): The iteration dimension parameter is a natural number with .
The vector space of by matrices over a field, with entrywise operations: is a real matrix and acts on real coordinate vectors by matrix multiplication.
Refutation
For and , , so , , , and . The first bidiagonalization residual is , so and the one-dimensional projected least-squares problem is exact.
Its projected matrix is and right-hand side is , so the unique minimizer is . Consequently , , and . The noise is , so the error-to-noise ratio is . This refutes the proposed uniform bound and shows that the projected solve can fit a small noise component in a weak singular direction. The value marks bidiagonalization breakdown; the projected solve still forms the exact one-step iterate before the algorithm tests its final status. For the assigned discrepancy-stopped algorithm, the initial test already returns at index zero because ; this computation concerns continuation to the full projected solve and claims no breakdown return.
Depends on
- Exact-arithmetic LSQR with Golub–Kahan bidiagonalization and explicit statuses
- The vector space $M_{m \times n}(F) := F^{\,m \times n}$ of $m$ by $n$ matrices over a field, with entrywise operations
- Rectangular matrix multiplication and the identity matrix $I_n$, including zero-sized shapes
- The transpose $A^{\mathsf T}$ of a matrix
- The Euclidean inner product $\langle x,y\rangle = \sum_{k<n} x_k y_k$ on $\mathbb{R}^n$
- The natural numbers $\mathbb{N}$ (von Neumann)
Used by
Nothing in the library uses this result yet.
Dependency tree · two levels
25 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.