A superfast method for solving Toeplitz linear least squares problems.
Standard algorithms for solving linear least squares problems require \(O(mn^2)\) flops, algorithms that require only \(O(mn)\) flops are called fast, algorithms that require less operations are called superfast. In this paper a superfast \(O((m+n)\log(m+n))\) complexity algorithm for solving a least squares problem with an \(m\times n\) Toeplitz coefficient matrix is developed. It is based on the augmented matrix approach that relates the \(m\times n\) least squares problem with an equivalent \((m+ n)\times(m+ n)\) linear system. This system is transformed by means of the discrete Fourier transform into a Vandermonde block system (into a tangential interpolation problem) which is solved by a divide and conquer strategy in a superfast way. To avoid breakdowns and to guarantee a certain degree of stability ``difficult interpolation points are selected out during the execution of the algorithm and are treated in the standard fast (i.e. not superfast ) way at the end. The presented results of computational experiments show that the algorithm under discussion is indeed superfast (as long as the number of difficult points is small compared to the total number of interpolation points).
- A fast block Hankel solver based on an inversion formula for block Loewner matrices
- A fast Hankel solver based on an inversion formula for Loewner matrices
- A Fast Stable Solver for Nonsymmetric Toeplitz and Quasi-Toeplitz Systems of Linear Equations
- A general module theoretic framework for vector M-Padé and matrix rational interpolation
- A General Orthogonalization Technique with Applications to Time Series Analysis and Signal Processing
- A new algorithm for solving Toeplitz systems of equations
- A stabilized superfast solver for nonsymmetric Toeplitz systems
- Asymptotically fast solution of Toeplitz and related systems of linear equations
- Downdating of Szegö polynomials and data-fitting applications
- Fast Gaussian Elimination with Partial Pivoting for Matrices with Displacement Structure
- Fast Parallel Algorithms for QR and Triangular Factorization
- Fast solution of toeplitz systems of equations and computation of Padé approximants
- Fast Toeplitz orthogonalization
- Fast Toeplitz Orthogonalization Using Inner Products
- High performance algorithms for Toeplitz and block Toeplitz matrices
- scientific article; zbMATH DE number 686840 (Why is no real title available?)
- scientific article; zbMATH DE number 778080 (Why is no real title available?)
- Hybrid algorithm for fast Toeplitz orthogonalization
- Linear algebra, rational approximation and orthogonal polynomials
- New Fast Algorithms for Structured Linear Least Squares Problems
- Numerical experience with a superfast real Toeplitz solver
- QR factorization of Toeplitz matrices
- Solving Toeplitz systems after extension and transformation
- Stable and Efficient Algorithms for Structured Systems of Linear Equations
- Superfast Solution of Real Positive Definite Toeplitz Systems
- The prolate matrix
- Transformation techniques for Toeplitz and Toeplitz-plus-Hankel matrices. I: Transformations
- Transformation techniques for Toeplitz and Toeplitz-plus-Hankel matrices. II: Algorithms
- Fast robust regression algorithms for problems with Toeplitz structure
- A fast algorithm for linear least-squares smoothing and boundary value problems using number-theoretic transforms
- A least squares approach to reduce stable discrete linear systems preserving their stability.
- Fast iterative methods for solving Toeplitz-plus-Hankel least squares problems
- The fast Slepian transform
- scientific article; zbMATH DE number 1617949 (Why is no real title available?)
- Superfast and stable structured solvers for Toeplitz least squares via randomized sampling
- scientific article; zbMATH DE number 4147401 (Why is no real title available?)
- Superlinear PCG methods for symmetric Toeplitz systems
- Schur-Type Methods for Solving Least Squares Problems with Toeplitz Structure
- scientific article; zbMATH DE number 2151323 (Why is no real title available?)
- A Divide and Conquer Algorithm for the Superfast Solution of Toeplitz-like Systems
- scientific article; zbMATH DE number 7625175 (Why is no real title available?)
- Fast Solution of Toeplitz‐ and Cauchy‐Like Least‐Squares Problems
- A unified least squares approach to identify and to reduce continuous asymptotically stable systems
This page was built for publication: A superfast method for solving Toeplitz linear least squares problems.
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1874682)
