A fast algorithm for <i>V</i>-system

doi:10.3785/j.issn.1008-9497.2023.06.011

Journal of Zhejiang University (Science Edition)

2023, Vol. 50

Issue (6): 761-769 DOI: 10.3785/j.issn.1008-9497.2023.06.011

CSIAM-GDC 2023

A fast algorithm for V-system

Wei CHEN¹(

),Jinwen QI¹,Jian LI²,Ruixia SONG³

^1.School of Artificial Intelligence and Computer Science，Jiangnan University，Wuxi 214122，Jiangsu Province，China
^2.Faculty of Applied Sciences，Macao Polytechnic University，Macao 999078，China
^3.College of Sciences，North China University of Technology，Beijing 100144，China

Download:

HTML( 0 )

PDF(1706KB)
Export: BibTeX | EndNote (RIS)

Abstract

V-system is a kind of complete orthogonal piecewise polynomial function system on $L 2 [0,1]$ , because of the discontinuous nature of its basis functions, it has significant advantages in the expression and analysis of discontinuous signals. However, in the current V-system transformation algorithm, for a signal with a length of N, it not only needs to generate and store an N-order orthogonal matrix in advance, but also its time complexity is as high as $Ο (N 3)$ . Therefore, in order to adapt to the efficient processing needs, this paper designs and implements a fast decomposition and reconstruction algorithm for V-systems from the perspective of multi-resolution analysis of V-systems. This fast algorithm does not need to store additional information, and its time complexity is only $Ο (N 2)$ . The test results show that the fast algorithm proposed in this paper can meet the requirements of high-efficiency processing of large-scale data, which lays the foundation for the application of V-system in more fields.

Key words： V-system orthogonal resolution analysis double scale equation multi wavelet fast algorithm

Received: 21 June 2023 Published: 30 November 2023

CLC:

TP 391

	Service
	E-mail this article
	Add to my bookshelf
	Add to citation manager
	E-mail Alert
	RSS
	Articles by authors
	Wei CHEN
	Jinwen QI
	Jian LI
	Ruixia SONG

Cite this article:

Wei CHEN,Jinwen QI,Jian LI,Ruixia SONG. A fast algorithm for V-system. Journal of Zhejiang University (Science Edition), 2023, 50(6): 761-769.

URL:

https://www.zjujournals.com/sci/EN/Y2023/V50/I6/761

V-系统的快速变换算法

V-系统是 $L 2 [0,1]$ 上的一类完备正交分段多项式函数系，由于其基函数的间断特性，在非连续信号的表达与分析上优势显著。然而，在目前的V-系统变换算法中，对于一个长度为N的信号，不仅需要事先生成并存储一个N阶的正交矩阵，而且其时间复杂度高达 $Ο (N 3)$ 。为实现对大规模数据的高效处理，从V-系统的多分辨率分析角度出发，设计并实现了V-系统的快速分解与重构算法，不仅无须存储额外信息，而且其时间复杂度仅为 $Ο (N)$ 。测试结果表明，提出的快速算法能够满足大规模数据高效处理要求，为V-系统在更多领域的应用奠定了基础。

关键词： V-系统, 多分辨率分析, 双尺度方程, 多小波, 快速算法

$k$	$V$ 系统
注释	尺度空间 $V 0$ $? k 0 x, ? k 1 x, ???? ?, ? k k x$	小波空间 $W 0$ $ψ k, 0 0,0 x, ψ k, 0 0,1 x, ???? ?, ψ k, 0 0, k x$	小波空间 $W 1$ $ψ k, 1 j, i x = 2 ψ k, 0 0, i (2 x - j), ???? x ∈ j 2, j + 1 2, 0, ???? 其他,$ $i = 0,1, 2, ?, k; j = 0,1$	小波空间 $W 2$ $ψ k, 2 j, i x = 2 ψ k, 0 0, i (4 x - j), ???? x ∈ j 4, j + 1 4, 0, ???? 其他,$ $i = 0,1, 2 ， ?, k; j = 0,1, 2,3$	小波空间 $W n$ $ψ k, n j, i x = 2 ψ k, 0 0, i (2 n x - j), ???? x ∈ j 2 n, j + 1 2 n, 0, ???? 其他,$ $i = 0,1, 2 ， ?, k; j = 0,1, 3 ， ?, 2 n - 1$
0					…
1					…
2					…
3					…

Table 1 Complete k th-order orthogonal V-system on the interval ［0， 1］

Table 2 Algorithm running time（in seconds） under different signal lengths

Fig.1 Contour cluster diagram

Fig.2 Precise reconstruction results of contour clusters


[1]	SHENSA M. The discrete wavelet transform： Wedding the a trous and Mallat algorithms［J］. IEEE Transactions on Signal Processing， 1992， 40（10）： 2464-2482. DOI：10.1109/78.157290 doi: 10.1109/78.157290

[2]	BLAHUT R E. Fast Algorithms for Signal Processing［M］. Cambridge： Cambridge University Press， 2010. doi:10.1017/cbo9780511760921 doi: 10.1017/cbo9780511760921

[3]	LEZCANO-CASADO M， MARTINEZ-RUBIO D. Cheap orthogonal constraints in neural networks： A simple parametrization of the orthogonal and unitary group［C］// International Conference on Machine Learning. Long Beach ：PMLR， 2019： 3794-3803. doi:10.48550/arXiv.1901.08428 doi: 10.48550/arXiv.1901.08428

[4]	SHAH S B， CHAKKA V K， REDDY A S. Orthogonal and non-orthogonal signal representations using new transformation matrices having NPM structure［J］. IEEE Transactions on Signal Processing， 2020， 68： 1229-1242. DOI：10.1109/tsp.2020.2971936 doi: 10.1109/tsp.2020.2971936

[5]	FEDORENKO S V. Duhamel/Hollmann-like discrete fourier transform algorithm with the smallest multiplicative complexity over a finite field［J］. IEEE Transactions on Signal Processing， 2020， 68： 4813-4823. DOI：10.1109/tsp.2020.3015419 doi: 10.1109/tsp.2020.3015419

[6]	MA H， QI D X， SONG R X， et al. The complete orthogonal V-system and its applications［J］. Communications on Pure and Applied Analysis， 2007， 6（3）： 853-871. DOI：10.3934/cpaa.2007.6.853 doi: 10.3934/cpaa.2007.6.853

[7]	齐东旭，宋瑞霞，李坚. 非连续正交函数： U-系统， V-系统，多小波及其应用［M］. 北京：科学出版社， 2011. QI D X， SONG R X， LI J. Discontinuous Orthogonal Function： U-System， V-System， Multiwavelet and Its Application［M］. Beijing： Science Press， 2011

[8]	李坚，宋瑞霞，叶梦杰，等. 基于三角域上V-系统的三维几何模型的正交重构［J］. 计算机学报， 2009， 32（2）： 193-202. DOI：10.3724/SP.J.1016.2009. 00193 LI J， SONG R X， YE M J， et al. Orthogonal reconstruction of 3D model based on V-system over triangular domain［J］. Journal of Computer Science and Technology， 2009， 32（2）： 193-202. DOI：10. 3724/SP.J.1016.2009.00193 doi: 10. 3724/SP.J.1016.2009.00193

[9]	YE B， YUAN X X， CAI Z C， et al. Severity assessment of COVID-19 based on feature extraction and V-descriptors［J］. IEEE Transactions on Industrial Informatics， 2021， 17（11）： 7456-7467. DOI：10. 1109/TII.2021.3056386 doi: 10. 1109/TII.2021.3056386

[10]	SONG R X， YAO D X， WANG X C， et al. Retrieval method for 3D object group based on V-system［J］. Journal of Advanced Mechanical Design， Systems， and Manufacturing， 2012， 6（3）： 340-353. DOI：10. 1299/JAMDSM.6.340 doi: 10. 1299/JAMDSM.6.340

[11]	WANG Z H， LIN H W. 3D shape retrieval based on Laplace operator and joint Bayesian model［J］. Visual Informatics， 2020， 4 （3）： 69-76. DOI：10.1016/j.visinf.2020.08.002 doi: 10.1016/j.visinf.2020.08.002

[12]	陈伟，张晓婷. 正交旋转不变V矩及其在图像重建中的应用［J］. 自动化学报， 2015， 41（2）： 376-385. DOI：10.16383/j.aas.2015.c140347 CHEN W， ZHANG X T. Orthogonal rotation-invariant V moments and application to image reconstruction［J］. IEEE/CAA Journal of Automatica Sinica， 2015， 41（2）： 376-385. DOI：10. 16383/j.aas.2015.c140347 doi: 10. 16383/j.aas.2015.c140347

[13]	宋传鸣，赵长伟，刘丹，等. 3D 多尺度几何分析研究进展［J］. 软件学报， 2015， 26（5）： 1213-1236. DOI：10.13328/j.cnki.jos.004822 SONG C M， ZHAO C W， LIU D， et al. Advances in three-dimensional multiscale geometrical analysis［J］. Journal of Software， 2015， 26（5）： 1213-1236. DOI：10.13328/j.cnki.jos.004822 doi: 10.13328/j.cnki.jos.004822

[14]	CAO W， MENG Z G， LI A J， et al. Thermal features of lunar regolith in mare humboldtianum based on brightness temperature differences and surface parameters［J］. Authorea Preprints， 2022. DOI：10. 1002/essoar.10505601.1 doi: 10. 1002/essoar.10505601.1

[15]	王小春，宋瑞霞. 一类正交函数系的离散表示及快速变换［J］. 计算机工程与应用， 2008， 44（8）： 40-44. doi:10.3778/j.issn.1002-8331.2008.08.012 WANG X C， SONG R X. Discrete representation and fast algorithm of new class of orthogonal system［J］. Computer Engineering and Applications， 2008， 44（8）： 40-44. doi:10.3778/j.issn.1002-8331.2008.08.012 doi: 10.3778/j.issn.1002-8331.2008.08.012

[16]	宋瑞霞，孙坦坦，孙相东，等. 广义V-系统的构造及相应的快速变换［J］. 计算机辅助设计与图形学学报， 2018， 30（5）： 808-815. DOI：10.3724/SP.J.1089. 2017.16644 SONG R X， SUN T T， SUN X D， et al. The construction of generalized V-system and the corresponding fast transformation［J］. Journal of Computer-Aided Design & Computer Graphics， 2018， 30（5）： 808-815. DOI：10.3724/SP.J.1089. 2017.16644 doi: 10.3724/SP.J.1089. 2017.16644

[17]	HUANG C， YANG L， QI D X. A new class of multi-wavelet bases： V-system［J］. Acta Mathematica Sinica， 2012， 28（1）： 105-120. DOI：10.1007/s10114-012-9424-8 doi: 10.1007/s10114-012-9424-8

[18]	陈伟，蔡占川，齐东旭，等. 从GF-系统到V-系统：V-系统的一种新的构造方法［J］. 澳门科技大学学报， 2009， 3（2）： 8-14. CHEN W， CAI Z C， QI D X， et al. From GF-system to V-system： A new construction method of V-system［J］. Journal of Macau University of Science and Technology， 2009， 3（2）： 8-14.

[19]	宋瑞霞，李成华，王小春，等. V-系统的小波函数的数学结构［J］. 中国科学（数学）， 2016（6）： 867-876. SONG R X， LI C H， WANG X C， et al. Mathematical structure of wavelet functions of the V-system［J］. Scientia Sinica（Mathematica）， 2016（6）： 867-876.

[1]	Zhe HUANG, Ben ZHA, Hangfeng SHEN, Guoqing ZHAI, Feiyan ZHANG. Characteristics of rainstorm in northwestern mountainous area of Zhejiang[J]. Journal of Zhejiang University (Science Edition), 2019, 46(2): 227-235.

[2]	JIANG Enhua. Research on the cyclic codes decoding based on the generalized orthogonal matching pursuit gOMP algorithm[J]. Journal of Zhejiang University (Science Edition), 2017, 44(5): 555-560,575.

Viewed

Full text

Abstract

Cited

Shared

Discussed