Subgradient and Sampling Algorithms for `l_1` Regression

Ken Clarkson

Bell Labs, Lucent Technologies

`l_1` Regression: Points and Lines

Distances: sum= 0 rms= 0

`l_1` Regression: Matrices and Vectors

Who cares?

Algorithms: Before

Algorithms: Today

Ideas

Elementary column Operations

Conditioning `A` Using the Ellipsoid Method

Conditioning, II

Subgradients

Subgradient Descent

Subgradient Descent: Stepsize

Subgradient Descent: How good is the subgradient?

Subgradient Descent: Using conditioning

Subgradient Descent: Using the subgradient

Sampling Algorithm: Preprocessing

Sampling Algorithm: Sampling and Solving

Sampling Algorithm: Why it works

Bernstein Bounds

Coresets (motivation)

Coresets: uses