Source-linked AI summary
Partial Sum Minimization of Singular Values in Robust PCA: Algorithm and Applications
Tae-Hyun Oh, Yu-Wing Tai, Jean-Charles Bazin, Hyeongwoo Kim, In So Kweon
TL;DR
RPCA rank minimization does not fully use known target-rank information, especially when observations are deficient. The paper minimizes a partial sum of singular values instead of the nuclear norm, reporting greater robustness in deficient-sample settings and nearly identical solutions when samples are sufficient.
Problem
Conventional rank minimization does not fully exploit known target rank information in low-level vision problems, and limited observations can degrade its results.
Method
The paper minimizes the partial sum of singular values beyond target rank N and develops a corresponding minimization method using PSVT.
Results
With deficient observations, the proposed formulation is reported as more robust to outliers than nuclear-norm rank minimization, while both solutions are almost identical with sufficient samples.
Takeaways & Limitations
The approach provides better control of the target rank and is applied to multiple low-level vision problems, including HDR, photometric stereo, image alignment, and image recovery.
Takeaways & Limitations
Robust model estimation and outlier rejection require more than the theoretical minimum number of samples, with the additional amount depending on the problem setting.
Abstract
from arXiv · showhide
Robust Principal Component Analysis (RPCA) via rank minimization is a powerful tool for recovering underlying low-rank structure of clean data corrupted with sparse noise/outliers. In many low-level vision problems, not only it is known that the underlying structure of clean data is low-rank, but the exact rank of clean data is also known. Yet, when applying conventional rank minimization for those problems, the objective function is formulated in a way that does not fully utilize a priori target rank information about the problems. This observation motivates us to investigate whether there is a better alternative solution when using rank minimization. In this paper, instead of minimizing the nuclear norm, we propose to minimize the partial sum of singular values, which implicitly encourages the target rank constraint. Our experimental analyses show that, when the number of samples is deficient, our approach leads to a higher success rate than conventional rank minimization, while the solutions obtained by the two approaches are almost identical when the number of samples is more than sufficient. We apply our approach to various low-level vision problems, e.g. high dynamic range imaging, motion edge detection, photometric stereo, image alignment and recovery, and show that our results outperform those obtained by the conventional nuclear norm rank minimization method.
1 INTRODUCTION
The paper replaces nuclear-norm RPCA with partial-sum singular-value minimization that uses known target rank information. Experiments report greater robustness with deficient observations and similar solutions when observations are sufficient.
- Low-level vision tasks can be formulated as low-rank recovery, but outliers make conventional PCA and matrix factorization error-prone.
- PSSV minimizes singular values beyond the known target rank N, where N is derived from the problem definition.
- The nuclear-norm surrogate minimizes all singular values, including those within the target rank, potentially biasing low-rank estimation when observations are limited.
- PSVT provides a soft rank constraint and encourages the solution to meet the target rank even when target-rank singular values are small.
- With limited observations, Eq. (3) is reported as more robust to outliers than nuclear-norm Eq. (2), while the solutions are almost identical with sufficient samples.
- The work contributes a partial-sum objective, a minimization method, convergence analysis, and applications across several low-level vision problems.
2 RELATED WORKS
The related-work discussion places the method within RPCA, nuclear-norm variants, and matrix-factorization approaches. It emphasizes deficient observations as a practical weakness of standard rank minimization and positions the proposed objective as an addendum when target rank is known.
- RPCA: Nuclear-norm RPCA has an exact convex-relaxation guarantee under sparsity, randomness, and a sufficiently low underlying rank.
- Nuclear-norm variants: Prior nuclear-norm variants include adaptive weighted norms and truncated nuclear norm methods, whose optimization can require alternating updates and additional SVD computations.
- Matrix factorization: Matrix factorization can enforce target rank directly through bilinear forms and matrix reprojection or orthogonal Procrustes.
- RPCA: Standard rank minimization depends on many observations, whereas limited observations can cause correct samples to be treated as outliers and vice versa.
- Proposed approach: The proposed objective is presented as an efficient complement to standard rank minimization for deficient-sample problems when the target or approximate target rank is known.
3 PARTIAL SUM MINIMIZATION BY THE PSVT OPERATOR
The paper derives PSSV by relaxing a target-rank formulation with a projection operator that preserves the largest singular values. Unlike nuclear-norm minimization, PSSV avoids reducing variance within the target subspace and better preserves rank under limited observations.
- 3.1 Derivation of Partial Sum of Singular Values: The relaxation uses a rank-r projection built from singular vectors associated with the r largest singular values.These singular vectors define the projection that preserves the leading singular-value information.
- 3.1.1 From rank constraint to projection: The toy example shows nuclear norm minimization selecting a rank-2 solution, whereas PSSV selects a rank-1 solution when the target rank is one.For A = [1 1; 3 x], nuclear norm is minimized at x = 1, while PSSV is minimized at x = 3.
- 3.1.1 From rank constraint to projection: PSSV preserves the target-rank singular values and drives residual singular values toward zero, so rank approaches N when rank(A) is at least N.If the input rank is below N, the target rank cannot be reached; corruptions can help satisfy the rank condition by increasing input rank.
- 3.1.2 Why the partial sum of singular values?: Nuclear norm minimization can bias estimates by shrinking target-rank singular values and treating some inliers as outliers, especially with limited observations.PSSV instead minimizes variance only in residual ranks, avoiding the same small-variance bias within the target subspace.
3.2 Optimization by ADMM
The constrained PSSV problem is optimized with an ADMM or inexact augmented-Lagrangian scheme. The method alternates minimization over variables while holding the others fixed.
- 3.2 Optimization by ADMM: ADMM is applied because the PSSV objective forms a constrained optimization problem.The paper identifies the method as an alternating direction method, also called inexact augmented Lagrange multipliers.
- 3.2 Optimization by ADMM: The augmented Lagrangian introduces a multiplier, a quadratic proximity term, and the PSSV and l1 error penalties.Its variables are minimized alternately rather than jointly.
- 3.2 Optimization by ADMM: The alternating updates are indexed by iteration k.The resulting subproblems separately support updates for the low-rank matrix and sparse error matrix.
3.3 Solving A∗
The A-subproblem is solved by Partial Singular Value Thresholding, which leaves the largest N singular values unchanged and soft-thresholds the remainder. PSVT provides a closed-form global optimum for this subproblem despite the non-convex objective.
- 3.3 Solving A∗: The derivation aligns the singular-vector factors of X and Y, reducing optimization to independent quadratic problems in the singular values.The minimizer follows from first-order optimality in the feasible singular-value domain.
- 3.3 Solving A∗: PSVT solves the A-subproblem by preserving the first N singular values and shrinking singular values after N.The residual singular values are processed with the soft-thresholding operator Sτ[x] = sign(x) · max(|x| − τ, 0).
- 3.3 Solving A∗: PSVT is a special case of weighted nuclear-norm optimization and gives a closed-form global optimum for the non-convex A-subproblem.The weighting is determined to encourage the target-rank constraint.
- 3.3 Solving A∗: When τ is infinite, PSVT becomes singular value projection, enforcing the target rank through projection.When leading singular values fall below τ, conventional SVT can make the matrix rank-deficient, whereas PSVT retains them.
3.4 Solving E∗
The E-subproblem is solved with element-wise soft-thresholding, a shrinkage operation suited to the l1 penalty on sparse errors.
- 3.4 Solving E∗: The sparse-error update is obtained using the soft-thresholding operator.The operator applies element-wise to vectors and matrices.
- 3.4 Solving E∗: Soft-thresholding minimizes the l1 penalty together with the quadratic proximity term and yields a global minimum for subproblems of this form.This update promotes sparsity in the error matrix E.
3.5 Updating A∗and E∗
Algorithm 1 uses an ADMM framework with outer and inner loops to update the low-rank matrix A and sparse error E for PSSV-based RPCA. The iterations continue until the equality constraint is sufficiently satisfied, using inexact ALM for computational efficiency.
- Iterations terminate when the equality constraint is satisfied, with all experiments using a relative Frobenius residual below 1e−7.
- One inner-loop iteration is empirically sufficient for an accurate solution, yielding the computationally efficient inexact ALM method.
- Algorithm 1 applies ADMM to update A and E for PSSV-based RPCA, with (A_k, E_k) as the output.
- The method initializes A_0 and E_0 at zero, sets the constraint rank N, and specifies λ, μ_0, ρ, and Z.
- At each outer iteration, inner-loop updates continue until convergence before updating the dual variable Z and penalty parameter μ.
3.6 Convergence Analysis
The analysis establishes a KKT-point convergence property while acknowledging that global optimality is not guaranteed for the non-convex ADMM scheme. Empirically, the method performs better with limited observations and similarly to nuclear-norm RPCA when observations are sufficient.
- The non-convex ADMM is treated as a local optimization method, and its general convergence property for alternating non-convex and convex subproblems remains unresolved.
- The objective value decreases for the primal variables optimized in each subproblem iteration, but the Lagrangian need not decrease monotonically because of the dual update.
- In the sufficient-sample setting, the nuclear-norm and PSSV solutions are very similar for a rank-3 matrix of size 10000 × 3000.
- Any convergent sequence generated by Algorithm 1 converges to a KKT point of Eq. (3).
4 EXPERIMENT RESULTS
Experiments show that PSSV is more robust than nuclear-norm RPCA when observations are limited, while matching it more closely with sufficient observations. Across synthetic tests and low-level vision applications, PSSV improves recovery accuracy, rank preservation, and some computational outcomes.
- Synthetic data: As observations decrease, RPCA’s success ratio falls more rapidly than PSSV’s; above n = 25, both methods behave similarly.This pattern is reported across rank-1, 2, 3, 5, and 10 constraints.
- Comparisons with other low-rank approximations: PSSV produces more accurate solutions than LMaFit, Zheng et al., and Eriksson et al., including under-sampled cases with unbalanced singular values.The under-sampled setting includes a rank-3 ground truth whose third basis direction has very small variance.
- Convergence and runtime: PSSV achieves higher accuracy than RPCA with gradual convergence while taking similar time and terminating at similar moments.The comparison uses the same termination criterion and reports runtime comparable to inexact ALM-based RPCA.
5 DISCUSSIONS AND CONCLUSION
The paper concludes that replacing the nuclear norm with PSSV improves control of a known target rank, especially with limited observations, and performs effectively across synthetic and real-world tasks.
- DISCUSSIONS AND CONCLUSION: PSSV provides better control of the target rank than the nuclear norm when observations are limited.The formulation implicitly encourages the desired rank without fully enforcing it.
- DISCUSSIONS AND CONCLUSION: The method can be incorporated into existing algorithms such as ADMM while retaining efficient computation properties.
- DISCUSSIONS AND CONCLUSION: Extensive synthetic and real-world experiments show that PSSV outperforms the conventional nuclear norm objective.
- DISCUSSIONS AND CONCLUSION: Robust estimation requires more than the theoretical minimum number of samples, with the needed surplus depending on the problem setting and sample distribution.For example, the theoretical minimum is 2 images for HDR and 3 images for photometric stereo.
- DISCUSSIONS AND CONCLUSION: With very limited samples, PSVT can produce a rank below the target when the observed samples span a subspace smaller than that rank.
SUPPLEMENTARY MATERIAL
The supplementary material documents the paper’s scope, establishes Lipschitz continuity for PSSV, and develops convergence arguments for the non-convex algorithm using generalized subdifferentials and KKT conditions.
- SUPPLEMENTARY MATERIAL: The supplementary material proves Proposition 1 and provides image-recovery pseudocode plus an additional experiment.Parameters follow the main paper or cited methods unless otherwise stated.
- SUPPLEMENTARY MATERIAL: PSSV is Lipschitz continuous because it is the difference between the nuclear norm and a Ky-Fan p-norm, both Lipschitz continuous.
- SUPPLEMENTARY MATERIAL: Because PSSV is non-convex, the proof uses the Clarke generalized subdifferential to derive stationary points.
- SUPPLEMENTARY MATERIAL: The generalized subdifferential is non-empty, convex, and compact for locally Lipschitz continuous functions, supporting the convergence proof.
- SUPPLEMENTARY MATERIAL: Any accumulation point generated by the algorithm satisfies the first-order necessary optimality condition, namely a KKT point.
- SUPPLEMENTARY MATERIAL: The convergence argument establishes KKT convergence under boundedness and non-decreasing penalty parameters, while further analysis remains future work.
2 ALGORITHM FOR IMAGE RECOVERY
The image-recovery algorithm uses ADMM with a target-rank constraint, alternating updates until convergence and returning the recovered low-rank matrix.
- 2 ALGORITHM FOR IMAGE RECOVERY: Algorithm 2 takes the observation matrix, index map, and constraint rank N as inputs.
- 2 ALGORITHM FOR IMAGE RECOVERY: The algorithm initializes A0 = O, B0 = Z0 = 0, μ0 > 0, ρ > 1, and k = 0 before iterating.
- 2 ALGORITHM FOR IMAGE RECOVERY: Each iteration updates Z and μ, increments k, and outputs A_k after convergence.