Low-Rank Approximation and Regression in Input Sparsity Time

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

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 (99)

• 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
• 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
• 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

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)