Source-linked AI summary
Generalized Singular Value Thresholding
Canyi Lu, Changbo Zhu, Chunyan Xu, Shuicheng Yan, Zhouchen Lin
TL;DR
Nonconvex low-rank minimization needs methods that improve on convex nuclear-norm surrogates while handling the difficulty of nonconvex optimization. The paper proves proximal monotonicity for lower-bounded functions, derives GSVT by singular-value shrinkage, and proposes a solver for common penalties. GSVT enables GPG, which outperforms IRNN in recovery error and objective value on synthetic and real matrix-completion data.
Problem
Convex ℓ1 and nuclear-norm surrogates can be suboptimal because they loosely approximate ℓ0 and rank, while nonconvex low-rank minimization is more challenging.
Method
The paper proves Proxg(·) is monotone for any lower-bounded g, applies it to singular values to form GSVT, and develops a solver for eligible nonconvex penalties.
Results
GPG using GSVT outperforms IRNN in recovery error and objective function value on synthetic and real matrix-completion experiments.
Takeaways & Limitations
GSVT generalizes SVT from the convex nuclear norm to lower-bounded functions and supports solving nonconvex low-rank minimization.
Takeaways & Limitations
IRNN may decrease the objective slowly because its upper-bound surrogate can be quite loose.
Abstract
from arXiv · showhide
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.
Introduction
The paper develops GSVT for nonconvex low-rank minimization by proving proximal monotonicity for lower-bounded functions and reducing matrix optimization to singular-value proximal problems. It also proposes a solver for common nonconvex penalties and reports that GPG outperforms IRNN on matrix completion.
- GSVT formulation: Monotonicity reduces GSVT to applying Proxg(·) independently to the singular values of B, generalizing SVT beyond the convex nuclear norm.For convex g, the same formulation follows from the usual monotonicity of the proximal operator.
- Related result: The weighted nuclear-norm formula is not generally optimal: fw,B(bX) = 0.2262 is lower than fw,B(X∗) = 0.2393, although the formula is optimal when 0 ≤ w1 ≤ ··· ≤ wm.The failure arises because the required pairwise monotonicity condition need not hold for arbitrary weights.
- Contribution: The paper proves that Proxg(·) is monotone for any lower-bounded g, regardless of whether g is convex.This resolves the key condition needed to preserve the nonincreasing order of singular values after shrinkage.
- Experiments: Using GSVT within GPG, the paper solves nonconvex low-rank minimization and reports better recovery error and objective function value than IRNN on matrix completion experiments.The comparison includes both synthetic and real data experiments.
- Proximal solver: For eligible nonconvex functions, the proposed solver finds Proxg(b) by computing the largest local minimum and comparing objective values at that point and zero.Many listed surrogates, including ℓp, logarithm, MCP, Geman, and Laplace penalties, satisfy the stated assumption.
Algorithms
The paper develops a general solver for the scalar proximal problem underlying GSVT, then uses GSVT within GPG for nonconvex low-rank optimization. GPG has a tighter-surrogate update, an SVD-based per-iteration cost, and convergence guarantees under µ > L(h).
- GSVT solver: A general solver for the scalar proximal problem enables solving GSVT for functions satisfying Assumption 1.The solver identifies candidate solutions and selects the optimal one by comparing objective values.
- GSVT solver: The fixed-point iteration searches for the largest local minimum ˆx_b from x_0 = b within [0, b].The paper states that this iteration is theoretically guaranteed to find ˆx_b.
- Experiments: Figure 3 reports Frequency of Success for noise-free recovery, relative error for noisy recovery, and IRNN-versus-GPG convergence curves.The figure covers low-rank matrix recovery on random data.
- GSVT solver: For nonsmooth g or nonconvex ∇g, the solver may require smart initial points, all local solutions, and nonsmooth points as candidates.These cases are presented as settings where the fixed-point procedure may remain applicable rather than as unconditional guarantees.
- GPG algorithm: GPG uses GSVT in its update rule and has the same main per-iteration cost as many convex methods: computing an SVD.The method generalizes previous proximal-gradient approaches for the nonconvex problem.
- GPG algorithm: When µ > L(h), GPG monotonically decreases F(X^k), and every limit point of {X^k} is a stationary point.The paper expects faster decrease than IRNN because GPG uses a tighter surrogate function.
Experiments
Experiments evaluate GPG with GSVT against IRNN and convex methods on synthetic, noisy, image-inpainting, and collaborative-filtering matrix-completion tasks. GPG generally achieves the strongest reported recovery or prediction performance, while noise-free recovery becomes difficult at higher ranks.
- Low-Rank Matrix Recovery on Random Data: GPG and IRNN both outperform convex ALM on noise-free synthetic recovery, with GPG slightly better at relatively small ranks but both failing when r ≥32.The comparison uses relative recovery error on 150×150 matrices with half the entries missing.
- Low-Rank Matrix Recovery on Random Data: GPG significantly outperforms IRNN and APGL on noisy synthetic recovery and decreases the objective faster than IRNN.The noisy experiments add 0.1E and compare mean relative error across 100 runs for each tested rank.
- Applications on Real Data: GPG achieves the best image-inpainting performance, with the largest PSNR and smallest relative error among APGL, IRNN, and GPG.The experiment uniformly removes 40% of pixels and applies matrix completion independently to the red, green, and blue channels.
- Applications on Real Data: GPG achieves the best NMAE on the MovieLens movie-100K, movie-1M, and movie-10M collaborative-filtering problems.The reported improvement is attributed to GPG’s fast and exact GSVT solver.
Conclusions
The paper establishes GSVT for nonconvex singular-value penalties and uses it within generalized proximal gradient optimization. Experiments report smaller recovery error and objective values than previous methods, while the framework may extend convex low-rank models to nonconvex settings.
- Conclusions: The paper proves that the proximal operator of any lower-bounded g is monotone, allowing GSVT to apply Proxg separately to singular values.This preserves the nonincreasing order of singular values after shrinkage and thresholding.
- Conclusions: A general solver is proposed for Proxg(b) under specified conditions on g, and GPG uses GSVT to solve nonconvex low-rank minimization.The solver is formulated for b ≥0 and certain nonconvex functions.
- Conclusions: GSVT plays the role of SVT in convex minimization and may enable extensions of other convex low-rank models to nonconvex cases.The paper identifies affine-constraint optimization and convergence analysis as future work.
Supplementary Material of Generalized Singular Value Thresholding
The supplementary material is identified with the paper’s authors, Canyi Lu, Changbo Zhu, Chunyan Xu, Shuicheng Yan, and Zhouchen Lin.
- Supplementary Material of Generalized Singular Value Thresholding: The supplementary material lists Canyi Lu, Changbo Zhu, Chunyan Xu, Shuicheng Yan, and Zhouchen Lin as authors.
1 Ananlysis of the Proximal Operator of Nonconvex Function
The proximal analysis characterizes candidate minimizers through intersections between a line and the gradient of g, then selects between zero and a largest stationary candidate. The resulting cases depend on gradient behavior and threshold values.
- Case analysis: When b exceeds a threshold, the scalar objective has two local minima: zero and the larger intersection point xb 2.For b > b∗, xb 2 is the global minimum.
- Case analysis: When b ≤ b̄, the global minimum is zero because the gradient of the scalar objective is nonnegative.This follows from D(x) lying above Cb(x).
- Finite-gradient case: Under the finite-gradient condition in Proposition 3, a single intersection exists for b > ∇g(0), and the corresponding xb is the global minimizer.The proposition also imposes C∇g(0)(x) ≤ ∇g(x) on (0, ∇g(0)).
- Limitations: For b ≤ b∗, the line and gradient may have more than two intersection points, so the intersection structure is not uniformly simple.This possibility is stated as a limitation of the case characterization.
- Proximal solution: The optimal proximal value can be found by comparing zero with the largest stationary candidate ˆxb.Corollary 1 defines x∗ as the minimizer over {0, ˆxb}.
2 Proof of Theorem 2
For any lower bounded function g, its proximal operator is monotone: larger inputs produce no smaller optimal proximal values. The proof uses finite optimal solutions and compares their optimality inequalities.
- Monotonicity result: Theorem 2 establishes that Prox_g(·) is monotone for every lower bounded function g.For x1 > x2, corresponding proximal solutions satisfy p*1 ≥ p*2.
- Proof basis: The lower bound on g guarantees that problem (1) has a finite solution.
- Proof basis: Comparing the optimality conditions for the two proximal problems and summing them yields an inequality relating the two solutions.
- Proof conclusion: When x1 > x2, the resulting inequality implies p*1 ≥ p*2.
3 Convergence Analysis of Algorithm 1
The proximal solver identifies a candidate fixed point in [0,b] and uses fixed-point iteration from x0 = b to reach it. When no positive candidate exists, 0 solves the proximal problem.
- Proximal solver: The candidate solution x̂b is the largest x in [0,b] satisfying ∇g(x) + x − b = 0.
- Proximal solver: If the candidate condition does not produce a positive solution, 0 is a solution to problem (1).
- Fixed-point iteration: The analysis proves that fixed-point iteration is sufficient to find x̂b.
- Fixed-point iteration: When ∇g(b) = 0, the solver immediately obtains x̂b = b.
- Fixed-point iteration: For x̂b < b, iteration starting from x0 = b converges to x̂b.
4 Convergence Analysis of Generalized Proximal Gradient Algorithm
Under concavity and smoothness assumptions, the Generalized Proximal Gradient algorithm decreases the objective when its parameter exceeds the gradient Lipschitz constant. If the objective is coercive, every limit point is stationary.
- Assumptions: The analysis assumes g is continuous, concave, and nonincreasing, while h has a Lipschitz continuous gradient with constant L(h).
- Theorem 3: Theorem 3 states that the algorithmic sequence has convergence properties when μ > L(h).
- Objective behavior: F(Xk) decreases monotonically along the generated sequence.
- Stationarity: If F(X) → +∞ as ||X||F → +∞, any limit point of {Xk} is a stationary point.
- Stationarity: The stationarity conclusion follows by establishing boundedness, extracting a convergent subsequence, and passing to the limit in the optimality relations.