Generalized Singular Value Thresholding
This provides a foundational tool for researchers in optimization and machine learning dealing with nonconvex low rank problems, though it is incremental as it generalizes an existing method.
The paper tackles the problem of nonconvex low rank minimization by introducing the Generalized Singular Value Thresholding (GSVT) operator, which extends the known Singular Value Thresholding (SVT) to handle nonconvex functions on singular values, enabling solutions to nonconvex low rank minimization problems.
This work studies the Generalized Singular Value Thresholding (GSVT) operator ${\text{Prox}}_{g}^{σ}(\cdot)$, \begin{equation*} {\text{Prox}}_{g}^{σ}(B)=\arg\min\limits_{X}\sum_{i=1}^{m}g(σ_{i}(X)) + \frac{1}{2}||X-B||_{F}^{2}, \end{equation*} associated with a nonconvex function $g$ defined on the singular values of $X$. We prove that GSVT can be obtained by performing the proximal operator of $g$ (denoted as $\text{Prox}_g(\cdot)$) on the singular values since $\text{Prox}_g(\cdot)$ is monotone when $g$ is lower bounded. If the nonconvex $g$ satisfies some conditions (many popular nonconvex surrogate functions, e.g., $\ell_p$-norm, $0<p<1$, of $\ell_0$-norm are special cases), a general solver to find $\text{Prox}_g(b)$ is proposed for any $b\geq0$. GSVT greatly generalizes the known Singular Value Thresholding (SVT) which is a basic subroutine in many convex low rank minimization methods. We are able to solve the nonconvex low rank minimization problem by using GSVT in place of SVT.