Sparse graph based sketching for fast numerical linear algebra

arXiv2102.05758MaRDI QIDQ6360347FDOQ6360347

Authors: Dong Hu, Shashanka Ubaru, Alex Gittens, Kenneth L. Clarkson, Lior Horesh, Vassilis Kalantzis 

Publication date: 10 February 2021

Abstract: In recent years, a variety of randomized constructions of sketching matrices have been devised, that have been used in fast algorithms for numerical linear algebra problems, such as least squares regression, low-rank approximation, and the approximation of leverage scores. A key property of sketching matrices is that of subspace embedding. In this paper, we study sketching matrices that are obtained from bipartite graphs that are sparse, i.e., have left degree~s that is small. In particular, we explore two popular classes of sparse graphs, namely, expander graphs and magical graphs. For a given subspace $mathcalUsubseteqmathbb{R}^n$ of dimension $k$, we show that the magical graph with left degree $s=2$ yields a $(1pmepsilon)$ ${ell}_2$-subspace embedding for $mathcalU$, if the number of right vertices (the sketch size) $m=mathcalO(k^2/epsilo{n}^2)$. The expander graph with $s=mathcalO(logk/epsilon)$ yields a subspace embedding for $m=mathcalO(klogk/epsilo{n}^2)$. We also discuss the construction of sparse sketching matrices with reduced randomness using expanders based on error-correcting codes. Empirical results on various synthetic and real datasets show that these sparse graph sketching matrices work very well in practice.

This page was built for publication: Sparse graph based sketching for fast numerical linear algebra

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6360347)