Total: 1
We propose a dynamic working set method (DWS) for the problem min 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 \|b\|=1. Let s be the number of non-zeros in the unknown signal. We prove that for any given \varepsilon > 0, DWS reaches a solution with an additive error \varepsilon/\eta^2 such that each call of the solver uses only O(\frac{1}{\varepsilon}s\log s \log\frac{1}{\varepsilon}) variables, and each intermediate solution has O(\frac{1}{\varepsilon}s\log s\log\frac{1}{\varepsilon}) non-zero coordinates.