Compression properties for large Toeplitz-like matrices
Bernhard Beckermann, Daniel Kressner, Heather Wilber · 2025
Read Compression properties for large Toeplitz-like matrices by Bernhard Beckermann, Daniel Kressner, Heather Wilber (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2502-09823.txt.
Introduction
Bernhard Beckermann and co-authors explain why a large class of structured matrices can be squeezed into far smaller form, in a 2025 paper. Toeplitz matrices, whose diagonals repeat, fill signal and control work, and fast solvers lean on the fact that their off diagonal blocks have low rank. That fact was used more than understood.
The team traces the compression to the matrices' displacement structure, a kind of hidden simplicity. They give explicit rank bounds for the blocks that arise in hierarchical solvers. The bounds yield lean, adaptive compression schemes and point toward superfast solvers that build themselves as they go.
Catalog record
| CREATOR | Bernhard Beckermann, Daniel Kressner, Heather Wilber |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 64 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2502-09823
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Compression properties for large Toeplitz-like matrices Bernhard Beckermann, Daniel Kressner, Heather Wilber Abstract Toeplitz matrices are abundant in computational mathematics, and there is a rich literature on the development of fast and superfast algorithms for solving linear systems involving such matrices. Any Toeplitz matrix can be transformed into a matrix with off-diagonal blocks that are of low numerical rank. This compressibility is relied upon in practice in a number of superfast Toeplitz solvers. In this paper, we show that the compression properties of these matrices can be thoroughly explained using their displacement structure and Zolotarev numbers. We provide explicit bounds on the numerical ranks of important submatrices that arise when applying HSS, HODLR and other approximations with hierarchical low-rank structure to transformed Toeplitz and Toeplitz-like matrices. Our results lead to very efficient displacement-based compression strategies that can be used to formulate adaptive superfast rank-structured solvers. keywords low-rank approximation, Toeplitz, numerical rank, displacement structure, superfast solver, hierarchical matrices, HSS matrices AMS 15B05, 15A18, 15A23, 15A06, 65F05, 41A20 1 Introduction A matrix that is constant along the diagonals is called a Toeplitz matrix: T=\begin{bmatrix}t_{0}&t_{-1}&\cdots&t_{-n+1}\\ t_{1}&t_{0}&\ddots&\vdots\\ \vdots&\ddots&\ddots&t_{-1}\\ t_{n-1}&\cdots&t_{1}&t_{0}\end{bmatrix}\in\mathbb{C}^{n\times n}. This and similar matrix structures appear frequently in computational mathematics, for instance in the context of discretized differential and integral equations, orthogonal polynomials, time series analysis, as well as image and signal processing [ 3 , 24 , 23 , 29 , 31 , 45 ] . Although the development of fast (and superfast) solvers for linear systems with Toeplitz matrices is a classical topic that is more than 60 years old, there have still been significant advances in recent years. In particular, a novel and versatile class of solvers is based on the observation that any Toeplitz (or Toeplitz-like) matrix can be transformed into a Cauchy-like matrix C with compressible off-diagonal blocks [ 13 , 38 , 55 ] . In turn, this allows one to leverage existing algorithms for matrices with hierarchical low-rank structure, not only for linear systems but also for, e.g., eigenvalue problems [ 44 ] , matrix functions, and matrix equations [ 32 ] . The goal of this work is to perform an analysis of the compressibility of C . Our analysis not only completes and improves upon existing analyses, but we will demonstrate that it is also the basis of new, deterministic algorithms for compressing C . Most fast direct solvers for a matrix T with Toeplitz and related structures are based on the observation that the displacement rank of T is small. More specifically, in this work we consider the Sylvester displacement equation (1) ZT-TZ=GH^{*},\quad Z=\begin{pmatrix}0&1\\ I_{n-1}&0\end{pmatrix},\quad{\rm rank}({G}{H}^{*})=\rho\ll n. For a Toeplitz matrix T , one can choose the displacement rank \rho=2 . Our developments also apply to Toeplitz-like matrices [ 31 , 45 ] , that is, matrices T that satisfy ( 1 ) for some \rho that is still small but possibly larger than 2 . Let us stress that the choice of displacement equation is by no means unique [ 31 ] . Our choice ( 1 ) is simple but not suitable for all purposes because the linear operator T\mapsto ZT-TZ is singular and, in turn, T cannot be fully reconstructed from the generator matrices G and H . Other choices have been made in the literature, using coefficient matrices different from Z or a Stein equation instead of a Sylvester equation. Classical fast solvers of complexity \mathcal{O}(n^{2}) , such as the generalized Schur algorithm, exploit the observation that Schur complements and inverses preserve the displacement rank, which in turn allows one to perform certain operations on T , such as the LU factorization, entirely in terms of the generator matrices; see [ 31 ] for a survey. Classical superfast solvers of complexity \mathcal{O}(n\log^{2}n) are obtained by combining this idea with a divide-and-conquer approach; see [ 30 ] and the references therein. The matrix Z in ( 1 ) is circulant and thus easily diagonalized by a unitary discrete Fourier transform F . In turn, the transformed matrix C=FTF^{*} satisfies a displacement equation with diagonal coefficients. This observation has been used in [ 20 ] to derive fast solvers with enhanced numerical stability; pivoting does not destroy the Cauchy-like structure of C . More recently, several works [ 13 , 38 , 55 ] have derived new superfast solvers from the fact that off-diagonal submatrices of C are well-approximated by low-rank matrices. Algorithm 1 describes the general framework of these solvers applied to a linear system (2) Tx=b,\quad T\in\mathbb{C}^{n\times n}, with a Toeplitz-like matrix T satisfying ( 1 ). Algorithm 1 Superfast solvers for a Toeplitz-like linear system ( 2 ). 1: Compute \widetilde{b}=Fb , \widetilde{G}=FG , \widetilde{H}=FH . 2: Determine \widetilde{C} , a hierarchical low-rank approximation of C=FTF^{*} from its generators \widetilde{G},\widetilde{H} . 3: Solve \widetilde{C}\widetilde{x}=\widetilde{b} . 4: Compute x=F^{*}\widetilde{x}. Steps 1 and 4 of Algorithm 1 can be easily accomplished in \mathcal{O}(n\rho\log n) operations using fast Fourier transforms (FFTs). For Step 2, several hierarchical approximations of C are possible. This includes the relatively simple HODLR (Hierarchical Off-Diagonal Low-Rank) format, as well as the more involved SSS (sequentially semi-separable) and HSS (hierarchical semi-separable) formats used in [ 13 , 37 , 55 ] . In all these formats, the approximation \widetilde{C} is constructed by recursively partitioning C into successively smaller submatrices and replacing each submatrix by a low-rank approximation. HSS format features additional structure; the low-rank factors between different levels of the recursion tree are nested; see Section 4 . Its use leads to particularly efficient \mathcal{O}(np^{2}) direct solvers for Step 3 [ 12 , 55 ] , assuming that the rank of each low-rank approximant in \widetilde{C} is bounded by p . The efficiency of Steps 2 and 3 depends on (i) the hierarchical low-rank format used, (ii) the compressibility of C , (iii) the method of approximation used to find \widetilde{C} , and (iv) the type of solver used in Step 3. In this work, we focus on analysis related to (ii) and (iii). 1.1 Main results The primary novelty in our paper is the introduction of new bounds that more thoroughly explain the low-rank properties of the Cauchy-like matrix C . This mproves upon some results that currently exist in the literature, and it provides explicit bounds on the singular values of the relevant submatrices of C . We show that the alternating implicit direction (ADI) method can be used to construct low rank approximations with errors controlled by our bounds. This leads to an efficient and adaptive algorithm for constructing HODLR and HSS approximations to C in Step 2 of Algorithm 1 . The current state-of-the-art for solving ( 2 ) given an arbitrary Toeplitz matrix is based on randomized linear algebra [ 55 ] . Our analysis more thoroughly explains the effectiveness of this method, and it also serves as the basis of competitive deterministic analogue methods. To describe the compressibility of C , we use the notion of numerical rank, also called \epsilon -rank: Definition 1 . Let \sigma_{1}(X)\geq\sigma_{2}(X)\geq\cdots\geq\sigma_{\min\{m,n\}}(X)\geq 0 denote the singular values of a matrix X\in\mathbb{C}^{m\times n} . Given 0<\epsilon<1 , the \epsilon -rank of X is {\rm rank}_{\epsilon}(X)=k for the smallest integer k such that \sigma_{k+1}(X)\leq\epsilon\|X\|_{2} , where \|\cdot\|_{2}=\sigma_{1}(X) denotes the spectral