Fast and robust solution techniques for large scale linear least squares problems
Büyük ölçekli doğrusal en küçük kareler problemleri için hızlı ve gürbüz çözüm yöntemleri
- Tez No: 633368
- Danışmanlar: PROF. DR. ORHAN ARIKAN
- Tez Türü: Yüksek Lisans
- Konular: Elektrik ve Elektronik Mühendisliği, Electrical and Electronics Engineering
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2020
- Dil: İngilizce
- Üniversite: İhsan Doğramacı Bilkent Üniversitesi
- Enstitü: Mühendislik ve Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Elektrik-Elektronik Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Elektrik Elektronik Mühendisliği Bilim Dalı
- Sayfa Sayısı: 136
Özet
Büyük ölçekli ve doğrusal en küçük kareler problemleri için bir grup çözücü olan Momentum Yinelemeli Hessian Krokileme (M-IHS) teknikleri önerilmiş ve analiz edilmiştir. Önerilen M-IHS teknikleri, Ağır Top Hızlandırmasının Yinelemeli Hessian Krokileme algoritmasına dahil edilmesiyle elde edilir ve rastlantısal ön koşullandırma teknikleri üzerinde önemli gelişmeler sağlar. Önerilen teknikler, yinelemelerle birlikte yaklaşık çözücüler kullanarak tüm matris ayrışmalarından ve ters çevirmelerden kaçınabilir, bu nedenle önerilen yöntemler büyük ölçekli problemlerde Blendenpik ve LSRN gibi alternatif çözücülere göre daha avantajlıdır. Chebyshev Yarı-iterasyonlarına benzer şekilde, M-IHS varyantları da yinelemeler sırasında herhangi bir iç çarpım kullanmaz, dolayısıyla hiyerarşik veya dağıtılmış bellek sistemlerinde iç çarpım hesaplamalarının neden olduğu senkronizasyon adımlarını ortadan kaldırır ve önerilen M-IHS teknikleri Chebyshev Yarı-iterasyonlarına dayalı çözümlerden daha hızlı bir şekilde çözüme yakınsar. Çeşitli rasgele dağılımlar için gerekli olan en küçük çizim boyutu, önerilen tekniklerin hata analizleri yoluyla belirlenmiştir. Önerilen M-IHS teknikleri çözüm yaklaşıklaması üretmek için, daha önce önerilen yaklaşımların aksine, katsayı matrisinin kertesinden her zaman daha küçük olan istatistiksel boyutla orantılı bir kroki matris boyutu kullanabilir. Tüm bunlara ek olarak, l2-norm düzenlileştirme parametresinin bilinmediği durumlarda, bu parametreyi M-IHS tekniklerinin yinelemeleri sırasında tahmin etmek için melez şemalar önerilmiştir. Önerilen Melez M-IHS şemaları düzenlileştirme parametresini, gerekirci projeksiyonlar yoluyla elde ettiği Krylov Altuzayları'nı kullanarak tahmin eden geleneksel melez yöntemlerden farklı olarak, rastgele projeksiyonlarla oluşturduğu daha düşük boyutlu alt problemlerden tahmin eder. Melez M-IHS yinelemeleri sırasında ortaya çıkan bu düşük boyutlu alt problemler, Newton alt sistemlerine yakın yaklaşıklamalar olduğundan ve bu alt problemlerin çözümlerinin doğruluğu katlanarak arttığından, bu alt problemlerden tahmin edilen düzenlileştirme parametreleri hızla tam problem kullanılarak tahmin edilen parametrelere yakınsar. Farklı gürültü seviyelerinde yapılan çeşitli sayısal deneylerde, Melez M-IHS şemaları, doğrudan yöntemler aracılığıyla tam problemden tahmin edilen düzenlileştirme parametrelerinden daha az hataya sebep olan parametreleri ve bu parametrelere denk gelen çözümleri geleneksel melez yöntemlerden çok daha az yineleme gerektirerek üretmiştir. Katsayı matrisinin bir bellek dizisi üzerinde dağıtıldığı büyük ölçekli uygulamalarda, önerilen Melez M-IHS şemaları katsayı matrisi kullanılarak hesaplanan dağıtılmış matris-vektör çarpımlarının sayısını en aza indirerek önemli bir verimlilik sağlamaktadır.
Özet (Çeviri)
Momentum Iterative Hessian Sketch (M-IHS) techniques, a group of solvers for large scale linear Least Squares (LS) problems, are proposed and analyzed in detail. Proposed M-IHS techniques are obtained by incorporating the Heavy Ball Acceleration into the Iterative Hessian Sketch algorithm and they provide significant improvements over the randomized preconditioning techniques. By using approximate solvers along with the iterations, the proposed techniques are capable of avoiding all matrix decompositions and inversions, which is one of the main advantages over the alternative solvers such as the Blendenpik and the LSRN. Similar to the Chebyshev Semi-iterations, the M-IHS variants do not use any inner products and eliminate the corresponding synchronization steps in hierarchical or distributed memory systems, yet the M-IHS converges faster than the Chebyshev Semi-iteration based solvers. Lower bounds on the required sketch size for various randomized distributions are established through the error analyses of the M-IHS variants. Unlike the previously proposed approaches to produce a solution approximation, the proposed M-IHS techniques can use sketch sizes that are proportional to the statistical dimension which is always smaller than the rank of the coefficient matrix. Additionally, hybrid schemes are introduced to estimate the unknown l2-norm regularization parameter along with the iterations of the M-IHS techniques. Unlike conventional hybrid methods, the proposed Hybrid M-IHS techniques estimate the regularization parameter from the lower dimensional sub-problems that are constructed by random projections rather than the deterministic projections onto the Krylov Subspaces. Since the lower dimensional sub-problems that arise during the iterations of the Hybrid M-IHS variants are close approximations to the Newton sub-systems and the accuracy of their solutions increase exponentially, the parameters estimated from them rapidly converge to a proper regularization parameter for the full problem. In various numerical experiments conducted at several noise levels, the Hybrid M-IHS variants consistently estimated better regularization parameters and constructed solutions with less errors than the direct methods in far fewer iterations than the conventional hybrid methods. In large scale applications where the coefficient matrix is distributed over a memory array, the proposed Hybrid M-IHS variants provide improved efficiency by minimizing the number of distributed matrix-vector multiplications with the coefficient matrix.
Benzer Tezler
- Adaptif kontrol sistemleri ve bir mikrokontrolör ile simülasyonu
Adaptive control systems and simulation by a microcontroller
CANAN MÖRÜ
Yüksek Lisans
Türkçe
1991
Elektrik ve Elektronik Mühendisliğiİstanbul Teknik ÜniversitesiDOÇ.DR. LEYLA GÖREN
- Uyarlamalı süzgeçler
Adaptive filters
RIDVAN AYSEL
Yüksek Lisans
Türkçe
1994
Elektrik ve Elektronik Mühendisliğiİstanbul Teknik ÜniversitesiPROF.DR. AHMET H. KAYRAN
- Reduced-order modelling of shallow water equations
Sığ sularda dalga denklemleri için model indirgeme yöntemleri
SÜLEYMAN YILDIZ
Doktora
İngilizce
2021
Fizik ve Fizik MühendisliğiOrta Doğu Teknik ÜniversitesiBilimsel Hesaplama Ana Bilim Dalı
PROF. DR. BÜLENT KARASÖZEN
- Hipersezgisel yöntemlerle lojistik ağ tasarımı ve optimizasyon
Logistic network design and optimization using hyperheuristic methods
VURAL EROL
Doktora
Türkçe
2017
Endüstri ve Endüstri Mühendisliğiİstanbul Teknik ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
DOÇ. DR. MURAT BASKAK
PROF. DR. GÜLGÜN KAYAKUTLU
- The speed control of induction motor with fuzzy logic based vector control used in a wind energy conversion system
Rüzgar enerjisi dönüşüm sisteminde kullanılan bir asenkron motorun bulanık mantık tabanlı vektör kontrolü ile hız kontrolü
ELMIRA MOUSAREZAEE
Yüksek Lisans
İngilizce
2022
Elektrik ve Elektronik Mühendisliğiİstanbul Teknik ÜniversitesiElektrik Mühendisliği Ana Bilim Dalı
PROF. DR. LALE ERGENE