Improved Approximation Algorithms for Large Matrices via Random Projections

By Tamás Sarlós. IEEE Annual Symposium on Foundations of Computer Science, 2006

890 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computational Theory and Mathematics

View Paper: https://www.semanticscholar.org/paper/238a0814109dc166f1a1c0c3b5c33bc59250ae3f

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 Theory and Mathematics

Citations in the corpus

Tighter Low-rank Approximation via Sampling the Leveraged Element (2014, methodology): “[14, 20, 9, 6] have given low rank approximation algorithms with relative error guarantees in Frobenius norm.”
Differentially-Private Multi-Party Sketching for Large-Scale Statistics (2020, methodology): “[58, 3, 20]), including providing another method for approximating the L2 norm of a frequency vector of a stream of data items.”
SenticNet 4: A Semantic Resource for Sentiment Analysis Based on Conceptual Primitives (2016, background): “Structured random projections for making matrix multiplication much faster was introduced in (Sarlos, 2006).”
SenticNet 5: Discovering Conceptual Primitives for Sentiment Analysis by Means of Context Embeddings (2018, background): “Structured random projections for making matrix multiplication much faster was introduced in (Sarlos 2006).”
Performance of Johnson-Lindenstrauss transform for k-means and k-medians clustering (2018, background): “The literature on data-dependent dimension reduction for k -means is ample [DFK + 99, Sar06, BDM09, BZD10, FSS13, BMI13, BZMD15, CEM + 15] and we refer the reader to [CEM + 15] for a comprehensive overview.”
Faster least squares approximation (2007, methodology): “Preliminary versions of parts of this paper have appeared as conference proceedings in the 17th ACM-SIAM Symposium on Discrete Algorithms [12] and in the 47th IEEE Symposium on Foundations of Computer Science [23]; and the original Technical Report version of this journal paper has appeared on the a”
A unified framework for approximating and clustering data (2011, methodology): “Sarlos [38] provides a streaming algorithm that requires two passes over the data and uses space O ( n )( k/ε + k log k ) 2 .”
Handbook of Big Data (2016, methodology): “Combined pan/zoom based on focus rectangles is described in Section 6.4.3.”
Sketchy Decisions: Convex Low-Rank Matrix Optimization with Optimal Storage (2017, background): “This idea dates to the paper of Sarlós [33]; see also [26, 30, 38].”
Learning Two Layer Rectified Neural Networks in Polynomial Time (2018, background): “Proposition 67 (Gaussian Subspace Embedding Sarlos (2006)) Fix any rank k-matrix matrix U ∈ Rm×k, and let S ∈ Rc1k/ 2×m be a random matrix where every entry is generated i.”
Sketching as a Tool for Numerical Linear Algebra (2014, methodology): “The starting point of this survey is a beautiful work by Tamás Sarlós [105] which observed that one could use sketching techniques to improve upon the above time complexities, if one is willing to settle for a randomized approximation algorithm.”
New and Improved Johnson-Lindenstrauss Embeddings via the Restricted Isometry Property (2010, positive): “As a consequence, the JL Lemma has become a valuable tool for dimensionality reduction in a myriad of applications ranging from computer science [26], numerical linear algebra [36, 23, 18], manifold learning [6], and compressed sensing [7], [40], [10].”
Improved Distributed Principal Component Analysis (2014, methodology): “We change Algorithm disPCA to instead have each server first sample an oblivious subspace embedding (OSE) [22, 5, 19, 17] matrix Hi, and instead run the algorithm on the point set defined by the rows of HiPi.”
Online sketching hashing (2015, methodology): “An extensive body of algorithms exist, including CUR decomposition [5], random projection [31, 22], column sampling method [7, 1], and Nyström method [6].”
Randomized Extended Kaczmarz for Solving Least Squares (2012, methodology): “…generic two step procedure: ﬁrst randomly (and efﬁciently) project the linear system into sufﬁciently many dimensions, and second return the solution of the down-sampled linear system as an approximation to the original optimal solution [DMM06, Sar06, CW09, NDT09, MZ11, DMMS11], see also [CW12].”
Simple and deterministic matrix sketching (2012, background): “The second approach is to randomly combine matrix rows [25][28][27][21].”