Closed-form algorithms for computing the intersection of two subspaces

doi:10.21629/JSEE.2019.02.03

Journal of Systems Engineering and Electronics ›› 2019, Vol. 30 ›› Issue (2): 245-250.doi: 10.21629/JSEE.2019.02.03

• Electronics Technology • Previous Articles Next Articles

Closed-form algorithms for computing the intersection of two subspaces

Fenggang YAN(), Shuai LIU(), Jun WANG(), Ming JIN*()

School of Information Science and Engineering, Harbin Institute of Technology at Weihai, Weihai 264209, China

Received:2017-02-22 Online:2019-04-01 Published:2019-04-28
Contact: Ming JIN E-mail:yfglion@163.com;boy@163.com;hitwangjun@126.com;jinming0987@163.com
About author:YAN Fenggang was born in 1982. He received his Ph.D. degree in information and communication engineering from Harbin Institute of Technology, Harbin, in 2014. From July 2008 to March 2011, he was a research associate of the Fifth Research Institute of China Aerospace Science and Technology Corporation (CASC), where his research mainly focused on the processing of remote sensing images. Since October 2015, he became an associate professor of the Department of Electronics Information Engineering, Harbin Institute of Technology at Weihai, Weihai, China. His current research interests include array signal processing and statistical performance. E-mail:yfglion@163.com|LIU Shuai was born in 1980. He received his B.E. and M.S. degrees from Northwestern Polytechnical University China, in 2002 and 2005, respectively, and received his Ph.D. degree in information and communication engineering from Harbin Institute of Technology, China, in 2013. Since 2013, he has been an associate professor of the School of Information and Electricity Engineering, Harbin Institute of Technology, Weihai, China. His current interests are in the area of conformal array and polarization sensitive array signal processing. E-mail:liu shuai boy@163.com|WANG Jun was born in 1976. He received his Ph.D. degree in information and communication engineering from Harbin Institute of Technology, Harbin, China, in 2014. Since 2015, he has been an associate professor of the Department of Electronics information Engineering, Harbin Institute of Technology at Weihai, Weihai, China. His current research interest is mainly radar signal processing. E-mail:hitwangjun@126.com|JIN Ming was born in 1968. He received his B.E., M.S., and Ph.D. degrees in information and communication engineering from Harbin Institute of Technology, China, in 1990, 1998 and 2004, respectively. From 1998 to 2004, He was with the Department of Electronics Information Engineering, Harbin Institute of Technology. Since 2006, he became a professor of the School of Information and Electricity Engineering, Harbin Institute of Technology at Weihai. His current interests include array. E-mail:jinming0987@163.com
Supported by:
the National Natural Science Foundation of China(61501142);the National Natural Science Foundation of China(61871149);the project supported by Discipline Construction Guiding Foundation in Harbin Institute of Technology (Weihai)(WH2-0160107);This work was supported by the National Natural Science Foundation of China (61501142; 61871149), and the project supported by Discipline Construction Guiding Foundation in Harbin Institute of Technology (Weihai) (WH2-0160107)

Abstract

Abstract:

Finding the intersection of two subspaces is of great interest in many fields of signal processing. Over several decades, there have been numerous formulas discovered to solve this problem, among which the alternate projection method (APM) is the most popular one. However, APM suffers from high computational complexity, especially for real-time applications. Moreover, APM only gives the projection instead of the orthogonal basis of two given subspaces. This paper presents two alternate algorithms which have a closed form and reduced complexity as compared to the APM technique. Numerical simulations are conducted to verify the correctness and the effectiveness of the proposed methods.

Key words: orthogonal projection, singular value decomposition, alternate projection method (APM), intersection

Fenggang YAN, Shuai LIU, Jun WANG, Ming JIN. Closed-form algorithms for computing the intersection of two subspaces[J]. Journal of Systems Engineering and Electronics, 2019, 30(2): 245-250.

Figures/Tables 5

Table 1

Fig 1

Fig 2

Fig 3

Table 2

References 36

1	NI Y, ZHAO J, WANG Y, et al. Beamforming and interference cancellation for D2D communication assisted by twoway decode-and-forward relay node. China Communications, 2018, 15 (3): 100- 111.
2	ZHANG Y, HE P, PAN F. Three-dimension localization of wide-band sources using sensor network. Chinese Journal of Electronics, 2017, 26 (6): 1302- 1307. doi: 10.1049/cje.2017.07.003
3	YAN F G, LIU S, WANG J, et al. Fast DOA estimation using co-prime array. Electronics Letters, 2018, 54 (7): 409- 410. doi: 10.1049/el.2017.2491
4	YAO B, ZHANG W, WU Q. Weighted subspace fitting for twodimension DOA estimation in massive MIMO systems. IEEE Access, 2017, 5, 14020- 14027. doi: 10.1109/ACCESS.2017.2731379
5	LI J, LI D, JIANG D, et al. Extended-aperture unitary root MUSIC-based DOA estimation for coprime array. IEEE Communications Letters, 2018, 22 (4): 752- 755. doi: 10.1109/LCOMM.2018.2802491
6	TIAN X, LEI J, DU L. A generalized 2-D DOA estimation method based on low-rank matrix reconstruction. IEEE Access, 2018, 6, 17407- 17414. doi: 10.1109/ACCESS.2018.2820165
7	NAGANANDA K G, ANAND G V. Subspace intersection method of bearing estimation in shallow ocean using acoustic vector sensors. Proc. of the 16th European Signal Processing Conference, 2008, 1- 5.
8	ANAND G V, NAGESHA P V. High resolution bearing estimation in partially known ocean using short sensor arrays. Proc. of the International Symposium on Ocean Electronics, 2011, 47- 56.
9	PANG J, LIN J, ZHANG J, et al. Subspace intersection method of bearing estimation based on least square approach in shallow ocean. Proc. of the IEEE International Conference on Acoustics, Speech and Signal Processing, 2008, 2433- 2436.
10	GESBERT D, VAN DER VEEN A J, PAULRAJ A. On the equivalence of blind equalizers based on MRE and subspace intersection. IEEE Trans. on Signal Processing, 1999, 47 (3): 856- 859. doi: 10.1109/78.747791
11	BARBAROSSA S. Parameter estimation of multicomponent polynomial-phase signals by intersection of signal subspaces. Proc. of the 8th Workshop on Statistical Signal and Array Processing, 1996, 452- 455.
12	PETROCHILOS N, VAN DER VEEN A J. Blind time delay estimation in asynchronous CDMA via subspace intersection and ESPRIT. Proc. of the IEEE International Conference on Acoustics, Speech and Signal Processing, 2001, 4, 2217- 2220.
13	MURDOCK C, TORRE F D L. Approximate grassmannian intersections:subspace-valued subspace learning. Proc. of the IEEE International Conference on Computer Vision, 2017, 4318- 4326.
14	AL-SAEDY M, AL-IMARI M, AL-SHURAIFI M, et al. Joint user selection and multimode scheduling in multicell MIMO cellular networks. IEEE Trans. on Vehicular Technology, 2017, 66 (12): 10962- 10972. doi: 10.1109/TVT.2017.2717909
15	YUAN B, LIAO X, GAO F, et al. Achievable degrees of freedom of the four-user MIMO Y channel. IEEE Communications Letters, 2014, 18 (1): 6- 9. doi: 10.1109/LCOMM.2013.112613.131444
16	MARKOVIĆ D, ANTONACCI F, SARTI A, et al. 3D beam tracing based on visibility lookup for interactive acoustic modeling. IEEE Trans. on Visualization and Computer Graphics, 2016, 22 (10): 2262- 2274. doi: 10.1109/TVCG.2016.2515612
17	GOLUB G H, VAN LOAN C H. Matirx computations. Baltimore, MD, USA: The Johns Hopkins University Press, 1996.
18	ANDERSON JR W N, DUFFIN R J. Series and parallel addition of matrices. Journal on Mathematics Analysis & Applications, 1968, 26 (3): 576- 594.
19	VON NEUMANN J. Functional operators Ⅱ: the geometry of orthogonal spaces. Princeton: Princeton University Press, 1950.
20	ARONSZAJN N. Theory of reproducing kernels. Transactions of the American Mathematics Society, 1950, 68 (3): 337- 404. doi: 10.1090/S0002-9947-1950-0051437-7
21	KAYALAR S, WEINERT H. Error bounds for the method of alternating projections. Mathematics of Control Signals & Systems, 1988, 1 (1): 43- 59.
22	DEUTSCH F. The angle between subspaces of a Hilbert space. Singh S P ed. Approximation theory, wavelets and applications. Dordrecht: Springer Netherlands, 1995: 107-130.
23	DEUTSCH F. Best approximation in inner product spaces. New York: Springer, 2001.
24	HALPERIN I. The product of projection operators. Acta Scientiarum Mathematicarum, 1962, 23 (23): 96- 99.
25	BEN-ISRAEL A. Projectors on intersection of subspaces. benisrael.net/BEN-ISRAEL-NOV-30-13.pdf.
26	ZHOU M, VAN DER VEEN A J. Improved subspace intersection based on signed URV decomposition. Proc. of the Asilomar Conference on Signals, Systems, and Computers, 2011, 2174- 2178.
27	ZHANG Z, LENG W, WANG A, et al. Effective estimation of the desired-signal subspace and its application to robust adaptive beamforming. Proc. of the IEEE International Conference on Acoustics, Speech and Signal Processing, 2017, 3370- 3374.
28	PHAN H M. Linear convergence of the douglas-rachford method for two closed sets. Optimization, 2016, 65 (2): 369- 385. doi: 10.1080/02331934.2015.1051532
29	HESSE R, LUKE D R. Nonconvex notions of regularity and convergence of fundamental algorithms for feasibility problems. SIAM Journal on Optimization, 2013, 23 (4): 2397- 2419. doi: 10.1137/120902653
30	DAVIS D, YIN W. Faster convergence rates of relaxed Peaceman-Rachford and ADMM under regularity assumptions. Mathematics of Operations Research, 2014, 42 (3): 1- 40.
31	GISELSSON P, BOYD S. Linear convergence and metric selection for Douglas-Rachford splitting and ADMM. IEEE Trans. on Automatic Control, 2017, 62, 532- 544. doi: 10.1109/TAC.2016.2564160
32	GISELSSON P. Tight global linear convergence rate bounds for Douglas-Rachford splitting. Journal of Fixed Point Theory and Applications, 2017, 19 (4): 2241- 2270. doi: 10.1007/s11784-017-0417-1
33	BAUSCHKE H H, CRUZ J Y B, NGHIA T T A, et al. The rate of linear convergence of the Douglas-Rachford algorithm for subspaces is the cosine of the Friedrichs angle. Journal of Approximation Theory, 2014, 185, 63- 79. doi: 10.1016/j.jat.2014.06.002
34	DOUGLAS J, RACHFORD H H. On the numerical solution of heat conduction problems in two and three space variables. Transactions of the American Mathematical Society, 1956, 82 (2): 421- 439. doi: 10.1090/S0002-9947-1956-0084194-4
35	FÄLT M, GISELSSON P. Optimal convergence rates for generalized alternating projections. Proc. of the 56th IEEE Annual Conference on Decision and Control, 2017, 2268- 2274.
36	BAUSCHKE H H, CRUZ J Y B, NGHIA T T A, et al. Optimal rates of linear convergence of relaxed alternating projections and generalized Douglas-Rachford methods for two subspaces. Numerical Algorithms, 2016, 73 (1): 33- 76.

Algorithm	Primary computational flops
APM	$O(m^{3n})$
Method in (7)	$O[m^3+mr_1 r_2 +mr_1 (m-r_1-r_2)]$
Method in (8)	$O(3m^3+m^2r_1 +m^2r_2)$
m-SVD	$O(m^3+m+m^2r+m^2r_1 +m^2r_2)$
s-SVM	$O(2m+m^2r+m^2r_1 +m^2r_2)$

Algorithm	$n$=1	$n$=5	$n$=10	$n$=15	$n$=20	$n$=25
APM	0.012	0.038	0.051	0.058	0.062	0.064
Method in (7)	0.021	0.022	0.023	0.021	0.022	0.022
Method in (8)	0.034	0.033	0.036	0.033	0.035	0.038
m-SVD	0.029	0.028	0.028	0.030	0.028	0.028
s-SVD	0.011	0.012	0.016	0.012	0.012	0.014

[1]	Wei Jiang, Hongli Wang, Jinghui Lu, and Zheng Xie. HOSVD-based LPV modeling and mixed robust H2/H∞ control design for air-breathing hypersonic vehicle [J]. Systems Engineering and Electronics, 2016, 27(1): 183-.
[2]	Weijian Liu, Wenchong Xie, and Yongliang Wang. Adaptive detection based on orthogonal partition of the primary and secondary data [J]. Journal of Systems Engineering and Electronics, 2014, 25(1): 34-42.
[3]	Tianqi Zhang, Shaosheng Dai, Guoning Ma, Wei Zhang, and Pu Miao. Approach to blind estimation of the PN sequence in DS-SS signals with residual carrier [J]. Journal of Systems Engineering and Electronics, 2010, 21(1): 1-8.
[4]	Huachun Tan, Yujin Zhang, Hao Chen, Yanan Zhao, and Wuhong Wang. Person-independent expression recognition based on person-similarity weighted expression feature [J]. Journal of Systems Engineering and Electronics, 2010, 21(1): 118-126.
[5]	Tianqi Zhang1,*, Shaosheng Dai1, Guoning Ma2, Wei Zhang2, and Pu Miao1. Approach to blind estimation of the PN sequence in DS-SS signals with residual carrier [J]. Journal of Systems Engineering and Electronics, 2010, 21(1): 1-8.
[6]	Wang Ling, Yin Jihao & Chen Tianqi. New direction of arrival estimation method for wideband coherent signals [J]. Journal of Systems Engineering and Electronics, 2008, 19(3): 473-478.
[7]	Liu Donghong, Hu Wenlong & Chen Zhijie. SVD-TLS extending Prony algorithm for extracting UWB radar target feature [J]. Journal of Systems Engineering and Electronics, 2008, 19(2): 286-291.

Closed-form algorithms for computing the intersection of two subspaces

RichHTML

PDF (PC)

Knowledge

Abstract

Cite this article

Share this article

Figures/Tables 5

References 36

Related Articles 7

Recommended Articles

Metrics

Comments