@article {daskalakis2019SIAMJISasr, title = {Accelerating Sparse Recovery by Reducing Chatter}, journal = {SIAM Journal on Imaging Sciences}, volume = {13}, number = {3}, year = {2020}, note = {(SIAM Journal on Imaging Sciences)}, month = {07}, pages = {1211{\textendash}1239}, abstract = {Compressive Sensing has driven a resurgence of sparse recovery algorithms with l_1-norm minimization. While these minimizations are relatively well understood for small underdetermined, possibly inconsistent systems, their behavior for large over-determined and inconsistent systems has received much less attention. Specifically, we focus on large systems where computational restrictions call for algorithms that use randomized subsets of rows that are touched a limited number of times. In that regime, l_1-norm minimization algorithms exhibit unwanted fluctuations near the desired solution, and the Linear Bregman iterations are no exception. We explain this observed lack of performance in terms of chatter, a well-known phenomena observed in non-smooth dynamical systems, where intermediate solutions wander between different states stifling convergence. By identifying chatter as the culprit, we modify the Bregman iterations with chatter reducing adaptive element-wise step lengths in combination with potential support detection via threshold crossing. We demonstrate the performance of our algorithm on carefully selected stylized examples and a realistic seismic imaging problem involving millions of unknowns and matrix-free matrix-vector products that involve expensive wave-equation solves.}, keywords = {chatter, inconsistent linear systems, Kacmarz, linearized Bregman dynamical systems, non-smooth dynamics, sparsity promotion}, doi = {10.1137/19M129111X}, url = {https://slim.gatech.edu/Publications/Public/Journals/SIAMJournalOnImagingSciences/2020/daskalakis2019SIAMJISasr/daskalakis2019SIAMJISasr.pdf}, author = {Emmanouil Daskalakis and Felix J. Herrmann and Rachel Kuske} }