Full Text:   <1760>

Summary:  <2168>

CLC number: TP391

On-line Access: 2017-09-08

Received: 2015-12-09

Revision Accepted: 2016-08-23

Crosschecked: 2017-08-24

Cited: 0

Clicked: 3527

Citations:  Bibtex RefMan EndNote GB/T7714


Yi-xuan Zhou


-   Go to

Article info.
Open peer comments

Frontiers of Information Technology & Electronic Engineering  2017 Vol.18 No.8 P.1131-1141


Sparse fast Clifford Fourier transform

Author(s):  Rui Wang, Yi-xuan Zhou, Yan-liang Jin, Wen-ming Cao

Affiliation(s):  School of Communication and Information Engineering, Shanghai University, Shanghai 200444, China; more

Corresponding email(s):   wmcao@szu.edu.cn

Key Words:  Sparse fast Fourier transform (sFFT), Clifford Fourier transform (CFT), Sparse fast Clifford Fourier transform (SFCFT), Clifford algebra

Rui Wang, Yi-xuan Zhou, Yan-liang Jin, Wen-ming Cao. Sparse fast Clifford Fourier transform[J]. Frontiers of Information Technology & Electronic Engineering, 2017, 18(7): 1131-1141.

@article{title="Sparse fast Clifford Fourier transform",
author="Rui Wang, Yi-xuan Zhou, Yan-liang Jin, Wen-ming Cao",
journal="Frontiers of Information Technology & Electronic Engineering",
publisher="Zhejiang University Press & Springer",

%0 Journal Article
%T Sparse fast Clifford Fourier transform
%A Rui Wang
%A Yi-xuan Zhou
%A Yan-liang Jin
%A Wen-ming Cao
%J Frontiers of Information Technology & Electronic Engineering
%V 18
%N 8
%P 1131-1141
%@ 1869-1951
%D 2017
%I Zhejiang University Press & Springer

T1 - Sparse fast Clifford Fourier transform
A1 - Rui Wang
A1 - Yi-xuan Zhou
A1 - Yan-liang Jin
A1 - Wen-ming Cao
J0 - Frontiers of Information Technology & Electronic Engineering
VL - 18
IS - 8
SP - 1131
EP - 1141
%@ 1869-1951
Y1 - 2017
PB - Zhejiang University Press & Springer
ER -

The clifford Fourier transform (CFT) can be applied to both vector and scalar fields. However, due to problems with big data, CFT is not efficient, because the algorithm is calculated in each semaphore. The sparse fast Fourier transform (sFFT) theory deals with the big data problem by using input data selectively. This has inspired us to create a new algorithm called sparse fast CFT (SFCFT), which can greatly improve the computing performance in scalar and vector fields. The experiments are implemented using the scalar field and grayscale and color images, and the results are compared with those using FFT, CFT, and sFFT. The results demonstrate that SFCFT can effectively improve the performance of multivector signal processing.


概要:Clifford傅里叶变换(Clifford Fourier transform, CFT)可以应用于矢量场和标量场,但无法有效解决大数据问题,因为该算法是基于每个信号量计算的。稀疏快速傅里叶变换(sparse fast Fourier transform, sFFT)理论通过选择性地使用输入数据来处理大数据问题。受之启发,我们提出一个称为稀疏快速Clifford傅里叶变换(sparse fast CFT, SFCFT)的算法,该算法能够大幅度提高在标量场和矢量场中的计算性能。实验对标量场、灰度图和彩色图像数据进行处理,通过与FFT,CFT和sFFT进行比较,表明SFCFT可以有效提升多矢量信号处理的性能。


Darkslateblue:Affiliate; Royal Blue:Author; Turquoise:Article


[1]Batard, T., Berthier, M., Saint-Jean, C., 2010. Clifford–Fourier transform for color image processing. In: Bayro-Corrochano, E., Scheuermann, G. (Eds.), Geometric Algebra Computing. Springer London, London, UK, p.135-162.

[2]Bujack, R., Scheuermann, G., Hitzer, E., 2015. Demystification of the geometric Fourier transforms and resulting convolution theorems. Math. Meth. Appl. Sci., 39(7): 1877-1890.

[3]Cao, W.M., Feng, H., 2010. Geometric Algebra in Biomimetic Pattern Recognition and Signal Processing. Science Press, Beijing, China (in Chinese).

[4]Cao, W.M., Liu, H., Xu, C., et al., 2013. 3D medical image registration based on conformal geometric algebra. Sci. China Inform. Sci., 43(2):254-274.

[5]Ebling, J., Scheuermann, G., 2003. Clifford convolution and pattern matching on vector fields. IEEE Visualization, p.193-200.

[6]Ebling, J., Scheuermann, G., 2005. Clifford Fourier transform on vector fields. IEEE Trans. Visual. Comput. Graph., 11(4):469-479.

[7]Evans, C.J., Sangwine, S.J., Ell, T.A., 2000. Colour-sensitive edge detection using hypercomplex filters. 10th European Signal Processing Conf., p.1-4.

[8]Frigo, M., Johnson, S.G., 2005. The design and implementation of FFTW3. Proc. IEEE, 93(2):216-231.

[9]Gilbert, A., Indyk, P., 2010. Sparse recovery using sparse matrices. Proc. IEEE, 98(6):937-947.

[10]Gilbert, A.C., Indyk, P., Iwen, M., et al., 2014. Recent developments in the sparse Fourier transform: a compressed Fourier transform for big data. IEEE Signal Process. Mag., 31(5):91-100.

[11]Hassanieh, H., Adib, F., Katabi, D., et al., 2012a. Faster GPS via the sparse Fourier transform. Proc. 18th Annual Int. Conf. on Mobile Computing and Networking, p.353-364.

[12]Hassanieh, H., Indyk, P., Katabi, D., et al., 2012b. Nearly optimal sparse Fourier transform. Proc. 44th Annual ACM Symp. on Theory of Computing, p.563-578.

[13]Hassanieh, H., Indyk, P., Katabi, D., et al., 2012c. Simple and practical algorithm for sparse Fourier transform. Proc. 23rd Annual ACM-SIAM Symp. on Discrete Algorithms, p.1183-1194.

[14]Hassanieh, H., Shi, L., Abari, O., et al., 2014. GHz-wide sensing and decoding using the sparse Fourier transform. Proc. IEEE INFOCOM, p.2256-2264.

[15]Hestenes, D., 1999. New Foundations for Classical Mechanics. Springer, New York, USA.

[16]Hestenes, D., Sobczyk, G., 1984. Clifford Algebra to Geometric Calculus. Springer, New York, USA.

[17]Hitzer, E., 2012. Introduction to Clifford’s geometric algebra. SICE J. Contr. Meas. Syst. Integr., 4(1):1-11.

[18]Hitzer, E., 2013. The Clifford Fourier transform in real Clifford algebras. Int. Conf. on the Applications of Computer Science and Mathematics in Architecture and Civil Engineering, p.227-240.

[19]Hitzer, E., Mawardi, B., 2008. Clifford Fourier transform on multivector fields and uncertainty principles for dimensions n=2 (mod 4) and n=3 (mod 4). Adv. Appl. Clifford Alg., 18(3-4):715-736.

[20]Hitzer, E., Sangwine, S.J., 2013. Quaternion and Clifford Fourier transforms and wavelets. In: Hitzer, E., Stephen, J., Sangwine, S.J. (Eds.), Trends in Mathematic. Springer Basel, Basel, Switzerland.

[21]Hitzer, E., Helmstetter, J., Abłamowicz, R., 2013. Square roots of –1 in real Clifford algebras. In: Hitzer, E., Stephen, J., Sangwine, S.J. (Eds.), Trends in Mathematic. Springer Basel, Basel, Switzerland.

[22]Iwen, M.A., 2010. Combinatorial sublinear-time Fourier algorithms. Found. Comput. Math., 10(3):303-338.

[23]Li, H.B., 2005. Conformal geometric algebra—a new framework for computational geometry. J. Comput. Aid. Des. Comput. Graph., 17(11):2383-2393.

[24]Mishra, B., Wilson, P., Wilcock, R., 2015. A geometric algebra co-processor for color edge detection. Electronics, 4(1): 94-117.

[25]Mueen, A., Nath, S., Liu, J., 2010. Fast approximate correlation for massive time-series data. Proc. ACM SIGMOD Int. Conf. on Management of Data, p.171-182.

[26]Porat, E., Strauss, M.J., 2012. Sublinear time, measurementoptimal, sparse recovery for all. Proc. 23rd Annual ACM-SIAM Symp. on Discrete Algorithms, p.1215-1227.

[27]Reich, W., Scheuermann, G., 2010. Analyzing real vector fields with Clifford convolution and Clifford–Fourier transform. In: Bayro-Corrochano, E., Scheuermann, G. (Eds.), Geometric Algebra Computing. Springer, London, UK, p.121-133.

[28]Schlemmer, M., Hotz, I., Natarajan, V., et al., 2005. Fast Clifford Fourier transformation for unstructured vector field data. Proc. Int. Conf. on Numerical Grid Generation in Computational Field Simulations, p.101-110.

[29]Schumacher, J., Puschel, M., 2014. High-performance sparse fast Fourier transforms. IEEE Workshop on Signal Processing Systems, p.1-6.

[30]Shi, L., Hassanieh, H., Davis, A., et al., 2014. Light field reconstruction using sparsity in the continuous Fourier domain. ACM Trans. Graph., 34(1), Article 12.

[31]Smith, J.O., 2011. Spectral Audio Signal Processing. W3K Publishing, London, UK.

[32]Wang, R., Jing, L.B., Tao, L., et al., 2013. Digital watermarking algorithm for 3D point cloud model based on Clifford algebra. J. Shanghai Jiao Tong Univ., 47(12):1863-1869.

[33]Wang, R., Zhang, X., Cao, W.M., 2015. Clifford fuzzy support vector machines for classification. Adv. Appl. Clifford Alg., 26(2):1-22.

[34]Xie, W., Cao, W.M., Meng, S., 2008. Coverage analysis for sensor networks based on Clifford algebra. Sci. China Inform. Sci., 51(5):460-475.

[35]Xu, C., Liu, H., Ouyang, C.J., et al., 2011. Theory and application of Clifford pseudo-differential operator on multispectral image. Sci. Sin. Inform., 41(12):1423-1435.

Open peer comments: Debate/Discuss/Question/Opinion


Please provide your name, email address and a comment

Journal of Zhejiang University-SCIENCE, 38 Zheda Road, Hangzhou 310027, China
Tel: +86-571-87952276/87952783; E-mail: jzus@zju.edu.cn
Copyright © 2000 - Journal of Zhejiang University-SCIENCE