Subspace Embedding and Linear Regression with Orlicz Norm

We consider a generalization of the classic linear regression problem to the case when the loss is an Orlicz norm. An Orlicz norm is parameterized by a non-negative convex function G:ℝ_+rightarrowℝ_+ with G(0)=0: the Orlicz norm of a vector x∈ℝn is defined as |x|G=infleftα>0largemidsumi=1n G(|xi|/α)≤ 1right. We consider the cases where the function G(·) grows subquadratically. Our main result is based on a new oblivious embedding which embeds the column space of a given matrix A∈ℝn× d with Orlicz norm into a lower dimensional space with ℓ2 norm. Specifically, we show how to efficiently find an embedding matrix S∈ℝm× n,m<n such that forall x∈ℝd,Omega(1/(dlog n)) · |Ax|G≤ |SAx|2≤ O(d2log n) · |Ax|G. By applying this subspace embedding technique, we show an approximation algorithm for the regression problem minx∈ℝd |Ax-b|G, up to a O(dlog2 n) factor. As a further application of our techniques, we show how to also use them to improve on the algorithm for the ℓp low rank matrix approximation problem for 1≤ p<2.