Truncated Pseudoinverses That Keep Their Toeplitz Structure

Many dense matrices in signal processing, function approximation and covariance estimation have hidden structure: they are Toeplitz (constant along diagonals), Hankel, Cauchy or Vandermonde. That structure lets you store them with $O(n)$ numbers and multiply by them, or even by their inverses, in $O(n \log n)$ time. The same matrices are often badly ill-conditioned, meaning some of their singular values are tiny, so an exact inverse amplifies noise enormously. The standard remedy is truncated SVD (TSVD): compute the singular value decomposition, throw away every direction whose singular value falls below a threshold $\tau$, and invert only the rest. TSVD works, but it costs $O(n^3)$, and the operator it returns has lost all Toeplitz-like structure. Practitioners therefore choose between fast structured inversion that is only trustworthy when the matrix is well-conditioned, and stable truncation that is slow and unstructured.

This note proposes a way out. Write the truncated pseudoinverse as a function of the matrix, and approximate that function by a short sum of shifted inverses $(\mathcal{A} + i\omega_j I)^{-1}$. Each shifted matrix keeps low "displacement rank" (defined below), so each term has a closed-form fast inverse. The result is an explicit truncated pseudoinverse stored as $O(d\,r)$ length-$n$ generator vectors and applied in $O(d\,r\, n\log n)$ time, where $d$ is the number of shifts and $r$ the displacement rank. The choice of shifts has a second benefit that matters as much as the speed. The shifts guarantee that every term is a well-conditioned structured inversion. That is precisely the regime where existing stability proofs for fast Toeplitz inverse formulas hold.

Core Claim

The displacement framework describes structure through a residual. For fixed sparse operators $L$ and $R$ (for example, shift matrices), $\nabla(A) = LA - AR = GH^T$ with generators $G, H \in \mathbb{C}^{n\times r}$. A Toeplitz matrix has displacement rank $r \le 2$ with respect to shifts. Using this representation for compression and fast products is established by Structured Transforms for Small-Footprint Deep Learning and extended to learnable operators by Learning Compressed Transforms with Low Displacement Rank.

To avoid squaring the condition number through normal equations, we work with the Hermitian dilation $\mathcal{A} = \begin{pmatrix} 0 & A \\ A^* & 0\end{pmatrix}$. Its eigenvalues are $\pm\sigma_i(A)$, and it is block-Toeplitz-like with displacement rank at most about $2r$. The TSVD pseudoinverse corresponds to applying to $\mathcal{A}$ the odd scalar filter $\phi_\tau(x) = 1/x$ for $|x|\ge\tau$ and $0$ otherwise. We approximate that filter with a rational function whose poles lie on the imaginary axis:

$$ \phi_\tau(x) \approx \sum_{j=1}^{d} \frac{c_j}{x + i\omega_j}, \qquad \text{so}\qquad A_\tau^\dagger \approx \Big[\sum_{j=1}^d c_j (\mathcal{A} + i\omega_j I)^{-1}\Big]_{\text{off-diagonal block}}, $$

where $c_j$ are weights and $\omega_j>0$ are real shifts. Adding $i\omega_j I$ changes the displacement rank by at most one. The inverse of a low-displacement-rank matrix has the same displacement rank with respect to the swapped operators. So each term has a Gohberg–Semencul-type representation, and so does the sum, with displacement rank $O(dr)$.

The approximation is controlled only on the two regions $|x|\ge\tau$ and $|x|\le(1-\delta)\tau$. The number of terms needed for uniform error $\varepsilon$ on those regions should scale like $\log(1/\varepsilon)\cdot\log(\sigma_{\max}/(\delta\tau))$. That is the Zolotarev-type rate for rational approximation of a sign-like function on two separated intervals, the same machinery behind ADI shift selection. Every shifted matrix satisfies $\kappa(\mathcal{A}+i\omega_j I)\le \sqrt{\sigma_{\max}^2+\omega_j^2}/\omega_j$, and the smallest useful shift is of order $\delta\tau$. The conditioning of every structured inversion is therefore capped near $\sigma_{\max}/(\delta\tau)$, the same scale as the conditioning TSVD itself accepts.

The new object is a displacement-preserving truncated pseudoinverse: an operator whose singular-value filtering is certified to accuracy $\varepsilon$, which is stored in generator form, and which inherits forward stability from well-conditioned structured inversion. Section 4 of the research file flags this object as missing.

Relation to Prior Work

Two lines of work supply the fast inverse formulas this proposal reuses, and both stop at the conditioning barrier. A new Toeplitz inversion formula, stability analysis and the value writes $T^{-1}=S_1U_1+S_2U_2$ with skew-circulant and triangular Toeplitz factors, applied in $16n\log_2 n$ operations. Its forward-stability theorems (3.1, 3.2) assume well-conditioning. Skew cyclic displacements and decompositions of inverse matrix for an innovative structure matrix extends such decompositions to a wider class of matrices but requires exact nonsingularity. We use their formulas as the per-shift building block. The shifts deliberately place each call inside the regime where their stability analysis applies, rather than extending the formulas to ill-conditioned matrices directly.

On Drazin inverse of singular Toeplitz matrix gives a structured generalized inverse, but it is exact and algebraic. It is therefore numerically useless when singular values are tiny but nonzero, and it covers only bordered Toeplitz matrices. A Singular Woodbury and Pseudo-Determinant Matrix Identities and Application to Gaussian Process Regression handles rank-deficient covariance matrices through Bott–Duffin inverses and tests on Toeplitz covariances from ECG data. Its identities are dense and use exact subspace projections, not a tunable threshold. Both papers motivate the gap. Neither supplies a filtered, structured inverse.

The closest methodological relative is On the singular values of matrices with high displacement rank. It splits a Sylvester right-hand side by its SVD, chooses ADI shifts via rational approximation, and shows that solutions have rapidly decaying singular values. We borrow its rational-shift viewpoint, and its argument that numerical displacement rank, not exact rank, is what matters, for recompressing the $O(dr)$ generators. However, it solves $AX-XB=F$ and never forms an inverse or a regularized pseudoinverse. Its warning that non-normal operators incur eigenvector-conditioning penalties is a reason we filter the Hermitian dilation rather than $A$ itself.

On the application side, three papers show that TSVD, not the exact inverse, is what makes ill-conditioned structured approximation work, and all three use dense SVD. Parameter selection and numerical approximation properties of Fourier extensions from fixed data shows that the threshold trades precision against resolution. Stable and Accurate Least Squares Radial Basis Function Approximations on Bounded Domains stabilizes near-flat RBF systems with TSVD. Multivariate rational approximation of functions with curves of singularities reaches machine precision with TSVD on Cauchy-like bases. These papers define our testbeds and our accuracy ceiling.

LoRanPAC supplies evidence that hard truncation beats ridge regularization in long sequences of learning tasks. It also constrains the design: it reports randomized SVD as less stable than exact truncation, which argues against sketching as the shortcut.

Research Program

The first component is the filter design. For given $\tau$, transition width $\delta$ and target $\varepsilon$, we compute shifts and weights by a Zolotarev-type construction on the two intervals, falling back to rational least-squares fitting on a fine grid. We will tabulate how $d$ depends on $\varepsilon$ and $\sigma_{\max}/\tau$ and check the predicted doubly-logarithmic growth. Because $\sigma_{\max}$ can be estimated by a few power iterations with fast matrix products, the construction never needs the full spectrum.

The second component is structured assembly. For Toeplitz, Hankel and Cauchy-like $A$, we build generators of each $\mathcal{A}+i\omega_jI$, compute its inverse generators with a Gohberg–Semencul or skew-circulant formula (block versions for the dilation), and sum. The summed generators are then recompressed by an SVD of the stacked generator matrices, which costs only $O(n(dr)^2)$. The central empirical question is how much this recompression shrinks the displacement rank. If the numerical displacement rank of $A_\tau^\dagger$ stays near $O(r\log(1/\varepsilon))$ rather than $O(dr)$, that is a finding in its own right, analogous to the singular-value decay Townsend and Wilber prove for Sylvester solutions.

The third component is analysis. We will prove a forward error bound of the form "rational filtering error plus $d$ times the per-shift structured-inversion error." The per-shift error is controlled by the Zheng et al. theorems applied at condition number at most $\sigma_{\max}/(\delta\tau)$. We will also bound the displacement rank of the exact filtered operator.

The fourth component is the Hermitian special case. For symmetric positive semidefinite Toeplitz covariances, such as ECG covariances and AR, MA and fractional Brownian motion processes, the filter acts on eigenvalues directly. No dilation is needed, and positive semidefiniteness of the output is automatic when the fitted rational function is nonnegative on the spectrum.

Baselines

The accuracy ceiling is dense TSVD computed by LAPACK in $O(n^3)$, with the same threshold $\tau$. On rational approximation with edge singularities, Multivariate rational approximation of functions with curves of singularities reports a maximum error of $4.6\times10^{-15}$ using dense TSVD, and $6\times10^{-6}$ on the gravity Helmholtz Green's function. For TSVD Fourier extension error on the $f_1$–$f_9$ suite, no reported result was found on Lacuna, so we recompute it. We compare at equal threshold. Beating dense TSVD means matching its solution error within a factor of ten while being faster from a crossover size onward and using $O(n)$ storage.

The naive reference point is the unregularized fast inverse formula of A new Toeplitz inversion formula, stability analysis and the value applied directly to the ill-conditioned matrix. We expect it to lose most digits once $\kappa(A)$ exceeds about $10^{8}$. Documenting that collapse is part of the motivation.

The strongest fast competitor is truncated Golub–Kahan–Lanczos bidiagonalization driven by FFT matrix products. It computes the leading singular triplets above $\tau$ at $O(k\,n\log n)$ per sweep plus reorthogonalization. We run it with the same fast product routine, full reorthogonalization, and a tuning budget matched in wall-clock time. It beats us for one right-hand side if it reaches equal error in less total time. We claim to beat it when many right-hand sides are needed, when the number of kept singular values $k$ is large, or when an explicit operator must be stored or differentiated.

Structure-preserving Tikhonov, $(A^*A+\lambda I)^{-1}A^*$ solved with a displacement solver, is the single-shift special case of our method. It serves as the key ablation. Comparing $d=1$ against $d>1$ at matched cost isolates whether a sharp spectral cutoff, rather than mere shifting, buys accuracy.

For covariance experiments we add the projected least-squares and projected gradient estimators of Gohberg-Semencul Estimation of Toeplitz Structured Covariance Matrices and Their Inverses. Their exact normalized mean squared error figures are not reproduced in the file, so we rerun them at $N=8$, $P=16$ and larger. We also compare against the dense Bott–Duffin routines in detkit from Ameli and Shadden on MIT-BIH Toeplitz covariances; the file reports no wall-clock numbers for these.

Why not just…?

Why not just use Tikhonov regularization, which already preserves displacement structure? It does: $A^*A+\lambda I$ stays low-displacement-rank, so it is cheap. But it damps small singular values instead of removing them, which leaves bias in the retained directions. LoRanPAC reports that truncation beat ridge regularization by over 25% on ImageNet-A in its one-class-at-a-time setting. That is evidence from a different domain, not proof for structured approximation. Our $d=1$ ablation tests the question directly. If Tikhonov with a tuned $\lambda$ matches truncation on the Fourier extension and RBF suites, the sharp filter is not worth its cost there, and we will say so.

Why not just run Lanczos bidiagonalization with fast Toeplitz products? This is the real threat. For a single right-hand side and few kept singular values it may simply win. Its cost grows with the number of retained singular values $k$ and needs reorthogonalization. It returns an unstructured rank-$k$ operator, not a reusable $O(n)$-storage inverse. Our cost depends on $d$, which is tied to $\log(\sigma_{\max}/\tau)$, and not on $k$. The experiments sweep $k/n$ from 1% to 90% and the number of right-hand sides from 1 to $n$ to locate the crossover honestly.

Why not just use randomized SVD? LoRanPAC found randomized SVD less stable than exact truncation in its incremental setting. Randomized sketches also approximate the leading subspace poorly when singular values decay slowly around $\tau$, which is exactly where the cutoff sits in Fourier extension. We include a randomized-SVD run with oversampling and power iterations as a secondary baseline.

Why not just compute the dense TSVD and then fit a Toeplitz-like approximation to it? This costs $O(n^3)$ before any compression, so it defeats the purpose. It also gives no guarantee on filtering accuracy. We use it only as a diagnostic, to measure the true numerical displacement rank of $A_\tau^\dagger$ that our recompression should approach.

Proposed Experiments

The primary testbed is the Fourier extension suite of Adcock and Ruan, whose normal matrices are Toeplitz. We use $T=2$ and oversampling $\eta=2$ at sizes from $10^3$ to $10^5$, measuring maximum approximation error, wall-clock time and storage against dense TSVD, Lanczos TSVD and Tikhonov. The secondary testbeds are 1D Gaussian RBF least squares on equispaced centers, which gives Toeplitz structure, as in Huybrechs et al., and the Cauchy-like rational bases of Boullé et al. For the Cauchy-like bases, the per-shift inversion uses Cauchy displacement operators.

For covariance, we evaluate AR, MA and fractional Brownian motion processes under sample starvation, reporting normalized mean squared error of the inverse covariance and the rate of positive-definiteness failures. We also time the method on MIT-BIH Toeplitz covariances against detkit.

Three checks decide the proposal. First, at matched threshold, the structured pseudoinverse must track dense TSVD error across all $\kappa(A)$ up to $10^{14}$, while the unregularized fast formula fails. Second, the recompressed displacement rank must grow at most logarithmically in $1/\varepsilon$ and $\sigma_{\max}/\tau$. Linear growth in $d$ with no recompression gain would sharply limit the method's value. Third, a measured time crossover against Lanczos TSVD must exist as the number of kept singular values or right-hand sides grows. If none of these crossovers appears at sizes up to $10^5$, the honest conclusion is that Krylov methods already occupy this niche.