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\ast 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)

• Low-Rank PSD Approximation in Input-Sparsity Time
• Pass-efficient randomized algorithms for low-rank matrix approximation using any number of views
• Sublinear update time randomized algorithms for dynamic graph regression
• Title not available (Why is that?)
• Sparser Johnson-Lindenstrauss transforms
• 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
• Distributed penalized modal regression for massive data
• Small-deviation inequalities for sums of random matrices
• Matrix sketching for supervised classification with imbalanced classes
• \(\ell_p\) row sampling by Lewis weights
• Single pass spectral sparsification in dynamic streams
• Low Rank Approximation of a Sparse Matrix Based on LU Factorization with Column and Row Tournament Pivoting
• Regression-aware decompositions
• 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
• A bootstrap method for error estimation in randomized matrix multiplication
• Sketched ridge regression: optimization perspective, statistical perspective, and model averaging
• Randomized algorithms for the computation of multilinear rank-\((\mu_1,\mu_2,\mu_3)\) approximations
• Randomized LU decomposition using sparse projections
• Scalable kernel \(k\)-means clustering with Nyström approximation: relative-error bounds
• Fast regression with an \(\ell_{\infty}\) guarantee
• Optimal subsampling for large sample logistic regression
• More efficient estimation for logistic regression with optimal subsamples
• Randomized Low-Rank Approximation for Symmetric Indefinite Matrices
• Spectral estimation from simulations via sketching
• Fast randomized matrix and tensor interpolative decomposition using countsketch
• Guarantees for the Kronecker fast Johnson-Lindenstrauss transform using a coherence and sampling argument
• Sparse random matrices have simple spectrum
• Frequent directions: simple and deterministic matrix sketching
• On approximating matrix norms in data streams
• Robust frequent directions with application in online learning
• Sketching for principal component regression
• Optimal bounds for Johnson-Lindenstrauss transformations
• The fast Cauchy transform and faster robust linear regression
• Optimal CUR matrix decompositions
• Practical sketching algorithms for low-rank matrix approximation
• 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
• An Implicit Representation and Iterative Solution of Randomly Sketched Linear Systems
• Title not available (Why is that?)
• Input sparsity time low-rank approximation via ridge leverage score sampling
• Robust PCA by manifold optimization
• An Improved Analysis and Unified Perspective on Deterministic and Randomized Low-Rank Matrix Approximation
• Randomized Spectral Clustering in Large-Scale Stochastic Block Models
• Reverse iterative volume sampling for linear regression
• 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
• Fast quantum algorithms for least squares regression and statistic leverage scores
• Randomized local model order reduction
• Max-Plus Algebraic Statistical Leverage Scores
• 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
• Adaptive iterative Hessian sketch via \(A\)-optimal subsampling
• Streaming low-rank matrix approximation with an application to scientific simulation
• Structural conditions for projection-cost preservation via randomized matrix multiplication
• Title not available (Why is that?)
• Randomized algorithms in numerical linear algebra
• A count sketch maximal weighted residual Kaczmarz method for solving highly overdetermined linear systems
• Generalized linear models for massive data via doubly-sketching
• Massively parallel entity matching with linear classification in low dimensional space
• Estimating Leverage Scores via Rank Revealing Methods and Randomization
• Fast and accurate randomized algorithms for linear systems and eigenvalue problems
• Hessian averaging in stochastic Newton methods achieves superlinear convergence
• Robust and efficient subsampling algorithms for massive data logistic regression
• Weighted SGD for \(\ell_p\) regression with randomized preconditioning
• Nearly tight oblivious subspace embeddings by trace inequalities
• 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
• Online row sampling
• 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
• Nesterov's acceleration for approximate Newton
• Structured random sketching for PDE inverse problems
• 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

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)