@article { author = {Khas Ahmadi, Shahriyar and Gholami, Ali}, title = {Seismic velocity analysis using low-rank approximation of the Kernel function and a Butterfly algorithm}, journal = {Journal of the Earth and Space Physics}, volume = {42}, number = {3}, pages = {513-522}, year = {2016}, publisher = {Institute of Geophysics, University of Tehran}, issn = {2538-371X}, eissn = {2538-3906}, doi = {10.22059/jesphys.2016.58907}, abstract = {Velocity analysis is one of the most important step in seismic data processing. It affects not only many processing steps directly and indirectly, but also is known as a primary interpretation of the data. However, it can also be assumed as one of the most time consuming processing step. The conventional velocity analysis method measures the energy amplitude along hyperbolic trajectories within a velocity interval and creates a velocity model. In this procedure, the data from time-offset domain is mapped to time-velocity or time-slowness domain. For a number of , and time, offset and velocity samples respectively,  computations is necessary to obtain a velocity model. However, in the presence of large size data and model parameters, computing the velocity spectrum using conventional method would be a time consuming task. On the other hand, in order to improve the initial velocity model obtained in the processing steps, usually velocity analysis is conducted several times during the processing of the seismic data. Hence, there should be a better way to compute the velocity model in a much less time computation. In this paper, we introduce the Butterfly algorithm for fast computation of hyperbolic Radon transform (HRT), as a kind of time variant operator, with an application in seismic velocity analysis. In seismic data processing, Radon transforms map the overlapping data in seismic gathers to another domain which they can be separated. Among different types of Radon transforms, the HRT has the most similarity to the seismic events and hence, produce the most accurate approximation in the velocity spectrum. However, its time-variant kernel prohibits its fast computation especially for large size data. Unlike time-invariant operators which use the convolution theorem in the Fourier domain to compute the velocity domain for each frequency separately and therefore efficiently, Fourier transform of time-variant operators is a function of both frequency and time and using the convolution theorem is not applicable. The Butterfly algorithm can be used as a fast solver for the Fourier Integral Operators (FIO), so reformulating the HRT integral in the Fourier domain as FIO makes it possible to use this algorithm to overcome the problem of the time-variant kernel. The basis of this solution is the existence of low-rank approximations of the kernel when it is restricted to subdomains in data and model spaces. Subdividing the model and data domain properly to smaller subdomains admits low-rank approximations of the kernel. These low-rank approximations enable us to obtain functions of only one variable, time or frequency, which approximate the kernel. This decoupling of time and frequency variables allows fast computation of the HRT integral. In order to do the subdivision properly, a pair of quad trees, one for each data and model domains, is used to restrict the domains in a level-base structure in which the size of data domain subsets are increasing while the size of model domain subsets are decreasing in each level. The Butterfly algorithm is used to compute the kernel equivalent functions in each level of these quad trees for each subdomain. Finally, at the last level, the Radon panel or velocity model is obtained. The complexity of this method for two dimensional data is  in which depends on data and model variables range. As it was demonstrated in the synthetic and the real numerical examples,  complexity results in reduction of computation time in several orders relative to the conventional method.}, keywords = {Seismic velocity analysis,hyperbolic radon transform,Butterfly algorithm,low-rank approximation}, title_fa = {تحلیل سرعت لرزه‌ای با استفاده از تقریب رتبه کم تابع هسته ای و الگوریتم پروانه‌ای}, abstract_fa = {تحلیل سرعت را می‌توان یکی‌ از اساسی‌‌ترین مراحل پردازش داده‌های لرزه‌ای دانست چرا که نه تنها بسیاری از مراحل پردازش را به صورت مستقیم و غیرمستقیم تحت تاثیر قرار می‌دهد، بلکه می‌توان آن را تفسیری اولیه‌ از داده‌ها تلقی کرد. اما همچنان می‌توان آنرا یکی‌ از زمان‌گیرترین مراحل پردازش نیز دانست. روش معمول تحلیل سرعت با اندازه‌گیری دامنه انرژی در امتداد مسیر‌های هذلولی شکل و به ازای یک بازه از مقادیر سرعت سعی‌ در بدست آوردن یک مدل سرعت دارد که در صورت بزرگ بودن ابعاد داده محاسبه طیف سرعت به وسیله این روش بسیار زمان‌گیر خواهد بود. در این مقاله به معرفی‌ الگوریتم پروانه‌ای (Butterfly Algorithm) در حل سریع تبدیل رادون هذلولی به منظور تحلیل سرعت داده‌های لرزه‌ای می‌پردازیم. اساس این الگوریتم تغییر رابطه تبدیل رادون هذلولی به صورت یک عملگر انتگرال فوریه و سپس بدست آوردن تقریب‌هایی‌ با رتبه پائین (low-rank approximation) برای کرنل مسئله خواهد بود. همگرایی این روش برای داده‌های دو بعدی برابر خواهد بود که به بازه تغییرات متغیرهای داده و مدل بستگی دارد. همانطور که در مثال‌های عددی غیرواقعی و واقعی نشان داده خواهد شد، این همگرایی باعث کاهش زمان محاسبه مدل سرعت تا چندین برابر نسبت به روش معمول می‌شود.}, keywords_fa = {تحلیل سرعت لرزه ای,تبدیل رادون هذلولی,الگوریتم پروانه‌ای,تقریب رتبه پایین}, url = {https://jesphys.ut.ac.ir/article_58907.html}, eprint = {https://jesphys.ut.ac.ir/article_58907_9d5f07c099a2532ae07de25f807236fa.pdf} }