Sharper bounds for regularized data fitting
Haim Avron, Kenneth L. Clarkson, et al.
APPROX/RANDOM 2017
We present a fast randomized least-squares solver for distributed-memory platforms. Our solver is based on the Blendenpik algorithm, but employs multiple random projection schemes to construct a sketch of the input matrix. These random projection sketching schemes, and in particular the use of the randomized Discrete Cosine Transform, enable our algorithm to scale the distributed memory vanilla implementation of Blendenpik to terabyte-sized matrices and provide up to ×7.5 speedup over a state-of-the-art scalable least-squares solver based on the classic QR algorithm. Experimental evaluations on terabyte scale matrices demonstrate excellent speedups on up to 16,384 cores on a Blue Gene/Q supercomputer.
Haim Avron, Kenneth L. Clarkson, et al.
APPROX/RANDOM 2017
Sudhir B. Kylasa, Georgios Kollias, et al.
ASONAM 2015
Haim Avron, Christos Boutsidis, et al.
SIAM Journal on Scientific Computing
Po-Sen Huang, Haim Avron, et al.
ICASSP 2014