Fast and robust solution techniques for large scale linear least squares problems

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.