(1 + ε)-approximate sparse recovery
Eric Price, David P. Woodruff
FOCS 2011
We study an iterative, locally quadratically convergent algorithm for solving Toeplitz systems of equations from [R. P. Brent, F. G. Gustavson and D. Y. Y. Yun. "Fast solution of Toeplitz systems of equations and computation of Padé approximations", J. Algorithms, 1:259-295, 1980]. We introduce a new iterative algorithm that is locally quadratically convergent when used to solve symmetric positive definite Toeplitz systems. We present a set of numerical experiments on randomly generated symmetric positive definite Toeplitz matrices. In these experiments, our algorithm performed significantly better than the previously proposed algorithm. © 1993 Springer-Verlag.
Eric Price, David P. Woodruff
FOCS 2011
Yvonne Anne Pignolet, Stefan Schmid, et al.
Discrete Mathematics and Theoretical Computer Science
Maurice Hanan, Peter K. Wolff, et al.
DAC 1976
Thomas M. Cover
IEEE Trans. Inf. Theory