TY - JOUR

T1 - Superfast and stable structured solvers for Toeplitz least squares via randomized sampling

AU - Xi, Yuanzhe

AU - Xia, Jianlin

AU - Cauley, Stephen

AU - Balakrishnan, Venkataramanan

PY - 2014

Y1 - 2014

N2 - We present some superfast (O((m + n) log2(m + n)) complexity) and stable structured direct solvers for m× n Toeplitz least squares problems. Based on the displacement equation, a Toeplitz matrix T is first transformed into a Cauchy-like matrix C, which can be shown to have small off-diagonal numerical ranks when the diagonal blocks are rectangular. We generalize standard hierarchically semiseparable (HSS) matrix representations to rectangular ones, and construct a rectangular HSS approximation to C in nearly linear complexity with randomized sampling and fast multiplications of C with vectors. A new URV HSS factorization and a URV HSS solution are designed for the least squares solution. We also present two structured normal equation methods. Systematic error and stability analysis for our HSS methods is given, which is also useful for studying other HSS and rank structured methods. We derive the growth factors and the backward error bounds in the HSS factorizations, and show that the stability results are generally much better than those in dense LU factorizations with partial pivoting. Such analysis has not been done before for HSS matrices. The solvers are tested on various classical Toeplitz examples ranging from well-conditioned to highly ill-conditioned ones. Comparisons with some recent fast and superfast solvers are given. Our new methods are generally much faster, and give better (or at least comparable) accuracies, especially for ill-conditioned problems.

AB - We present some superfast (O((m + n) log2(m + n)) complexity) and stable structured direct solvers for m× n Toeplitz least squares problems. Based on the displacement equation, a Toeplitz matrix T is first transformed into a Cauchy-like matrix C, which can be shown to have small off-diagonal numerical ranks when the diagonal blocks are rectangular. We generalize standard hierarchically semiseparable (HSS) matrix representations to rectangular ones, and construct a rectangular HSS approximation to C in nearly linear complexity with randomized sampling and fast multiplications of C with vectors. A new URV HSS factorization and a URV HSS solution are designed for the least squares solution. We also present two structured normal equation methods. Systematic error and stability analysis for our HSS methods is given, which is also useful for studying other HSS and rank structured methods. We derive the growth factors and the backward error bounds in the HSS factorizations, and show that the stability results are generally much better than those in dense LU factorizations with partial pivoting. Such analysis has not been done before for HSS matrices. The solvers are tested on various classical Toeplitz examples ranging from well-conditioned to highly ill-conditioned ones. Comparisons with some recent fast and superfast solvers are given. Our new methods are generally much faster, and give better (or at least comparable) accuracies, especially for ill-conditioned problems.

KW - HSS error and stability analysis

KW - Randomized sampling

KW - Rectangular HSS matrix

KW - Superfast and stable solvers

KW - Toeplitz least squares

KW - URV factorization

UR - http://www.scopus.com/inward/record.url?scp=84897528667&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84897528667&partnerID=8YFLogxK

U2 - 10.1137/120895755

DO - 10.1137/120895755

M3 - Article

AN - SCOPUS:84897528667

SN - 0895-4798

VL - 35

SP - 44

EP - 72

JO - SIAM Journal on Matrix Analysis and Applications

JF - SIAM Journal on Matrix Analysis and Applications

IS - 1

ER -