Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Tuesday, January 20, 2015, 12:15 pm
Duration: 30 minutes
Location: OAT S15/S16/S17
Speaker: Kenneth Clarkson (IBM Research)
We give algorithms for *M-estimators*, that minimize $||Ax - b||_G$ with respect to $x$, where $A$ is an $n$ by $d$ matrix, $b$ is an $n$-vector, and the "norm" $||y||_G$ for $n$-vector $y$ is specified by a cost function $G : R^n \to R^+$, with $||y||_G == \sum_i G(y_i)$.
M-estimators generalize $L_p$ regression, for which $G(x) = |x|^p$. We use the *M-sketch*, a randomized construction of a sketching matrix $S$, so that $||SAx||_G$ is a useful approximation to $||Ax||_G$ for $d$-vector $x$. This yields an algorithm for M-estimators requiring $O(nnz(A)+ poly(d))$ time to find a solution whose residual error is within a constant factor of optimal.
We also show that one of the most popular M-estimators, using the Huber measure, can be computed up to relative error $\epsilon$ in $O(nnz(A) \log n + poly(d/\epsilon))$ time.
Joint work with David Woodruff.
Automatic MiSe System Software Version 1.4803M | admin login