2025/05/14 by Cheng, Siu-Wing, Wong, Man Ting
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2505.09370
We propose a dynamic working set method (DWS) for the problem min_\mathttx ∈ ℝn (1)/(2)‖\mathttAx-\mathttb‖2 + η‖\mathttx‖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 ‖b‖=1. Let s be the number of non-zeros in the unknown signal. We prove that for any given ε > 0, DWS reaches a solution with an additive error ε/η2 such that each call of the solver uses only O((1)/(ε)slog s log(1)/(ε)) variables, and each intermediate solution has O((1)/(ε)slog slog(1)/(ε)) non-zero coordinates.