CN102255616A - Sparse estimation-oriented synchronous subspace tracking method - Google Patents
Sparse estimation-oriented synchronous subspace tracking method Download PDFInfo
- Publication number
- CN102255616A CN102255616A CN2011101475593A CN201110147559A CN102255616A CN 102255616 A CN102255616 A CN 102255616A CN 2011101475593 A CN2011101475593 A CN 2011101475593A CN 201110147559 A CN201110147559 A CN 201110147559A CN 102255616 A CN102255616 A CN 102255616A
- Authority
- CN
- China
- Prior art keywords
- mrow
- iteration
- signal
- support set
- sparse
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Pending
Links
- 238000000034 method Methods 0.000 title claims abstract description 36
- 230000001360 synchronised effect Effects 0.000 title claims abstract description 23
- 239000011159 matrix material Substances 0.000 claims abstract description 37
- 238000012545 processing Methods 0.000 claims abstract description 10
- 230000007704 transition Effects 0.000 claims abstract description 10
- 239000013598 vector Substances 0.000 claims description 22
- 238000005259 measurement Methods 0.000 claims description 20
- 238000010606 normalization Methods 0.000 claims description 4
- 238000011084 recovery Methods 0.000 description 19
- OAICVXFJPJFONN-UHFFFAOYSA-N Phosphorus Chemical compound [P] OAICVXFJPJFONN-UHFFFAOYSA-N 0.000 description 2
- 238000002474 experimental method Methods 0.000 description 2
- 230000009286 beneficial effect Effects 0.000 description 1
- 238000005457 optimization Methods 0.000 description 1
- 238000000926 separation method Methods 0.000 description 1
- 238000004088 simulation Methods 0.000 description 1
- 239000013589 supplement Substances 0.000 description 1
- 238000012360 testing method Methods 0.000 description 1
Images
Landscapes
- Measurement Of Velocity Or Position Using Acoustic Or Ultrasonic Waves (AREA)
Abstract
The invention discloses a sparse estimation-oriented synchronous subspace tracking method, which belongs to the field of sparse signal processing and aims at solving the problems of higher complexity and easily-caused error matching phenomenon caused by the adoption of an SOMP (Space Oblique Mercator Projection) estimation algorithm. The method comprises the following steps of: acquiring an observed signal Y of a multi-sparsity signal X by using a measuring matrix A; calculating a subspace which is most matched with a residual Rl-1 obtained by the (l-1)th iteration after the lth iteration and assigning a union set of the obtained subspace and a support set S of the (l-1)th iteration to the lth iteration to obtain a transition support set S'; modifying the support set S calculated with the (l-1)th iteration by using the lth iteration; and performing no more than K times of iteration on the multi-sparsity signal X of which the sparsity is K to recover a source signal support set. The method is suitable for recovering a multi-sparsity signal support set, and plays a decisive role in recovering a later stage signal.
Description
Technical Field
The invention belongs to the field of sparse signal processing, and particularly relates to a synchronous estimation method for a support set of multiple sparse signals.
Background
A sparse signal is a signal in which most of the time signals are zero and few of the time signals are non-zero. Due to its unique properties, sparse signal processing has become a popular direction in the signal processing field in recent years, and a plurality of branches, such as underdetermined blind separation, compressed sensing, and the like, have been developed. In many problems of processing sparse signals, recovery of acquired sparse signals is often needed, wherein a greedy algorithm is an important method for sparse signal recovery, the most core idea of the greedy algorithm is to find a support set of signals, and as long as the support set of signals can be found, source signals can be successfully recovered.
The traditional greedy algorithm mainly aims at a one-dimensional signal or a sparse signal, while in a practical problem, the signal may be multidimensional, and a practical problem is that synchronous estimation needs to be carried out on the multidimensional signal. I.e. to solve the following optimization problem:
arg min||X||2，0s.t.y-AX is 0 formula one
Wherein
Is a multi-sparse signal, N is the length of each sparse signal, d is the number of sparse signals,in order to measure the matrix of the measurements,to observe the signal, define | | | X | non-woven phosphor2，0The following were used:
Wherein X [ i ]:]line i, which represents X, when | | X [ i,:]||2if > 0, I is equal to 1, otherwise, I is equal to 0. If | | X | non-conducting phosphor2，0And if the sparsity of X is less than or equal to K, the sparsity of X is called K.
At present, the multidimensional sparse signal support set estimation mainly adopts a Simultaneous Orthogonal Matching Pursuit (SOMP) algorithm. The SOMP algorithm can only estimate one supporting point of the signal at a time, and the supporting point is not changed after being determined, which is easy to cause the phenomenon of mismatching.
Disclosure of Invention
The invention provides a sparse estimation-oriented synchronous subspace tracking method, aiming at solving the problems that an SOMP estimation algorithm is high in complexity and prone to causing error matching.
The invention is realized by the following scheme: a synchronous subspace tracking method facing sparse estimation comprises the following steps:
firstly, acquiring an observation signal Y of a plurality of sparse signals X through a measurement matrix A,
setting initial state values of all parameters in the synchronous subspace tracking process:
wherein the polytrophobic signal X is a real matrix with dimension Nxd and sparsity K, i.e.
Wherein
A set of real numbers is represented by,
setting the measurement matrix A to be a real matrix of m rows and N columns, i.e.
WhereinA set of real numbers is represented by,
presetting iteration error delta and setting initial value R of residual error0Y, rarefaction signal support set
Representing an empty set, wherein the initial value of the iteration number l is 1;
step two, according to the residual error R after the first-1 iterationl-1Calculating the sum residual R after the first iterationl-1Best matched subspace
Wherein,
is the k-th element of the base vector 1, ATRepresenting measured momentsTranspose of matrix A, equation three, the slave vector
Assigning the largest K element labels to subspaces
Step three, the subspace obtained in the step two
And assigning the union of the support set S of the l-1 iteration to the transition support set S' obtained by the l iteration, namely:
Step four, calculating a subspace which is most matched with the observation signal Y after the first iteration according to the observation signal Y and the transition support set S' of the first iteration obtained in the step three, namely a signal support set S:
Wherein,
is ASPseudo-inverse of' and AS'represents a matrix composed of column vectors indexed by elements in the transition support set S';
step five, calculating residual error R after the first iteration according to the signal support set S obtained in the step fourl：
Wherein A isSRepresenting a matrix composed of column vectors indexed by elements in the signal support set S;
step six, judging the residual error R after the ith iteration in the step fivelIf the norm 2 is less than the preset iteration error delta, if the judgment result is yes, executing the step nine, and if the judgment result is no, executing the step seven;
step seven, judging whether the value of the iteration times l in the step six is larger than the observation number m, if so, executing the step nine, and if not, executing the step eight;
step eight, adding 1 to the value of the iteration times l, and returning to the step two;
and ninthly, outputting a multi-sparse signal support set S to realize sparse estimation-oriented synchronous subspace tracking.
The invention has the beneficial effects that: the invention corrects the support set S obtained by the (l-1) th iteration operation through the (l) th iteration, and for a multi-sparse signal X with the support number of K, the search of the support set can be completed without exceeding the K iterations under the condition that the measurement number m is large enough. The method has low complexity, reduces the phenomenon of error matching, can simultaneously meet the requirements of recovery probability and recovery efficiency, and is widely applied to the recovery process of the sparse signal in the fields of information source coding, blind signal processing, compressed sensing and the like.
Drawings
FIG. 1 is a flow chart of a sparse estimation oriented synchronous subspace tracking method of the present invention; FIG. 2 is a graph of recovery probability results of the sparse estimation-oriented synchronous subspace tracking method and the SOMP algorithm when the X amplitude of the sparse signal is a Gaussian distribution signal; FIG. 3 is a graph showing the comparison of recovery probabilities of the sparse-estimation-oriented synchronous subspace tracking method and the SOMP algorithm when the amplitude of the sparse signal X is a binary signal.
Detailed Description
The first embodiment is as follows: the present embodiment is described with reference to fig. 1: in this embodiment, a sparse estimation-oriented synchronous subspace tracking method includes:
firstly, acquiring an observation signal Y of a plurality of sparse signals X through a measurement matrix A,
setting initial state values of all parameters in the synchronous subspace tracking process:
wherein the polytrophobic signal X is a real matrix with dimension Nxd and sparsity K, i.e.
Wherein
A set of real numbers is represented by,
setting the measurement matrix A to be a real matrix of m rows and N columns, i.e.
WhereinA set of real numbers is represented by,
presetting iteration error delta and setting initial value R of residual error0Y, rarefaction signal support set
Representing an empty set, wherein the initial value of the iteration number l is 1;
step two, according to the residual error R after the first-1 iterationl-1Calculating the sum residual R after the first iterationl-1Best matched subspace
Wherein,
is the k-th element of the base vector 1, ATThe transpose matrix representing the measurement matrix A, equation three, i.e., the slave vector
Assigning the largest K element labels to subspaces
Step three, the subspace obtained in the step two
And assigning the union of the support set S of the l-1 iteration to the transition support set S' obtained by the l iteration, namely:
Step four, calculating a subspace which is most matched with the observation signal Y after the first iteration according to the observation signal Y and the transition support set S' of the first iteration obtained in the step three, namely a signal support set S:
Wherein,
is ASPseudo-inverse of' and AS'represents a matrix composed of column vectors indexed by elements in the transition support set S';
step five, calculating residual error R after the first iteration according to the signal support set S obtained in the step fourl：
Wherein A isSRepresenting a matrix composed of column vectors indexed by elements in the signal support set S;
step six, judging the residual error R after the ith iteration in the step fivelIf the norm 2 is less than the preset iteration error delta, if the judgment result is yes, executing the step nine, and if the judgment result is no, executing the step seven;
step seven, judging whether the value of the iteration times l in the step six is larger than the observation number m, if so, executing the step nine, and if not, executing the step eight;
step eight, adding 1 to the value of the iteration times l, and returning to the step two;
and ninthly, outputting a multi-sparse signal support set S to realize sparse estimation-oriented synchronous subspace tracking.
In the second step of the embodiment, K support points can be estimated at one time, so that the operation efficiency of the algorithm is improved.
In step four of the embodiment, the subspace S which is most matched with the observation signal Y after the ith iteration is corrected, so that the accuracy of searching for the signal support set is improved.
The second embodiment is as follows: this embodiment is a further description of a first step in the sparse estimation oriented synchronous subspace tracking method according to the first embodiment, in which the iteration error δ is preset to 10 "5.
The third concrete implementation mode: the present embodiment is a further description of the sparse estimation oriented synchronous subspace tracking method according to the first or second embodiment, where the measurement matrix a in the first step obeys gaussian distribution.
A fourth specific embodiment is a further supplement to the first, second or third specific embodiments, where in the first step, the method further includes a step of performing amplitude normalization processing on each column vector in the measurement matrix a, where a process of performing amplitude normalization processing on a qth column vector a [ q ] in the measurement matrix a is as follows:
measuring the q column vector A [ q ] of the matrix A]Divided by | | A [ q ]]||2The latter column vector is used as the new qth column vector of the measurement matrix A, where q ∈ {1, 2.,. N }, | · | | computationally |2Representing a 2-norm.
Fifth embodiment this embodiment will be described in detail below with reference to fig. 2 and 3. In the embodiment, the method and the SOMP algorithm are respectively applied to the support set estimation of the multi-sparse signal X, and the recovery probability of each algorithm is compared.
The process of calculating the recovery probability of each algorithm comprises the following steps:
randomly generating a Gaussian distribution measurement matrix
Giving a sparsity K, randomly selecting K positions, respectively assigning values to the K positions to obtain needed simulation test sparse signals, giving the number d of sparse signals, generating the remaining d-1 sparse signals according to the same method, wherein K non-zero positions of all d sparse signals are completely the same, namely signal support sets, so that a multi-sparse signal set X is obtained, and the amplitude of the multi-sparse signal X adopts Gaussian distribution or binary signals of 0-1;
obtaining an observation signal Y (AX) through the measurement matrix A, obtaining a multi-sparse signal support set S by utilizing each algorithm, and if S is the same as the support set of the source multi-sparse signal, successfully recovering;
and thirdly, running each recovery algorithm 500 times, and calculating the recovery probability.
In the experiment process of the embodiment, the signal with the Gaussian distribution amplitude and the binary signal of 0 to 1 are respectively adopted for the experiment. When the sparsity K of the multi-sparse signal X is 1, 2, 20 respectively, calculating the support set recovery probability of each algorithm under different K values under Gaussian distribution, and drawing a change curve of the recovery probability along with the sparsity. When the sparsity K of the multi-sparsity signal X is 1, 2, 13, calculating the support set recovery probability of each algorithm under different K values under the condition that the amplitude is 0-1 binary value distribution, and drawing a change curve of the recovery probability along with the sparsity.
The experimental results are shown in fig. 2 and 3, wherein fig. 2 is the experimental result of the signal with the amplitude of gaussian distribution, fig. 3 is the experimental result of the binary signal with 0-1, and fig. 2 and 3 are the bandsThe marked curve is the recovery probability by the method of the present embodimentCurve, band
The labeled curve is the recovery probability curve using the SOMP method. It can be seen from the figure that the recovery probability of the method of the present embodiment is greatly improved compared with the SOMP method for any kind of sparse signals, so that the present embodiment is particularly suitable for estimation of a sparse signal support set, and has a decisive role in recovery of signals in the later period.
Claims (4)
1. A synchronous subspace tracking method facing sparse estimation is characterized in that: the method comprises the following steps:
firstly, acquiring an observation signal Y of a plurality of sparse signals X through a measurement matrix A,
setting initial state values of all parameters in the synchronous subspace tracking process:
wherein the polytrophobic signal X is a real matrix with dimension Nxd and sparsity K, i.e.
Wherein
A set of real numbers is represented by,
setting the measurement matrix A to be a real matrix of m rows and N columns, i.e.
Wherein
A set of real numbers is represented by,
presetting iteration error delta and setting initial value R of residual error0Y, rarefaction signal support set
Representing an empty set, wherein the initial value of the iteration number l is 1;
step two, according to the residual error R after the first-1 iterationl-1Calculating the sum residual R after the first iterationl-1Best matched subspace
Wherein,
is the k-th element of the base vector 1, ATThe transpose matrix representing the measurement matrix A, equation three, i.e., the slave vector
Assigning the largest K element labels to subspaces
Step three, the subspace obtained in the step two
And assigning the union of the support set S of the l-1 iteration to the transition support set S' obtained by the l iteration, namely:
Step four, calculating a subspace which is most matched with the observation signal Y after the first iteration according to the observation signal Y and the transition support set S' of the first iteration obtained in the step three, namely a signal support set S:
Wherein,is ASPseudo-inverse of' and AS'represents a matrix composed of column vectors indexed by elements in the transition support set S';
step five, calculating residual error R after the first iteration according to the signal support set S obtained in the step fourl：
Wherein A isSRepresenting a matrix composed of column vectors indexed by elements in the signal support set S;
step six, judging the residual error R after the ith iteration in the step fivelIf the norm 2 is less than the preset iteration error delta, if the judgment result is yes, executing the step nine, and if the judgment result is no, executing the step seven;
step seven, judging whether the value of the iteration times l in the step six is larger than the observation number m, if so, executing the step nine, and if not, executing the step eight;
step eight, adding 1 to the value of the iteration times l, and returning to the step two;
and ninthly, outputting a multi-sparse signal support set S to realize sparse estimation-oriented synchronous subspace tracking.
2. The sparse estimation-oriented synchronous subspace tracking method according to claim 1, wherein: presetting an iteration error delta to be 10 in the step one-5。
3. The sparse estimation-oriented synchronous subspace tracking method according to claim 1, wherein: the measurement matrix a described in step one follows a gaussian distribution.
4. The sparse estimation-oriented synchronous subspace tracking method according to claim 3, wherein: in the first step, the method further includes a step of performing amplitude normalization processing on each column vector in the measurement matrix a, where the process of performing amplitude normalization processing on the qth column vector a [ q ] in the measurement matrix a is as follows:
measuring the q column vector A [ q ] of the matrix A]Divided by | | A [ q ]]||2The latter column vector is used as the new qth column vector of the measurement matrix A, where q ∈ {1, 2.,. N }, | · | | computationally |2Representing a 2-norm.
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN2011101475593A CN102255616A (en) | 2011-06-02 | 2011-06-02 | Sparse estimation-oriented synchronous subspace tracking method |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN2011101475593A CN102255616A (en) | 2011-06-02 | 2011-06-02 | Sparse estimation-oriented synchronous subspace tracking method |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| CN102255616A true CN102255616A (en) | 2011-11-23 |
Family
ID=44982630
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN2011101475593A Pending CN102255616A (en) | 2011-06-02 | 2011-06-02 | Sparse estimation-oriented synchronous subspace tracking method |
Country Status (1)
| Country | Link |
|---|---|
| CN (1) | CN102255616A (en) |
Cited By (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN102497337A (en) * | 2011-12-11 | 2012-06-13 | 天津大学 | Compressed sensing wireless communication channel estimation method based on sparsity self-adapting |
| CN103490848A (en) * | 2012-06-13 | 2014-01-01 | 华为技术有限公司 | Method and device for sparsity order estimation |
| CN105375927A (en) * | 2015-01-23 | 2016-03-02 | 四川大学 | Low frequency band number support set fast recovery algorithm based on MWC system |
Citations (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US20090063605A1 (en) * | 2007-08-28 | 2009-03-05 | Honda Motor Co., Ltd. | Signal processing device |
| CN101908889A (en) * | 2010-07-30 | 2010-12-08 | 哈尔滨工业大学 | Compressed sensing reconstructing method of sparse signal with unknown block sparsity |
| CN102034478A (en) * | 2010-11-17 | 2011-04-27 | 南京邮电大学 | Voice secret communication system design method based on compressive sensing and information hiding |
-
2011
- 2011-06-02 CN CN2011101475593A patent/CN102255616A/en active Pending
Patent Citations (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US20090063605A1 (en) * | 2007-08-28 | 2009-03-05 | Honda Motor Co., Ltd. | Signal processing device |
| CN101908889A (en) * | 2010-07-30 | 2010-12-08 | 哈尔滨工业大学 | Compressed sensing reconstructing method of sparse signal with unknown block sparsity |
| CN102034478A (en) * | 2010-11-17 | 2011-04-27 | 南京邮电大学 | Voice secret communication system design method based on compressive sensing and information hiding |
Cited By (6)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN102497337A (en) * | 2011-12-11 | 2012-06-13 | 天津大学 | Compressed sensing wireless communication channel estimation method based on sparsity self-adapting |
| CN102497337B (en) * | 2011-12-11 | 2014-08-20 | 天津大学 | Compressed sensing wireless communication channel estimation method based on sparsity self-adapting |
| CN103490848A (en) * | 2012-06-13 | 2014-01-01 | 华为技术有限公司 | Method and device for sparsity order estimation |
| CN103490848B (en) * | 2012-06-13 | 2016-12-21 | 华为技术有限公司 | The method and device that a kind of degree of rarefication is estimated |
| CN105375927A (en) * | 2015-01-23 | 2016-03-02 | 四川大学 | Low frequency band number support set fast recovery algorithm based on MWC system |
| CN105375927B (en) * | 2015-01-23 | 2018-01-23 | 四川大学 | Supported collection quick recovery method under low-frequency band number based on MWC systems |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| CN101908889B (en) | Compressed sensing reconstructing method of sparse signal with unknown block sparsity | |
| CN101895297B (en) | Compressed sensing-oriented block-sparse signal reconfiguring method | |
| CN103941220B (en) | The outer target Wave arrival direction estimating method of a kind of grid based on sparse reconstruct | |
| CN101908890B (en) | Blind reconstructing method of block sparse signal with unknown block size | |
| CN102611455B (en) | Compressed sensing-oriented sparse multiband signal reconstruction method | |
| CN101534168B (en) | Blind identification method of coding parameters of RS code of error-tolerant code | |
| CN109490819B (en) | Sparse Bayesian learning-based method for estimating direction of arrival of wave in a lattice | |
| CN111337893A (en) | Off-grid DOA estimation method based on real-value sparse Bayesian learning | |
| CN104007414B (en) | Estimating two-dimensional direction-of-arrival method and estimator based on planar array | |
| CN102880737B (en) | Based on the workpiece method for registering in flexible assembly and system | |
| CN103941221A (en) | Method for estimating parameters of space stretching electromagnetic vector sensor array | |
| CN110244272B (en) | Direction-of-arrival estimation method based on rank-denoising model | |
| CN105515585A (en) | Compressed sensing reconstruction method for signals with unknown sparseness | |
| CN103886207A (en) | Nest multiple-input and multiple-output radar DOA estimating method based on compressed sensing | |
| CN105678047B (en) | Merge empirical mode decomposition noise reduction and the wind field characterizing method of Complex Networks Analysis | |
| CN111562545A (en) | Sparse array DOA estimation method based on PD-ALM algorithm | |
| CN110907923B (en) | Bistatic EMVS-MIMO radar angle estimation algorithm and device based on parallel factor algorithm | |
| CN104392146A (en) | Underdetermined blind separation source signal recovery method based on SCMP (Subspace Complementary Matching Pursuit) algorithm | |
| CN107290717A (en) | For the direct localization method of multiple target of not rounded signal | |
| CN102255616A (en) | Sparse estimation-oriented synchronous subspace tracking method | |
| CN104155629B (en) | Fewer snapshots method for estimating signal wave direction under a kind of impact noise background | |
| CN102801428A (en) | Approximation optimization and signal acquisition reconstruction method for 0-1 sparse cyclic matrix | |
| Arnaudon et al. | Stochastic algorithms for computing p-means of probability measures, geometry of radar Toeplitz covariance matrices and applications to HR Doppler processing | |
| CN103336963A (en) | Method and device for image feature extraction | |
| CN103929256B (en) | A kind of multiframe compressed sensing signal spectrum detection method |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| C06 | Publication | ||
| PB01 | Publication | ||
| C10 | Entry into substantive examination | ||
| SE01 | Entry into force of request for substantive examination | ||
| C02 | Deemed withdrawal of patent application after publication (patent law 2001) | ||
| WD01 | Invention patent application deemed withdrawn after publication |
Application publication date: 20111123 |