MP(Matching Pursuits)
1. The basic idea: from the dictionary matrix D (complete atomic library), choose one and signal y the best match of atomic (that is, a column), build a sparse approximation, and the residual signal, and then continue to choose and residual signal the best match of atoms, repeated iterations, signal y can be linear and by these atoms, plus the residual values. Obviously, if the residuals are in the negligible range, then the signal Y is a linear combination of these atoms.
2. How to select the atom that best matches signal Y?
Answer: Calculate the inner product of signal Y with each column of the dictionary matrix (or residual matrix), and select the atom with the largest absolute value, which is the one that best matches signal Y in this iteration.
Think: why is PI *< RI-1, PI >? Should not ask the projection vector PI * (ri – 1, PI > / | | PI ^ 2?
OMP(Orthogonal Matching Pursuits)
1. Basic idea: in MP algorithm, the vertical projection of the signal (residual value) on the selected atom is non-orthogonal, which makes the result of each iteration suboptimal rather than optimal, and the convergence needs many iterations. The improvement of OMP algorithm is that all the selected atoms are normalized in each step of decomposition, which makes OMP algorithm converge faster when the accuracy is the same.
2. How to orthogonalize:
Its residual value is orthogonal to each of the preceding components
3. Algorithm steps:
BP(Basis Pursuits)
1. Basic idea: optimize the problem
PS: Remove the absolute value of the objective function and solve:
Disadvantages: Compared with GREEDY algorithms such as MP and OMP, BP optimization algorithm has high computational complexity and long reconstruction time.
FOCUSS(focal underdetermined system solver)
It is essentially a weighted least norm least square method. The FOCUSS algorithm uses a posterior knowledge iterative weighting to gradually concentrate the energy of the solution obtained from the smallest norm. The iterative method is adopted to generate a new weighting function from the iterative data obtained by the previous calculation, and the energy of the iterative data obtained by the new weighting function is more concentrated than that of the previous step.
reference
MP algorithm and OMP algorithm and their ideas
Introduction to Matching pursuit algorithm (MP)
Basis Pursuit (BP) for Compressed Sensing Reconstruction Algorithm