Subgradient and Sampling Algorithms for L_1 Regression (NOT KNOWN IF TALK GIVEN)

Given an (n x d)-matrix A and an (n x 1)-vector b, the L_1 regression problem is to find the vector x minimizing the objective function ||Ax - b||_1, where ||y||_1 = sum_i |y_i| for vector y. This paper gives an algorithm needing 0(n log n)d^{0(1))} time in the worst case to obtain an approximate solution, with objective function value within a fixed ratio of optimum.