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

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

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