降低基於交替迭代體積最大化於混合非負訊號源之凸分析演算法的運算複雜度

Convex analysis of mixtures of non-negative sources (CAMNS) 是近年來新發展的盲蔽非負訊號源分離 (nBSS) 方法，相較於其它現存 nBSS方法， CAMNS 提供了較高的分離效能；此外， CAMNS 不需要任何訊號源獨立的基本假設，因此它可以應用在真實世界中各種不同的應用，如生物醫學影像分析 (biomedical imaging analysis) ，超光譜影像 (hyper-spectral imaging analysis) 等應用，這些應用的未知訊號源一般來說皆是統計獨立的。具體的說， CAMNS 利用了凸分析的概念來發展一個新穎的 nBSS 準則，將nBSS 的問題轉換成一個尋找多面體集合 (polyhedral set) 所有極點 (extreme point) 的問題(即極點列舉問題 (extreme point enumeration problem) )。在CAMNS中，使用兩種方法來找尋所有極點，第一種方法，是有系統地解一序列的線性規劃問題以找尋所有極點，稱為 (CAMNS-LP)。第二種方法，則是利用了多面體集合所形成的單形 (simplex) 體積最大化以及交替迭代線性規劃來尋找所有極點，稱為 (CAMNS-AVM) ，而且於模型不匹配時較為強健。然而在大多數的影像分析應用中，影像像素 (pixel) 的個數通常都是相當龐大，這會使得 CAMNS-AVM 演算法在應用到真實影像資料的實驗時，會消耗相當多運算時間。在這篇論文中，我們提出了三種方法來降低 CAMNS-AVM 演算法的運算複雜度 (complexity reduction) ，第一種方法，我們證明了在 CAMNS-AVM 演算法中，原本需要解兩個基於線性最佳化子問題，簡化為解一個線性最佳化子問題就可以得到相同最佳化的解。第二種方法，我們實現了針對 CAMNS-AVM 的線性最佳化所特別設計的線性程式來求解，我們可以控制給定尋找最佳解的初始值，以及將這次尋找到的最佳解當作下一次尋找最佳解的初始值以增加運算速度。第三種方法，移除在線性規劃中多餘的不等式約束，然而結合了眾所皆知的 Quickhull 演算法以及隨機投影的概念來辨識有效的不等式，因此可以降低線性規劃的運算複雜度。在我們改善了 CAMNS-AVM 演算法的運算效率後，我們延伸了 CAMNS-AVM 演算法，即使在 local dominance 假設不成立的時候，可以經由最糟情況的強健性最佳化過程，將此問題同樣地轉換成線性規劃的問題，如此一來，上述所提到的三種降低運算複雜度的方法就可以應用在這種情況下所推導出來的線性最佳化問題。另外，我們還將上述所提到的三種降低運算複雜度方法，應用到另一個近年來新發展使用線性規劃的演算法，稱為 non-negative least correlated component analysis by iterative volume maximization (nLCA-IVM) 。最後，我們經由幾組數據進行模擬，以及超光譜影像的真實影像資料實驗，證明我們提出運算複雜度降低的方法，可以有效地降低 CAMNS-AVM 演算法的運算複雜度。

關鍵字

凸分析最佳化；降低複雜度；非負訊號源分離

並列摘要

無資料

並列關鍵字

convex optimization ； complexity reduction ； non-negative source separation

參考文獻

[1] A. Hyv¨arinen, J. Karhunen, and E. Oja, Independent Component Analysis. New

York: John Wiley, 2001.

[3] M. D. Plumbley, “Algorithms for non-negative independent component analysis,”

IEEE Trans. Neural Netw., vol. 14, no. 3, pp. 534-543, 2003.

[4] A. T. Erdogan, “A simple geometric blind source separation method for bound magnitude

國際替代計量

降低基於交替迭代體積最大化於混合非負訊號源之凸分析演算法的運算複雜度

主題瀏覽