Superfast and stable structured solvers for Toeplitz least squares via randomized sampling (Q2877078)

Let \(T \in \mathbb{C}^{m\times n}\) is a Toeplitz matrix with \(m \geq n\), and \(b \in \mathbb{C}^m\). A Toeplitz least squares problem in the following form \(\min\limits_x ||Tx-b||_2\) is considered. Superfast and stable structure direct solvers of this problem are proposed. The Toeplitz matrix \(T\) is fist transformed into a Cauchy-like matrix \(\mathcal{C}\), which has small off-diagonal numerical ranks when the diagonal blocks are rectangular. Standard hierarchically semiseparable (HSS) matrix representations to a rectangular generalized and a rectangular HSS approximation to \(\mathcal{C}\) in nearly linear complexity with randomized sampling and fast multiplications of \(\mathcal{C}\) with vectors are constructed. A new URV HSS factorization and a URV HSS solution are designed for the least squares solution.