Sparse fast Clifford Fourier transform

Abstract

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.

Keywords

Sparse fast Fourier transform (sFFT) / Clifford Fourier transform (CFT) / Sparse fast Clifford Fourier transform (SFCFT) / Clifford algebra

References

[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. https://doi.org/10.1007/978-1-84996-108-0_8

[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. https://doi.org/10.1002/mma.3607

[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., , 2013. 3D medical image registration based on conformal geometric algebra. Sci. China Inform. Sci., 43(2):254–274. https://doi.org/10.1360/112012-592

[5] Ebling,J., Scheuermann, G., 2003. Clifford convolution and pattern matching on vector fields. IEEE Visualization, p.193–200. https://doi.org/10.1109/VISUAL.2003.1250372

[6] Ebling,J., Scheuermann, G., 2005. Clifford Fourier transform on vector fields. IEEE Trans. Visual. Comput. Graph., 11(4):469–479. https://doi.org/10.1109/TVCG.2005.54

[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. https://doi.org/10.1109/JPROC.2004.840301

[9] Gilbert,A., Indyk,P., 2010. Sparse recovery using sparse matrices. Proc. IEEE, 98(6):937–947. https://doi.org/10.1109/JPROC.2010.2045092

[10] Gilbert,A.C., Indyk,P., Iwen,M., , 2014. Recent developments in the sparse Fourier transform: a compressed Fourier transform for big data. IEEE Signal Process. Mag., 31(5):91–100. https://doi.org/10.1109/MSP.2014.2329131

[11] Hassanieh,H., Adib,F., Katabi,D., , 2012a. Faster GPS via the sparse Fourier transform. Proc. 18th Annual Int. Conf. on Mobile Computing and Networking, p.353–364. https://doi.org/10.1145/2348543.2348587

[12] Hassanieh,H., Indyk,P., Katabi,D., , 2012b. Nearly optimal sparse Fourier transform. Proc. 44th Annual ACM Symp. on Theory of Computing, p.563–578. https://doi.org/10.1145/2213977.2214029

[13] Hassanieh,H., Indyk,P., Katabi,D., , 2012c. Simple and practical algorithm for sparse Fourier transform. Proc. 23rd Annual ACM-SIAM Symp. on Discrete Algorithms, p.1183–1194. https://doi.org/10.1137/1.9781611973099.93

[14] Hassanieh,H., Shi,L., Abari,O., , 2014. GHz-wide sensing and decoding using the sparse Fourier transform. Proc. IEEE INFOCOM, p.2256–2264. https://doi.org/10.1109/INFOCOM.2014.6848169

[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.https://doi.org/10.1007/s00006-008-0098-3

[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. https://doi.org/10.1007/978-3-0348-0603-9

[21] Hitzer,E., Helmstetter, J., Abamowicz,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. https://doi.org/10.1007/978-3-0348-0603-9_7

[22] Iwen,M.A., 2010. Combinatorial sublinear-time Fourier algorithms. Found. Comput. Math., 10(3):303–338. https://doi.org/10.1007/s10208-009-9057-1

[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. https://doi.org/10.3390/electronics4010094

[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. https://doi.org/10.1145/1807167.1807188

[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. https://doi.org/10.1137/1.9781611973099.96

[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. https://doi.org/10.1007/978-1-84996-108-0_7

[28] Schlemmer,M., Hotz,I., Natarajan,V. , , 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. https://doi.org/10.1109/SiPS.2014.6986055

[30] Shi,L., Hassanieh, H., Davis,A. , , 2014. Light field reconstruction using sparsity in the continuous Fourier domain. ACM Trans. Graph., 34(1), Article 12. https://doi.org/10.1145/2682631

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

[32] Wang,R., Jing,L.B., Tao,L., , 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. https://doi.org/10.1007/s00006-015-0616-z

[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. https://doi.org/10.1007/s11432-008-0048-7

[35] Xu,C., Liu,H., Ouyang,C.J. , , 2011. Theory and application of Clifford pseudo-differential operator on multispectral image. Sci. Sin. Inform., 41(12):1423–1435. https://doi.org/10.1360/zf2011-41-12-1423

RIGHTS & PERMISSIONS

2017 Zhejiang University and Springer-Verlag GmbH Germany