Alphabeta Math
CounterexampleConstruction: AI-generatedVerification: 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.

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 N≥2, let AN=diag⁡(1,N−2), exact solution x†=0, exact datum y=0, and noisy datum yδ=(0,N−1)T. The noise level is δN=N−1→0. The un-stopped projected LSQR solve takes one Golub–Kahan step and returns x1δ=(0,N)T with zero residual. Thus the error is N, which is not bounded by a fixed multiple of δN. With the assigned discrepancy-stopped procedure and zero initial guess, the initial residual already satisfies ∥r0∥=δN≤τδN; 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.

[F1]

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.

[F2]

Rectangular matrix multiplication and the identity matrix In, including zero-sized shapes: Matrix-vector multiplication is the coordinate sum of each row against the vector.

[F3]

The transpose AT of a matrix: (AT)ji=aij.

[F4]

The Euclidean inner product ⟨x,y⟩=∑k<nxkyk on Rn: ∥u∥2=(uTu)1/2 on real coordinate vectors.

[F5]

The natural numbers N (von Neumann): The iteration dimension parameter N is a natural number with N≥2.

[F6]

The vector space Mm×n(F):=F m×n of m by n matrices over a field, with entrywise operations: AN is a real 2×2 matrix and acts on real coordinate vectors by matrix multiplication.

Refutation

1.1givenF1F2F3F4F5F6algebra

For AN and yδ, r0=(0,N−1)T, so β1=N−1, u1=(0,1)T, α1=N−2, and v1=(0,1)T. The first bidiagonalization residual is ANv1−α1u1=0, so β2=0 and the one-dimensional projected least-squares problem is exact.

2.1F1F2F3F4F5F6step 1.1algebra∎

Its projected matrix is B1=(N−2,0)T∈R2×1 and right-hand side is β1e1=(N−1,0)T∈R2, so the unique minimizer is z1=N. Consequently x1δ=x0+Nv1=(0,N)T, ANx1δ=yδ, and ∥x1δ−x†∥2=N. The noise is ∥yδ−y∥2=N−1, so the error-to-noise ratio is N2→∞. 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 β2=0 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 ∥r0∥2=δN≤τδN; this computation concerns continuation to the full projected solve and claims no breakdown return.

Depends on

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.