@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}
}
@article {li2015GEOPmgn,
	title = {Modified Gauss-Newton full-waveform inversion explained{\textendash}-why sparsity-promoting updates do matter},
	journal = {Geophysics},
	volume = {81},
	number = {3},
	year = {2016},
	note = {(Geophysics)},
	month = {05},
	pages = {R125-R138},
	abstract = {Full-waveform inversion can be formulated as a nonlinear least-squares optimization problem. This non-convex problem can be extremely computationally expensive because it requires repeatedly solving large linear systems that correspond to discretized partial differential equations. Randomized subsampling techniques allow us to work with small subsets of (monochromatic) source experiments, reducing the computational cost. However, this subsampling weakens subsurface illumination and introduces subsampling related incoherent artifacts. These subsampling-related artifacts{\textendash}-in conjunction with local minima that are known to plague full-waveform inversion{\textendash}-motivate us to come up with a technique to "regularize" this problem. Following earlier work, we take advantage of the fact that curvelets represent subsurface models and perturbations parsimoniously. At first impulse promoting sparsity on the model directly seems the most natural way to proceed, but we will demonstrate that in certain cases it can be advantageous to promote sparsity on the Gauss-Newton updates instead. While constraining the one-norm of the descent directions does not change not change the underlying full-waveform inversion objective, the constrained model updates remain descent directions, remove subsampling-related artifacts and improve the overall inversion result. We empirically observe this phenomenon in situations where the different model updates occur at roughly the same locations in the curvelet domain. We further investigate and analyze this phenomenon, where nonlinear inversions benefit from sparsity-promoting constraints on the updates, by means of a set of carefully selected examples including phase retrieval and full-waveform inversion. In all cases, we observe a faster decay of the residual and model error as a function of the number of iterations.},
	keywords = {Full-waveform inversion, Gauss-Newton method, sparsity promotion},
	doi = {10.1190/geo2015-0266.1},
	url = {https://slim.gatech.edu/Publications/Public/Journals/Geophysics/2016/li2015GEOPmgn/li2015GEOPmgn.pdf},
	author = {Xiang Li and Ernie Esser and Felix J. Herrmann}
}
@conference {witte2015IIPFWIspl,
	title = {Sparsity-promoting least-square migration with linearized Bregman and compressive sensing},
	booktitle = {Inaugural Full-Waveform Inversion Workshop},
	year = {2015},
	note = {(Natal, Brazil)},
	month = {08-09},
	abstract = {We present a novel adaptation of a recently developed relatively simple iterative algorithm to solve large-scale sparsity-promoting optimization problems. Our algorithm is particularly suitable to large-scale geophysical inversion problems, such as sparse least-squares reverse-time migration or Kirchoff migration since it allows for a tradeoff between parallel computations, memory allocation, and turnaround times, by working on subsets of the data with different sizes. Comparison of the proposed method for sparse least-squares imaging shows a performance that rivals and even exceeds the performance of state-of-the art one-norm solvers that are able to carry out least-squares migration at the cost of a single migration with all data.},
	keywords = {Bregman, compressed sensing, FWI, migration, sparsity promotion, time domain},
	presentation = {https://slim.gatech.edu/Publications/Public/Conferences/IIPFWI/witte2015IIPFWIspl/witte2015IIPFWIspl_pres.pdf},
	author = {Philipp A. Witte and Ning Tu and Ernie Esser and Mengmeng Yang and Mathias Louboutin and Felix J. Herrmann}
}
@techreport {tschannen2014tdl,
	title = {Time domain least squares migration and dimensionality reduction},
	number = {TR-EOAS-2014-9},
	year = {2014},
	month = {06},
	institution = {UBC},
	abstract = {Least-squares seismic migration (LSM) is a wave equation based linearized inversion problem relying on the minimization of a least-squares misfit function, with respect to the medium perturbation, between recorded and modeled wavefields. Today{\textquoteright}s challenges in Hydrocarbon ex- ploration are to build high resolution images of more and more complicated geological reservoirs, which requires to handle very large systems of equations. The extreme size of the problem com- bined with the fact that it is ill-conditioned make LSM not yet feasible for industrial purposes. To overcome this "curse of dimensionality", dimension reduction and divide-and-conquer tech- niques that aim to decrease the computation time and the required memory, while conserving the image quality, have recently been developed. By borrowing ideas from stochastic optimiza- tion and compressive sensing, the imaging problem is reformulated as an L1-regularized, sparsity promoted LSM. The idea is to take advantage of the compressibility of the model perturbation in the curvelet domain and to work on series of smaller subproblems each involving a small ran- domized subset of data. We try two different subset sampling strategies, artificial randomized simultaneous sources experiments ("supershots") and drawing sequential shots firing at random source locations. These subsets are changed after each subproblem is solved. In both cases we obtain good migration results at significantly reduced computational cost. Application of these methods to a complicated synthetic model yields to encouraging results, underlining the usefulness of sparsity promotion and randomization in time stepping formulation.},
	keywords = {Compressive Sensing, sparsity promotion, Stochastic optimization, Wave equation migration},
	url = {https://slim.gatech.edu/Publications/Public/TechReport/2014/tschannen2014tdl/tschannen2014tdl.pdf},
	author = {Valentin Tschannen and Zhilong Fang and Felix J. Herrmann}
}
