智能贪婪追踪算法：l0最小化下的稀疏重构提升

6 浏览量更新于2024-08-26 收藏 2.87MB PDF 举报

本文主要探讨的是"基于l0最小化的稀疏重构智能贪婪追踪模型"，该研究针对压缩感知领域的经典问题——l0最小化稀疏重构提出了创新的解决方案。l0最小化是一个著名的NP完全问题，由于其计算复杂度极高，传统的算法往往难以有效处理，特别是在实际应用中寻求最优解。然而，贪婪算法通常被用于近似解决这类问题，但结果可能存在次优性。作者Dan Lin、Qiang Wang和Yi Shen针对这一挑战，提出了智能贪婪追踪（Intelligent Greedy Pursuit, IGP）算法。IGP算法的核心在于首先引入了一种新颖的优化函数，该函数考虑了稀疏性级别，即使在缺乏先验知识的情况下也能提供一种有效的框架。这与传统的l0最小化方法相比，能够更好地处理未知的稀疏性水平，从而提高重构的精度。接下来，作者设计了一种两周期优化算法，旨在通过全局搜索和组合优化问题的解决，智能地找到支持集以及相应的系数，从而达到更精确的信号或图像重建。这种设计结合了智能优化算法的全局视野和贪婪算法的高效匹配策略，能够在保持重建速度的同时，显著提升重构的质量。值得一提的是，IGP算法在算法复杂性和实际性能上都取得了突破。它在信号和图像重建任务中的表现超越了现有最先进的重建算法，且在保持较低测量速率的情况下，能够实现更准确的重构。这表明IGP不仅简化了求解过程，而且在实际应用中具有显著的优势。本文的研究对于压缩感知领域的l0最小化问题提供了一种创新且高效的解决方案，智能贪婪追踪模型有望在实际的压缩感知系统中发挥重要作用，推动压缩传感技术的进一步发展。

4. The proposed model IGP is as simple as greedy algo-

rithm, while it overcomes the common shortcoming

that greedy algorithm is more likely to fall into a sub-

optimal solution.

The rest of this paper is organized as follow: Section 2

presents the modeling of IGP, the two-cycle optimization

algorithm of IGP, the computational complexity analysis

and connections between IGP and other existing works.

Simulation results are given in Section 3 to illustrate the

performance of the proposed model IGP. Section 4 con-

cludes this paper.

The follow notations are used in the rest of this paper.

The l

norm of signal x can be represented by J xJ

. Let ϕ

indicates the measurement matrix and ϕ

represents the

ith column of ϕ. S ¼ 1; 2; …; N indicates the index of each

entries of the original signal, where N represents the

length of the original signal. Suppose K entries are selected

from S to generate the support collection I

, the vector x

consists the entries of x indexed by i  I

and the matrix

is composed of the columns of ϕ with indexes i  I

The pseudo-inverse operation of measurement matrix ϕ

can be calculated by ϕ

†

¼ðϕ

ϕÞ

 1

ϕ

, where > repre-

sents matrix transportation.

2. Intelligent greedy model

In this section, we ﬁrst propose a novel optimization

function for the sparse reconstruction problem, and then

design a two-cycle optimization algorithm to solve the

proposed optimization function. Next, we analyse the

computational complexity of IGP. In the end, we compare

our IGP model to some existing arts.

2.1. Modeling of IGP

Suppose the original signal x is sparse and the sparsity

level K is known as a prior, we can obtain the measure-

ment signal by y ¼ ϕx, where ϕ is the measurement

matrix. As applied in many greedy algorithms such as

OMP, SP, and CoSaMP, the l

minimization problem can be

handled by a two-step strategy. In the ﬁrst step, an esti-

mated support collection I which satisﬁes J xJ

¼ K is

obtained. Then the nonzero elements of the reconstructed

signal recx

can be calculated using the least square

method and the estimated solution recx is obtained by Eq

(4) in the second step:

recx

¼ ϕ

†

y and recx

S  I

¼ 0: ð4Þ

However, the sparsity level is hard to be estimated in

many reconstruction problem in practice. So we propose a

novel optimization function in Theorem 1 when the

sparsity level is unknown in advance. Before giving it, we

provide a uniqueness solution method in Lemma pro-

posed in [22], which can be used to prove the Theorem 1.

Lemma. Suppose that recx



with support collection I



is the

unique solution of Eq. (2), and that the sparsity level satisﬁes

K o sparkðϕÞ=2, where sparkðϕÞ is the smallest number of

columns from ϕ that are linearly dependent. Then we have

recx ¼ recx



if and only if ϕ



ϕ

†



y ¼ y, where I



satisfying



¼ K is the estimated support collection and the estimated

solution recx



is obtained using Eq. (4).

As described in Lemma, if the sparsity level satisﬁes

K o sparkðϕÞ=2, we can obtain the unique solution by

seeking a support collection I which satisﬁes I ¼ K and

ϕ

†

y ¼ y. If the estimated support collection can be

estimated, it satisﬁes FðIÞ¼0. As Eq. (5) satisﬁes f ðIÞ Z 0,

the optimization function of [22] can be set as Eq. (5) and

the estimated support collection can be obtained by opti-

mizing Eq. (6) when the sparsity level is known as a prior:

f ðIÞ¼‖ϕ

ϕ

†

y y‖

; ð5Þ

min

A Θ

f ðIÞ: ð6Þ

Theorem 1. Suppose the sparsity level K which satisﬁes

K r sparkðϕÞ=2 is unknown in advance, the two-step strategy

turns to estimate the collection I

by optimizing the opti-

mization function described in Eq. (7) and then the estimated

solution can be obtained by Eq. (8):

min

f ðI

Þ¼‖ϕ

ϕ

†

yy‖

; ð7Þ

where, the collection I

represents all mmcardinality

(where mm is bigger than the sparsity level K and smaller

than the measurement number m) subsets of the set S:

recx

¼ ϕ

†

y and recx

S  I

¼ 0: ð8Þ

Proof. As proved in [17], let the columns of ϕ be in general

position, suppose I

denotes the support of the original

signal x

and I

denotes the support of x

.IfI

is a subset of

, then we have perfect recovery:

¼ x

ð9Þ

□

If the support collection I satisﬁes J ϕ

ϕ

†

yy J

¼ 0

and the collection I

includes I, I

must satisfy the

condition that J ϕ

ϕ

†

yy J

¼ 0. So Eq. (7) can be set

as the optimization function and the reconstructed signal

can be obtained by optimizing the problem minf ðI

when the sparsity level is unknown in advance.

The representation of the optimization function of IGP

is the same as that of the optimization function in [22].

However, the independent variable I

of the optimization

function of IGP is different to that I of the optimization

function in [22], which is the main difference between

them. The length of I

does not equal to the sparsity

level, which means the sparsity level need not to be

known as a prior for reconstruction. The proposed opti-

mization function of IGP can relax the initial precondition

for reconstruction and can extend the applications of IGP.

In the condition that the sparsity level is known as a

prior, the size of the feasible domain Θ, which represents

the solution set consisted of all K-cardinality subsets of the

set S, can be calculated by C

. However, there is only one

global optimal solution. As mentioned in Theorem 1, the

size of the feasible domain Θ

can be calculated by C

when the sparsity level is unknown as a prior. While there

are C

mm  K

N  K

global optimal solutions. The main reason is

D. Li et al. / Signal Processing 122 (2016) 138–151140

剩余13页未读，继续阅读

weixin_38611254

粉丝: 4
资源: 898

智能贪婪追踪算法：l0最小化下的稀疏重构提升

压缩感知 随机梯度贪婪类追踪算法性能比较 MATLAB

基于深度学习的压缩感知FDD大规模MIMO系统稀疏信道估计算法.docx

Matching_Pursuit:匹配追踪 (MP) 算法以恢复稀疏信号-matlab开发

压缩感知重构算法综述.docx

压缩感知技术中OMP与MP稀疏重构方法比较

压缩感知技术下的L0-范数最小化问题解决方案

稀疏表示与逼近算法：凸松弛与贪婪法详解

利用贪婪算法优化组稀疏信号重建：matlab实现与应用

压缩感知基础重构算法新手入门指南

单幅图像非均匀校正与GPSR重构技术研究

最新资源

压缩感知随机梯度贪婪类追踪算法性能比较 MATLAB