One objective · two computational traditions · one modern reunion

Least squares: from Householder QR and ADALINE to DeltaNet

Householder QR and the Widrow–Hoff delta rule are usually taught in different subjects. One belongs to numerical linear algebra; the other to adaptive filters and early neural networks. Both address the same mathematical object: linear least squares.

The numerical branch solves the whole problem with an orthogonal factorization. The adaptive branch moves toward the solution one observation at a time. Modern fast-weight linear attention turns the adaptive update into a matrix-valued memory rule; DeltaNet then exposes an identity-minus-rank-one state transition, and the Householder/WY machinery returns to make that recurrence run efficiently on GPUs.

The relationship

The fork and reunion

Historical scope. The shared objective and the modern algebraic reunion are explicit. The sources cited here do not establish that Widrow and Hoff derived their rule from Householder QR. Treat the 1958–1965 fork as two parallel computational responses to least squares, not as a documented chain of influence.

1. Common mathematical problem

Linear least squares

Start with a matrix A ∈ R^m×n, an unknown parameter vector x ∈ Rⁿ, and measured targets b ∈ R^m. Usually there are more observations than unknowns, so no vector x satisfies every equation exactly.

x* = arg min_x 1/2 ||Ax − b||²

The objective chooses the parameters whose predictions Ax have the smallest total squared error against b. This is least squares.

The same objective has two obvious computational regimes:

All observations are available

Factor the whole matrix and solve the problem as numerical linear algebra.

Observations arrive over time

Use each new example to update the parameters incrementally.

2. Batch branch

Householder QR turns least squares into a triangular solve

For A ∈ R^m×n with m ≥ n, a full orthogonal QR reduction chooses a square orthogonal matrix Q ∈ R^m×m so that

QᵀA = [ R ]
[ 0 ]

where R ∈ R^n×n is upper triangular. Because Q is orthogonal, multiplying the complete residual by Qᵀ preserves its Euclidean norm:

||Ax − b|| = ||Qᵀ(Ax − b)||

Write Qᵀb = [c₁; c₂], with c₁ ∈ Rⁿ. Then

||Ax − b||² = ||Rx − c₁||² + ||c₂||²

The second term does not depend on x. The least-squares minimizer therefore comes from the triangular system Rx = c₁. The equivalent thin notation is the familiar A = Q₁R, where Q₁ contains the first n columns of the full orthogonal matrix.

Businger and Golub's 1965 paper states this reduction directly and uses Householder transformations to construct the triangular form.

Why Householder reflections?

H = I − 2vvᵀ/(vᵀv)

A Householder reflector is orthogonal. Choose v so that applying H to a column zeros the entries below its diagonal element. Repeating this column by column produces the triangular matrix R.

Householder's 1958 paper came from a line of orthogonal triangularization work at Oak Ridge that emphasized numerical stability. Orthogonal transformations do not amplify vector lengths, so they provide a stable route to reduction before the triangular solve.

Batch view: preserve the least-squares objective exactly, reorganize the whole data matrix, then solve.

3. Online branch

ADALINE takes gradient steps on squared error

Widrow and Hoff's 1960 ADALINE work also starts from mean-square error, but the machine sees patterns over time. For one example, let a ∈ Rⁿ be the input, y the desired output, and w ∈ Rⁿ the adjustable weights.

L(w) = 1/2 (y − wᵀa)²

The gradient is

∇_wL = −(y − wᵀa)a

so a gradient-descent step is

w ← w + η(y − wᵀa)a

This is the Widrow–Hoff delta rule, also known through the least-mean-squares (LMS) adaptive-filter tradition. The 1960 paper describes steepest descent on mean-square neuron error and emphasizes that one pattern per iteration is enough to obtain the required derivative signal.

Instead of solving one large matrix problem, the current weights carry forward what has been learned from previous observations.

Online view: do not solve the least-squares system in one batch; repeatedly move the current parameters downhill on squared error.

4. Same objective, different computation

QR and the delta rule are not competing formulas for the same step

Property	Householder QR	Widrow–Hoff delta rule
Objective	minimize total squared residual	minimize mean / sample squared error
Data view	whole matrix of observations	one pattern or small stream step at a time
Computation	orthogonal factorization + triangular solve	iterative steepest-descent correction
State carried forward	factorization / solution workspace	the current learned weights
Main advantage	accurate stable batch solve	cheap streaming adaptation without retaining the whole dataset

The important connection is the objective, not an identity between algorithms. QR changes coordinates so the batch optimum is easy to solve. The delta rule estimates the same kind of optimum by repeated local corrections.

5. From regression weights to memory weights

Make the delta rule matrix-valued and it becomes an associative-memory update

Replace the scalar-output regression model with a vector-valued association. Let:

S ∈ R^dᵥ×dₖ be a memory matrix,
k ∈ R^dₖ be a key,
v ∈ R^dᵥ be the value that key should retrieve.

The memory currently predicts Sk. Give that association the squared-error objective

L(S) = 1/2 ||Sk − v||²

The matrix gradient is

∇_SL = (Sk − v)kᵀ

and one gradient step is therefore

S ← S + β(v − Sk)kᵀ

This is the delta-rule memory update used by DeltaNet. The scalar adaptive weight vector has become a matrix of fast weights, and one token supplies the key, target value, and write strength.

ADALINE / LMS	Fast-weight memory	Role
w	S	parameters being adapted
a	k	input / memory address
y	v	desired output
y − wᵀa	v − Sk	prediction error
η	β	adaptation / write strength

6. From online learning to temporary memory

Fast weights turn adaptation into sequence memory

In adaptive filtering, the changing weights are the model being fitted. Fast-weight systems reuse the same mechanism as temporary state: a slower network emits instructions that rapidly modify another set of weights while processing a sequence.

Schmidhuber's 1992 fast-weight memory work made this separation explicit. Schlag, Irie, and Schmidhuber's 2021 paper then showed that linearized self-attention is formally equivalent to a fast-weight programmer whose elementary writes are key-value outer products. They replaced purely additive writes with a delta-rule-like instruction so the memory can correct its existing key-to-value mapping rather than only accumulate another outer product.

Additive linear attention

S ← S + vkᵀ

Always add another association.

Delta-rule memory

S ← S + β(v − Sk)kᵀ

Read the current association, measure its error, then write the correction.

7. The numerical branch returns

DeltaNet's delta rule contains an identity-minus-rank-one transition

Expand the matrix-valued delta update:

S ← S + β(v − Sk)kᵀ
S ← S − βSkkᵀ + βvkᵀ
S ← S(I − βkkᵀ) + βvkᵀ

The old state is multiplied by I − βkkᵀ. Yang et al. describe this as a generalized Householder transformation: an identity matrix plus or minus a rank-one modification.

True Householder reflector

H = I − 2kkᵀ/(kᵀk)

Orthogonal. Geometrically a reflection.

DeltaNet transition

G = I − βkkᵀ

Same rank-one shape, but generally not orthogonal and therefore not literally a reflection.

If k is unit length, an exact Householder reflection would use coefficient 2. DeltaNet learns a write strength β; the useful connection is the structured rank-one form, not reflection geometry.

8. Reunion on modern hardware

Products of delta-rule transitions bring back WY

Over many tokens, DeltaNet repeatedly multiplies the old state by transitions of the form

G_t = I − β_tk_tk_tᵀ

so a chunk contains ordered products such as

G₁G₂···G_C

Evaluating those products token by token is exactly the kind of fine-grained recurrence that modern GPUs dislike. Yang et al. 2024 explicitly exploit a memory-efficient representation for products of Householder matrices and use the WY representation to obtain a chunkwise parallel DeltaNet algorithm.

The result closes the loop:

least squares
→ online delta rule
→ matrix-valued fast-weight memory
→ identity-minus-rank-one DeltaNet recurrence
→ products of generalized Householder transforms
→ WY blocking
→ GPU matrix multiplication

The historical symmetry: one least-squares branch developed orthogonal factorizations for stable batch solves. The other developed gradient adaptation for streaming data. DeltaNet inherits the adaptive branch, then needs the structured-product machinery developed on the numerical branch to train efficiently at scale.

9. Chronology

The two branches across six decades

Year	Work	Contribution to this lineage
1958	Householder	Orthogonal triangularization with numerically stable transformations.
1960	Widrow & Hoff	Adaptive switching / ADALINE: steepest descent on mean-square error, usable one pattern at a time.
1965	Businger & Golub	Explicit linear least-squares solver using Householder transformations.
1987	Bischof & Van Loan	WY representation accumulates products of Householder matrices into block operations.
1992	Schmidhuber	Fast-weight memories use rapidly changing weights as temporary sequence state.
2021	Schlag, Irie & Schmidhuber	Linear transformers as fast-weight programmers; delta-rule-like writes correct key-value mappings.
2024	Yang et al.	DeltaNet recurrence as generalized Householder transformations; WY enables chunk-parallel training.

Sources

Primary trail and background

A. S. Householder, Unitary Triangularization of a Nonsymmetric Matrix, JACM, 1958.
B. Widrow and M. E. Hoff Jr., Adaptive Switching Circuits, IRE WESCON, 1960.
P. Businger and G. H. Golub, Linear Least Squares Solutions by Householder Transformations, Numerische Mathematik, 1965.
C. Bischof and C. Van Loan, The WY Representation for Products of Householder Matrices, 1987.
J. Schmidhuber, Learning to Control Fast-Weight Memories, Neural Computation, 1992.
I. Schlag, K. Irie, J. Schmidhuber, Linear Transformers Are Secretly Fast Weight Programmers, 2021.
S. Yang et al., Parallelizing Linear Transformers with the Delta Rule over Sequence Length, 2024.

Background links: least squares, QR decomposition, ADALINE, WY/UT history, and linear attention and bounded memory.