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와 관련 low-level vision 문제에서는 heavy-tailed data에 더 잘 맞으면서 기존 non-convex solver의 높은 비용은 피하는 low-rank regularization이 필요하다. 이 논문은 Schatten-1/2 및 2/3 quasi-norm과 동등한 bilinear factor penalty를 도입해, 관측 수가 적을 때도 더 정확한 해를 얻고 다양한 vision task에서 우수한 성능을 달성한다.

  • 문제

    기존 nuclear- 및 Schatten-quasi-norm 접근법은 singular value를 과도하게 penalize하거나 비용이 큰 large-matrix SVD를 요구해, scalable low-rank modeling을 제한한다.

  • 방법

    이 논문은 double nuclear penalty와 Frobenius/nuclear hybrid penalty를 정의하고, 이들이 Schatten-1/2 및 2/3 quasi-norm과 동등함을 증명한 뒤 bilinear factor matrix를 통해 최적화한다.

  • 결과

    두 방법 모두 관측 수가 적을 때 original Schatten quasi-norm minimization을 능가하며, text removal, moving-object detection, alignment, inpainting에서도 기존 방법을 대체로 능가한다.

  • 시사점 및 한계

    제안한 penalty는 관측이 제한된 경우 Robust PCA와 관련 low-level vision application에 적용할 수 있는 tractable low-rank regularizer를 제공한다.

  • 시사점 및 한계

    기존 Schatten-quasi-norm solver는 매 iteration마다 large-matrix SVD를 요구하므로 여전히 computationally costly하다.

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 서론

이 논문은 희소 이상치와 행렬 singular value가 heavy-tailed distribution을 보이는 robust PCA 및 관련 low-level vision 문제를 다룬다. 다루기 쉬운 bilinear factor norm model을 제안하고, 이를 Schatten quasi-norm과 연결하며, 더 빠르고 정확한 응용 결과를 보고한다.

  • 한계: 기존 Schatten quasi-norm 방법은 각 iteration마다 singular value decomposition을 포함한 반복 최적화를 수행해야 하므로 scalability가 제한된다.nuclear norm은 rank를 완화하기 위해 일반적으로 사용되는 convex envelope이지만, Schatten quasi-norm 접근법은 rank에 더 가까운 근사를 추구한다,.
  • 동기: Heavy-tailed distribution은 희소 이상치와 행렬 singular value 모두를 특징짓기 때문에, 해석적으로 풀 수 있는 α=1/2 및 α=2/3 사례를 갖는 hyper-Laplacian modeling이 동기를 얻는다,,.희소 벡터의 경우 결과 알고리즘은 기존 알고리즘보다 몇 orders of magnitude 빠를 수 있지만, 행렬 방법은 여전히 iteration당 complexity O(min(m, n)mn)을 갖는다.
  • 기여: 이 논문은 heavy-tailed sparse noise와 singular value를 모델링하는 robust PCA용 다루기 쉬운 두 가지 bilinear factor matrix norm minimization model을 제안한다.이 model은 corrupted data의 empirical distribution에 맞추고, 그로 인해 발생하는 non-convex optimization 문제를 해결하도록 설계되었다.
  • 기여: double nuclear 및 Frobenius/nuclear hybrid penalty를 정의하고, 이들의 low-rank representation을 증명하며, image inpainting과 같은 matrix completion으로 알고리즘을 확장한다.이 정의는 저자들의 이전 연구 의 정의와 다르다.
  • 기여: 실험 결과, 두 bilinear factor matrix norm 방법은 관측값이 적을 때에도 original Schatten norm minimization을 능가하며, 여러 low-level vision task에서 우수한 결과를 달성한다.응용 분야에는 text removal, moving object detection, image alignment 및 inpainting이 포함된다.

2 관련 연구

RPCA는 손상된 관측값을 low-rank 성분과 sparse 성분으로 분리하지만, 정확한 정식화는 NP-hard이며 일반적인 convex relaxation은 대규모 환경에서 비용이 클 수 있다. 따라서 기존 연구에서는 확장성 또는 복원 성능을 개선하기 위해 factorized formulation과 대안적 nuclear-norm penalty를 개발했다.

  • RPCA 정식화: RPCA는 D=L*+S*에서 low-rank L과 sparse S를 찾지만, rank-plus-ℓ0 정식화는 NP-hard다.이 모델은 sparse 항의 regularization parameter로 λ를 사용한다.
  • Convex RPCA: Convex relaxation은 rank와 ℓ0를 nuclear norm과 ℓ1-norm으로 대체하며, 완화된 조건에서 높은 확률로 (L*, S*)를 정확히 복원할 수 있다,,.이 정식화는 object detection, background subtraction, image alignment, texture analysis, restoration, subspace clustering을 포함한 응용의 기반이기도 하다,,,,.
  • 최적화의 한계: ADMM과 관련 first-order method는 반복적으로 m × n SVD를 계산하므로 높은 계산 비용이 발생하고, 이로 인해 대규모 응용이 제한된다,.이러한 한계는 0 < q < 1에 대한 기존 Schatten-q quasi-norm minimization method에도 영향을 준다.
  • Factorized formulation: d≪min(m,n)인 조건에서 L=UV^T로 factorization하면 대형 행렬 최적화가 더 작은 factor-matrix 문제로 대체되며, orthonormal U는 ∥L∥*=∥V∥*를 통해 nuclear norm을 보존한다,.관련 연구에서는 matrix tri-factorization과 U에 대한 column-orthonormal constraint도 고려했다,,,,,.
  • 대안적 penalty: 다른 접근법은 bilinear spectral regularization 또는 modified nuclear norm을 사용하며, elastic-net factorization, weighted and truncated nuclear norm, partial singular value thresholding을 포함한다,,,,.이러한 변형은 RPCA와 low-level vision에서 확장 가능한 모델링 또는 더 효과적인 singular-value shrinkage를 목표로 한다.

3 BILINEAR FACTOR MATRIX NORM MINIMIZATION

이 절에서는 double nuclear 및 Frobenius/nuclear hybrid factor penalty를 도입하고, 이것들이 Schatten-1/2 및 Schatten-2/3 quasi-norm과 동치임을 증명한 뒤, 이를 사용해 더 다루기 쉽고 확장 가능한 RPCA 모델을 정식화한다.

  • 3 BILINEAR FACTOR MATRIX NORM MINIMIZATION: double nuclear penalty는 Schatten-1/2 quasi-norm과 동치인 quasi-norm이며 factorized nuclear-norm characterization을 허용한다.rank(X) ≤ d일 때, 이는 min_{X=UV^T} ∥U∥_*∥V∥_*와 같으며, 기존 정식화, 와 달리 실제 recovery 문제에 직접 사용할 수 있다.
  • 3 BILINEAR FACTOR MATRIX NORM MINIMIZATION: Frobenius/nuclear hybrid penalty는 Schatten-2/3 quasi-norm과 동치인 quasi-norm이며 실용적인 bilinear factorization을 갖는다.rank(X) = r ≤ d일 때, 이는 min_{X=UV^T} ∥U∥_F∥V∥_*와 같고, double nuclear penalty와 마찬가지로 실제 문제에 직접 사용할 수 있다.
  • 3 BILINEAR FACTOR MATRIX NORM MINIMIZATION: 제안한 RPCA 모델은 projection-based observation constraint 아래 sparse component를 위한 hyper-Laplacian priors와 이러한 bilinear penalty를 결합한다.모델은 sparse component에 ∥L∥_S1/2를 사용하고, P_Ω(L+S)=P_Ω(D)를 통해 관측되지 않은 entry를 반영하며, 예상 출력에서는 S_Ωc를 0으로 설정한다.
  • 3 BILINEAR FACTOR MATRIX NORM MINIMIZATION: 각 bilinear factor norm이 convex이므로, 제안한 두 모델은 기존 Schatten quasi-norm minimization 문제보다 더 다루기 쉽고 확장 가능하다.또한 이 penalty는 명시된 bound를 통해 low nuclear-norm approximation을 제공하며, unitary invariance와 같은 quasi-norm 특성을 유지한다.

4 최적화 알고리즘

이 논문은 variable splitting과 효율적인 ADMM scheme을 사용해 두 bilinear factorization 문제를 모두 해결한다. Closed-form update에서는 nuclear-norm subproblem에 SVT를, 해당 ℓ_p quasi-norm 항에 half- 또는 two-thirds-thresholding operator를 사용한다.

  • Variable splitting: Variable splitting은 bU와 bV, 또는 bV만 도입해 상호 의존적인 최적화 문제를 재정식화하며, 그 결과 얻어진 항들은 factorization constraint하에서 독립적으로 풀 수 있다.재정식화된 constraint는 bU = U, bV = V, UV^T = L, L + S = D를 강제한다.
  • ADMM 알고리즘: ADMM은 factor variable, auxiliary variable, low-rank L, sparse S, Lagrange multiplier를 번갈아 업데이트하는 주요 최적화 framework를 제공한다.Penalty parameter는 nested inner 및 outer loop에서 기하급수적으로 업데이트되며, µk+1 = ρµk이다.
  • ADMM 알고리즘: Auxiliary bU와 bV subproblem은 nuclear-norm-regularized least-squares 문제이며, singular value thresholding operator 를 사용해 closed form으로 푼다.다른 variable을 고정한 뒤 bU와 bV에 SVT를 각각 적용해 update한다.
  • Half-thresholding update: (S+L)1/2 model에서는 underlying ℓp 문제가 non-convex, non-smooth, non-Lipschitz임에도 sparse-variable subproblem을 closed-form half-thresholding operator로 푼다.Proposition 1은 행렬 해 X* = Hγ(A)를 제시하며, vectorization 후 원소별로 적용한다.
  • Acceleration: µ와 ρ의 adaptive update를 shrinkage-thresholding operator와 함께 사용해 convergence를 further accelerate하며, matrix rank 또는 nonzero element 수를 adaptive하게 선택할 수 있다.이 전략은 를 따른다.
  • Two-thirds-thresholding update: (S+L)2/3 model에서는 별도의 ADMM algorithm을 사용하며, sparse-variable update에 closed-form two-thirds-thresholding operator를 적용한다.Proposition 2는 X* = Tγ(C)를 제시하고, scalar thresholding formula를 원소별로 행렬에 확장한다.

5 알고리즘 분석

제안한 ADMM 방법은 강한 경험적 수렴을 보이며, Algorithm 1은 완화된 조건에서 KKT conditions를 만족하는 critical point로 수렴할 것이 이론적으로 보장된다. 반복은 대체로 약 50 iterations 이내에 수렴하며, O(mnd) 복잡도는 여러 factorization 기반 baseline과 일치한다.

  • 수렴 분석: 알고리즘은 강한 경험적 수렴을 보이지만, 비볼록 multi-block ADMM의 일반적 수렴을 보장하는 일은 여전히 어렵다.수렴 보장은 Algorithm 1에 대해 제시되며, Algorithm 2에 대해서도 유사한 수렴을 보장할 수 있다.
  • 수렴 분석: 완화된 조건에서 Algorithm 1의 sequence는 Cauchy primal-variable sequences를 가지며, 모든 accumulation point는 Problem (17)의 KKT conditions를 만족한다.동등하게, 각 accumulation point는 Lagrangian function의 critical point이며 first-order optimality conditions를 만족한다.
  • 수렴 분석: 제안한 ADMM 방법은 하나의 Lagrange-multiplier sequence만 bounded이면 되며, 이는, 에서 요구하는 모든 multiplier의 boundedness보다 약한 조건이다.정리는 제안한 single-inner-iteration ADMM scheme에 적용되며, 수렴한 inner loop에 대한 추가 분석은 향후 과제로 남겨 둔다.
  • 종료 기준: synthetic data에는 stopping tolerance ϵ=10^-5를, real-world problems에는 ϵ=10^-4를 사용할 때, 방법들은 대체로 50 iterations 이내에 수렴한다.supplementary experiments에 따르면 stopping tolerance와 relative squared error가 빠르게 감소한다.
  • 복잡도 분석: d ≪ m, n일 때, Algorithms 1과 2의 각 iteration 비용은 O(mnd)이며, LMaFit, RegL1, ROSL, Unifying, factEN 의 복잡도와 일치한다.지배적인 비용은 U, V, L을 갱신하기 위한 matrix multiplication이며, LpSq 와 같은 기존 Schatten quasi-norm 방법은 O(mn^2) thin-SVD computation을 필요로 한다.

6 실험 결과

실험에서는 synthetic 및 real-world 문제에서 (S+L)1/2와 (S+L)2/3를 state-of-the-art baseline과 비교·평가한다. matrix recovery와 low-level vision 응용 전반에서 제안 방법은 높은 scalability와 efficiency를 유지하면서 대체로 더 정확한 결과를 달성한다.

  • Synthetic matrix recovery: corrupted matrix에서 두 제안 방법은 기존 방법보다 더 정확한 해와 높은 scalability를 달성하며, 특히 대규모 matrix와 관측 수가 매우 제한된 경우에 그 차이가 두드러진다.비교는 Gaussian noise와 outlier corruption 상황에서 average RSE, F-measure, running time을 사용하며, Table 3은 서로 독립적인 10회 실행에 대한 결과를 보고한다.
  • Synthetic matrix recovery: missing entry가 80%인 경우 두 제안 방법은 LpSq를 포함한 competing method보다 훨씬 정확한 RSE 해를 산출하며, 관측 수가 늘어나면 두 방법과 LpSq가 다른 방법보다 우수한 성능을 보인다.이 비교는 outlier가 5%이고 missing ratio가 변하는 matrix factorization method를 대상으로 한다.
  • Synthetic matrix recovery: 1,000×1,000 matrix에서 두 제안 방법은 competing factorization method보다 유의하게 높은 정확도를 유지하면서도 훨씬 짧은 running time을 사용한다.LMaFit은 시간이 지날수록 성능이 저하되는 반면, 제안 방법은 효율적으로 정확한 해를 제공한다.
  • Moving object detection: surveillance-video background subtraction에서 두 제안 방법은 F-measure에서 다른 방법을 일관되게 능가하며 RegL1보다 훨씬 빠르다.또한 RegL1과 factEN보다 시각적으로 더 나은 decomposition을 생성한다. factEN은 약간 더 빠르지만 대체로 결과 품질이 낮다.
  • Image alignment: image alignment에서 두 제안 방법은 image를 강건하게 정렬하고 occlusion을 검출·제거하며 RASL과 PSVT보다 더 우수한 low-rank component를 달성한다.비교 결과는 Fig. 11의 결과와 close-up view를 통해 제시된다.
  • Image inpainting: image inpainting에서 두 제안 방법은 보고된 missing-pixel 설정 전반에 걸쳐 다른 방법보다 훨씬 더 나은 PSNR 결과를 일관되게 산출하며, 여러 방법보다 25배 이상 빠르게 실행된다.평가에는 random missing pixel이 85%인 경우의 average PSNR과 running time, 그리고 missing pixel이 80%인 경우의 시각적 결과가 포함된다.

7 결론 및 논의

이 논문은 Schatten-1/2 및 2/3 quasi-norms와 동등한 bilinear factor matrix penalty를 도입하여, low-level vision에서 hyper-Laplacian prior를 활용하는 다루기 쉬운 방법을 제시한다. 실험 결과 기존 Schatten quasi-norm 방법보다 정확도가 향상되었으며, 향후 연구에서는 이론, recovery guarantee, auxiliary regularization을 다룬다.

  • 결론: 제안된 double nuclear 및 Frobenius/nuclear hybrid penalty는 각각 Schatten-1/2 및 2/3 quasi-norms와 동등하며, low-level vision을 위한 다루기 쉬운 bilinear factor matrix 방법을 가능하게 한다.이 penalty들은 low-rank component의 sparse noise/outlier와 singular value에 대한 hyper-Laplacian prior를 활용하도록 설계되었다.
  • 결론: 두 제안 방법은 관측 수가 제한된 경우를 포함하여 기존 Schatten quasi-norm minimization 방법보다 더 정확한 해를 산출한다.결론에서는 관측 수가 제한될 때에도 기존 Schatten quasi-norm 방법보다 성능이 훨씬 우수하다고 명시한다.
  • 향후 연구: 향후 연구에는 두 bilinear factor matrix penalty를 nuclear norm 및 Schatten quasi-norm과 이론적으로 비교하고, 신뢰할 수 있는 low-rank recovery에 필요한 충분한 관측 수를 결정하는 일이 포함된다.이 논문은 제한된 관측 환경에서의 recovery를 미해결 이론 문제로도 제시한다.
  • 향후 연구: 저자들은 graph Laplacian,,, hyper-Laplacian matrix [82], elastic-net 과 같은 auxiliary information을 사용해 모델을 regularize할 계획도 세우고 있다.이는 regularization framework를 확장하기 위해 제안된 연구 방향이다.

보충 자료: Bilinear Factor Matrix Norm Minimization for Robust PCA: Algorithms and Applications

보충 자료는 정리, 보조정리, 성질의 증명, 알고리즘 세부 사항, 종료 기준, 새로운 ADMM 절차와 추가 실험을 제공한다. 또한 0<p<1에서의 비볼록 Schatten-p quasi-norm을 포함해 벡터 및 행렬 norm 표기를 정립한다.

  • 보충 자료: 보충 자료는 상세한 증명, 종료 기준, Algorithm 2의 세부 사항, pseudocode를 포함한 두 가지 새로운 ADMM image-recovery algorithm, 그리고 추가적인 합성 및 실제 실험을 제공한다.이 자료들은 본 논문의 이론적, 알고리즘적, 실증적 설명을 확장한다.
  • 표기법 및 norm 정의: 표기법은 실수 벡터 및 행렬 공간, trace inner product, 정렬된 singular value, rank, singular value decomposition, identity matrix를 정의한다.또한 벡터 ℓ1 norm을 볼록으로, 0<p<1에서의 ℓp quasi-norm을 비볼록으로 정의하고 ℓ2 norm도 정의한다.
  • 표기법 및 norm 정의: singular value에 기반한 Schatten-p matrix norm을 정의하고, 0<p<1에서는 삼각 부등식을 위반하는 비볼록 quasi-norm이 된다고 설명한다.보충 자료는 Schatten-1이 nuclear norm과 일치하고 Schatten-2가 Frobenius norm과 일치한다는 점도 제시한다.

부록 A: 보조정리 2의 증명

부록에서는 doubly stochastic matrix를 도입하고 unitary matrix가 관련된 trace 기반 논증에 ordered-sequence lemma를 적용하여 보조정리 2를 증명한다.

  • doubly stochastic matrix는 음이 아닌 원소를 가지며, 모든 행과 열의 합이 1이다.
  • 보조정리 7에서는 doubly stochastic matrix P와 서로 반대 순서로 정렬된 음이 아닌 수열을 다루며, x_1 ≤ x_2 ≤ … ≤ x_n이고 y_1 ≥ y_2 ≥ … ≥ y_n이다.
  • 증명에서는 음이 아닌 계수를 구성하고 Kronecker-delta 항등식을 사용하여 보조정리의 결과를 확립한다.
  • 보조정리 2의 증명에서는 trace의 성질을 사용하고 unitary transformation으로 구성된 행렬이 doubly stochastic임을 관찰하여, 보조정리 7이 주어진 trace inequality를 도출하도록 한다.

부록 B: 정리 1과 2의 증명

부록 B에서는 X = UV^T를 만족하는 factor matrix에 Lemma 3과 4를 적용하고 X의 SVD를 사용하여 Theorem 1과 2를 증명한다. 또한 초기화, 교대 업데이트, multiplier 업데이트, 종료 조건을 포함하여 (S+L)2/3 problem에 대한 ADMM 절차를 제시한다.

  • Theorem 1의 증명: Theorem 1은 X = UV^T로 제약된 factor matrix U와 V에 Lemma 3을 적용한 뒤, SVD 기반 논증을 통해 증명한다.명시된 결과를 확립하면 증명이 끝난다.
  • Algorithm 2: Algorithm 2는 (S+L)2/3 problem (18)을 풀기 위해 µ0, ρ > 1, k = 0, ϵ으로 ADMM을 초기화한다.입력은 D ∈ R^m×n, 주어진 rank d, 그리고 λ이다.
  • Algorithm 2: 각 inner iteration에서 ADMM은 U와 V를 업데이트하고, bV를 계산하며, 지정된 방정식을 사용해 L과 S를 업데이트한다.알고리즘은 수렴할 때까지 이러한 업데이트를 반복한다.
  • Theorem 2의 증명: Theorem 2는 X = UV^T인 factor U와 V에 Lemma 4를 적용하고 X의 SVD를 사용하여 유사한 방식으로 증명한다.부록에서는 이것으로 증명이 완료된다고 서술한다.

APPENDIX C: PROPERTY 4의 증명 … Lk+1 업데이트:

Appendix C에서는 ℓp-norm 부등식, compact SVD 표기, Theorems 1과 2를 사용해 Property 4를 증명한다. Appendix D 및 이후 업데이트에서는 (18)을 위한 ADMM solver를 도출하며, factor, singular-value-thresholding, least-squares 업데이트를 포함한다.

  • APPENDIX C: PROPERTY 4의 증명: 0 < p2 ≤ p1 ≤ 1에 대한 ℓp-norm 부등식과 compact-SVD 표기, Theorems 1과 2를 사용해 Property 4를 증명한다.
  • APPENDIX D: ADMM을 통한 (18)의 풀이: (18)의 ADMM formulation은 세 개의 matrix-valued Lagrange multipliers인 Y1, Y2, Y3를 사용하는 augmented Lagrangian으로 구성된다.
  • Uk+1과 Vk+1 갱신:: Uk+1과 Vk+1의 갱신은 각각 별도의 최적화 문제를 정식화하고 최적해를 구해 얻는다.
  • Uk+1과 Vk+1의 업데이트:: bVk+1 subproblem은 다른 변수들을 고정한 상태에서 nuclear-norm penalty와 quadratic Frobenius 항을 결합한다.
  • Uk+1과 Vk+1의 업데이트:: bVk+1 subproblem의 closed-form solution은 singular value thresholding operator 를 사용해 구한다.
  • Uk+1과 Vk+1의 업데이트:: SVT operator는 Sτ(x) = max(|x| −τ, 0) · sgn(x),, 를 통해 soft shrinkage를 적용한다.
  • Lk+1 업데이트:: Lk+1 업데이트는 closed-form solution을 갖는 least-squares problem이다.
  • Lk+1 업데이트:: (33)의 Sk+1 업데이트와 함께 이 단계들은 Frobenius/nuclear hybrid norm penalized RPCA problem (18)을 위한 efficient ADMM algorithm을 구성하며, Algorithm 2에 요약되어 있다.

부록 E: 정리 3의 증명 … Uk+1 및 Vk+1 업데이트:

부록에서는 Algorithm 1의 반복점과 multiplier가 유계임을 보이고, 점근적으로 KKT conditions으로 수렴함을 증명하며, image recovery를 위한 효율적인 ADMM 업데이트와 stopping criteria를 제시한다.

  • 부록 E: 정리 3의 증명: 증명에서는 U_k, V_k, auxiliary variables, S_k, L_k가 Cauchy sequences임을 보여 Algorithm 1이 유한한 반복 횟수 내에 stopping criterion을 만족함을 보인다.논증은 연속한 차이가 소멸함을 도출하고 이를 모든 원시 수열과 보조 수열에 적용한다.
  • 부록 F: 중지 기준: Algorithm 1의 stopping test는 (15)의 KKT conditions와 이에 동등한 formulation (17)에서 도출되며, factor 및 auxiliary variables와 관련된 residual conditions를 사용한다.부록에서는 stopping conditions를 정의하기 전에 original formulation과 split formulation의 관계를 명시적으로 연결한다.
  • 부록 G: Image Recovery를 위한 Algorithms: matrix completion을 위해 paper는 equivalent auxiliary-variable formulations를 도입하고, D-N 및 F-N penalty가 regularization된 least-squares problems를 위한 efficient ADMM Algorithms 3 and 4를 제안한다.이 formulations는 observed entries P_Ω(D)를 사용하면서 L = UV^T, U = bU, V = bV를 강제한다.
  • Uk+1 및 Vk+1 업데이트:: U 및 V subproblems는 closed-form solutions를 갖는 smooth convex optimizations이며, auxiliary factor updates에는 singular-value thresholding을 사용한다.ADMM scheme는 factor updates, SVT-based nuclear-norm proximal steps, observation-constrained L update를 교대로 수행한다.
  • Uk+1 및 Vk+1 업데이트:: Figure 14에서는 stopping criteria와 relative squared error를 사용하여 matrix ranks 5, 10, and 20에서 (S+L)1/2 및 (S+L)2/3 methods의 convergence behavior를 분석한다.figure는 세 가지 rank 설정에서 두 methods에 사용된 convergence diagnostics를 보고한다.

부록 H: 추가 실험 결과 … Image Inpainting

추가 실험에서 제안 방법들은 빠르게 수렴하고 rank 및 regularization 선택에 강건하며, text removal과 image inpainting에서 비교 방법들을 능가한다. 실험 결과에는 surveillance-video separation과 기존 baseline과의 비교도 포함된다.

  • 부록 H: 추가 실험 결과: 부록에서는 두 제안 방법을 LMaFit, RegL1, Unifying, factEN, RPCA, PSVT, WNNM, LpSq 와 비교한다.제안 방법의 Matlab code도 논문의 download link를 통해 제공된다.
  • 수렴 거동: 5% outlier가 포함된 1,000×1,000 matrix에서 두 방법은 stopping tolerance와 RSE를 빠르게 줄이며, 대체로 50 iteration 이내에 수렴한다.Fig. 14는 iteration에 따른 RSE와 stopping criterion을 추적한다.
  • 강건성: 10% outlier ratio에서 두 방법은 rank 선택 전반에 걸쳐 PSVT, Unifying, LpSq 보다 더 강건하게 우수한 성능을 보인다.Fig. 15(a)는 rank parameter d에 대한 민감도를 평가한다.
  • 강건성: 제안된 rank-estimation procedure로 rank를 추정할 때 두 방법은 regularization parameter가 10^-4에서 100까지 변해도 강건성을 유지한다.Fig. 15(b)는 10% outlier ratio에서 λ에 대한 민감도를 평가한다.
  • Moving Object Detection: moving-object 실험에서는 Bootstrap, Hall, Lobby, Mall, WaterSurface surveillance sequence를 사용하며, 네 sequence에서 background–foreground separation 결과를 제시한다.Table 4는 다섯 sequence를 설명하고, Fig. 17은 Hall, Mall, Lobby, WaterSurface의 separation output을 제시한다.
  • Image Inpainting: 두 제안 방법은 missing-pixel 설정 전반에서 average PSNR과 standard deviation 기준으로 APGL 과 WNNM 을 일관되게 능가하며, observed pixel이 5%일 때 더 큰 이점을 보인다.Fig. 18은 observed-pixel fraction이 95%에서 80%까지일 때의 average PSNR과 standard deviation을 보고한다.
  • Image Inpainting: rank d가 7에서 15까지 변할 때 두 제안 방법은 image inpainting에서 TNNR 보다 더 강건하다.Fig. 19는 average PSNR과 standard deviation을 비교하며, TNNR 은 50회의 independent run에 대해 평균하고 주 비교에는 d=9를 사용한다.
Loading 1810.05186v1…