34 2 Vol. 34, No. 2 2008 2 ACTA AUTOMATICA SINICA February, 2008 1, 2 1 1 ( ). m,., k, k-sca., l 1. ( ). (BSS), (SCA),,, k TN912.3 Underdetermined Blind Source Separation Algorithm Based on Normal Vector of Hyperplane XIAO Ming 1, 2 XIE Sheng-Li 1 FU Yu-Li 1 Abstract Discussion of blind signal separation problem under underdetermined case (i.e., the case of less observed signals than sources) is presented. First, a formula to calculate the normal vector of any hyperplane is given and a mixing matrix recovery algorithm based on the normal vector of any hyperplane is proposed. Second, for audio signal, k-source intervals are introduced and a method to detect them is proposed. So, the algorithms under the k-sca condition are extended to blind non-sparse signal separation. To reconstruct the sources, a new algorithm is proposed to simplify the l 1 -norm solution. Several experiments demonstrate the performance of the proposed algorithm. Key words Underdetermined blind signal separation (BSS), sparse component analysis (SCA), hyperplane clustering, normal vector, k-source interval (Independent component analysis, ICA) (Blind signal separation, BSS) [1 3],.,, [4 8],,,., Georgiev, k-sca [9 10], k-sca 2006-11-06 2007-05-08 Received November 6, 2006; in revised form May 8, 2007 (U0635001, 60505005, 60674033), (04205783, 05006508), (2005CCA04100) Supported by National Natural Science Foundation of China (U0635001, 60505005, 60674033), Natural Science Fundation of Guangdong Province, China (04205783, 05006508), Specialized Prophasic Basic Research Projects of Ministry of Science and Technology, China (2005CCA04100) 1. 510641 2. 525000 1. College of Electrics and Information Engineering, South China University of Technology, Guangzhou 510641 2. Department of Electrics and Information Engineering, Maoming College, Maoming, Guangdong 525000 DOI: 10.3724/SP.J.1004.2008.00142. k-sca [11 14],. Theis Cichocki [12],, m,,., k-sca,, k-sca,,., 4 3, ( 1),,, k-sca,,, k-sca.,,, k-sca.,, k ; k, k,.
2 : 143, l 1,., Theis [12] Washizawa [14],. 1 4 3 ((a) ; (b) ) Fig. 1 Four speech signals mixed into three mixtures ((a) Scatter plot of three mixtures; (b) Their projections 1 on unit sphere ), X = AS (1), A R m n S R n N. Georgiev k-sca : 1) A m m ; 2) n m + 1, S n m + 1 ; 3) : n m + 1 I = {i 1,, i n m+1 } {1,, n}, S m 0 I, m 1. k-sca, :? m {u k } m 1, u k = (u k1,, u km ) T, H, H = {y y R m, c 1,, c m 1 R, y = c 1 u 1 + + c m 1 u m 1 }.,,., m, m 1 H,, 1. m n m {u k } m 1 H, y H, n, y = 0, n H ( ), n H,,., U = (u 1,, u m 1 ) m (m 1), l, (m 1) (m 1) u 11 u m 1,1...... u.. 1,l 1 um 1,l 1 U l =. u.. 1,l+1 um 1,l+1..... u 1m u m 1,m 1. m {u k } m 1 H,, n 0 = (det(u 1 ), det(u 2 ),, ( 1) m 1 det(u m )) T H ;, n 0 m H.., n 0 {u k } m 1 u 1 : n 0, u 1 = u 11 det(u 1 ) u 12 det(u 2 ) + + u 1m ( 1) m 1 det(u m ) = u 11 u 11 u m 1,1...... = 0 u 1m u 1m u m 1,m, n 0, u l = 0 (l = 1,, m), n 0 H.,, n H, n, u l = 0 (l = 1,, m 1), U T n = 0, U m 1 n 0, c n 0 ( n = c n 0, c R), n 0,, H., n 0, {u k } m 1 H, H, v H v / H, v {u k } m 1, {u k } m 1 v m m, m, n 0 H H, n 0 {u k } m 1 v, n 0 m
144 34,,, n 0 H.. H, n = n 0 / n 0. 2 k-sca, A a j, (1) x t = n a j s t j (2) j=1, x t X, a j = 1., A k-sca 1), m 1 {a ik } m 1 m H q, H q = {y y R m, c ik R, y = c i1 a i1 + + c im 1 a im 1 },, q = 1,, C m 1 n, C m 1 n = n!/[(m 1)!(n m + 1)!]. 1, b q = (det(a q 1), det(a q 2),, ( 1) m 1 det(a q m)) T, b q H q,, A q l a 1j1 a 1jm 1...... A q l = a.. l 1,j1 al 1,jm 1., l = 1,, m a.. l+1,j1 al+1,jm 1..... a m,j1 a m,jm 1 k-sca 2), S s t n m + 1,, X x t A Q H q, x t Q H q=1 q (Q = Cn m 1, t = 1,, N),,, X Q ( 5 3(b)). Q H q? : 1) X, X {x t } N t=1, xj = x j / x j. 2) x j + x k = 0 x j x k = 0,. y l = x j, X y l, {y j } N l j=1, Y = (y 1,, y N l ), yl h l. 3) det(y l1,, y lm ) 0, m {y li } m i=1, m, m 1, Y n 1 N min,., {n j } L j=1, L {H j } L j=1. 4) Y n j, j 1,, j k {1,, N l }, X n j m j, m j = k h i=1 j i, m j. 5) m j,, Q n j,, ˆb j = n j. 6) {ˆb j } Q j=1, a j C m 2 n 1, {ˆb j } Q j=1 C m 2 n 1, {ˆb j } Q j=1 m 1 a j., S s t n m + 1, m 1 {a ik } m 1 m Cm 1 n H q x t,, S s t n m + 1, Cn m 1 H q,,,. 3 k, k-sca 2),, k-sca. k-sca,, k : 4, 1, ;, 2 ; 3, 3. k, n m + 1, m 1, k. k. 2., [t 1, t 2 ], k (k m 1) 0, 0, [t 1, t 2 ] k. [15 16], k 1
2 : 145, : 3., [t 1, t 2 ], 0, [t 1, t 2 ]., k. 2. m m, [t 1, t 2 ] k, k = m 1, t [t 1, t 2 ], x t ; x t [t 1, t 2 ] m 1,,.. t [t 1, t 2 ], s t n m + 1, m 1,, {s t j l } m 1 l=1, x t = m 1 a l=1 jl s t j l, x t {a ji } m 1 i=1,, x t [t 1, t 2 ] m 1, [t 1, t 2 ] m 1, 1,,. t i [t 1, t 2 ] (i = 1,, m), {x t i } m i=1, : 1. m m, [t 1, t 2 ] k, k = m 1, t i [t 1, t 2 ] (i = 1,, m), det([x t 1,, x t m ]) = 0, k m {x t i } m i=1 0., k, k k-sca 3,. 3., k (k = m 1) k-sca 3,.. k,, k,, [9],,. 3 k-sca 3 : n m + 1. 2 1 k (k = m 1), 2 1,, k N min, k : 1) [16] ; 2) 2 1 k, N min k ; 3) 2 k-sca. 4 (Laplacian) A,, l 1 J(S) = T n t=1 j=1 st j, S. l 1 [6] n n min s t j, s. t. a j s t j = x t (3) j=1 j=1, X ; m 0, 0,, (3) min A ik n s t j, s. t. j=1 m a i k s t i k = x t (4), A ik A m, A ik = (a i1,, a im ). A ik Cn m, (4) Cm n n j=1 st j, m ai k st i k = x t, s t i k, A min i k, { A min i k (s t i 1,, s t i m ) T = x t (5) s t j = 0 (i i k ) (4) (5) l 1,, m 0, 0. 5 5.1 1 Theis [12], k-sca ( 2(a)), 2(b), A = 0.4545-0.7912-0.6634 0.4568 0.4545 0.2120-0.3830-0.7912 0.7660 0.5736 0.6428 0.4067
146 34,, (0.494, 0.7598, 0.4225), (0.2646, 0.8419, 0.47), 10 7, X,. 8,,,. 3, 2 ((a) ; (b) ; (c) ) Fig. 2 Waveform of signals ((a) Sources; (b) Mixtures; (c) The estimated signals ) 3, 3(b),,, 6 ;, 6 ( ˆb 1,, ˆb 6 ) 400 317 302 286 257 244, B = [ˆb 1,, ˆb 6 ]. B = 0.5857 0.6105 0.5653 0.8012 0.3655 0.0999-0.8005 0.2197 0.6112 0.1672 0.5837-0.8806 0.1275 0.7610 0.5539-0.5746 0.7250 0.4632 Â = 0.6634 0.4545 0.7912 0.4568 0.3830 0.4545-0.2121-0.7912-0.6428 0.7660-0.5736 0.4067 min P P ÂP A 2, P., 0. Theis [12], min P P ÂP A 2 0.04, Theis., 2(c), 108 db 145 db 228 db 115 db; Theis 36 db 38 db 36 db 37 db. 5.2 2 Washizawa, ( 4(a)) [14], S 40 % 0,, k-sca, n m + 1. A = 0.5525 0.3919 0.5707 0.3934 0.6904 0.6863-0.6066 0.5166 0.8634-0.6007 0.4730 0.6917-0.6383-0.3158 0.4032 3 4 3 ((a) ;(b) ) Fig. 3 Four sparse sources mixed into three mixtures ((a) Scatter plot of mixtures; (b) Scatter plot of the normalized mixtures ) 5,,,, k-sca.
2 : 147, Â = 0.6918 0.3755 0.3931 0.5527 0.5703-0.5981-0.6102 0.8636 0.6860 0.5179 0.4045 0.6976-0.3156 0.4731-0.6376. 4 ((a) ; (b) ) Fig. 4 Waveform of signals ((a) Sources; (b) The estimated signals ),,,,, 10, 406 372 364 359 358 358 356 351 340 338, B = [ˆb 1,, ˆb 10 ], B. min P P ÂP A 2 = 3.2956E-004., 4 (b), 21 db 11 db 17 db 10 db 17 db. Washizawa [14], min P P ÂP A 2 = 0.2018,. 5.3 3 http://www.princeton.edu/ srickard/ bss.html (Available date: Jane 17, 2005), 3 1, 6 (a), A = 0.4545-0.7912-0.6634 0.4568 0.4545 0.2120-0.3830-0.7912 0.7660 0.5736 0.6428 0.4067 5 5 3 ((a) ; (b) ) Fig. 5 Five sparse sources mixed into three mixtures ((a) Scatter plot of mixtures; (b) Scatter plot of the normalized mixtures) B, ˆb 10,, 6 ((a) ; (b) ; (c) ) Fig. 6 Waveform of signals ((a) Sources; (b) Mixtures; (c) The estimated signals ) B = 0.5681 0.0331 0.7930 0.4046 0.1779 0.4270 0.7678 0.5066 0.8326 0.1655 0.1051 0.7610-0.1448 0.7851 0.6812 0.7877-0.1986-0.4899-0.4803-0.4094-0.8162 0.6479 0.5917 0.4690 0.7102 0.4440-0.6091-0.7095-0.2758-0.8972
148 34 6 (b) ( ), 1. 1,.,, 0.025, 3, Â 1 = -0.4522 0.7917 0.4613-0.4556-0.2195-0.7940-0.7668-0.5702 0.3960 3 16 8 14. k,, k 0.008, k 6, 2 k, k,,, 7. 7 (a) k ; 7 (b) 6, k ; 7 (c) 3 3. 7, k 3., (0.6673, 0.3789, 0.6412) 3,, Â = -0.4522 0.7917 0.4613 0.6673-0.4556-0.2195-0.7940 0.3789-0.7668-0.5702 0.3960-0.6412 min P P ÂP A 2 = 2.5258E-004, 34.7 db 7.6 db 18.3 db 8.1 db. 6 k-sca, : 1) m, Georgiev,, Theis ; 2) k, k-sca, Georgiev k-sca.,,, 4 k. References 1 Cardoso J F. Blind signal separation: statistical principles. Proceedings of the IEEE, 1998, 90(10): 2009 2025 7 ((a) k ; (b) (c) ) Fig. 7 Simulation results ((a) Scatter plot of the samples in k-sources intervals; (b) and (c) Their projections on the unit sphere ) 1 7, 2. k,, (0.3662, 0.5827, 0.7255), ( 0.5718, 0.8123, 0.1151) ( 0.6334, 0.2768, 0.7226), 3 2 Cichocki A, Amari S I. Adaptive Blind Signal and Image Processing: Learning Algorithms and Applications. New York: Wiley, 2002 3 Li Y Q, Wang J. Sequential blind extraction of instantaneously mixed sources. IEEE Transactions on Signal Processing, 2002, 50(5): 997 1006 4 Bofill P, Zibulevsky M. Underdetermined blind source separation using sparse representations. Signal Processing, 2001, 81(11): 2353 2362 5 He Zhao-Shui, Xie Sheng-Li, Fu Yu-Li. Sparse representation and blind source separation of illposed mixtures. Science in China (Series E): Information Sciences, 2006, 36(8): 864 879 (,,.. (E ):, 2006, 36(8): 864 879) 6 He Zhao-Shui, Xie Sheng-Li, Fu Yu-Li. Sparsity analysis of signals. Progress in Natural Science, 2006, 16(9): 1167 1173 (,,.., 2006, 16(9): 1167 1173) 7 Delgado K K, Murray J F, Rao B D, Engan K, Lee T W, Sejnowski T J. Dictionary learning algorithms for sparse representation. Neural Computation, 2003, 15(2): 349 396
2 : 149 8 Li Y Q, Amari S, Cichocki A, Ho D W C, Xie S L. Underdetermined blind source separation based on sparse representation. IEEE Transactions on Signal Processing, 2006, 54(2): 423 437 9 Georgiev P, Theis F J, Cichocki A. Blind source separation and sparse component analysis of overcomplete mixtures. In: Proceedings of International Conference on Acoustics, Speech, and Signal Processing. Montreal, Canada: IEEE, 2004. 493 496 10 Georgiev P, Theis F J, Cichocki A. Sparse component analysis and blind source separation of underdetermined mixtures. IEEE Transactions on Neural Networks, 2005, 16(4): 992 996 11 Bradley P S, Mangasarian O L. k-plane clustering. Journal of Grobal Optimization, 2000, 16(1): 23 32 12 Theis F J, Georgiev P, Cichocki A. Robust overcomplete matrix recovery for sparse sources using a generalized hough transform. In: Proceedings of the 12th European Symposium on Artificial Neural Networks. Bruges, Belgium: 2004. 343 348 13 He Z, Cichocki A. k-subspace clustering and its application in sparse component analysis. In: Proceedings of the 14th European Symposium on Artificial Neural Networks. Bruges, Belgium: 2006. 26 28 14 Washizawa Y, Cichocki A. On line k-plane clustering learning algorithm for sparse component analysis. In: Proceedings of IEEE International Conference on Acoustics, Speech and Signal Processing. Toulouse, France: IEEE, 2006 15 Xiao M, Xie S L, Fu Y L. A novel approach for underdetermined blind source in frequency domain. Lecture Notes in Computer Science, 2005, 3497: 484 489 16 Xie S L, Xiao M, Fu Y L. A novel approach for underdetermined blind speech sources separation. Dynamics of Continuous Discrete and Impulsive Systems, Series A: Mathematical Analysis, 2006, 13(4): 1846 1853,.. E-mail: xiaoming1968@163.com (XIAO Ming Ph. D. candidate at School of Electronics and Information Engineering, South China University of Technology, associate professor at Maoming College. His research interest covers blind source processing.), RFID.. E-mail: adshlxie@scut.edu.cn (XIE Sheng-Li Professor at School of Electronics and Information Engineering, South China University of Technology. His research interest covers intelligent information processing, digital home networks, RFID theory and techonology, blind signal processing, and image processing. Corresponding author of this paper.). 2000.. E-mail: fuyuli@scut.edu.cn (FU Yu-Li Professor at School of Electronics and Information Engineering, South China University of Technology. He received his Ph. D. degree from Huazhong University of Science and Technology in 2000. His research interest covers blind signal processing.)