CN106899305A - A kind of primary signal reconstructing method based on Second Generation Wavelets - Google Patents

Abstract

The invention discloses a kind of primary signal reconstructing method based on Second Generation Wavelets.Its implementation is：The present invention uses the Second Generation Wavelets to carry out rarefaction representation to primary signal x as sparse base, x samplings are carried out to primary signal with computing cluster afterwards, measured value y is obtained by calculation matrix Φ and primary signal x, measured value y is stored or is transmitted, the reconstruct of data is finally carried out using segmentation orthogonal matching pursuit, make it possible to by measured value y, i.e. result after primary signal x compressions recovers primary signal x in the distortion range for allowing.The present invention solves the problems, such as that traditional compressed sensing technology can not well carry out rarefaction representation for destructuring mass network data, propose a kind of primary signal reconstructing method based on Second Generation Wavelets, to solve the problems, such as that conventional compression perceives the unworthiness for destructuring mass network data, compression ratio and distortion as small as possible as big as possible is reached.

Description

A kind of primary signal reconstructing method based on Second Generation Wavelets

Technical field

The invention belongs to field of data compression, more particularly to a kind of primary signal reconstructing method based on Second Generation Wavelets,The reconstruct to destructuring mass network data is perceived suitable for conventional compression.

Background technology

Compressed sensing as an emerging sampling theory, by using the sparse characteristic of data, can far below howUnder conditions of Qwest's sample rate, data sample of the data volume much smaller than primary signal is obtained, then by nonlinear algorithm weightStructure primary signal.

Traditional compressed sensing technology is developed for being applied to compression of images field, due to view data available pointThe form of battle array is indicated, and rarefaction representation can be carried out to it well as sparse base with first generation small echo.And for non-knotStructure mass network data, due to its obvious unstructured nature, it is right well to be difficult to as sparse base using first generation small echoIt carries out rarefaction representation, and this will cause compressed sensing to be remarkably decreased the quality of destructuring mass network data.

Second Generation Wavelets method, relative to Traditional Wavelet algorithm, is a kind of more fast and effectively wavelet transformation realization sideMethod, is independent of Fourier conversion, completes the construction to biorthog-onal wavelet filter in time domain completely.This building method existsStructured Design and self-adaptive construction aspect outstanding advantages compensate for the deficiency of traditional frequency domain building method.In compressed sensing technologyIn, be used as sparse base by Second Generation Wavelets carries out rarefaction representation to primary signal so that destructuring mass data energyEnough by good rarefaction representation.

The content of the invention

It is an object of the invention to propose a kind of primary signal reconstructing method based on Second Generation Wavelets, to solve traditional pressureContracting perceives the unworthiness problem for destructuring mass network data, to realize as big as possible compression ratio and as small as possibleDistortion.

To achieve the above object, technical scheme includes as follows：

A kind of primary signal reconstructing method based on Second Generation Wavelets, comprises the following steps：

Step 1：Rarefaction representation is carried out to primary signal, sparse coefficient is obtained by sparse base and primary signal；

Step 2：Primary signal is sampled, measured value is obtained by calculation matrix and primary signal；

Step 3：Sparse base, measured value and random number seed are stored；

Step 4：Sparse coefficient is obtained by iteration, primary signal is reconstructed using sparse base.

Further according to the primary signal reconstructing method based on Second Generation Wavelets, to primary signal described in step 1Rarefaction representation is carried out, sparse coefficient is obtained by sparse base and primary signal：

For the point set S={ x for giving₁,x₂,…,x_n, there is x₁<x₂<…<x_n, n=k × 2^l, wherein n, k, l is just wholeNumber；

Matrix V for any one 2k × 2k, then V^LTable takes following k × 2k half parts of matrix V, V^UExpression takes squareK × 2k half parts of the top of battle array V, have

Be used as sparse base by Second Generation Wavelets carries out rarefaction representation to primary signal x so that destructuring mass dataRarefaction representation can be carried out to primary signal x by good rarefaction representation, carried out as follows：

(1-1) constructs the matrix M of 2k × 2k_1,i,Wherein i=1 ..., n/2k, s_i=(i-1) 2k；

Matrix M_1,iOrthogonal basis U_1,i, U_1,i=[Orth (M_1,i)]^T, Orth represents and seeks orthogonal Base computing；By U_1,iObtain U₁：

By U₁Obtain first basic matrix Ψ₁, first basic matrix Ψ₁It is fortune in the middle of necessary when constructing sparse base ΨCalculate result, Ψ₁=U₁；

(1-2) constructs a matrix M of 2k × 2k_2,i,Wherein i=1 ..., n/2k, byM_2,iObtain U_2,i, U_2,i=[Orth (M_2,i)]^T；Pass through U again_2,iObtain U₂′：

Wherein n₂=n/4k, by U₂' obtain U₂,Wherein I_n/2It is the unit square of (n/2) × (n/2)Battle array；

By U₂And U₁, obtain second basic matrix ψ₂, ψ₂=U₁U₂；

According to structural matrix M_1,iMethod construct M_1,2iAnd M_1,2i-1；

(1-3) obtains j-th basic matrix ψ_j, wherein j=2 ..., log₂(n/k) the matrix M of 2k × 2k, is constructed_j,i,Wherein i=1 ..., n/2k, by M_j,iU can be obtained_j,i, U_j,i=[Orth (M_j,i)]^T, byU_j,iU can be obtained_j′：

By U_j' U can be obtained_j,

For j=2 ..., log₂(n/k) U obtained by_jAnd U₁, j-th basic matrix ψ can be obtained_j, ψ_j=U₁U₂…U_j；

(1-4) obtains maximum log as j₂(n/k) when, j-th basic matrix ψ of gained_jAs sparse base ψ, i.e.,

(1-5) obtains sparse coefficient s, specific s=ψ by sparse base ψ and primary signal x^-1X, wherein ψ^-1Expression asks diluteDredge the inverse matrix of base ψ；

The sparse coefficient s is exactly the result of primary signal x rarefaction representations on sparse base ψ.

Further according to the primary signal reconstructing method based on Second Generation Wavelets, to primary signal described in step 2Sampled, measured value is obtained by calculation matrix and primary signal；

One size of construction is the Bernoulli random matrixes of M × N as calculation matrix Φ, and each of which element is onlyIt is vertical to obey Bernoulli distributions, the i-th row, jth row element Φ_i,jRepresent：

Measured value y, y=Φ x=Φ ψ s=As are obtained by calculation matrix Φ and primary signal x.

Further according to the primary signal reconstructing method based on Second Generation Wavelets, to sparse base, survey described in step 3Value and random number seed are stored：

The random number seed of sparse base ψ, measured value y and Bernoulli random matrixes as calculation matrix Φ is carried outStorage, is called when needing and primary signal is reconstructed；

The random number seed refers to the true random number that computer is used to generate random matrix, each element in matrixAll it is to be calculated through algorithm by a true random number from computer system time, the true random number is random numberSeed；Certain in seed, in the case that algorithm is certain, the random matrix of acquisition is identical；In storage, it is not necessary to which storage is passedDefeated whole calculation matrix Φ, only stores random number seed；

Further according to the primary signal reconstructing method based on Second Generation Wavelets, obtained by iteration described in step 4To sparse coefficient, primary signal is reconstructed using sparse base, carried out as follows：

(4-1) obtains measured value y, random number seed and sparse base ψ, generates calculation matrix Φ, and by calculation matrix ΦSensing matrix A, A=Φ ψ are obtained with sparse base ψ；

(4-2) does not start residual error r during iteration₀=y, does not start index set during iterationIteration timeThe initial value 1 of number t, wherein t is iterations, and maximum iteration is t_max；

The residual error r that (4-3) is obtained by last iteration_t-1With the line number M of sensing matrix A, thresholding T is obtained_h,||·||₂2 norms of matrix are sought in expression, and wherein ts is threshold parameter ts, when rt represents the t times iterationResidual error；

By sensing matrix A and residual error r_t-1A vectorial u of a length of N is obtained, there are u=abs (A^Tr_t-1), abs () is representedModulus value；

For 1≤j≤N, calculate successively<r_t-1,a_j>,<·,·>Inner product of vectors is sought in expression, the N number of numerical value structure that will be obtainedInto vectorial u, thresholding T is more than in selection u_hValue, the row sequence number j of correspondence sensing matrix A is constituted into set J₀, the collection is combined into rowSequence number set, J₀Represent the index that each iteration finds；

(4-4) index set Λ_t=Λ_t-1∪J₀, row set A_t=A_t-1∪a_j, seek y=A_ts_tLeast square solution, obtain s_t'sEstimateUpdate residual errort=t+1；

Wherein a_jThe jth row of representing matrix sensing matrix A, A_tRepresent by index Λ_tThe row set of the sensing matrix A for selecting；

If Λ_t=Λ_t-1, or t>t_max, or r_t=0, then stop iteration；

Reconstruct gainedIn Λ_tThere is nonzero term at place, and its value is last time iteration gained sparse coefficient s_t,It is iteration knotTo the final estimate of sparse coefficient s, s during beam_tTo the estimate of sparse coefficient s during for the t times iteration；

At the end of (4-5) iteration, sparse coefficient is obtainedUsing sparse base ψ restructural primary signals, that is, obtain original letterThe estimate of number x

The estimateThe primary signal for as reconstructing.

The present invention compared with prior art, has the following advantages that：

1. the present invention to primary signal x using Second Generation Wavelets as sparse base due to carrying out rarefaction representation so that non-knotStructure mass data can solve traditional compressed sensing technology based on first generation small echo to non-by good rarefaction representationThe unworthiness problem of structuring mass data, obtains larger compression ratio, and Second Generation Wavelets are multinomials, so having meterCalculate fireballing advantage.

2. the present invention is due to carrying out the reconstruct of data using segmentation orthogonal matching pursuit, enabling by measured value y,That is the result after primary signal x compressions, primary signal x is recovered in the distortion range for allowing, and is provided to improving compression ratioSound assurance.

Brief description of the drawings

Fig. 1 is that a kind of primary signal reconstructing method based on Second Generation Wavelets of the present invention realizes flow chart.

Specific embodiment

To make the objects, technical solutions and advantages of the present invention become more apparent, below in conjunction with accompanying drawing, to of the present inventionScheme and effect are described in further detail.

As shown in figure 1, the present invention is to a kind of primary signal reconstructing method based on Second Generation Wavelets, specific steps are such asIt is lower described.

Step 1：Rarefaction representation is carried out to primary signal, sparse coefficient is obtained by sparse base and primary signal.

For the point set S={ x for giving₁,x₂,…,x_n, wherein x₁<x₂<…<x_n, n=k × 2^l, n, k, l is just wholeNumber.

Matrix V for any one 2k × 2k, then V^LTable takes following k × 2k half parts of matrix V, V^UExpression takes squareK × 2k half parts of the top of battle array V, have

Be used as sparse base by Second Generation Wavelets carries out rarefaction representation to primary signal x so that destructuring mass dataRarefaction representation can be carried out to primary signal x by good rarefaction representation, carried out as follows：

(1-1) constructs the matrix M of 2k × 2k_1,iIt is as follows：

Wherein i=1 ..., n/2k, s_i=(i-1) 2k.

Matrix M_1,iOrthogonal basis U_1,i, U_1,i=[Orth (M_1,i)]^T, Orth is represented and is sought orthogonal Base computing, by U_1,iObtain U₁：

By U₁Obtain first basic matrix Ψ₁, first basic matrix Ψ₁It is fortune in the middle of necessary when constructing sparse base ΨCalculate result, Ψ₁=U₁。

(1-2) constructs a matrix M of 2k × 2k_2,i,Wherein i=1 ..., n/2k, byM_2,iObtain U_{2, i}, U_{2, i}=[Orth (M_{2, i})]^T, then by U_{2, i}Obtain U₂′：

Wherein n₂=n/4k, by U₂' obtain U₂,Wherein I_n/2It is the unit square of (n/2) × (n/2)Battle array.

By U₂And U₁, obtain second basic matrix ψ₂, ψ₂=U₁U₂。

According to structural matrix M_{1, i}Method construct M_1,2iAnd M_1,2i-1。

(1-3) obtains j-th basic matrix ψ_j, wherein j=2 ..., log₂(n/k) the matrix M of 2k × 2k, is constructed_{J, i},Wherein i=1 ..., n/2k, by M_{J, i}U can be obtained_{J, i}, U_{J, i}=[Orth (M_{J, i})]^T, byU_{J, i}U can be obtained_j′：

By U_j' U can be obtained_j,

For j=2 ..., log₂(n/k) U obtained by_jAnd U₁, j-th basic matrix Ψ can be obtained_j, ψ_j=U₁U₂…U_j。

(1-4) obtains maximum log as j₂(n/k) when, j-th basic matrix ψ of gained_jAs sparse base ψ, i.e.,

(1-5) obtains sparse coefficient s, specific s=ψ by sparse base ψ and primary signal x^-1x.Wherein ψ^-1Expression asks diluteDredge the inverse matrix of base ψ.

The sparse coefficient s is exactly the result of primary signal x rarefaction representations on sparse base ψ.

Step 2：Primary signal is sampled, measured value is obtained by calculation matrix and primary signal.

One size of construction is the Bernoulli random matrixes of M × N as calculation matrix Φ, and each of which element is onlyIt is vertical to obey Bernoulli distributions, the i-th row, jth row element Φ_i,jRepresent：

Measured value y, y=Φ x=Φ ψ s=As are obtained by calculation matrix Φ and primary signal x.

Step 3：Sparse base, measured value and random number seed are stored.

The random number seed of sparse base ψ, measured value y and Bernoulli random matrixes as calculation matrix Φ is carried outStorage, is called when needing and primary signal is reconstructed.

The random number seed refers to the true random number that computer is used to generate random matrix, each element in matrixAll it is to be calculated through algorithm by a true random number from computer system time, the true random number is random numberSeed.Certain in seed, in the case that algorithm is certain, the random matrix of acquisition is identical.In storage, it is not necessary to which storage is passedDefeated whole calculation matrix Φ, only stores random number seed.

Step 4：Sparse coefficient is obtained by iteration, primary signal is reconstructed using sparse base.

Carry out as follows：

(4-1) obtains measured value y, random number seed and sparse base ψ, generates calculation matrix Φ, and by calculation matrix ΦSensing matrix A, A=Φ ψ are obtained with sparse base ψ；

(4-2) does not start residual error r during iteration₀=y, does not start index set during iterationIteration timeThe initial value 1 of number t, wherein t is iterations, and maximum iteration is t_max；

The residual error r that (4-3) is obtained by last iteration_t-1With the line number M of sensing matrix A, thresholding T is obtained_h,||·||₂2 norms of matrix, wherein t are asked in expression_sIt is threshold parameter t_s, r_tWhen representing the t times iterationResidual error；

By sensing matrix A and residual error r_t-1Obtain a vectorial u of a length of N, u=abs (A^Tr_t-1), abs () is represented and askedModulus value；

For 1≤j≤N, calculate successively<r_t-1,a_j>,<,·>Inner product of vectors is sought in expression, and the N number of numerical value that will be obtained is constitutedVectorial u, thresholding T is more than in selection u_hValue, the row sequence number j of correspondence sensing matrix A is constituted into set J₀, the collection is combined into row sequenceNumber set, J₀Represent the index that each iteration finds；

(4-4) index set Λ_t=Λ_t-1∪J₀, row set A_t=A_t-1∪a_j, seek y=A_ts_tLeast square solution, obtain s_t'sEstimateUpdate residual errort=t+1；

Wherein a_jThe jth row of representing matrix sensing matrix A, A_tRepresent by index Λ_tThe row set of the sensing matrix A for selecting；

If Λ_Λ=Λ_t-1, or t>t_max, or r_t=0, then stop iteration；

Reconstruct gainedIn Λ_tThere is nonzero term at place, and its value is last time iteration gained sparse coefficient s_t,For iteration terminatesWhen to the final estimate of sparse coefficient s, s_tTo the estimate of sparse coefficient s during for the t times iteration；

At the end of (4-5) iteration, sparse coefficient is obtainedUsing sparse base ψ restructural primary signals, that is, obtain original letterThe estimate of number x

The estimateThe primary signal for as reconstructing.

The above is only and the preferred embodiment of the present invention is described, technical scheme is not limited toThis, any known deformation that those skilled in the art are made on the basis of major technique of the invention design belongs to the present inventionClaimed technology category, the specific protection domain of the present invention is defined by the record of claims.

Claims (5)

1. a kind of primary signal reconstructing method based on Second Generation Wavelets, it is characterised in that comprise the following steps：

Step 1：Rarefaction representation is carried out to primary signal, sparse coefficient is obtained by sparse base and primary signal；

Step 2：Primary signal is sampled, measured value is obtained by calculation matrix and primary signal；

Step 3：Sparse base, measured value and random number seed are stored；

Step 4：Sparse coefficient is obtained by iteration, primary signal is reconstructed using sparse base.

2. the primary signal reconstructing method of Second Generation Wavelets is based on according to claim 1, it is characterised in that institute in step 1State carries out rarefaction representation to primary signal, and sparse coefficient is obtained by sparse base and primary signal：

For the point set S={ x for giving₁,x₂,…,x_n, there is x₁<x₂<…<x_n, n=k × 2^l, wherein n, k, l is positive integer；

Matrix V for any one 2k × 2k, then V^LTable takes following k × 2k half parts of matrix V, V^UExpression takes matrix VK × 2k half parts of top, have

Be used as sparse base by Second Generation Wavelets carries out rarefaction representation to primary signal x so that destructuring mass data canBy good rarefaction representation, rarefaction representation is carried out to primary signal x, carried out as follows：

(1-1) constructs the matrix M of 2k × 2k_1,i’Wherein i=1 ..., n/2k,s_i=(i-1) 2k；

Matrix M_1,iOrthogonal basis U_1,i, U_1,i=[Orth (M_1,i)]^T, Orth represents and seeks orthogonal Base computing；By U_1,iObtain U₁：

By U₁Obtain first basic matrix Ψ₁, first basic matrix Ψ₁It is necessary intermediate operations knot when constructing sparse base ΨReally, Ψ₁=U₁；

(1-2) constructs a matrix M of 2k × 2k_2,i,Wherein i=1 ..., n/2k, by M_2,iObtainU_2,i, U_2,i=[Orth (M_2,i)]^T；Pass through U again_2,iObtain U₂′：

Wherein n₂=n/4k, by U₂' obtain U₂,Wherein I_n/2It is the unit matrix of (n/2) × (n/2)；

By U₂And U₁, obtain second basic matrix ψ₂, ψ₂=U₁U₂；

According to structural matrix M_1,iMethod construct M_1,2iAnd M_1,2i-1；

(1-3) obtains j-th basic matrix ψ_j, wherein j=2 ..., log₂(n/k) the matrix M of 2k × 2k, is constructed_j,i,Wherein i=1 ..., n/2k, by M_j,iU can be obtained_j,i, U_j,i=[Orth (M_j,i)]^T, byU_j,iU can be obtained_j′：

By U_j' U can be obtained_j,

For j=2 ..., log₂(n/k) U obtained by_jAnd U₁, j-th basic matrix ψ can be obtained_j, ψ_j=U₁U₂…U_j；

(1-4) obtains maximum log as j₂(n/k) when, j-th basic matrix ψ of gained_jAs sparse base ψ, i.e.,

(1-5) obtains sparse coefficient s, specific s=ψ by sparse base ψ and primary signal x^-1X, wherein ψ^-1Sparse base ψ is sought in expressionInverse matrix；

The sparse coefficient s is exactly the result of primary signal x rarefaction representations on sparse base ψ.

3. the primary signal reconstructing method based on Second Generation Wavelets according to claim 1 or claim 2, it is characterised in that in step 2It is described that primary signal is sampled, measured value is obtained by calculation matrix and primary signal；

One size of construction is the Bernoulli random matrixes of M × N as calculation matrix Φ, and each of which element independently takesFrom Bernoulli distributions, the i-th row, jth row element Φ_i,jRepresent：

${\mathrm{\&Phi;}}_{i,j}=\left\{\begin{array}{cc}\frac{1}{\sqrt{M}}& P=\frac{1}{2}\\ -\frac{1}{\sqrt{M}}& P=\frac{1}{2}\end{array}\right.=\frac{1}{\sqrt{M}}\left\{\begin{array}{cc}+1& P=\frac{1}{2}\\ -1& P=\frac{1}{2}\end{array}\right.$

Measured value y, y=Φ x=Φ ψ s=As are obtained by calculation matrix Φ and primary signal x.

4. the primary signal reconstructing method of Second Generation Wavelets is based on according to claim any one of 1-3, it is characterised in that stepSparse base, measured value and random number seed are stored described in rapid 3：

The random number seed of sparse base ψ, measured value y and Bernoulli random matrixes as calculation matrix Φ is stored,It is called when needing and primary signal is reconstructed；

The random number seed refers to the true random number that computer is used to generate random matrix, and each element in matrix isIt is calculated through algorithm by a true random number from computer system time, the true random number is random severalSon；Certain in seed, in the case that algorithm is certain, the random matrix of acquisition is identical；In storage, it is not necessary to storage transmissionWhole calculation matrix Φ, only stores random number seed.

5. the primary signal reconstructing method of Second Generation Wavelets is based on according to claim any one of 1-4, it is characterised in that stepSparse coefficient is obtained by iteration described in rapid 4, primary signal is reconstructed using sparse base, carried out as follows：

(4-1) obtains measured value y, random number seed and sparse base ψ, generates calculation matrix Φ, and by calculation matrix Φ and diluteDredge base ψ and obtain sensing matrix A, A=Φ ψ；

(4-2) does not start residual error r during iteration₀=y, does not start index set during iterationIterations tInitial value 1, wherein t be iterations, maximum iteration is t_max；

The residual error r that (4-3) is obtained by last iteration_t-1With the line number M of sensing matrix A, thresholding T is obtained_h,||·||₂2 norms of matrix, wherein t are asked in expression_sIt is threshold parameter t_s, r_tRepresent residual error during the t times iteration；

By sensing matrix A and residual error r_t-1Obtain a vectorial u of a length of N, u=abs (A^Tr_t-1), abs () represents modulus value；

For 1≤j≤N, calculate successively<r_t-1,a_j>,<·,·>Inner product of vectors is sought in expression, and the N number of numerical value that will be obtained constitutes vectorU, thresholding T is more than in selection vector u_hValue, the row sequence number j of correspondence sensing matrix A is constituted into set J₀, the collection is combined into row sequenceNumber set, J₀Represent the index that each iteration finds；

(4-4) index set Λ_t=Λ_t-1∪J₀, row set Λ_t=Λ_t-1∪a_j, seek y=A_ts_tLeast square solution, obtain s_t'sEstimateUpdate residual errort=t+1；

Wherein a_jThe jth row of representing matrix sensing matrix A, A_tRepresent by index Λ_tThe row set of the sensing matrix A for selecting；

If Λ_t=Λ_t-1, or t>t_max, or r_t=0, then stop iteration；

Reconstruct gainedIn Λ_tThere is nonzero term at place, and its value is last time iteration gained sparse coefficient s_t,It is right at the end of for iterationThe final estimate of sparse coefficient s, s_tTo the estimate of sparse coefficient s during for the t times iteration；

At the end of (4-5) iteration, sparse coefficient is obtainedUsing sparse base ψ restructural primary signals, that is, obtain primary signal x'sEstimate

The estimateThe primary signal for as reconstructing.