A Dynamic Working Set Method for Compressed Sensing

Abstract

We propose a dynamic working set method (DWS) for the problem ${\min }_{\mathtt{x}\in {\mathbb{R}}^n}\frac{1}{2}\Vert \mathtt{Ax}-\mathtt{b}{\Vert }^2+\hat{I}\cdot \Vert \mathtt{x}{\Vert }_1$ that arises from compressed sensing. DWS manages the working set while iteratively calling a regression solver to generate progressively better solutions. Our experiments show that DWS is more efficient than other state-of-the-art software in the context of compressed sensing. Scale space such that $\Vert b\Vert =1$. Let $s$ be the number of non-zeros in the unknown signal. We prove that for any given $\epsilon >0$, DWS reaches a solution with an additive error $\epsilon /\hat{I}{\cdot }^2$ such that each call of the solver uses only $O(\frac{1}{\epsilon }s\log s\log \frac{1}{\epsilon })$ variables, and each intermediate solution has $O(\frac{1}{\epsilon }s\log s\log \frac{1}{\epsilon })$ non-zero coordinates.