Input-sparsity Time Algorithms for Embeddings and Regression Problems
Talkat Workshop on Succinct Data Representations and Applications (Simons Institute Big Data 2013) · 2013-09-16..09-19·
summary
Claims that L2 and L1 subspace embeddings can be built in near input-sparsity time by using a projection Pi = S D where D is a random diagonal (±1 for L2, Cauchy diagonal for L1) and S has one non-zero per column on average. Analysis splits rows by leverage scores into heavy and light hitters to get 1±ε relative error; Pi A is computable in O(nnz(A)) plus poly(d/ε) factors and enables practical samplings (SPC1/SPC2/SPC3) that scale to billion-by-200 matrices and terabyte datasets.
AI-written summary · about
chapters (18)
- 0:00Introduction
- 17:37Defining a nice matrix
- 20:41Subspace preserving sampling
- 26:05What is sparsity time
- 27:00NNZ
- 30:24P Stable Distribution
- 30:43Tail Inequality
- 31:10Upper Bounds
- 32:13Lower Bounds
- 33:46LP Regression
- 34:19Quantile Regression
- 35:45Quantile Reactions
- 36:35Quantile Regressions
- 39:21Summary
- 41:18Randomized Algorithm
- 41:52Synthetic Data
- 43:05Running Time
- 44:11Extensions
related talks
01h 03mSampling for Linear Algebra, Statistics, and Optimization I
44mActive Regression via Linear-Sample Sparsification
28mSketching for M-Estimators: A Unified Approach to Robust Regression
28mRandomized Constrained Matrix Decompositions
01h 04mSketching for Linear Algebra III: Randomized Hadamard, Kernel Methods
01h 05mRecovering Hidden Sparsity via Sum of Squares
01h 02mTheory and Big Data
01h 06mAnalytic Methods for Supervised Learning III