Randomized Sketching for Large-Scale Sparse Ridge Regression Problems

Chander Iyer, Christopher D. Carothers, Petros DrineasScalA@SC 2016 · OpenReview

Abstract

We present a fast randomized ridge regression solver for sparse overdetermined matrices in distributed-memory platforms. Our solver is based on the Blendenpik algorithm, but employs sparse random projection schemes to construct a sketch of the input matrix. These sparse random projection sketching schemes, and in particular the use of the Randomized Sparsity-Preserving Transform, enable our algorithm to scale the distributed memory vanilla implementation of Blendenpik and provide up to × 13 speedup over a state-of-the-art parallel Cholesky-like sparse-direct solver.
BibTeX
@inproceedings{iyer2016randomized,
  author = {Chander Iyer and Christopher D. Carothers and Petros Drineas},
  title = {{Randomized Sketching for Large-Scale Sparse Ridge Regression Problems}},
  booktitle = {ScalA@SC},
  year = {2016},
  url = {https://openreview.net/forum?id=zkJ0vxaGh1},
}

Loading related content...

Figure