---

• 压缩感知系列博客：
• 压缩感知入门①从零开始压缩感知
• 压缩感知入门②信号的稀疏表示和约束等距性
• 压缩感知入门③基于ADMM的全变分正则化的压缩感知重构算法
• 压缩感知入门④基于总体最小二乘的扰动压缩感知重构算法

---

1. Problem Formulation

---

考虑一个线性方程组求解问题：
$$Ax=b\text{\hspace{1em}(1)}$$

其中，$A\in {\mathbb{R}}^{m\times n}$，$x\in {\mathbb{R}}^{n\times 1}$，$b\in {\mathbb{R}}^{m\times 1}$且$m\ll n$

这是一个欠定方程组，即该问题有无穷多解，那么如何添加一些约束，使得能够在这组无穷多解中找到一个最优的呢？

试试考虑一下稀疏性。

什么是稀疏性？通俗来讲，如果一个信号中仅有少量的大值，其余都是零，那么这个信号是稀疏的（或者说仅有少量的值相对于其他的值明显大得多）。稀疏性意味着信号是可压缩的，因为在数据表达时只需要考虑大值信号的位置和大小。

回到这个欠定方程组求解问题，如果待求解信号$x$是稀疏的，那么无穷多组解中找到最稀疏的那个解即为所求。该问题可以表达为一个$l_0$范数优化问题，即
$$min\parallel x{\parallel }_{0}s.t.Ax=b\text{\hspace{1em}(2)}$$

其中$\parallel x{\parallel }_0$表示$x$的0范数，即为$x$中非零值的个数，该问题是一个NP-hardness问题¹，求解相当困难。

幸运的是，当$A$与$b$满足RIP条件时²，问题 (2) 可以等价于求解一个$l_1$范数优化问题，即
$$min\parallel x{\parallel }_{1}s.t.Ax=b\text{\hspace{1em}(3)}$$

其中$\parallel x{\parallel }_1$表示$x$的1范数，即为$x$中元素的绝对值之和。这是一个$l_1$范数的凸优化问题(基追踪问题)，存在最优解。

$l_1$范数优化问题可以转化为一个标准的线性规划问题进行求解³，即
$$min{c}^T\theta s.t.\Phi \theta =s\text{\hspace{1em}(5)}$$

其中$c^T=[1,1,...,1]\in {\mathbb{R}}^{1\times 2n},\theta =[u;v]\in {\mathbb{R}}^{2n\times 1},\Phi =[A,-A]\in {\mathbb{R}}^{m\times 2n},s=b\in {\mathbb{R}}^{m\times 1}$

最后$x=u-v$

2. Simulation

---

3. Algorithm

---

clear
close all
M = 40;
N = 100;
K = 10;
x = zeros(N,1);
ind = randperm(N);  
x(ind(1:K)) = 10*randn(K,1);
A = randn(M,N);
b = A * x;
%% signal reconstruction
x0 = CS_linprog(A,b);
%% error analysis
plot(x);hold on
plot(x0,'*')

function x=CS_linprog(A,b)len=size(A,2);Phi=[A,-A];s=b;c=ones(1,2*len);lb=zeros(1,2*len);theta = linprog(c,[],[],Phi,s,lb);x=theta(1:len)-theta(len+1:2*len);
end

https://github.com/dwgan/Compressed-Sensing-Basic-Pursuit.git

参考⁴

---

1. https://www.jianshu.com/p/58fea4d97b2a ↩︎

2. D. L. Donoho, “Compressed sensing,” IEEE Transactions on Information Theory, vol. 52, no. 4, pp. 1289-1306, 2006, doi: 10.1109/TIT.2006.871582. ↩︎

3. S. S. Chen, D. L. Donoho, and M. A. Saunders, “Atomic Decomposition by Basis Pursuit,” SIAM Review, vol. 43, no. 1, pp. 129-159, 2001/01/01 2001, doi: 10.1137/S003614450037906X. ↩︎

4. https://blog.csdn.net/jbb0523/article/details/51986554#t5 ↩︎