當前位置：首頁 > 编程资源 > 编程问答 >内容正文

编程问答

论文笔记-Augmented Lagrange Multiplier Method for Recovery of Low-Rank Matrices

發布時間：2025/3/20 编程问答 47 豆豆

生活随笔收集整理的這篇文章主要介紹了论文笔记-Augmented Lagrange Multiplier Method for Recovery of Low-Rank Matrices 小編覺得挺不錯的,現在分享給大家,幫大家做個參考.

論文題目：The Augmented Lagrange Multiplier Method for Exact Recovery of Corrupted Low-Rank Matrices

Abstract

1.Robust PCA問題： recovering a?low-rank?matrix with an?unknown fraction?of its entries being?arbitrarily corrupted.

RPCA問題是一個凸優化問題：minimizes a combination of the?nuclear norm and the L1-norm

2.本文提出一種更好更快的求解RPCA問題的算法：即用 Augmented Lagrange multipliers (ALM) 增廣拉格朗日乘子法求解。

比之前用的APD（accelerated proximal gradient）快了5倍，精度也提高了，內存需求也減少了。

3.ALM也用于了 tensor completion

4.Matlab代碼：?http://perception.csl.illinois.edu/matrix-rank/home.html

Introduction

1.PCA assumes that the given high-dimensional data lie near a much lower-dimensional linear subspace

2.PCA的推導方式挺多的，常見的是方差角度的，這里是另一個角度：

D為 m*n 原數據，A為低秩矩陣，E為它們的差，r 遠小于 min(m,n) 為目標子空間維數，目標函數中的?F 范數對應于數據被獨立同分布高斯噪聲腐蝕的假設。

問題可通過對 D 做 SVD ，取前 r 列向量，再投影。

3.當數據被加性高斯噪聲腐蝕時，PCA得到效果很好，在噪聲幅值不大的情況下，效果也不錯。

如果 A 被任意腐蝕（即E任意大），PCA恢復出的 A 可以任意差。

4.RPCA:

[1]提出當 E 足夠稀疏時（相對于A），通過求解如下凸優化問題，可以精確恢復出 A：

第一項為 A 的 nuclear norm （the sum of its singular values）,第二項為 L1 范數(the sum of the absolute value of matrix entries)，λ is a positive weighting parameter

RPCA對 large errors or outliers,gross corruption 效果也很好，背景建模的應用如下：

5. （2）再轉化為一個可以看作普通凸優化問題，用任何 interior point solver 求解，推薦 CVX 工具箱 [2]

但是內點法在小矩陣上收斂很快，但是矩陣在 70*70 以上就很慢了；慢是由于內點法rely on second-order information of the objective function.

iterative thresholding （IT）方法求解：

對于目標函數中的 L1-norm 和：有 [3,4,5,6] 等；

對于目標函數中的 nuclear norm 有 [7] 。

[1] （[1] 同名有兩個版本一個用的IT，一個用的[APG]）中用了 IT （結合了[3]和[7]）；但是收斂很慢，m=800 時，要跑 8 小時。

[8] 提出了2個算法：

The first one is an accelerated proximal gradient (APG) algorithm applied to the primal, which is a direct application of the FISTA framework introduced by [4], coupled with a fast continuation technique(Similar techniques have been applied to the matrix completion problem by [9].); The second one is a?gradient-ascent?algorithm applied to the?dual?of the problem (2). From simulations with matrices of dimension up to m = 1000, both methods are at least 50 times faster than the iterative thresholding method

6. 本文用 ALM 做 matrix recovery 。EALM Q-linear convergence speed while the APG is in theory only sub-linear.? IALM required numbers of partial SVDs is significantly less, at least five times faster than APG. and its precision is also higher.

the number of non-zeros in E computed by IALM is much more accurate than that by APG,which?often leave many small non zero terms in E.

Previous Algorithms for Matrix Recovery

1.The Iterative Thresholding Approach [1]

[1] 用 IT 求解 (2) 的松弛凸優化：

τ is a large positive scalar 后面加入的倆項對目標函數的影響就小了，使用拉格朗日乘子：

Then the IT approach updates A E Y iteratively ：

1.固定 Y ，最小化 L（A,E,Y）更新 A 和 E

2. 用 A+E=D 的限制來更新 Y （對Y求導，梯度下降）

soft-thresholding（shrinkage）operator：ε>0

由[7,3]可知：?這里很重要，很多文章都用，一個求解核范數，一個求解L1范數。

USVT 為 W 的SVD

對（4）中 A , E 分別優化，把內積和F范數合并成F范數，然后用（6）求解，具體不推了，應該能看出來。

盡管IT非常簡潔且理論證明完善，但需要迭代很多次才能收斂，Y的學習率也不容易確定。

The Accelerated Proximal Gradient Approach

APG理論見[4,10,11]，[4]介紹了 PG 到 APG 到 APGL 3個算法。

下面算法中 4,7?由公式（8）推出，注意對 A 求min時，E，Y的項都可以丟掉，對E求 min 時也一樣，（8）中第2項和第3項可以和為（6）中兩個公式的第二項的形式，然后再用（6）求解，就推出了下面算法：

The Dual Approach

先了解下對偶范數：

dual norm （對偶范數）：

sup{}是上確界，基本可以看成max，與max的區別就是，集合里可能沒有上界值。

某范數的對偶范數的對偶范數就是它本身。

幾個常見對偶范數：

1. F 范數的對偶范數還是 F 范數：

2. L1 范數的對偶范數是 L ∞ 范數（元素中絕對值最大值），下面這個算法也用到了，注意公式（10）的 max（）中第二個 L ∞范數就是對應的（2）中的 L1 范數，λ也對應（2）中λ！

3. 譜范數（由p-2范數誘導出的矩陣2范數，最大奇異值）的對偶范數是核范數，同樣下面算法也用到了，公式（10）max（）中第一項

[8] 中除了APG外第二種方法是求解（2）的對偶問題：（FaLRTC 張量填充算法也用到了對偶范數），注意（10）中 max（）中第一項是譜范數，由于譜范數是p=2的誘導范數，所以右下角寫的2！

?The Methods of Augmented Lagrange Multipliers

ALM簡述：比拉格朗日乘子法多了（12）中的第3項

ALM優點：

1.收斂性：

當 {u_k} 為遞增序列，f ，h 為 continuously di?erentiable 時：

{u_k} is bounded ： Q-linearly

{u_k} is unbounded ：super-Q-linearly

各種收斂定義：https://en.wikipedia.org/wiki/Rate_of_convergence

2.算法3中第4行 Y_k 的最優更新步長（學習率）可以證明設為 u_k 最好，調參更容易了。

3.ALM收斂到精確解，而之前的 IT 和 APG 都是近似解。

Two ALM Algorithms for Robust PCA (Matrix Recovery)

對（2）使用ALM：

注意幾點：

1.Y的初值設置

2.由于（2） non-smooth ，所以 ALM 的收斂性結論不能直接用，但是論文證明了結論依然成立。

3. u_k 增加越快，收斂越快；但是 u_k 過大，算法4中第3，6行求 A E 的兩個子問題中 IT 就會變慢，所以有個折中。

下面給出 EALM：

注意到算法4中第5行，while，反復對A E求min，得出第3行結果，這個過程算法執行 SVD 的次數太多，所以改進：

其實不需要 while 只需要一次就好（感覺其實本質就是 Alternative direction method），得到 IALM：

文章證明了 IALM 也能收斂到最優解，但是收斂率的證明比較困難，但是實驗證明還是二次收斂，但當 u_k 增長過快時，就不能保證收斂到最優解了，所以 u_k 的調參是一個權衡，詳見文章 P9 Theorem 2.

An ALM Algorithm for Matrix Completion

之前做的矩陣恢復，做矩陣填充也可以。

矩陣填充優化問題：

把矩陣填充問題表示成類似（2）的形式：

partial augmented Lagrangian function：

for updating E the constraint?（（15）中第二個約束） should be enforced when minimizing （16）

與之前一模一樣了，算法如下：

由于第7行，所以 Y 在需要填充的位置上永遠為 0.

References

[1] Wright, J., Ganesh, A., Rao, S., Ma, Y.: Robust principal component analysis: Exact recovery of corrupted low-rank matrices via convex optimization. submitted to Journal of the ACM (2009)

[2] Grant, M., Boyd, S.: CVX: Matlab software for disciplined convex programming (web page and software).http://stanford.edu/?boyd/cvx?(2009)

[3] Yin, W., Hale, E., Zhang, Y.: Fixed-point continuation for L1-minimization: methodologyand convergence. preprint (2008)

[4] Beck, A., Teboulle, M.: A fast iterative shrinkage-thresholding algorithm for linear inverse problems. SIAM Journal on Imaging Sciences 2(1), 183{202 (2009)

[5] Yin, W., Osher, S., Goldfarb, D., Darbon, J.: Bregman iterative algorithms for L1-minimization with applications to compressed sensing. SIAM Journal on Imaging Sciences
1(1), 143{168 (2008)

[6] Cai, J.F., Osher, S., Shen, Z.: Linearized Bregman iterations for compressed sensing. Math.Comp. 78, 1515{1536 (2009)

[7] Cai, J., Candμes, E., Shen, Z.: A singular value thresholding algorithm for matrix completion. preprint, code available athttp://svt.caltech.edu/code.html?(2008)

[8] Lin, Z., Ganesh, A., Wright, J., Wu, L., Chen, M., Ma, Y.: Fast convex optimization algorithms for exact recovery of a corrupted low-rank matrix. SIAM J. Optimization

[9] Toh, K.C., Yun, S.: An accelerated proximal gradient algorithm for nuclear norm regularized least squares problems. preprint (2009)

[10] Tseng, P.: On accelerated proximal gradient methods for convex-concave optimization.submitted to SIAM Journal on Optimization (2008)
[11] Wright, J., Ganesh, A., Rao, S., Peng, Y., Ma, Y.: Robust principal component analysis: Exact recovery of corrupted low-rank matrices via convex optimization. In: Proceedings of Advances in Neural Information Processing Systems (2009)

總結

以上是生活随笔為你收集整理的论文笔记-Augmented Lagrange Multiplier Method for Recovery of Low-Rank Matrices的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。