Accelerating Sparse Recovery by Reducing Chatter

TitleAccelerating Sparse Recovery by Reducing Chatter
Publication TypeJournal Article
Year of Publication2020
AuthorsEmmanouil Daskalakis, Felix J. Herrmann, Rachel Kuske
JournalSIAM Journal on Imaging Sciences
Keywordschatter, inconsistent linear systems, Kacmarz, linearized Bregman dynamical systems, non-smooth dynamics, sparsity promotion

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.


(SIAM Journal on Imaging Sciences)

Citation Keydaskalakis2019SIAMJISasr