Uncertain linear equations

Abstract

Bu tezde, çeşitli belirsizlikler içeren denklem sistemleri için kuramsal sonuçlar ve uygulamaları sunulmaktadır. İlk kısımda, denklem sayısının bilinmeyen sayısından fazla olduğu durum (artık belirtilmiş) ele alınmaktadır. Katsayı matrisi ve ölçüm vektöründe birlikte belirsizlik bulunan denklem sistemleri için gürbüz ve isabetli yeni bir yöntem önerilmektedir. Çözüme ulaşmak ve başarımı analiz etmek için gradyan alanına dayalı yeni bir analitik yaklaşım sunulmaktadır. Sunulan kuramsal sonuçlar literatürde bilinen diğer yöntemlerin de incelenmesi için kullanılmıştır. Önerilen yöntem için başarım sınırları türetilmiş ve sinyal gürültü oranının belirli bir miktardan düşük olduğu durumda önerilen yöntemin diğer yöntemlere kıyasla daha başarılı olduğu ispatlanmıştır. Sayısal sonuçlar kısmında sistem tanımlama, çoklu frekans kestirimi ve ters evrişim problemlerindeki başarım oranı diğer yöntemlerle karşılaştırılmış ve düşük sinyal gürültü oranları için daha az toplam hata kare elde edilmiştir. Bu bölümde incelenen diğer bir belirsizlik modeli de seyrek belirsizliktir. Bu tür belirsizliklerin eğer yeteri kadar denklem varsa bazı koşullar altında kesin olarak çözülebileceği gösterilmiştir. Çözüm için bir optimizasyon kriteri ve konveks relaksiyonu önerilmektedir. Kesin ve kararlı çözüm için yeterli koşullar bulunmuştur. Nümerik örnekler önerilen yöntemin kesin çözüm olasılığının yüksek olduğunu göstermektedir. Yöntem kablosuz çokyollu kanal kestirim ve takibine uygulanmış ve yüksek başarım sağlanmıştır. Tezin ikinci kısmında bilinmeyen sayısı denklem sayısından fazla olduğu (eksik belirtilmiş) durum ele alınmıştır. Arıkan'ın kutuplaşma kuramı sürekli dağılımlı rastgele değişkenlere genişletilerek, Hadamard ve Ayrık Fourier Dönüşümü'nün bağımsız eş dağılımlı sıkıştırılabilir değişkenlerdeki bilgi içeriğini kutuplaştırdığı gösterilmiştir. Sıkıştırılabilme ise Shannon'ın diferansiyel entropisi olarak tanımlanmıştır. Elde edilen bu sonuçlarla, eğer gözlem entropisi yeterliyse doğrusal denklem sistemin çözümünün belirlenebileceği gösterilmiştir. Bu yaklaşım sıkıştırılabilir sinyalleri örneklemeye uygulanmış ve ?Kutupsal Örnekleme? adı verilmiştir. Bu sonuç Sıkıştırmalı Örnekleme (Compressive Sampling) kuramının seyrek sinyallerden sıkıştırılabilir sinyallere bilgi kuramı yardımıyla genellenmesini sağlamıştır. Kutupsal Örnekleme yöntemi sayısal olarak dalgacıklar yardımıyla sıkıştırılabilir bir sinyali Nyquist hızı altında örneklemede denenmiş ve sonuçlar sunulmuştur.

In this thesis, new theoretical and practical results on linear equations with various types of uncertainties and their applications are presented. In the first part, the case in which there are more equations than unknowns (overdetermined case) is considered. A novel approach is proposed to provide robust and accurate estimates of the solution of the linear equations when both the measurement vector and the coefficient matrix are subject to uncertainty. A new analytic formulation is developed in terms of the gradient flow to analyze and provide estimates to the solution. The presented analysis enables us to study and compare existing methods in literature. We derive theoretical bounds for the performance of our estimator and show that if the signal-to-noise ratio is low than a treshold, a significant improvement is made compared to the conventional estimator. Numerical results in applications such as blind identification, multiple frequency estimation and deconvolution show that the proposed technique outperforms alternative methods in mean-squared error for a significant range of signal-to-noise ratio values. The second type of uncertainty analyzed in the overdetermined case is where uncertainty is sparse in some basis. We show that this type of uncertainty on the coefficient matrix can be recovered exactly for a large class of structures, if we have sufficiently many equations. We propose and solve an optimization criterion and its convex relaxation to recover the uncertainty and the solution to the linear system. We derive sufficiency conditions for exact and stable recovery. Then we demonstrate with numerical examples that the proposed method is able to recover unknowns exactly with high probability. The performance of the proposed technique is compared in estimation and tracking of sparse multipath wireless channels. The second part of the thesis deals with the case where there are more unknowns than equations (underdetermined case). We extend the theory of polarization of Arikan for random variables with continuous distributions. We show that the Hadamard Transform and the Discrete Fourier Transform, polarizes the information content of independent identically distributed copies of {/it compressible} random variables, where compressibility is measured by Shannon's differential entropy. Using these results we show that, the solution of the linear system can be recovered even if there are more unknowns than equations if the number of equations is sufficient to capture the entropy of the uncertainty. This approach is applied to sampling compressible signals below the Nyquist rate and coined `Polar Sampling`. This result generalizes and unifies the sparse recovery theory of Compressed Sensing by extending it to general low entropy signals with an information theoretical analysis. We demonstrate the effectiveness of Polar Sampling approach on a numerical sub-Nyquist sampling example.