PaperlayerView exact revision on arXiv

Source-linked AI summary

Bilinear Factor Matrix Norm Minimization for Robust PCA: Algorithms and Applications

Fanhua Shang, James Cheng, Yuanyuan Liu, Zhi-Quan Luo, Zhouchen Lin

arXiv:1810.05186v1cs.LGcs.CVmath.OCstat.ML

TL;DR

Robust PCA and related low-level vision problems need low-rank regularization that better fits heavy-tailed data without the high cost of existing non-convex solvers. The paper introduces bilinear factor penalties equivalent to Schatten-1/2 and 2/3 quasi-norms, achieving more accurate solutions with few observations and strong results across vision tasks.

  • Problem

    Existing nuclear- and Schatten-quasi-norm approaches either over-penalize singular values or require costly large-matrix SVDs, limiting scalable low-rank modeling.

  • Method

    The paper defines double nuclear and Frobenius/nuclear hybrid penalties, proves their equivalence to Schatten-1/2 and 2/3 quasi-norms, and optimizes them through bilinear factor matrices.

  • Results

    Both methods outperform original Schatten quasi-norm minimization with few observations and generally outperform existing methods across text removal, moving-object detection, alignment, and inpainting.

  • Takeaways & Limitations

    The proposed penalties provide tractable low-rank regularizers for robust PCA and related low-level vision applications when observations are limited.

  • Takeaways & Limitations

    Existing Schatten-quasi-norm solvers remain computationally costly because they require large-matrix SVDs at every iteration.

Abstract

from arXiv · show

The heavy-tailed distributions of corrupted outliers and singular values of all channels in low-level vision have proven effective priors for many applications such as background modeling, photometric stereo and image alignment. And they can be well modeled by a hyper-Laplacian. However, the use of such distributions generally leads to challenging non-convex, non-smooth and non-Lipschitz problems, and makes existing algorithms very slow for large-scale applications. Together with the analytic solutions to lp-norm minimization with two specific values of p, i.e., p=1/2 and p=2/3, we propose two novel bilinear factor matrix norm minimization models for robust principal component analysis. We first define the double nuclear norm and Frobenius/nuclear hybrid norm penalties, and then prove that they are in essence the Schatten-1/2 and 2/3 quasi-norms, respectively, which lead to much more tractable and scalable Lipschitz optimization problems. Our experimental analysis shows that both our methods yield more accurate solutions than original Schatten quasi-norm minimization, even when the number of observations is very limited. Finally, we apply our penalties to various low-level vision problems, e.g., text removal, moving object detection, image alignment and inpainting, and show that our methods usually outperform the state-of-the-art methods.

1 INTRODUCTION

The paper targets robust PCA and related low-level vision problems whose sparse outliers and matrix singular values exhibit heavy-tailed distributions. It proposes tractable bilinear factor norm models, establishes their connections to Schatten quasi-norms, and reports faster, more accurate applications.

  • Limitations: Existing Schatten quasi-norm methods require iterative optimization with singular value decomposition in each iteration, limiting scalability.The nuclear norm is the convex envelope commonly used to relax rank, but Schatten quasi-norm approaches seek closer rank approximations,.
  • Motivation: Heavy-tailed distributions characterize both sparse outliers and matrix singular values, motivating hyper-Laplacian modeling with analytically solvable cases α=1/2 and α=2/3,,.For sparse vectors, the resulting algorithm can be several orders of magnitude faster than existing algorithms [10], while matrix methods still have per-iteration complexity O(min(m, n)mn).
  • Contributions: The paper proposes two tractable bilinear factor matrix norm minimization models for robust PCA that model heavy-tailed sparse noise and singular values.The models are designed to fit empirical distributions of corrupted data and address the resulting non-convex optimization challenges.
  • Contributions: It defines double nuclear and Frobenius/nuclear hybrid penalties, proves their low-rank representations, and extends the algorithms to matrix completion such as image inpainting.These definitions differ from those in the authors’ previous work.
  • Contributions: Experiments show both bilinear factor matrix norm methods outperform original Schatten norm minimization with few observations and achieve superior results in several low-level vision tasks.Applications include text removal, moving object detection, image alignment, and inpainting.

2 RELATED WORK

RPCA separates corrupted observations into low-rank and sparse components, but its exact formulation is NP-hard and common convex relaxations can be costly at scale. Prior work therefore developed factorized formulations and alternative nuclear-norm penalties to improve scalability or recovery performance.

  • RPCA formulations: RPCA seeks low-rank L and sparse S from D=L*+S*, but the rank-plus-ℓ0 formulation is NP-hard.The model uses λ as the regularization parameter for the sparse term.
  • Convex RPCA: Convex relaxation replaces rank and ℓ0 with the nuclear norm and ℓ1-norm, and can exactly recover (L*, S*) with high probability under mild conditions,,.The formulation also underlies applications including object detection, background subtraction, image alignment, texture analysis, restoration, and subspace clustering,,,,.
  • Optimization limitations: ADMM and related first-order methods repeatedly compute an m × n SVD, creating high computational cost that limits large-scale applications,.This limitation also affects existing Schatten-q quasi-norm minimization methods for 0 < q < 1.
  • Factorized formulations: Factorizing L=UV^T with d≪min(m,n) replaces large-matrix optimization with smaller factor-matrix problems, and orthonormal U preserves the nuclear norm through ∥L∥*=∥V∥* [47],.Related work also considered matrix tri-factorization and column-orthonormal constraints on U [48],,,,,.
  • Alternative penalties: Other approaches use bilinear spectral regularization or modified nuclear norms, including elastic-net factorization, weighted and truncated nuclear norms, and partial singular value thresholding,,,,.These variants target scalable modeling or more effective singular-value shrinkage in RPCA and low-level vision.

3 BILINEAR FACTOR MATRIX NORM MINIMIZATION

This section introduces double nuclear and Frobenius/nuclear hybrid factor penalties, proves their equivalence to Schatten-1/2 and Schatten-2/3 quasi-norms, and uses them to formulate more tractable, scalable RPCA models.

  • 3 BILINEAR FACTOR MATRIX NORM MINIMIZATION: The double nuclear penalty is a quasi-norm equivalent to the Schatten-1/2 quasi-norm and admits a factorized nuclear-norm characterization.For rank(X) ≤ d, it equals min_{X=UV^T} ∥U∥_*∥V∥_*; unlike an earlier formulation,, it is directly usable in practical recovery problems.
  • 3 BILINEAR FACTOR MATRIX NORM MINIMIZATION: The Frobenius/nuclear hybrid penalty is a quasi-norm equivalent to the Schatten-2/3 quasi-norm and has a practical bilinear factorization.For rank(X) = r ≤ d, it equals min_{X=UV^T} ∥U∥_F∥V∥_* and, like the double nuclear penalty, can be used directly in practical problems.
  • 3 BILINEAR FACTOR MATRIX NORM MINIMIZATION: The proposed RPCA models combine these bilinear penalties with hyper-Laplacian priors for sparse components under a projection-based observation constraint.The models use ∥L∥_S1/2 for sparse components and account for unobserved entries through P_Ω(L+S)=P_Ω(D), with S_Ωc set to zero in the expected output.
  • 3 BILINEAR FACTOR MATRIX NORM MINIMIZATION: Because each bilinear factor norm is convex, the two proposed models are more tractable and scalable than the original Schatten quasi-norm minimization problem.The penalties also provide low nuclear-norm approximations through their stated bounds and retain quasi-norm properties such as unitary invariance.

4 OPTIMIZATION ALGORITHMS

The paper solves both bilinear factorization problems with variable splitting and efficient ADMM schemes. Closed-form updates use SVT for nuclear-norm subproblems and half- or two-thirds-thresholding operators for the corresponding ℓ_p quasi-norm terms.

  • Variable splitting: Variable splitting reformulates the interdependent optimization problems by introducing bU and bV, or only bV, so the resulting terms can be solved independently under the factorization constraints.The reformulated constraints enforce bU = U, bV = V, UV^T = L, and L + S = D.
  • ADMM algorithms: ADMM provides the main optimization framework, with alternating updates for factor variables, auxiliary variables, low-rank L, sparse S, and Lagrange multipliers.The penalty parameter is updated geometrically, µk+1 = ρµk, within nested inner and outer loops.
  • ADMM algorithms: The auxiliary bU and bV subproblems are nuclear-norm-regularized least-squares problems solved in closed form by the singular value thresholding operator.The updates fix the other variables and apply SVT separately to bU and bV.
  • Half-thresholding update: For the (S+L)1/2 model, the sparse-variable subproblem is solved by a closed-form half-thresholding operator despite the underlying ℓp problem being non-convex, non-smooth, and non-Lipschitz.Proposition 1 establishes the matrix solution X* = Hγ(A), which is applied elementwise after vectorization.
  • Acceleration: Adaptive updates of µ and ρ, together with shrinkage-thresholding operators, are used to further accelerate convergence and can adaptively select matrix rank or the number of nonzero elements.The strategy follows.
  • Two-thirds-thresholding update: For the (S+L)2/3 model, a separate ADMM algorithm uses a closed-form two-thirds-thresholding operator for the sparse-variable update.Proposition 2 gives X* = Tγ(C), extending the scalar thresholding formula elementwise to matrices.

5 ALGORITHM ANALYSIS

The proposed ADMM methods exhibit strong empirical convergence, while Algorithm 1 is theoretically guaranteed under mild conditions to approach critical points satisfying the KKT conditions. Their iterations typically converge within about 50 iterations, and their O(mnd) complexity matches several factorization-based baselines.

  • Convergence analysis: The algorithms show strong empirical convergence, although general convergence of non-convex multi-block ADMM remains difficult to guarantee.The convergence guarantee is stated for Algorithm 1; analogous convergence can also be guaranteed for Algorithm 2.
  • Convergence analysis: Under mild conditions, Algorithm 1's sequence has Cauchy primal-variable sequences, and every accumulation point satisfies the KKT conditions for Problem (17).Equivalently, each accumulation point is a critical point of the Lagrangian function and satisfies the first-order optimality conditions.
  • Convergence analysis: The proposed ADMM methods require only one Lagrange-multiplier sequence to be bounded, weaker than the all-multiplier boundedness required by,.The theorem applies to the proposed single-inner-iteration ADMM scheme, while further analysis for converged inner loops is left open.
  • Stopping criterion: With stopping tolerances ϵ=10^-5 for synthetic data and ϵ=10^-4 for real-world problems, the methods usually converge within 50 iterations.The stopping tolerance and relative squared error decrease rapidly according to the supplementary experiments.
  • Complexity analysis: When d ≪ m, n, each iteration of Algorithms 1 and 2 costs O(mnd), matching the complexity of LMaFit, RegL1, ROSL, Unifying, and factEN.The dominant cost is matrix multiplication for updating U, V, and L, whereas existing Schatten quasi-norm methods such as LpSq require O(mn^2) thin-SVD computation.

6 EXPERIMENTAL RESULTS

The experiments evaluate (S+L)1/2 and (S+L)2/3 on synthetic and real-world problems against state-of-the-art baselines. Across matrix recovery and low-level vision applications, the proposed methods generally achieve more accurate results with strong scalability and efficiency.

  • Synthetic matrix recovery: On corrupted matrices, both proposed methods achieve more accurate solutions and greater scalability than existing methods, especially for large matrices and very limited observations.The comparisons use average RSE, F-measure, and running time under Gaussian noise and outlier corruption, with Table 3 reporting results over ten independent runs.
  • Synthetic matrix recovery: With 80% missing entries, both proposed methods yield much more accurate RSE solutions than competing methods including LpSq; with more observations, they and LpSq outperform the other methods.These comparisons concern matrix factorization methods with 5% outliers and varying missing ratios.
  • Synthetic matrix recovery: On 1,000×1,000 matrices, both proposed methods maintain significantly better accuracy than competing factorization methods while using much shorter running times.LMaFit’s performance worsens over time, whereas the proposed methods provide accurate solutions efficiently.
  • Moving object detection: For surveillance-video background subtraction, both proposed methods consistently outperform the other methods in F-measure and are much faster than RegL1.They also produce visually better decompositions than RegL1 and factEN, while factEN is slightly faster but usually has poorer result quality.
  • Image alignment: For image alignment, both proposed methods robustly align images, detect and remove occlusions, and achieve better low-rank components than RASL and PSVT.The comparison is shown through results and close-up views in Fig. 11.
  • Image inpainting: For image inpainting, both proposed methods consistently produce much better PSNR results than the other methods across the reported missing-pixel settings and run more than 25 times faster than several methods.The evaluation includes average PSNR and running time with 85% random missing pixels, plus visual results with 80% missing pixels.

7 CONCLUSIONS AND DISCUSSIONS

The paper introduces bilinear factor matrix penalties equivalent to Schatten-1/2 and 2/3 quasi-norms, yielding tractable methods that exploit hyper-Laplacian priors for low-level vision. Experiments show improved accuracy over original Schatten quasi-norm methods, while future work targets theory, recovery guarantees, and auxiliary regularization.

  • Conclusions: The proposed double nuclear and Frobenius/nuclear hybrid penalties are equivalent to the Schatten-1/2 and 2/3 quasi-norms, respectively, and enable tractable bilinear factor matrix methods for low-level vision.These penalties are designed to exploit hyper-Laplacian priors for sparse noise/outliers and singular values of low-rank components.
  • Conclusions: Both proposed methods produce more accurate solutions than original Schatten quasi-norm minimization methods, including when observations are limited.The conclusions specifically note that the methods perform much better than existing Schatten quasi-norm methods with limited observations.
  • Future Work: Future work includes theoretically comparing both bilinear factor matrix penalties with the nuclear norm and Schatten quasi-norm, including determining sufficient observations for reliable low-rank recovery.The paper also identifies recovery under limited observations as an open theoretical question.
  • Future Work: The authors also plan to regularize the models with auxiliary information such as graph Laplacian,,, hyper-Laplacian matrix [82], or elastic-net.These are proposed directions for extending the regularization framework.

Supplementary Materials: Bilinear Factor Matrix Norm Minimization for Robust PCA: Algorithms and Applications

The supplementary material supplies theorem, lemma, and property proofs, algorithmic details, stopping criteria, new ADMM procedures, and additional experiments. It also establishes vector and matrix norm notation, including the non-convex Schatten-p quasi-norms for 0<p<1.

  • Supplementary materials: The supplement provides detailed proofs, stopping criteria, Algorithm 2 details, two new ADMM image-recovery algorithms with pseudocodes, and additional synthetic and real-world experiments.These materials extend the theoretical, algorithmic, and empirical presentation of the main paper.
  • Notation and norm definitions: The notation specifies real vector and matrix spaces, trace inner products, ordered singular values, rank, singular value decomposition, and identity matrices.It also defines the vector ℓ1 norm as convex, the ℓp quasi-norm for 0<p<1 as non-convex, and the ℓ2 norm.
  • Notation and norm definitions: It defines the singular-value-based Schatten-p matrix norm and notes that 0<p<1 yields a non-convex quasi-norm that violates the triangle inequality.The supplement also identifies Schatten-1 with the nuclear norm and Schatten-2 with the Frobenius norm.

APPENDIX A: PROOF OF LEMMA 2

The appendix proves Lemma 2 by introducing doubly stochastic matrices and applying an ordered-sequence lemma to a trace-based argument involving unitary matrices.

  • A doubly stochastic matrix has nonnegative entries, with every row and column summing to 1.
  • Lemma 7 considers a doubly stochastic matrix P and nonnegative sequences ordered oppositely, with x_1 ≤ x_2 ≤ … ≤ x_n and y_1 ≥ y_2 ≥ … ≥ y_n.
  • The proof constructs nonnegative coefficients and uses Kronecker-delta identities to establish the lemma’s result.
  • The proof of Lemma 2 uses trace properties and notes that a matrix formed from unitary transformations is doubly stochastic, enabling Lemma 7 to yield the stated trace inequality.

APPENDIX B: PROOFS OF THEOREMS 1 AND 2

Appendix B proves Theorems 1 and 2 by applying Lemmas 3 and 4 to factor matrices satisfying X = UV^T and using the SVD of X. It also specifies an ADMM procedure for the (S+L)2/3 problem, including initialization, alternating updates, multiplier updates, and termination.

  • Proof of Theorem 1: Theorem 1 is proved using Lemma 3 for factor matrices U and V constrained by X = UV^T, followed by an SVD-based argument.The proof concludes after establishing the stated result.
  • Algorithm 2: Algorithm 2 initializes ADMM with µ0, ρ > 1, k = 0, and ϵ for solving the (S+L)2/3 problem (18).Its inputs are D ∈ R^m×n, the given rank d, and λ.
  • Algorithm 2: Within each inner iteration, ADMM updates U and V, computes bV, and updates L and S using the specified equations.The algorithm repeats these updates until convergence.
  • Proof of Theorem 2: Theorem 2 is proved analogously using Lemma 4 for factors U and V with X = UV^T and the SVD of X.The appendix states that this completes the proof.

APPENDIX C: PROOF OF PROPERTY 4 … Update of Lk+1:

Appendix C proves Property 4 using ℓp-norm inequalities, compact SVD notation, and Theorems 1 and 2. Appendices D and subsequent updates derive an ADMM solver for (18), including factor, singular-value-thresholding, and least-squares updates.

  • APPENDIX C: PROOF OF PROPERTY 4: Property 4 is proved from recalled ℓp-norm inequalities for 0 < p2 ≤ p1 ≤ 1, together with compact-SVD notation and Theorems 1 and 2.
  • APPENDIX D: SOLVING (18) VIA ADMM: The ADMM formulation for (18) uses an augmented Lagrangian with three matrix-valued Lagrange multipliers, Y1, Y2, and Y3.
  • Update of Uk+1 and Vk+1:: The updates of Uk+1 and Vk+1 are obtained by formulating separate optimization problems and solving for their optimal solutions.
  • Update of Uk+1 and Vk+1:: The bVk+1 subproblem combines a nuclear-norm penalty with a quadratic Frobenius term while holding the other variables fixed.
  • Update of Uk+1 and Vk+1:: The closed-form solution of the bVk+1 subproblem is obtained using the singular value thresholding operator.
  • Update of Uk+1 and Vk+1:: The SVT operator applies soft shrinkage through Sτ(x) = max(|x| −τ, 0) · sgn(x),,.
  • Update of Lk+1:: The Lk+1 update is a least-squares problem with a closed-form solution.
  • Update of Lk+1:: Together with the Sk+1 update in (33), these steps yield an efficient ADMM algorithm for the Frobenius/nuclear hybrid norm penalized RPCA problem (18), summarized in Algorithm 2.

APPENDIX E: PROOF OF THEOREM 3 … Updating Uk+1 and Vk+1:

The appendix proves that Algorithm 1 has bounded iterates and multipliers, converges asymptotically to KKT conditions, and supports efficient ADMM updates and stopping criteria for image recovery.

  • APPENDIX E: PROOF OF THEOREM 3: The proof shows that U_k, V_k, their auxiliary variables, S_k, and L_k are Cauchy sequences, so Algorithm 1 satisfies its stopping criterion in finitely many iterations.The argument derives vanishing successive differences and applies these to all primal and auxiliary sequences.
  • APPENDIX F: STOPPING CRITERION: The stopping test for Algorithm 1 is derived from the KKT conditions of (15) and their equivalent formulation (17), using residual conditions involving the factor and auxiliary variables.The appendix explicitly connects the original and split formulations before defining the stopping conditions.
  • APPENDIX G: ALGORITHMS FOR IMAGE RECOVERY: For matrix completion, the paper introduces equivalent auxiliary-variable formulations and proposes efficient ADMM Algorithms 3 and 4 for the D-N and F-N penalty regularized least-squares problems.The formulations enforce L = UV^T, U = bU, and V = bV while using observed entries P_Ω(D).
  • Updating Uk+1 and Vk+1:: The U and V subproblems are smooth convex optimizations with closed-form solutions, while auxiliary factor updates use singular-value thresholding.The ADMM scheme alternates factor updates, SVT-based nuclear-norm proximal steps, and an observation-constrained L update.
  • Updating Uk+1 and Vk+1:: Figure 14 examines convergence behavior of the (S+L)1/2 and (S+L)2/3 methods for matrix ranks 5, 10, and 20 using stopping criteria and relative squared error.The figure reports the convergence diagnostics used for the two methods across three rank settings.

APPENDIX H: MORE EXPERIMENTAL RESULTS … Image Inpainting

Across additional experiments, the proposed methods converge quickly, remain robust to rank and regularization choices, and outperform comparison methods in text removal and image inpainting. Results also cover surveillance-video separation and comparisons with established baselines.

  • APPENDIX H: MORE EXPERIMENTAL RESULTS: The appendix compares both proposed methods with LMaFit, RegL1, Unifying, factEN, RPCA, PSVT, WNNM, and LpSq.Matlab code for the proposed methods is also provided through the paper’s download link.
  • Convergence Behavior: On 1,000×1,000 matrices with 5% outliers, both methods rapidly reduce stopping tolerance and RSE and usually converge within 50 iterations.Fig. 14 tracks RSE and the stopping criterion over iterations.
  • Robustness: Both methods outperform PSVT, Unifying, and LpSq more robustly across rank choices at a 10% outlier ratio.Fig. 15(a) evaluates sensitivity to the rank parameter d.
  • Robustness: Both methods remain robust over regularization parameters from 10^-4 to 100 when the rank is estimated by the proposed rank-estimation procedure.Fig. 15(b) evaluates sensitivity to λ at a 10% outlier ratio.
  • Moving Object Detection: The moving-object experiments use Bootstrap, Hall, Lobby, Mall, and WaterSurface surveillance sequences and show background–foreground separation results on four sequences.Table 4 describes the five sequences, while Fig. 17 presents separation outputs for Hall, Mall, Lobby, and WaterSurface.
  • Image Inpainting: Both proposed methods consistently outperform APGL and WNNM in average PSNR and standard deviation across missing-pixel settings, with greater advantages at 5% observed pixels.Fig. 18 reports the average PSNR and standard deviation for observed-pixel fractions from 95% to 80%.
  • Image Inpainting: With rank d varying from 7 to 15, both proposed methods are more robust than TNNR in image inpainting.Fig. 19 compares average PSNR and standard deviation, with TNNR averaged over 50 independent runs and d=9 used for the main comparison.
Loading 1810.05186v1…