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:{\mathbb{R}}_{+}\to {\mathbb{R}}_{+}$ with $G(0)=0$: the Orlicz norm of a vector $x\in {\mathbb{R}}^n$ is defined as $ |x|G=\inf\left{\alpha>0\large\mid\sum{i=1}^n G(|x_i|/\alpha)\leq 1\right}. $Weconsiderthecaseswherethefunction$G(\cdot)$ grows subquadratically. Our main result is based on a new oblivious embedding which embeds the column space of a given matrix $A\in {\mathbb{R}}^{n\times d}$ with Orlicz norm into a lower dimensional space with ${\mathrm{\ell }}_2$ norm. Specifically, we show how to efficiently find an embedding matrix $S\in$\mathbb{R}$^{m\times n},m<n$suchthat$\forall x\in$\mathbb{R}$^{d},\Omega(1/(d\log n)) \cdot |Ax|_G\leq |SAx|_2\leq O(d^2\log n) \cdot |Ax|_G.$ By applying this subspace embedding technique, we show an approximation algorithm for the regression problem ${\min }_{x\in {\mathbb{R}}^d}\mathrm{\parallel }Ax-b{\mathrm{\parallel }}_G$, up to a $O(d{\log }^{2}n)$ factor. As a further application of our techniques, we show how to also use them to improve on the algorithm for the ${\mathrm{\ell }}_p$ low rank matrix approximation problem for $1\le p<2$.