admm演算法去中心

1. ADMM演算法matlab實現

Basis pursuit解決基本方法的，例子：

Generate problem data
rand('seed', 0);
randn('seed', 0);

n = 30;
m = 10;
A = randn(m,n);

x = sprandn(n, 1, 0.1*n);
b = A*x;

xtrue = x;

Solve problem
[x history] = basis_pursuit(A, b, 1.0, 1.0);

2. 什麼是基追蹤演算法

基追蹤（basis pursuit）演算法是一種用來求解未知參量L1范數最小化的等式約束問題的演算法。
基追蹤是通常在信號處理中使用的一種對已知系數稀疏化的手段。將優化問題中的L0范數轉化為L1范數的求解就是基追蹤的基本思想。
比如我原先有一個優化問題：
min ||x||_0（就是L0范數的最小值）subject to y=Ax。
這個||x||_0，就是表示x中有多少個非零元素；那麼我們要求min ||x||_0，就是想知道含有最多0元素的那個解x是什麼。
但是呢，L0范數有非凸性，不怎麼好求解，這時我們就轉而求解L1范數的優化問題。
那麼，基追蹤演算法就是轉而求解
min||x||_1（就是L1范數的最小值）subject to||y-Ax||_2=0（2范數）
這個||x||_1，就是x的絕對值；那麼我們要求min||x||_1，就是求絕對值最小的那個解x是什麼。
更通俗一點來講，比如我要求一個線性方程組
Ax=b
x就是我們要求的未知量。這個A矩陣不是個方陣，是個欠定矩陣，那麼就導致這個線性方程組會有若干組解。那麼我們到底要哪組解好呢？
如果在一般情況下，可以直接用最小二乘法來獲得一組最小二乘解，就是x=(A'A)^(-1)A'b。但是我們現在利用基追蹤，就是想要來獲得一組含0元素最多的解。
那麼我們為什麼希望我們獲得的解裡面0元素越多越好呢？這就要談到「稀疏化」了。所謂稀疏化，就是希望我獲得的這個解放眼望去全是0，非0元素稀稀疏疏的。這樣在大樣本或者高維數的情況下，計算速度不會太慢，也不會太占計算機的內存。當然，所謂稀疏解是有一定精度誤差的，想要提高計算速度，必然會損失一點精度，這是不可避免的。
可以參考：Stephen Byod 的<Distributed Optimization and Statistical Learning via the ADMM>41頁