Simple and deterministic matrix sketching

By Edo Liberty. Knowledge Discovery and Data Mining, 2012

326 citations recorded by the source corpus.

A sketch of a matrix A is another matrix B which is significantly smaller than A but still approximates it well. Finding such sketches efficiently is an important building block in modern algorithms for approximating, for example, the PCA of massive matrices. This task is made more challenging in the streaming model, where each row of the input matrix can only be processed once and storage is severely limited. In this paper we adapt a well known streaming algorithm for approximating item frequencies to the matrix sketching setting. The algorithm receives n rows of a large matrix A ε ℜ n x m one after the other in a streaming fashion. It maintains a sketch B ℜ l x m containing only l << n rows but still guarantees that ATA BTB. More accurately, ∀x || x,||=1 0≤||Ax||2 - ||Bx||2 ≤ 2||A||_f 2 l Or BTB prec ATA and ||ATA - BTB|| ≤ 2 ||A||f2 l. This gives a streaming algorithm whose error decays proportional to 1/l using O(ml) space. For comparison, random-projection, hashing or sampling based algorithms produce convergence bounds proportional to 1/√l. Sketch updates per row in A require amortized O(ml) operations and the algorithm is perfectly parallelizable. Our experiments corroborate the algorithm's scalability and improved convergence rate. The presented algorithm also stands out in that it is deterministic, simple to implement and elementary to prove.

Subfields: Artificial Intelligence, Computational Mathematics, Computational Mechanics

View Paper: https://www.semanticscholar.org/paper/b77a727db76d7196d29815ea7ddd31e554cc033c

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mathematics

In Computational Mechanics

Citations in the corpus

Dimensionality Reduction for k-Means Clustering and Low Rank Approximation (2014, background): “Building on [35], [22] gives a deterministic algorithm for this problem using O(dk/ ) words of space in the row-wise streaming model, where the matrix A is presented to a server one row at a time.”
One-Pass AUC Optimization (2013, unknown): “, the frequent direction (Liberty, 2013) and the sparse approach are proposed to approximate the covariance matrices for dense and sparse datasets, respectively.”
Online sketching hashing (2015, methodology): “In this way, the storage of the sketch Q will be much easier, and the computations can be performed much faster than with the original P [18, 8, 21].”
Continual Learning via Online Leverage Score Sampling (2019, background): “Different from the leverage score sampling sketching technique, a deterministic bound is guaranteed for the accuracy of the sketch: ∥∥∥ATA− Â Â∥∥∥2 2 ≤‖A−Ak‖2F /(`− k) with l > k and Ak denotes best rank-k approximation of A [18, 10].”
Schatten Norms in Matrix Streams: Hello Sparsity, Goodbye Dimension (2019, background): “For a thorough study of external memory algorithms, including motivation for the row-order model and for multiple passes, see (Gib-bons and Matias, 1999; Vitter, 2001; Liberty, 2013).”
Scaling Up Quasi-newton Algorithms: Communication Efficient Distributed SR1 (2019, methodology): “In our communication-efficient method, we propose that the matrix is approximated via sketching [34, 57], using quantities that are already computed, i.”
Towards Detecting Anomalous User Behavior in Online Social Networks (2014, methodology): “Furthermore, efficient algorithms for PCA based on approximation andmatrix sketching have been designedwhich have close to O(mn) complexity [46, 57].”
Streaming PCA: Matching Matrix Bernstein and Near-Optimal Finite Sample Guarantees for Oja's Algorithm (2016, methodology): “Most of the existing methods here first compute a sketch of the matrix nd use that to compute an estimate of the top eigenvector [18, 19, 20, 21, 22, 23].”
Low rank approximation with entrywise l1-norm error (2017, background): “, [23, 45, 54, 57, 61, 66, 89]), though almost exclusively for the Frobenius norm.”
Tighter Low-rank Approximation via Sampling the Leveraged Element (2014, background): “Algorithms in [10, 17, 12, 16] achieve O( ) communication complexity with relative error guarantees in Frobenius norm, under this model.”
Feature Selection (2016, methodology): “e bottleneck of Eq. (114) is that the singular value decomposition of X(t) is computationally expensive, especially when nt is very large. Therefore, FSDS utilizes the matrix sketching strategy from (Liberty, 2013) to maintain a low-rank approximation of X(t). Let B(t) ∈ Rℓ×d denote the matrix sketc”
Stat260/cs294: Randomized Algorithms for Matrices and Data (background): “• Dasgupta and Gupta, " An elementary proof of a theorem of Johnson and Lindenstrauss " • Appendix of: Drineas, Mahoney, Muthukrishnan, and Sarlos, " Faster Least Squares Approximation " • Achlioptas, " Database-friendly random projections: Johnson-Lindenstrauss with binary coins " 5.1 Spectral…”
Randomized Matrix Decompositions using R (2016, background): “Several probabilistic strategies have been proposed to find a ‘good’ smaller matrix, and we refer the reader to the surveys by Mahoney (2011), Liberty (2013), and Halko, Martinsson, and Tropp (2011b) for an in-depth discussion, and theoretical results.”
Optimal principal component analysis in distributed and streaming models (2015, methodology): “In the column-partition distributed model, there are many existing protocols using O ( skmε − 1 ) words of communication [24, 6, 33, 26, 30, 9], and the protocols work in very different ways: that of [24, 6] is based on coresets, while that of [33, 26] is based on adapting a streaming algorithm to…”