More Like this

1. Anderson acceleration for seismic inversion

   https://doi.org/10.1190/geo2020-0462.1  

   Yang, Yunan ( January 2021 , GEOPHYSICS)

   null (Ed.)

   State-of-the-art seismic imaging techniques treat inversion tasks such as full-waveform inversion (FWI) and least-squares reverse time migration (LSRTM) as partial differential equation-constrained optimization problems. Due to the large-scale nature, gradient-based optimization algorithms are preferred in practice to update the model iteratively. Higher-order methods converge in fewer iterations but often require higher computational costs, more line-search steps, and bigger memory storage. A balance among these aspects has to be considered. We have conducted an evaluation using Anderson acceleration (AA), a popular strategy to speed up the convergence of fixed-point iterations, to accelerate the steepest-descent algorithm, which we innovatively treat as a fixed-point iteration. Independent of the unknown parameter dimensionality, the computational cost of implementing the method can be reduced to an extremely low dimensional least-squares problem. The cost can be further reduced by a low-rank update. We determine the theoretical connections and the differences between AA and other well-known optimization methods such as L-BFGS and the restarted generalized minimal residual method and compare their computational cost and memory requirements. Numerical examples of FWI and LSRTM applied to the Marmousi benchmark demonstrate the acceleration effects of AA. Compared with the steepest-descent method, AA can achieve faster convergence and can provide competitive results with some quasi-Newton methods, making it an attractive optimization strategy for seismic inversion. 

   more » « less
2. Effective Dimension Adaptive Sketching Methods for Faster Regularized Least-Squares Optimization

   Lacotte, Jonathan ; Pilanci, Mert ( January 2020 , 34th Conference on Neural Information Processing Systems (NeurIPS 2020))

   We propose a new randomized algorithm for solving L2-regularized least-squares problems based on sketching. We consider two of the most popular random embeddings, namely, Gaussian embeddings and the Subsampled Randomized Hadamard Transform (SRHT). While current randomized solvers for least-squares optimization prescribe an embedding dimension at least greater than the data dimension, we show that the embedding dimension can be reduced to the effective dimension of the optimization problem, and still preserve high-probability convergence guarantees. In this regard, we derive sharp matrix deviation inequalities over ellipsoids for both Gaussian and SRHT embeddings. Specifically, we improve on the constant of a classical Gaussian concentration bound whereas, for SRHT embeddings, our deviation inequality involves a novel technical approach. Leveraging these bounds, we are able to design a practical and adaptive algorithm which does not require to know the effective dimension beforehand. Our method starts with an initial embedding dimension equal to 1 and, over iterations, increases the embedding dimension up to the effective one at most. Hence, our algorithm improves the state-of-the-art computational complexity for solving regularized least-squares problems. Further, we show numerically that it outperforms standard iterative solvers such as the conjugate gradient method and its pre-conditioned version on several standard machine learning datasets. 

   more » « less
3. Effective Dimension Adaptive Sketching Methods for Faster Regularized Least-Squares Optimization

   Lacotte, Jonathan ; Pilanci, Mert ( January 2020 , Advances in neural information processing systems)

   null (Ed.)

   We propose a new randomized algorithm for solving L2-regularized least-squares problems based on sketching. We consider two of the most popular random embeddings, namely, Gaussian embeddings and the Subsampled Randomized Hadamard Transform (SRHT). While current randomized solvers for least-squares optimization prescribe an embedding dimension at least greater than the data dimension, we show that the embedding dimension can be reduced to the effective dimension of the optimization problem, and still preserve high-probability convergence guarantees. In this regard, we derive sharp matrix deviation inequalities over ellipsoids for both Gaussian and SRHT embeddings. Specifically, we improve on the constant of a classical Gaussian concentration bound whereas, for SRHT embeddings, our deviation inequality involves a novel technical approach. Leveraging these bounds, we are able to design a practical and adaptive algorithm which does not require to know the effective dimension beforehand. Our method starts with an initial embedding dimension equal to 1 and, over iterations, increases the embedding dimension up to the effective one at most. Hence, our algorithm improves the state-of-the-art computational complexity for solving regularized least-squares problems. Further, we show numerically that it outperforms standard iterative solvers such as the conjugate gradient method and its pre-conditioned version on several standard machine learning datasets. 

   more » « less
4. Efficient Globally Convergent Stochastic Optimization for Canonical Correlation Analysis

   Wang, Weiran ; Wang, Jialei ; Garber, Dan ; Srebro, Nati ( January 2016 , Advances in Neural Information Processing Systems 29 (NIPS 2016))

   We study the stochastic optimization of canonical correlation analysis (CCA), whose objective is nonconvex and does not decouple over training samples. Although several stochastic gradient based optimization algorithms have been recently proposed to solve this problem, no global convergence guarantee was provided by any of them. Inspired by the alternating least squares/power iterations formulation of CCA, and the shift-and-invert preconditioning method for PCA, we propose two globally convergent meta-algorithms for CCA, both of which transform the original problem into sequences of least squares problems that need only be solved approximately. We instantiate the meta-algorithms with state-of-the-art SGD methods and obtain time complexities that significantly improve upon that of previous work. Experimental results demonstrate their superior performance. 

   more » « less
5. Correlation-based full-waveform shear wave elastography

   https://doi.org/10.1088/1361-6560/acc37b  

   Elmeliegy, Abdelrahman M. ; Guddati, Murthy N. ( May 2023 , Physics in Medicine & Biology)

   Objective. With the ultimate goal of reconstructing 3D elasticity maps from ultrasound particle velocity measurements in a plane, we present in this paper a methodology of inverting for 2D elasticity maps from measurements on a single line.Approach. The inversion approach is based on gradient optimization where the elasticity map is iteratively modified until a good match is obtained between simulated and measured responses. Full-wave simulation is used as the underlying forward model to accurately capture the physics of shear wave propagation and scattering in heterogeneous soft tissue. A key aspect of the proposed inversion approach is a cost functional based on correlation between measured and simulated responses.Main results. We illustrate that the correlation-based functional has better convexity and convergence properties compared to the traditional least-squares functional, and is less sensitive to initial guess, robust against noisy measurements and other errors that are common in ultrasound elastography. Inversion with synthetic data illustrates the effectiveness of the method to characterize homogeneous inclusions as well as elasticity map of the entire region of interest.Significance. The proposed ideas lead to a new framework for shear wave elastography that shows promise in obtaining accurate maps of shear modulus using shear wave elastography data obtained from standard clinical scanners.

    

   more » « less