On sparse representations of linear operators and the approximation of matrix products

Built on

“An identity for the Schur complement of a matrix,”
D. E. Crabtree and E. V. Haynsworth, · 1969
Earlier work this paper cites.
“Matrix multiplication via arithmetic progressions,”
D. Coppersmith and S. Winograd, · 1990
Earlier work this paper cites.
Topics in Matrix Analysis
R. A. Horn and C. R. Johnson, · 1994
Earlier work this paper cites.
“Fast Monte-Carlo algorithms for finding low-rank approximations,”
A. M. Frieze, R. Kannan, and S. Vempala, · 1998
Earlier work this paper cites.
“An algorithmic theory of learning: Robust concepts and random projection,”
R. I. Arriaga and S. Vempala, · 1999
Earlier work this paper cites.

Matrix Analysis
R. A. Horn and C. R. Johnson, · 1999
Cited alongside, same era.
“Using the Nyström method to speed up kernel machines,”
C. K. I. Williams and M. Seeger, · 2001
Cited alongside, same era.
Introduction to Algorithms
T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, · 2001
Cited alongside, same era.
“Spectral grouping using the Nyström method,”
C. Fowlkes, S. Belongie, F. Chung, and J. Malik, · 2004
Cited alongside, same era.
“Adaptive sampling and fast low-rank matrix approximation,”
A. Deshpande and S. Vempala, · 2006
Cited alongside, same era.

“Improved approximation algorithms for large matrices via random projection,”
T. Sarlos, · 2006
Later among the works it cites.
“Fast Monte Carlo algorithms for matrices I: Approximating matrix multiplication,”
P. Drineas, R. Kannan, and M. W. Mahoney, · 2006
Later among the works it cites.
“Spectral methods in machine learning: New strategies for very large datasets,”
M.-A. Belabbas and P. J. Wolfe, · 2007
Closest in time.
“Fast low-rank approximation for covariance matrices,”
M.-A. Belabbas and P. J. Wolfe, · 2007
Closest in time.