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 演算法的運算複雜度。

CHINESE ABSTRACT
ABSTRACT
CHINESE ACKNOWLEDGMENTS
CONTENTS
1 INTRODUCTION
2 PROBLEM STATEMENT AND ASSUMPTIONS
3 BRIEF REVIEW OF CAMNS
3.1 Review of Some Basic Convex Analysis Concepts
3.1.1 Affine hull
3.1.2 Convex hull
3.2 Review of Convex Analysis of Mixtures of Non-negative Sources (CAMNS) Criterion
3.3 Review of CAMNS Problem via Alternating Volume Maximization (CAMNSAVM)
4 COMPLEXITY REDUCTION FOR CAMNS-AVM 16
4.1 Subproblem Equivalence
4.2 Customized Primal-Dual Interior-Point Method for Linear Programming
4.3 Redundant Constraints Removal
5 OTHER CONSIDERATIONS
5.1 Violation of Local Dominance Assumption (A2)
5.2 Application to nLCA
6 COMPUTER SIMULATION RESULTS
6.1 Example of 5-Source Case: Human Face Image Separation
6.2 Example of Random Source for N = 5, 6, 7
6.3 Example of Random Source Separation for (N − 1) > 9
6.4 Example of 3-Source Case: Local Dominance Assumption is Not Satisfied
6.5 Application to nLCA for Random Data Separation with N = 5, 6, 7
7 REAL DATA EXPERIMENTS
8 CONCLUSIONS
APPENDIX A
APPENDIX B
APPENDIX C
REFERENCES

[1] A. Hyv¨arinen, J. Karhunen, and E. Oja, Independent Component Analysis. New
York: John Wiley, 2001.
[2] A. Cichocki and S. Amari, Adaptive Blind Signal and Image Processing. John Wiley
and Sons, Inc., 2002.
[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
sources,” IEEE Trans. Signal Process., vol. 54, no. 2, pp. 438–449, 2006.
[5] S. Moussaoui, D. Brie, A. Mohammad-Djafari, and C. Carteret, “Separation of nonnegative
mixture of non-negative sources using a Bayesian approach and MCMC
sampling,” IEEE Trans. Signal Process., vol. 54, no. 11, pp. 4133–4145, Nov. 2006.
[6] M. D. Plumbley, “Conditions for nonnegative independent component analysis,”
IEEE Signal Processing Letters, vol. 9, no. 6, pp. 177-180, 2002.
[7] Y. Wang, J. Xuan, R. Srikanchana, and P. L. Choyke, “Modeling and reconstruction
of mixed functional and molecular patterns,” International Journal of Biomedical
Imaging, vol. 2006, pp. 1–9, 2006.
[8] N. Keshava and J.Mustard, “Spectral unmixing,” IEEE Signal Process. Mag., vol.
19, no. 1, pp. 44–57, Jan. 2002.
[9] E. R. Malinowski, Factor Analysis in Chemistry. New York: John Wiley, 2002.
[10] T.-H. Chan, W.-K. Ma, C.-Y. Chi, and Y. Wang, “A convex analysis framework for
blind separation of non-negative sources,” IEEE Trans. Signal Processing, vol. 56,
no. 10, pp. 5120–5134, Oct. 2008.
[11] J. M. P. Nascimento and J. M. B. Dias, “Does independent component analysis play
a role in unmixing hyperspectral data?” IEEE Trans. Geosci. Remote Sensing, vol.
43, no. 1, pp. 175–187, Jan. 2005.
[12] F.-Y.Wang, Y. Wang, T.-H. Chan, and C.-Y. Chi, “Blind separation of multichannel
biomedical image patterns by non-negative least-correlated component analysis,” in
Lecture Notes in Bioinformatics (Proc. PRIB06), Springer-Verlag, vol. 4146, Berlin,
Dec. 9-14, 2006, pp. 151–162.
[13] F.-Y. Wang, C.-Y. Chi, T.-H. Chan, and Y. Wang, “Blind separation of positive
dependent sources by non-negative least-correlated component analysis,” in Proc.
IEEE International Workshop on Machine Learning for Signal Processing (MLSP),
Maynooth, Ireland, Sept. 6-8, 2006, pp. 73–78.
[14] W.-K. Ma, T.-H. Chan, C.-Y. Chi, and Y. Wang, “Convex analysis for nonnegative
blind source separation with application in imaging,” Chpater 7 in
Convex Optimization in Signal Processing and Communications, D.P. Palomar and
Y. Eldar, Eds., UK: Cambridge University, 2010.
[15] J. F. Sturm, “Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric
cones,” Optimiz. Methods Softw., vol. 11–12, pp. 625–653, 1999.
[16] M. Grant, S. Boyd, and Y. Ye, “Disciplined convex programming,” pp. 155–210 in
Global Optimization: from Theory to Implementation, Nonconvex Optimization and
Its Applications, L. Liberti and N. Maculan, Eds., New York, Springer, 2006.
[17] M. Grant. Disciplined Convex Programming. PhD thesis, Department of Electrical
Engineering, Stanford University, December 2004. See http: www.stanford.edu/
~boyd/disc_cvx_prog.html.
[18] S. Boyd and L. Vandenberghe, Convex Optimization. UK: Cambridge Univ. Press,
2004.
[19] C. B. Barber, D. P. Dobkin, and H. Huhdanpaa, “The quickhull algorithm for convex
hulls,” ACM Transactions on Mathematical Software (TOMS), vol. 22, no. 4, pp.
469–483, 1996.
[20] F.-Y. Wang, C.-Y. Chi, T.-H. Chan, and Y. Wang, “Non-negative least-correlated
component analysis for separation of dependent sources by volume maximization,”
IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 32, no. 5, pp. 875–888,
May 2010.
[21] I. J. Lustig, R. E. Marsten, and D. F. Shanno, “Interior point methods for linear
programming: Computational state of the art,” ORSA Journal on Computing, vol.
6, no. 1, pp. 1–14, 1994.
[22] G. Strang, Linear Algebra and Its Applications, 4th ed. CA: Thomson, 2006.
[23] D. P. Bertsekas, A. Nedi´c, and A. E. Ozdaglar, Convex Analysis and Optimization.
MA: Athena Scientific, 2003.
[24] P. Tichavsk´y and Z. Koldovsk´y, “Optimal pairing of signal components separated by
blind techniques,” IEEE Signal Process. Lett., vol. 11, no. 2, pp. 119–122, 2004.
[25] J. R. Hoffman and R. P. S. Mahler, “Multitarget miss distance via optimal assignment,”
IEEE Trans. System, Man, and Cybernetics, vol. 34, no. 3, pp. 327–336, May
2004.
[26] H. W. Kuhn, “The Hungarian method for the assignment method,” Naval Research
Logistics Quarterly, vol. 2, pp. 83–97, 1955.
[27] S. J. Hook, J. J. Myers, K. J. Thome, M. Fitzgerald and A. B. Kahle, “The
MODIS/ASTER airborne simulator (MASTER) - a new instrument for earth science
studies,” Remote Sensing of Environment. 76 no. 1, pp. 93–102, 2001.