Displacement ranks of matrices and linear equations

By Thomas Kailath, S. Kung, M. Morf. 1979

Subfields: Numerical Methods & Scientific Computing

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Numerical Methods & Scientific Computing

Citations in the corpus

FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awareness (2022, background): “There have been several more general classes of structured matrices proposed in machine learning: Toeplitz-like [81], low-displacement rank [51], quasi-separable [27]).”
Randomized Matrix Computations (2012, unknown): “zed augmentation and dual augmentation, their link to aggregation processes (cf. [MP80], [PQa]), speciﬁcation of our methods to ill conditioned matrices that have displacement or rank structures (cf. [KKM79], [P90], 44 Table 10.4: The condition numbers κ(A) of random circulant matrices A n min mean ”
Learning Fast Algorithms for Linear Transforms Using Butterfly Factorizations (2019, methodology): “These were generalized under the seminal notion of low displacement rank (LDR) introduced by Kailath et al. [21], and were later uniﬁed under a single class of displacement structure (the conﬂuent Cauchy-like matrices) introduced by Olshevsky & Shokrollahi [32] to solve the Nevanlinna-Pick…”
Structured matrices and newton's iteration: unified approach (2000, background): “The modern study of structured matrices was largely motivated by the seminal paper [18] and, in particular, by the basic concept of the displacement rank introduced there.”
OFDM or single-carrier block transmissions? (2004, background): “The reason is that CFO introduces both ICI as well as reduction of the useful signal amplitude in OFDM, while ZP-only suffers only from the latter, which has a smaller effect than the former.”
Multilevel Toeplitz Matrices Generated by Tensor-Structured Vectors and Convolution with Logarithmic Complexity (2013, unknown): “Toeplitz structure was also generalized to the displacement structure possessed by Toeplitz-like matrices [17].”
Kaleidoscope: An Efficient, Learnable Representation For All Structured Linear Maps (2020, background): “…classes of structures matrices– orthogonal polynomial transforms (Driscoll et al., 1997; Szegö, 1967) as well as matrices with low displacement rank (Kailath et al., 1979; Olshevsky & Shokrollahi, 2000)– and presents a linear class of linear arithmetic circuits to solve their matrix vector…”
A Two-pronged Progress in Structured Dense Matrix Vector Multiplication (2018, methodology): “We remark that this form generalizes the well-known ΣLU representation of Toeplitz-like matrices, which is used in multiplication and inversion algorithms for them [25].”
Monarch: Expressive Structured Matrices for Efficient and Accurate Training (2022, background): “…of these transforms (e.g., Toeplitz-like (Sindhwani et al., 2015), orthogonal polynomial transforms (Driscoll et al., 1997), lowdisplacement rank (Kailath et al., 1979), quasi-separable (Eidelman & Gohberg, 1999)), though learnable, often lack efficient implementation on GPUs (Thomas et al.,…”
Structured Transforms for Small-Footprint Deep Learning (2015, background): “In Section 2, we attempt to give a self-contained overview of the displacement rank approach [13], [18] drawing key results from the relevant literature on structured matrix computations (proved in our supplementary material [1] for completeness).”
Tensor properties of multilevel Toeplitz and related matrices (2006, background): “⊗T−1 r is the tensor product of matrices with low displacement rank (the displacement rank of M is defined to be the rank of M − ZMZ , where M = [δi,j+1] [13], [11], [16]).”