An O(N)-Memory Representation of the Singular Basis of a General Toeplitz Operator

Deconvolution with a shift-invariant kernel is, under any of the standardregularisations, a projection onto the singular basis of a Toeplitz matrix; thatbasis is an N×N array and cannot be stored at the sizes where the projection isapplied repeatedly. Working in one dimension throughout, we give a representationof it in O(N) memory. Reversing the rows of a Toeplitz matrix gives a Hankel matrix, and that Hankelmatrix is symmetric for every kernel, symmetric or not; hence the singular valuedecomposition of a general Toeplitz matrix is the eigendecomposition of asymmetric Hankel matrix. On that matrix the shift obeys a rank-two commutator atfirst order and full rank in the form the singular basis needs, so we pass to thesecond power and obtain a displacement equation of rank four. Its solution makesthe image of the shift in the eigenbasis a Cauchy-type matrix determined by twolow-rank factors and the eigenvalues, that is by O(N) numbers, and the rows of thebasis are then generated from the last row by a one-step recurrence; bothtransforms are single passes over those rows. If the recurrence were exact there would be no error at all, and the error it doesincur is traceable: it comes from the division by d_j² − d_i², is amplified by thesmallest gap in the squared spectrum, and accumulates linearly over the N steps.Measured, the transform error grows from 3.6×10⁻¹³ at N = 128 to 1.4×10⁻⁹ atN = 4096, an exponent of about 1.7, not the cubic that a naive count of the stepswould suggest. Because the eigenvalues of a symmetric matrix are real, the Cauchy products can beevaluated hierarchically, at Θ(rN² log²N) per transform; measured, the operationcount per product falls from 3.3N² at N = 256 to 0.33N² at N = 8192 while itserror stays at the rounding level, and the error of the complete recurrence is setby the representation rather than by this evaluation. Calibration — a denseeigendecomposition — remains the binding constraint.