Showing cs.DSShow all
2 papers · 1 filter
cs.DS2025
Sublinear Time Low-Rank Approximation of Hankel Matrices
Michael Kapralov, Cameron Musco, Kshiteej Sheth
Hankel matrices are an important class of highly-structured matrices, arising across computational mathematics, engineering, and theoretical computer science. It is well-known that…
cs.DS2024
Sublinear Time Low-Rank Approximation of Toeplitz Matrices
Cameron Musco, Kshiteej Sheth
We present a sublinear time algorithm for computing a near optimal low-rank approximation to any positive semidefinite (PSD) Toeplitz matrix , given no…