The Fast Cauchy Transform and Faster Robust Linear Regression

DOI10.1137/140963698zbMath1342.68352arXiv1207.4684OpenAlexW2570048418MaRDI QIDQ2812147

Malik Magdon-Ismail, Kenneth L. Clarkson, Xiangrui Meng, Michael W. Mahoney, David P. Woodruff, Petros Drineas

Publication date: 16 June 2016

Published in: SIAM Journal on Computing, Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

Cauchy transformrandomized algorithmsrobust regressionsubspace embedding

Mathematics Subject Classification ID

Linear regression; mixed models (62J05) Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20)

Related Items (11)

Spectral estimation from simulations via sketching ⋮ The Simultaneous Communication of Disjointness with Applications to Data Streams ⋮ Semi-Infinite Linear Regression and Its Applications ⋮ Sampling Lasso quantile regression for large-scale data ⋮ Erasure Coding for Fault-Oblivious Linear System Solvers ⋮ Quantile regression for large-scale data via sparse exponential transform method ⋮ Structured Random Sketching for PDE Inverse Problems ⋮ Toward a unified theory of sparse dimensionality reduction in Euclidean space ⋮ Unnamed Item ⋮ Random projections for Bayesian regression ⋮ Tight Bounds for the Subspace Sketch Problem with Applications

Uses Software

• Blendenpik

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• CUR matrix decompositions for improved data analysis
• Faster least squares approximation
• The \(L_1\)-norm best-fit hyperplane problem
• Uncertainty Principles and Signal Recovery
• IMPROVED ANALYSIS OF THE SUBSAMPLED RANDOMIZED HADAMARD TRANSFORM
• Randomized Algorithms for Matrices and Data
• Blendenpik: Supercharging LAPACK's Least-Squares Solver
• Sparser Johnson-Lindenstrauss Transforms
• Stable distributions, pseudorandom generators, embeddings, and data stream computation
• Sparse representations in unions of bases
• A Fast Random Sampling Algorithm for Sparsifying Matrices
• Relative-Error $CUR$ Matrix Decompositions
• Sampling Algorithms and Coresets for $\ell_p$ Regression
• A Stable and Efficient Algorithm for the Rank-One Modification of the Symmetric Eigenproblem
• Uncertainty principles and ideal atomic decomposition
• On Minimum Volume Ellipsoids Containing Part of a Given Ellipsoid
• The Fast Johnson–Lindenstrauss Transform and Approximate Nearest Neighbors
• Subspace embeddings for the L ₁ -norm with applications

This page was built for publication: The Fast Cauchy Transform and Faster Robust Linear Regression