Low-Rank Approximation and Regression in Input Sparsity Time

DOI10.1145/3019134zbMATH Open1426.65057arXiv1207.6365OpenAlexW2580753685MaRDI QIDQ3177880FDOQ3177880

Authors: Kenneth L. Clarkson, David P. Woodruff 

Publication date: 2 August 2018

Published in: Journal of the ACM, Proceedings of the forty-eighth annual ACM symposium on Theory of Computing (Search for Journal in Brave)

Abstract: We design a new distribution over $poly(rep{s}^{-1})imesn$ matrices $S$ so that for any fixed $nimesd$ matrix $A$ of rank $r$, with probability at least 9/10, $orm{SAx}_2=(1pmeps)orm{Ax}_2$ simultaneously for all $xinmathbb{R}^d$. Such a matrix $S$ is called a emph{subspace embedding}. Furthermore, $SA$ can be computed in $nz(A)+poly(dep{s}^{-1})$ time, where $nz(A)$ is the number of non-zero entries of $A$. This improves over all previous subspace embeddings, which required at least $Omega(ndlogd)$ time to achieve this property. We call our matrices $S$ emph{sparse embedding matrices}. Using our sparse embedding matrices, we obtain the fastest known algorithms for $(1+eps)$-approximation for overconstrained least-squares regression, low-rank approximation, approximating all leverage scores, and $el{l}_p$-regression. The leading order term in the time complexity of our algorithms is $O(nz(A))$ or $O(nz(A)logn)$. We optimize the low-order $poly(d/eps)$ terms in our running times (or for rank-$k$ approximation, the $n*poly(k/eps)$ term), and show various tradeoffs. For instance, we also use our methods to design new preconditioners that improve the dependence on $eps$ in least squares regression to $log1/eps$. Finally, we provide preliminary experimental results which suggest that our algorithms are competitive in practice.

Full work available at URL: https://arxiv.org/abs/1207.6365

Recommendations

• Low-Rank Approximation and Regression in Input Sparsity Time
• Input sparsity time low-rank approximation via ridge leverage score sampling
• Low-Rank PSD Approximation in Input-Sparsity Time
• Reduced rank linear regression and weighted low rank approximations
• Low-distortion subspace embeddings in input-sparsity time and applications to robust linear regression
• Sparse principal component analysis via regularized low rank matrix approximation
• scientific article; zbMATH DE number 7506682
• Optimal regularized low rank inverse approximation
• Approximate sparse linear regression
• Sparse regression: scalable algorithms and empirical performance

zbMATH Keywords

regressionrandomized algorithmsketchinglow-rank approximationapproximationmatricesrandomizedleverage scores

Mathematics Subject Classification ID

Linear regression; mixed models (62J05) Computational methods for sparse matrices (65F50) Random matrices (algebraic aspects) (15B52) Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20)

Cited In (only showing first 100 items - show all)

• Estimating Leverage Scores via Rank Revealing Methods and Randomization
• Fast and accurate randomized algorithms for linear systems and eigenvalue problems
• Title not available (Why is that?)
• Hessian averaging in stochastic Newton methods achieves superlinear convergence
• Title not available (Why is that?)
• Robust and efficient subsampling algorithms for massive data logistic regression
• Structured Random Sketching for PDE Inverse Problems
• Fast randomized numerical rank estimation for numerically low-rank matrices
• Optimal subsampling for large‐sample quantile regression with massive data
• On unifying randomized methods for inverse problems
• Optimal Poisson subsampling for softmax regression
• A fast randomized algorithm for computing an approximate null space
• One-pass additive-error subset selection for \(\ell_p\) subspace approximation and \((k, p)\)-clustering
• \texttt{pylspack}: parallel algorithms and data structures for sketching, column subset selection, regression, and leverage scores
• Improving compressed matrix multiplication using control variate method
• Simpler is better: a comparative study of randomized pivoting algorithms for CUR and interpolative decompositions
• Title not available (Why is that?)
• Fast and Accurate Gaussian Kernel Ridge Regression Using Matrix Decompositions for Preconditioning
• Optimal subsampling algorithms for composite quantile regression in massive data
• Title not available (Why is that?)
• Tensor-Structured Sketching for Constrained Least Squares
• A stochastic perturbation analysis of the QR decomposition and its applications
• On randomized sketching algorithms and the Tracy-Widom law
• Sharp Analysis of Sketch-and-Project Methods via a Connection to Randomized Singular Value Decomposition
• Efficient bounds and estimates for canonical angles in randomized subspace approximations
• Principled interpolation of Green's functions learned from data
• Title not available (Why is that?)
• Sharper Bounds for Regularized Data Fitting
• SketchySGD: reliable stochastic optimization via randomized curvature estimates
• Title not available (Why is that?)
• RA-HOOI: rank-adaptive higher-order orthogonal iteration for the fixed-accuracy low multilinear-rank approximation of tensors
• Randomized tensor wheel decomposition
• Low-Rank PSD Approximation in Input-Sparsity Time
• Practical Sketching Algorithms for Low-Rank Matrix Approximation
• Sublinear update time randomized algorithms for dynamic graph regression
• Title not available (Why is that?)
• An homotopy method for l _p regression provably beyond self-concordance and in input-sparsity time
• An efficient algorithm for computing the approximate t-URV and its applications
• Perturbations of the \textsc{Tcur} decomposition for tensor valued data in the Tucker format
• Two-stage convex relaxation approach to low-rank and sparsity regularized least squares loss
• Title not available (Why is that?)
• Distributed penalized modal regression for massive data
• Small-deviation inequalities for sums of random matrices
• On Approximating Matrix Norms in Data Streams
• Matrix sketching for supervised classification with imbalanced classes
• Randomized Local Model Order Reduction
• Sketching for Principal Component Regression
• Low Rank Approximation of a Sparse Matrix Based on LU Factorization with Column and Row Tournament Pivoting
• An improvement of the parameterized frequent directions algorithm
• Structural Convergence Results for Approximation of Dominant Subspaces from Block Krylov Spaces
• Turning Big Data Into Tiny Data: Constant-Size Coresets for $k$-Means, PCA, and Projective Clustering
• Sampling algorithms for \(l_2\) regression and applications
• Randomized numerical linear algebra: Foundations and algorithms
• Title not available (Why is that?)
• Randomized algorithms for the computation of multilinear rank-\((\mu_1,\mu_2,\mu_3)\) approximations
• Randomized LU decomposition using sparse projections
• Randomized Low-Rank Approximation for Symmetric Indefinite Matrices
• Title not available (Why is that?)
• Spectral estimation from simulations via sketching
• Fast randomized matrix and tensor interpolative decomposition using countsketch
• Sparser Johnson-Lindenstrauss Transforms
• Guarantees for the Kronecker fast Johnson-Lindenstrauss transform using a coherence and sampling argument
• Fast Quantum Algorithms for Least Squares Regression and Statistic Leverage Scores
• Sparse random matrices have simple spectrum
• Single Pass Spectral Sparsification in Dynamic Streams
• Frequent directions: simple and deterministic matrix sketching
• Optimal CUR Matrix Decompositions
• Title not available (Why is that?)
• RidgeSketch: A Fast Sketching Based Solver for Large Scale Ridge Regression
• Low-Rank Approximation and Regression in Input Sparsity Time
• Randomized block Krylov subspace methods for trace and log-determinant estimators
• Streaming Low-Rank Matrix Approximation with an Application to Scientific Simulation
• An Implicit Representation and Iterative Solution of Randomly Sketched Linear Systems
• Title not available (Why is that?)
• An Improved Analysis and Unified Perspective on Deterministic and Randomized Low-Rank Matrix Approximation
• Title not available (Why is that?)
• Pass-Efficient Randomized Algorithms for Low-Rank Matrix Approximation Using Any Number of Views
• Randomized Spectral Clustering in Large-Scale Stochastic Block Models
• An efficient randomized algorithm for computing the approximate Tucker decomposition
• ISLET: Fast and Optimal Low-Rank Tensor Regression via Importance Sketching
• Low-distortion subspace embeddings in input-sparsity time and applications to robust linear regression
• Toward a unified theory of sparse dimensionality reduction in Euclidean space
• Low-complexity \(l_0\)-norm penalized shrinkage linear and widely linear affine projection algorithms
• Randomized LU decomposition
• Title not available (Why is that?)
• Max-Plus Algebraic Statistical Leverage Scores
• Title not available (Why is that?)
• Random projections for Bayesian regression
• Tail bounds for gaps between eigenvalues of sparse random matrices
• Fast quantum algorithms for least squares regression and statistic leverage scores
• Title not available (Why is that?)
• Optimal Subsampling for Large Sample Logistic Regression
• Adaptive iterative Hessian sketch via \(A\)-optimal subsampling
• Structural conditions for projection-cost preservation via randomized matrix multiplication
• Title not available (Why is that?)
• Title not available (Why is that?)
• Randomized algorithms in numerical linear algebra
• Optimal Bounds for Johnson-Lindenstrauss Transformations
• A count sketch maximal weighted residual Kaczmarz method for solving highly overdetermined linear systems
• Generalized linear models for massive data via doubly-sketching

This page was built for publication: Low-Rank Approximation and Regression in Input Sparsity Time

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