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}_+\rightarrow\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\}. $ We consider the cases where the function $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 $\ell_2$ norm. Specifically, we
show how to efficiently find an embedding matrix $S\in\mathbb{R}^{m\times
n},m<n$ such that $\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} \|Ax-b\|_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 $\ell_p$ low rank matrix approximation
problem for $1\leq p<2$.

本文针对经典线性回归问题进行推广，研究了 Orlicz 范数的损失函数，并提出了一种新的盲嵌入，用于将具有 Orlicz 范数的矩阵空间嵌入到具有二范数的较低维空间，从而得到回归问题和低秩矩阵逼近问题的近似算法。

用 Orlicz 范数进行子空间嵌入和线性回归

Subspace Embedding and Linear Regression with Orlicz Norm

Low rank matrix approximation (LRMA), which aims to recover the underlying
low rank matrix from its degraded observation, has a wide range of applications
in computer vision. The latest LRMA methods resort to using the nuclear norm
minimization (NNM) as a convex relaxation of the nonconvex rank minimization.
However, NNM tends to over-shrink the rank components and treats the different
rank components equally, limiting its flexibility in practical applications. We
propose a more flexible model, namely the Weighted Schatten $p$-Norm
Minimization (WSNM), to generalize the NNM to the Schatten $p$-norm
minimization with weights assigned to different singular values. The proposed
WSNM not only gives better approximation to the original low-rank assumption,
but also considers the importance of different rank components. We analyze the
solution of WSNM and prove that, under certain weights permutation, WSNM can be
equivalently transformed into independent non-convex $l_p$-norm subproblems,
whose global optimum can be efficiently solved by generalized iterated
shrinkage algorithm. We apply WSNM to typical low-level vision problems, e.g.,
image denoising and background subtraction. Extensive experimental results
show, both qualitatively and quantitatively, that the proposed WSNM can more
effectively remove noise, and model complex and dynamic scenes compared with
state-of-the-art methods.

本研究提出了一种更灵活的模型，称为加权 Schatten p - 范数最小化，用于恢复低秩矩阵。该模型不仅提供了更好的低秩矩阵逼近，并且考虑了不同秩分量的重要性。使用加权 Schatten p - 范数最小化在低级视觉问题（如图像去噪和背景减法）方面，相对于现有方法，可以更有效地去除噪声，对复杂和动态场景进行建模。