## Sparse Signal Recovery via Adaptive Filtering

1  Introduction

Compressive sensing (CS) is a novel technique that enables sampling below Nyquist rate, without (or with little) sacrificing reconstruction quality. It is based on exploiting signal sparsity in some typical domains. One of the main tasks of CS is to design a signal reconstruction algorithm, which aims to find the sparsest solution to an ill-conditioned system,

\label{problem}
{\bf y} = {\bf As},

where ${\bf s}\in\mathbb{R}^N$, ${\bf A}\in\mathbb{R}^{M\times N}, M\ll N$, and ${\bf y}\in\mathbb{R}^M$ denote unknown sparse signal, sensing matrix, and measurement, respectively.

For the first time, we propose an adaptive filtering framework to solve the under-determined equation (\ref{problem}). We find that CS reconstruction problem can be seen as a problem of sparse system identification by making some correspondence. Thus, a variant of Least Mean Square (LMS) algorithm, $l_0$-LMS, which imposes a zero attractor on standard LMS algorithm and has good performance in sparse system identification, is introduced to CS signal reconstruction.

This work is presented in the paper A stochastic gradient approach on compressive sensing signal reconstruction based on adaptive filtering framework, IEEE Journal of Selected topics in Signal Processing, 4(2) 2010 by Jian Jin, Yuantao Gu, and Shunliang Mei.

2  Adaptive Filtering Framework for Sparse Recovery

Adaptive filtering algorithms have been widely used nowadays when the exact nature of a system is unknown or its characteristics are time-varying. The estimation error of the adaptive filter output with respect to the desired signal $d(n)$ is denoted by

$$e(n) = d(n)-{\bf x}^{\rm T}(n){\bf w}(n),$$

where ${\bf w}(n) = \left[w_0(n),w_1(n),\cdots,w_L(n)\right]^{\rm T}$ and ${\bf x}(n) = \left[x(n),x(n-1),\cdots,x(n-L + 1)\right]^{\rm T}$ denote the filter coefficient vector and input vector, respectively, at time instant $n$ and $L$ is the filter length. By minimizing the cost function, the parameters of the unknown system can be identified iteratively.

CS reconstruction problem can be regarded as an adaptive sparse system identification problem by the following correspondences

\begin{array}{cc} \hline \text{adaptive filter} & \text{CS problem} \\\hline {\bf x}(n) & {\bf a}_k \\ {\bf w}(n) & {\bf s} \\ d(n) & y_k \\\hline \end{array}

where ${\bf a}_k$ and $y_k$ denote the $k$th row of $\bf A$ and $y_k$, respectively. Thus (\ref{problem}) can be solved in the framework of adaptive filtering.

When the above adaptive filtering framework is applied to solve CS problem, there may not be enough data to train the filter coefficients into convergence. Thus, the rows of $\bf A$ and the corresponding elements of $\bf y$ are utilized recursively. The procedures using adaptive filtering framework are illustrated in Fig.1.

Figure.1: The framework of adaptive filter to solve sparse signal recovery problem.

To be noticed, if traditional adaptive filtering algorithms are utilized, the solution produced by the proposed framework is definitely not sparse. In fact, we adopte $l_0$-LMS, which is an efficient and robust sparse system identification algorithm. You may please refer $l_0$-LMS for detail.

3  Convergence Analysis

Suppose that ${\bf s}$ is the original signal, and $\hat{\bf s}$ is the reconstruction signal by $l_0$-LMS, the final mean square derivation in steady state is

$${\rm E}\left\{\|\hat{\bf s}-{\bf{s}}\|_2^2\right\} =C\left[2\kappa \left(1-\frac{\mu}{M}\right){\rm E}\left\{(\hat{\bf s}-{\bf{s}})^{\rm T}{\bf g}(\hat{\bf s})\right\}+\kappa^2 {\rm E}\left\{{\bf g}^{\rm T}(\hat{\bf s}){\bf g}(\hat{\bf s})\right\} + \frac{N\mu^2}{M}{\rm E}\left\{v^2\right\}\right],$$

where $\displaystyle C=\frac{M^2}{2 \mu M-(N+2)\mu^2}$. At the same time, in order to guarantee convergence, parameter $\mu$ should satisfy $\displaystyle 0<\mu<\frac{2M}{N+2}$.

4  Extension

Based on the adaptive filtering framework for sparse recovery, we could further replace the gradient descent by projection to solution space and propose Zero-point Attracting Projection (ZAP) algorithm, which is also considered as a generalization of the projected subgradient method. You may please refer ZAP for detail.

5  Numerical Results

Experiment 1. Recovery Performance: To compare with the other algorithms, the average CPU time and MSD are listed in Table 1. Here, the parameter in IRLS is $p=1/2$. It can be seen that the proposed three methods have the least MSD.

$$\text{Table 1: The CPU time and MSD }$$

\begin{array}{ccc} \hline \text{algorithm} & \text{ average CPU time (in sec)} & \text{ MSD }\\\hline \text{BP} & 0.582 & 1.1\times 10^{-2} \\ \text{OMP} & 0.094 & 7.18 \times 10^{-2} \\ \text{IRLS} & 1.836 & 2.31 \times 10^{-3} \\ l1\_ls & 1.436 & 7.68\times 10^{-2} \\ \text{SpaRSA} & 0.221 & 7.25\times 10^{-2} \\ \text{GPSR-BB} & 0.266 & 7.43\times 10^{-2} \\ \text{FPC-AS} & 0.086 & 7.38\times 10^{-2} \\ l_0\text{-LMS} & 1.152 & 3.33\times 10^{-4} \\ l_0\text{-EFWLMS} & 1.544 & 2.44\times 10^{-4} \\ l_0\text{-ZAP} & 0.068 & 2.25\times 10^{-3}\\\hline \end{array}

Experiment 2. Effect of Sparsity on the performance: This experiment explores the answer to this question: with the proposed methods, how sparse a source vector $\bf s$ should be to make its estimation possible under given number of measurements. The results for all seven algorithms are demonstrated in Fig.2. As can be seen, performances of the proposed methods far exceed those of the other algorithms. While all the other algorithms fail when sparsity $K$ is larger than $40$, the three methods proposed succeed until sparsity $K$ reaches $45$. In addition, the proposed three methods have similar good performances.

Figure.2: The probability of exact reconstruction versus sparsity $K$.

Experiment 3. Effect of number of measurements on the performance: This experiment is to investigate the probability of exact recovery when given different numbers of measurements and a fixed signal sparsity $K=50$. The probability curves are shown in Fig.3. Again, it can be seen that the proposed methods have the best performances. While all other algorithms fail when the measurement number $M$ is lower than 230, the proposed methods can still reconstruct exactly the original signal until $M$ reaches 220. Meanwhile, the proposed algorithms have comparable good performances.

Figure.3: The probability of exact reconstruction versus measurement number $M$.

Experiment 4. Robustness against noise: The fourth experiment is to test the effect of signal-to-noise ratio (SNR) on reconstruction performance, where SNR is defined as $\text{SNR}=10\log{\|{\bf As}\|_2^2}/{\|{\bf v}\|_2^2}$. Fig.4 shows that the three new methods have better performances than the other traditional algorithms in all SNR. With the same SNR, the proposed algorithms can acquire small MSDs.

Figure.4: The reconstruction MSD versus SNR.