Fetching the paper…

Reading the bibliography…

2023

Structure-Aware Analyses and Algorithms for Interpolative Decompositions

Armstrong, Robin, Buzali, Alex, Damle, Anil

Original
PDF
Post on X

Understand

Low-rank approximation is a task of critical importance in modern science, engineering, and statistics.

Many low-rank approximation algorithms, such as the randomized singular value decomposition (RSVD), project their input matrix into a subspace approximating the span of its leading singular vectors.
Other algorithms compress their input into a small subset of representative rows or columns, leading to a so-called interpolative decomposition.
This paper investigates how the accuracy of interpolative decompositions is affected by the structural properties of the input matrix being operated on, including how these properties affect the performance comparison between interpolative decompositions and RSVD.

Structure-Aware Analyses and Algorithms for Interpolative Decompositions · Around

Built on

C. Eckart and G. Young
1936
Earlier work this paper cites.
P. Businger and G. H. Golub
1965
Earlier work this paper cites.
C. Davis and W. M. Kahan
1970
Earlier work this paper cites.
G. W. Stewart
1973
Earlier work this paper cites.
G. H. Golub, V. Klema, and G. Stewart
1976
Earlier work this paper cites.
P. Å. Wedin
1983
Earlier work this paper cites.
Y. Hong and C.-T. Pan
1992
Earlier work this paper cites.
S. Chandrasekaran and I. C. F. Ipsen
1994
Earlier work this paper cites.
M. Gu and S. C. Eisenstat
1996
Earlier work this paper cites.
L. N. Trefethen and D. Bau, III
1997
Earlier work this paper cites.
I. C. F. Ipsen
1998
Earlier work this paper cites.
A. Frieze, R. Kannan, and S. Vempala
2004
Earlier work this paper cites.

Similar

H. Cheng, Z. Gimbutas, P. G. Martinsson, and V. Rokhlin
2005
Cited alongside, same era.
L. Qiu, Y. Zhang, and C.-K. Li
2005
Cited alongside, same era.
A. Deshpande, L. Rademacher, S. Vempala, and G. Wang
2006
Cited alongside, same era.
E. Liberty, F. Woolfe, P.-G. Martinsson, V. Rokhlin, and M. Tygert
2007
Cited alongside, same era.
F. Woolfe, E. Liberty, V. Rokhlin, and M. Tygert
2007
Cited alongside, same era.
E. J. Candes and B. Recht
2008
Cited alongside, same era.
P. Drineas, M. W. Mahoney, and S. Muthukrishnan
2008
Cited alongside, same era.

Then

N. Halko, P. G. Martinsson, and J. A. Tropp
2011
Later among the works it cites.
M. Hardt and A. Roth
2012
Later among the works it cites.
G. H. Golub and C. F. V. Loan
2013
Later among the works it cites.
D. C. Sorensen and M. Embree
2016
Later among the works it cites.
J. Cape, M. Tang, and C. Priebe
2017
Later among the works it cites.
A. K. Saibaba
2019
Later among the works it cites.
A. Damle and Y. Sun
2020
Later among the works it cites.
M. Dereziński, R. Khanna, and M. W. Mahoney

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

E. J. Candès and B. Recht

2009

Cited alongside, same era.

M. W. Mahoney and P. Drineas

2009

Cited alongside, same era.

A. Çivril and M. Magdon-Ismail

2009

Cited alongside, same era.

A. Deshpande and L. Rademacher

2010

Cited alongside, same era.

V. Rokhlin, A. Szlam, and M. Tygert

2010

Cited alongside, same era.

2020

Later among the works it cites.

Y. Dong, P.-G. Martinsson, and Y. Nakatsukasa

2022

Later among the works it cites.

Y. Zhang and M. Tang

2022

Later among the works it cites.

J. A. Tropp and R. J. Webber

2023

Closest in time.