Pass efficient algorithms for approximating large matrices

No abstract is available for this paper.

• Publication year

  2003

• Venue

  ACM-SIAM Symposium on Discrete Algorithms

• Publication date

  2003-01-12

• Fields of study

  Mathematics, Computer Science

• Identifiers

  No identifiers available.

• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• FAST MONTE CARLO ALGORITHMS FOR MATRICES II: COMPUTING A LOW-RANK APPROXIMATION TO A MATRIX∗

  2004cited by this paper
• FAST MONTE CARLO ALGORITHMS FOR MATRICES III: COMPUTING A COMPRESSED APPROXIMATE MATRIX DECOMPOSITION∗

  2004cited by this paper
• Sampling lower bounds via information theory

  2003cited by this paper
• Near-optimal sparse fourier representations via sampling

  2002cited by this paper
• Finding frequent items in data streams

  2002cited by this paper
• Competitive recommendation systems

  2002cited by this paper
• Fast, small-space algorithms for approximate histogram maintenance

  2002cited by this paper
• Space lower bounds for distance approximation in the data stream model

  2002cited by this paper
• Approximate counting of inversions in a data stream

  2002cited by this paper
• Approximate clustering via core-sets

  2002cited by this paper
• Spectral partitioning of random graphs

  2001cited by this paper
• Fast computation of low rank matrix approximations

  2001cited by this paper
• Fast Monte-Carlo algorithms for approximate matrix multiplication

  2001influential reference
• Spectral analysis of data

  2001cited by this paper
• Data-streams and histograms

  2001cited by this paper
• Approximating multi-dimensional aggregate range queries over real attributes

  2000cited by this paper
• Stable distributions, pseudorandom generators, embeddings and data stream computation

  2000cited by this paper
• Similarity Search in High Dimensions via Hashing

  1999cited by this paper
• Clustering in large graphs and matrices

  1999cited by this paper
• Computing on data streams

  1999cited by this paper
• Fast Monte-Carlo algorithms for finding low-rank approximations

  1998cited by this paper
• Random projection: a new approach to VLSI layout

  1998cited by this paper
• Dimensionality reduction for similarity searching in dynamic databases

  1998cited by this paper
• Two algorithms for nearest-neighbor search in high dimensions

  1997cited by this paper
• The space complexity of approximating the frequency moments

  1996cited by this paper
• Property testing and its connection to learning and approximation

  1996cited by this paper
• MAX-CUT has a randomized approximation scheme in dense graphs

  1996cited by this paper
• The regularity lemma and approximation schemes for dense problems

  1996cited by this paper
• Polynomial time approximation schemes for dense instances of NP-hard problems

  1995cited by this paper
• Probabilistic counting

  1983cited by this paper
• The eigenvalues of random symmetric matrices

  1981cited by this paper
• Selection and sorting with limited storage

  1978influential reference

• Efficient and Accurate PageRank Approximation on Large Graphs

  2024cites this paper
• 3-D Random Noise Attenuation Using Stable CUR Matrix Decomposition

  2024cites this paper
• Least-Mean-Squares Coresets for Infinite Streams

  2023cites this paper
• Streaming and Distributed Algorithms for Robust Column Subset Selection

  2021cites this paper
• Filter Sketch for Network Pruning

  2020cites this paper
• Multiplicative Rank-1 Approximation using Length-Squared Sampling

  2019cites this paper
• Fast randomized matrix and tensor interpolative decomposition using CountSketch

  2019cites this paper
• Residual Based Sampling for Online Low Rank Approximation

  2019cites this paper
• Compressive Sensing of Internet Traffic Matrices using CUR Decomposition

  2018cites this paper
• Sliding window order statistics in sublinear space

  2018cites this paper
• Interpretable Structural Analysis of Traffic Matrix

  2017cites this paper
• Superfast CUR Approximation of Low Rank Matrices ∗

  2017cites this paper
• Matrix resconstruction: Skeleton decomposition versus singular value decomposition

  2017cites this paper
• Matrix Reconstruction: Skeleton Decomposition versus Singular Value Decomposition

  2017cites this paper
• Network-wide volume anomaly detection using alternate matrix decomposition techniques

  2017cites this paper
• Improving Utility Mining Based on Dimensionality Reduction

  2017cites this paper
• A Fast Frequent Directions Algorithm for Low Rank Approximation

  2017cites this paper
• Simultaneous Localization and Appearance Estimation with a Consumer RGB-D Camera

  2016cites this paper
• Superfast Low-Rank Approximation and Least Squares Regression

  2016cites this paper
• Scalable Semi-Supervised Query Classification Using Matrix Sketching

  2016cites this paper
• Matrix Sketching Over Sliding Windows

  2016cites this paper
• Efficient Frequent Directions Algorithm for Sparse Matrices

  2016cites this paper
• A machine learning approach to the unsupervised segmentation of mitochondria in subcellular electron microscopy data

  2016cites this paper
• Online Principal Components Analysis

  2015cites this paper
• Adaptive strategy for restricted-sampling noisy low-rank matrix completion

  2015cites this paper
• Online sketching hashing

  2015cites this paper
• Frequent Directions: Simple and Deterministic Matrix Sketching

  2015influential citation
• Sketching Hashing

  2015cites this paper
• Proposal High-Dimensional Analysis of Unsupervised Learning Problems

  2015cites this paper
• Online {PCA} with Spectral Bounds

  2015cites this paper
• Accuracy-Preserving and Scalable Column-Based Low-Rank Matrix Approximation

  2015cites this paper
• Optimal Sparse Linear Auto-Encoders and Sparse PCA

  2015cites this paper
• Improved Practical Matrix Sketching with Guarantees

  2014cites this paper
• Non-asymptotic, Local Theory of Random Matrices

  2014cites this paper
• Sketching as a Tool for Numerical Linear Algebra

  2014cites this paper
• Optimal CUR matrix decompositions

  2014cites this paper
• Fast Approximate Matrix Multiplication by Solving Linear Systems

  2014cites this paper
• Tighter Low-rank Approximation via Sampling the Leveraged Element

  2014cites this paper
• Algorithms for Data Mining by Grant

  2014cites this paper
• Online Principal Component Analysis

  2014cites this paper
• Subspace learning from extremely compressed measurements

  2014cites this paper
• Continuous Matrix Approximation on Distributed Data

  2014cites this paper
• Improving CUR matrix decomposition and the Nyström approximation via adaptive sampling

  2013cites this paper
• Learning from Subsampled Data: Active and Randomized Strategies

  2013cites this paper
• Matrix Entry-wise Sampling : Simple is Best [ Extended Abstract ]

  2013cites this paper
• Randomized interpolative decomposition of separated representations

  2013cites this paper
• Relative Errors for Deterministic Low-Rank Matrix Approximations

  2013cites this paper
• Approximation theory of matrices based on its low ranking and stochastic computation

  2012cites this paper
• A Scalable CUR Matrix Decomposition Algorithm: Lower Time Complexity and Tighter Bound

  2012influential citation
• Active spectral clustering via iterative uncertainty reduction

  2012cites this paper
• Simple and deterministic matrix sketching

  2012cites this paper
• Gossip PCA

  2011cites this paper
• Topics in Matrix Sampling Algorithms

  2011cites this paper
• Sparsified Randomization algorithms for low rank approximations and applications to integral equations and inhomogeneous random field simulation

  2011cites this paper
• Spectral counting of triangles via element-wise sparsification and triangle-based link recommendation

  2011cites this paper
• Cluster Indicator Decomposition for Efficient Matrix Factorization

  2011cites this paper
• Stochastic Algorithms in Linear Algebra - beyond the Markov Chains and von Neumann - Ulam Scheme

  2010cites this paper
• Low rank matrix-valued chernoff bounds and approximate matrix multiplication

  2010cites this paper
• Spectral methods for matrices and tensors

  2010cites this paper
• Spectral sparsification and restricted invertibility

  2010cites this paper
• A Sharp PageRank Algorithm with Applications to Edge Ranking and Graph Sparsification

  2010cites this paper
• Spectral Algorithms (draft)

  2010cites this paper
• A Survey on Streaming Algorithms for Massive Graphs

  2010cites this paper
• Spectral Algorithms

  2009cites this paper
• Spectral Counting of Triangles in Power-Law Networks via Element-Wise Sparsification

  2009cites this paper
• Euclidean Embeddings that Preserve Volumes

  2009cites this paper
• Pass-Efficient Algorithms for Learning Mixtures of Uniform Distributions

  2009cites this paper
• Solving Geometric Problems in Space-Conscious Models

  2009cites this paper
• Graph sparsification by effective resistances

  2008cites this paper
• Sampling subproblems of heterogeneous Max‐Cut problems and approximation algorithms

  2008cites this paper
• Clustered subset selection and its applications on it service metrics

  2008cites this paper
• Simple permutations mix even better

  2008cites this paper
• Computer Science Research Institute 2005 annual report of activities.

  2008cites this paper
• D S ] 1 4 M ar 2 00 8 Graph Sparsification by Effective Resistances ∗

  2008cites this paper
• Fast computation of low-rank matrix approximations

  2007cites this paper
• A randomized algorithm for a tensor-based generalization of the singular value decomposition

  2007influential citation
• Relative-Error CUR Matrix Decompositions

  2007cites this paper
• Lower Bounds for Quantile Estimation in Random-Order and Multi-pass Streaming

  2007cites this paper
• A Fast Random Sampling Algorithm for Sparsifying Matrices

  2006influential citation
• The space complexity of pass-efficient algorithms for clustering

  2006cites this paper
• Algorithms for data mining

  2006cites this paper
• Fast Monte Carlo Algorithms for Matrices III: Computing a Compressed Approximate Matrix Decomposition

  2006influential citation
• Distance Matrix Reconstruction from Incomplete Distance Information for Sensor Network Localization

  2006cites this paper
• Fast Monte Carlo Algorithms for Matrices II: Computing a Low-Rank Approximation to a Matrix

  2006influential citation
• Fast Monte Carlo Algorithms for Matrices I: Approximating Matrix Multiplication

  2006influential citation
• Matrix approximation and projective clustering via volume sampling

  2006cites this paper
• Adaptive Sampling and Fast Low-Rank Matrix Approximation

  2006cites this paper
• Massive data streams in graph theory and computational geometry

  2005influential citation
• Graph distances in the streaming model: the value of space

  2005cites this paper
• Matrix Approximation and Projective Clustering via Iterative Sampling

  2005cites this paper
• On graph problems in a semi-streaming model

  2005cites this paper
• Sampling from large matrices: An approach through geometric functional analysis

  2005influential citation
• Indexing hierarchical structures using graph spectra

  2005cites this paper
• Multi-Pass Geometric Algorithms

  2005cites this paper
• Approximating a Gram Matrix for Improved Kernel-Based Learning (Extended Abstract)

  2005cites this paper
• Sampling Sub-problems of Heterogeneous Max-cut Problems and Approximation Algorithms

  2005cites this paper
• On the Nyström Method for Approximating a Gram Matrix for Improved Kernel-Based Learning

  2005cites this paper
• Finding Graph Matchings in Data Streams

  2005cites this paper
• Data streams: algorithms and applications

  2005cites this paper
• FAST MONTE CARLO ALGORITHMS FOR MATRICES II: COMPUTING A LOW-RANK APPROXIMATION TO A MATRIX∗

  2004influential citation