Method for realizing sparse signal recovery on CPU (Central Processing Unit) based on OMP (Orthogonal Matching Pursuit) algorithm

A sparse signal and algorithm technology, applied in the field of signal processing, can solve the problems of slow convergence speed of MP algorithm and low probability of successful recovery, etc., and achieve the effect of significant acceleration performance of vector calculation, improved running speed, and fast convergence speed

Inactive Publication Date: 2012-10-24
TSINGHUA UNIV
View PDF3 Cites 20 Cited by
  • Summary
  • Abstract
  • Description
  • Claims
  • Application Information

AI Technical Summary

Problems solved by technology

The disadvantage of this method is that the convergence speed of the MP algorithm itself is s

Method used

the structure of the environmentally friendly knitted fabric provided by the present invention; figure 2 Flow chart of the yarn wrapping machine for environmentally friendly knitted fabrics and storage devices; image 3 Is the parameter map of the yarn covering machine
View more

Image

Smart Image Click on the blue labels to locate them in the text.
Viewing Examples
Smart Image
  • Method for realizing sparse signal recovery on CPU (Central Processing Unit) based on OMP (Orthogonal Matching Pursuit) algorithm
  • Method for realizing sparse signal recovery on CPU (Central Processing Unit) based on OMP (Orthogonal Matching Pursuit) algorithm
  • Method for realizing sparse signal recovery on CPU (Central Processing Unit) based on OMP (Orthogonal Matching Pursuit) algorithm

Examples

Experimental program
Comparison scheme
Effect test

Embodiment Construction

[0038] The present invention will be described in further detail below in conjunction with the accompanying drawings and embodiments.

[0039] exist figure 1 In the flowchart of the parallel OMP algorithm, memory space needs to be allocated and initialized on the GPU first. Then carry out iterative operation, this part is divided into the following four steps:

[0040] Step 1, calculate the residual energy, and check whether to terminate the iteration.

[0041]Step 2: Calculate the correlation between the observation matrix and the vector in parallel, and then select the column index with the highest correlation in parallel.

[0042] Step 3: Add the column vector corresponding to the column index generated in the previous step to the base matrix.

[0043] Step 4, based on the expanded basis matrix, the least squares method is used to estimate the restoration result. Skip to step one.

[0044] After the iteration is terminated, the recovery result of the last iteration is ...

the structure of the environmentally friendly knitted fabric provided by the present invention; figure 2 Flow chart of the yarn wrapping machine for environmentally friendly knitted fabrics and storage devices; image 3 Is the parameter map of the yarn covering machine
Login to view more

PUM

No PUM Login to view more

Abstract

The invention discloses a method for realizing sparse signal recovery on a CPU (Central Processing Unit) based on an OMP (Orthogonal Matching Pursuit) algorithm. The method comprises the following steps of: generating an observation matrix on the CPU, and selecting a column with the greatest relevancy to the residual in the observation matrix to complement a basis matrix, wherein the residual is the difference between the observations generated by an actual observation signal and an estimation signal, and the basis matrix is a matrix formed by nonzero element index values in corresponding column vectors in the observation matrix; by use of a method of least squares, estimating the nonzero elements of an original signal on the basis matrix of the kth step; continuing to select the column with the greatest relevancy to the residual in the observation matrix on the CPU to complement the basis matrix, when the variance between the real observation and the estimation observation is lower than a specified threshold, ending the iterative operation. The method provided by the invention has the following advantages: in parallel realization of the OMP algorithm by the CPU, the advantages of low computational complexity and high convergence rate of the OMP algorithm are combined, and simultaneously, the characteristic of remarkable acceleration performance of the CPU algorithm to the vector computation is fully used, and the running speed of the sparse recovery algorithm is improved effectively.

Description

technical field [0001] The invention belongs to the technical field of signal processing, and in particular relates to a method for realizing sparse signal restoration on a GPU based on an OMP algorithm. Background technique [0002] In recent years, compressive sensing theory has received widespread attention, which shows that under the premise that the signal satisfies sparsity, the original signal can be completely restored by sampling the data with a sampling frequency much smaller than the Nyquist sampling rate. Compressed sensing is formulated with the following mathematical expression: [0003] For the original signal x∈R N , through the observation matrix Φ∈R M×N , get the observation vector y∈R M : [0004] y=Φx (1) [0005] Where M<<N, the number of significant elements in x is S, and S<<N. The research of CS theory is: given the observation y, estimate the sparsest solution x that satisfies the formula (1), that is, to find a Satisfy: [0006]...

Claims

the structure of the environmentally friendly knitted fabric provided by the present invention; figure 2 Flow chart of the yarn wrapping machine for environmentally friendly knitted fabrics and storage devices; image 3 Is the parameter map of the yarn covering machine
Login to view more

Application Information

Patent Timeline
no application Login to view more
IPC IPC(8): G06F17/16
Inventor 张颢陈帅孟华东王希勤
Owner TSINGHUA UNIV
Who we serve
  • R&D Engineer
  • R&D Manager
  • IP Professional
Why Eureka
  • Industry Leading Data Capabilities
  • Powerful AI technology
  • Patent DNA Extraction
Social media
Try Eureka
PatSnap group products

Browse by: Latest US Patents, China's latest patents, Technical Efficacy Thesaurus, Application Domain, Technology Topic.

© 2024 PatSnap. All rights reserved.Legal|Privacy policy|Modern Slavery Act Transparency Statement|Sitemap