Adaptive Outlier Pursuit

1-bit Compressive Sensing [1]

    1-bit compressive sensing was firstly introduced and studied by Boufounos and Baraniuk in 2008, and the framework is as follows: $$y=A(x):=\mbox{sign}(\Phi x),$$ where $A(\cdot)$ is a mapping from $\mathbf{R}^N$ to the Boolean cube $\mathcal{B}^M:=\{-1,1\}^M$. We have to recover signals $x\in \sum_K^*:=\{x\in S^{N-1}:\|x\|_0\leq K\}$ where $S^{N-1}:=\{x\in\mathbf{R}^N:\|x\|_2=1\}$ is the unit hyper-sphere of dimension $N$. See more details about 1-bit compressive sensing, please go to http://dsp.rice.edu/1bitCS/.
    The problem we solved by using adaptive outlier pursuit (AOP) is as follows [1]: $$\begin{align} \begin{array}{rl} \min\limits_{x,\Lambda}& \sum\limits_{i=1}^M\Lambda_i\phi(y_{i},(\Phi x)_i)\\ \mbox{subject to: }& \sum\limits_{i=1}^M(1-\Lambda_i)\leq L,\quad \Lambda_i\in \{0,1\}\quad i=1,2,\cdots,M, \\ &\|x\|_2=1,\quad \|x\|_0\leq K, \end{array} \end{align}$$ where $\phi$ is the one-sided $\ell_1$ (or $\ell_2$) objective: $$\begin{align} \phi(x,y)=\left\{ \begin{array}{ll} 0,\ &\text{if}\ x\cdot y>0,\\ |x\cdot y|\ (\mbox{or } |x\cdot y|^2/2),\ &\text{otherwise.} \end{array} \right. \end{align}$$ and $\Lambda$ is used to detect the measurements having sign flips.

    Figure shows the performance comparison of AOP algorithms (AOP, AOP-f, AOP-$\ell_2$ and AOP-$\ell_2$-f) and binary iterative hard thresholding (BIHT and BIHT-$\ell_2$). AOP algorithms outperform BIHT algorithms, and for all AOP algorithms, algorithms based on one-sided $\ell_1$ objective (AOP and AOP-f) have better performance than algorithms with one-sided $\ell_2$ objective. For more details, please see [1].

Matlab Code Download:

Version 1.0

Impulse Noise Removal [2]

Matlab Code Download:

To be uploaded

Matrix Completion [3]

Matlab Code Download:

Version 1.0

Reference

[1] M. Yan, Y. Yang and S. Osher, Robust 1-bit compressive sensing using adaptive outlier pursuit. UCLA CAM report 11-71. (pdf)
[2] M. Yan, Restoration of images corrupted by impulse noise using blind inpainting and $\ell_0$ norm. UCLA CAM report 11-72. (pdf)
[3] M. Yan, Y. Yang and S. Osher, Exact low-rank matrix completion from sparsely corrupted entries via adaptive outlier pursuit. UCLA CAM report 12-34. (pdf)