结构化压缩感知：理论到应用

压缩感知

需积分: 10 148 浏览量更新于2024-07-19 1 收藏 6.88MB PDF 举报

身份认证购VIP最低享 7 折!

30元优惠券

"这篇文章主要探讨了压缩感知(Compressed Sensing, CS)这一领域的基本概念、发展历程以及在实际应用中的新趋势。它扩展了传统压缩感知理论，关注于结构化的压缩感知架构和更丰富的信号模型。" 正文: 压缩感知是一种新兴的信号处理技术，它打破了传统的采样理论，允许以远低于奈奎斯特定理所要求的速率对信号进行采样，然后重构信号。这一领域的研究在过去几年中得到了广泛的关注。早期的压缩感知理论主要集中在离散到离散的测量架构上，通常采用随机矩阵作为测量操作器，并假设信号具有标准的稀疏性。然而，随着压缩感知在不同应用领域的深入，如图像处理、医学成像和无线通信等，原有的理论框架需要进行扩展。文章《Structured Compressed Sensing: From Theory to Applications》强调了利用信号和测量结构的重要性。这意味着随机矩阵被更符合实际采集硬件特性的结构化传感架构所替代，这些架构能够更好地适应实际的硬件限制。此外，标准的稀疏性假设也被扩展到了包括更丰富的一类信号，比如连续时间信号和非均匀稀疏信号。这使得压缩感知能处理更复杂的数据模型，更好地适应现实世界中的各种信号类型。文章探讨了如何通过结构化的压缩感知策略将数学理论转化为实际应用，从而发掘其潜力，提高信号处理的效率和准确性。优化方法在压缩感知中扮演着关键角色，因为重构信号的过程通常是一个非线性和非凸的优化问题。文章可能涉及了如梯度下降法、迭代阈值算法、正则化技术等优化策略，这些方法可以帮助找到信号的最优稀疏表示，从而实现高质量的信号恢复。压缩感知的研究不仅限于理论发展，而是紧密地与实际应用相结合，不断地探索新的测量架构和信号模型，以应对各种工程挑战。通过深入理解信号的内在结构和测量过程的特性，可以设计出更加高效和实用的压缩感知系统。这种理论与实践的结合，使压缩感知在数据科学和工程领域展现出广阔的应用前景。

资源详情

资源推荐

When we consider sparse signals, the CS recovery process consists of a search for the sparsest signal x that

yields the measurements y. By deﬁning the `

“norm” of a vector kxk

as the number of nonzero entries in x,

the simplest way to pose a recovery algorithm is using the optimization

bx = arg min

x∈R

kxk

subject to y = Φx. (10)

Solving (10) relies on an exhaustive search and is successful for all x ∈ Σ

when the matrix Φ has the sparse

solution uniqueness property (i.e., for M as small as 2K, see Theorems 2 and 4). However, this algorithm has

combinatorial computational complexity, since we must check whether the measurement vector y belongs to the

span of each set of K columns of Φ, K = 1, 2, . . . , N . Our goal, therefore, is to ﬁnd computationally feasible

algorithms that can successfully recover a sparse vector x from the measurement vector y for the smallest possible

number of measurements M.

An alternative to the `

“norm” used in (10) is to use the `

norm, deﬁned as kxk

n=1

|x(n)|. The resulting

adaptation of (10), known as basis pursuit (BP) [22], is formally deﬁned as

bx = arg min

x∈R

kxk

subject to y = Φx. (11)

Since the `

norm is convex, (11) can be seen as a convex relaxation of (10). Thanks to the convexity, this

algorithm can be implemented as a linear program, making its computational complexity polynomial in the signal

length [49].

The optimization (11) can be modiﬁed to allow for noise in the measurements y = Φx + n; we simply change

the constraint on the solution to

bx = arg min

x∈R

kxk

subject to ky − Φxk

≤ , (12)

where  ≥ knk

is an appropriately chosen bound on the noise magnitude. This modiﬁed optimization is known as

basis pursuit with inequality constraints (BPIC) and is a quadratic program with polynomial complexity solvers [49].

The Lagrangian relaxation of this quadratic program is written as

bx = arg min

x∈R

kxk

+ λky − Φxk

, (13)

and is known as basis pursuit denoising (BPDN). There exist many efﬁcient solvers to ﬁnd BP, BPIC, and BPDN

solutions; for an overview, see [51].

Oftentimes, a bounded-norm noise model is overly pessimistic, and it may be reasonable instead to assume that

the noise is random. For example, additive white Gaussian noise n ∼ N(0, σ

I) is a common choice. Approaches

designed to address stochastic noise include complexity-based regularizaton [52] and Bayesian estimation [53].

These methods pose probabilistic or complexity-based priors, respectively, on the set of observable signals.

The particular prior is then leveraged together with the noise probability distribution during signal recovery.

Optimization-based approaches can also be formulated in this case; one of the most popular techniques is the

Dantzig selector [54]:

bx = arg min

x∈R

kxk

s. t. kΦ

(y − Φx)k

∞

≤ λ

log Nσ, (14)

A similar set of recovery algorithms, known as total variation minimizers, operate on the gradient of an image, which exhibits sparsity

for piecewise smooth images [50].

Algorithm 1 Orthogonal Matching Pursuit

Input: CS matrix Φ, measurement vector y

Output: Sparse representation bx

Initialize: bx

= 0, r = y, Ω = ∅, i = 0

while halting criterion false do

i ← i + 1

b ← Φ

r {form residual signal estimate}

Ω ← Ω ∪ supp(T (b, 1)) {update support with residual}

Ω

← Φ

†

Ω

y, bx

Ω

← 0 {update signal estimate}

r ← y − Φbx

{update measurement residual}

end while

return bx ← bx

where k · k

∞

denotes the `

∞

-norm, which provides the largest-magnitude entry in a vector and λ is a constant

parameter that controls the probability of successful recovery.

An alternative to optimization-based approaches, are greedy algorithms for sparse signal recovery. These methods

are iterative in nature and select columns of Φ according to their correlation with the measurements y determined

by an appropriate inner product. For example, the matching pursuit and orthogonal matching pursuit algorithms

(OMP) [24, 55] proceed by ﬁnding the column of Φ most correlated to the signal residual, which is obtained by

subtracting the contribution of a partial estimate of the signal from y. The OMP method is formally deﬁned as

Algorithm 1, where T (x, K) denotes a thresholding operator on x that sets all but the K entries of x with the

largest magnitudes to zero, and x|

Ω

denotes the restriction of x to the entries indexed by Ω. The convergence

criterion used to ﬁnd sparse representations consists of checking whether y = Φx exactly or approximately; note

that due to its design, the algorithm cannot run for more than M iterations, as Φ has M rows. Other greedy

techniques that have a similar ﬂavor to OMP include CoSaMP [56], detailed as Algorithm 2, and Subspace Pursuit

(SP) [57]. A simpler variant is known as iterative hard thresholding (IHT) [58]: starting from an initial signal

estimate bx

= 0, the algorithm iterates a gradient descent step followed by hard thresholding, i.e.,

= T (bx

i−1

+ Φ

(y − Φbx

i−1

), K), (15)

until a convergence criterion is met.

D. CS Recovery Guarantees

Many of the CS recovery algorithms above come with guarantees on their performance. We group these results

according to the matrix metric used to obtain the guarantee.

First, we review reuslts that rely on coherence. As a ﬁrst example, BP and OMP recover a K-sparse vector from

noiseless measurements when the matrix Φ satisﬁes (6) [28, 30, 31]. There also exist coherence-based guarantees

designed for meausrements corrupted with arbitrary noise.

Algorithm 2 CoSaMP

Input: CS matrix Φ, measurement vector y, sparsity K

Output: K-sparse approximation bx to true signal x

Initialize: bx

= 0, r = y, i = 0

while halting criterion false do

i ← i + 1

e ← Φ

r {form residual signal estimate}

Ω ← supp(T (e, 2K)) {prune residual}

T ← Ω ∪ supp(bx

i−1

) {merge supports}

← Φ

†

y, b|

← 0 {form signal estimate}

← T (b, K) {prune signal using model}

r ← y − Φbx

{update measurement residual}

end while

return bx ← bx

Theorem 5. [59] Let the signal x ∈ Σ

and write y = Φx + n. Denote γ = knk

. Suppose that K ≤

(1/µ(Φ) + 1)/4 and  ≥ γ in (12). Then the output bx of (12) has error bounded by

kx − bxk

≤

γ + 

1 − µ(Φ)(4K − 1)

, (16)

while the output bx of the OMP algorithm with halting criterion krk

≤ γ has error bounded by

kx − bxk

≤

1 − µ(Φ)(K − 1)

, (17)

provided that γ ≤ A(1 − µ(Φ)(2K − 1))/2 for OMP, with A being a positive lower bound on the magnitude of

the nonzero entries of x.

Note here that BPIC must be aware of the noise magnitude γ to make  ≥ γ, while OMP must be aware of the

noise magnitude γ to set an appropriate convergence criterion. Additionally, the error in Theorem 5 is proportional

to the noise magnitude γ. This is because the only assumption on the noise is its magnitude, so that n might be

aligned to maximally harm the estimation process.

In the random noise case, bounds on kx − bxk

can only be stated in high probability, since there is always

a small probability that the noise will be very large and completely overpower the signal. For example, under

additive white Gaussian noise (AWGN), the guarantees for BPIC in Theorems 5 hold with high probability when

the parameter  = σ

M + η

√

2M, with η denoting an adjustable parameter to control the probability of knk

being too large [60]. A second example gives a related result for the BPDN algorithm.

Theorem 6. [61] Let the signal x ∈ Σ

and write y = Φx+n, where n ∼ N(0, σ

I). Suppose that K < 1/3µ(Φ)

and consider the BPDN optimization problem (13) with λ =

16σ

log M. Then, with probability on the order

剩余59页未读，继续阅读

407xiaokai

粉丝: 0
资源: 1

结构化压缩感知：理论到应用

陆吾生_压缩感知讲义、论文与PPT.zip

一篇很好的有关压缩感知文章（概述性）

压缩感知入门学习整理

四篇压缩感知的入门资料

压缩感知论文

基于matlab实现的压缩感知中迂回式匹配追踪算法 压缩感知

小波omp，压缩感知程序

最全压缩感知入门资料指导

CS_MP.rar_CS MP matl_CS-MP_MP重构算法_matlab mp2d_压缩感知CS

压缩传感资料整理——Compressive Sensing

omp.zip_OMP 一维_omp_压缩跟踪

压缩感知：理论与进展概述-面向初学者

压缩感知：理论与资源概览

2012年压缩感知综述：理论与应用

探索压缩感知理论：稀疏表示与应用详解

多层感知机在姓氏分类中的应用与代码解析

压缩传感入门：简单易懂的详解

压缩传感入门：探索信号处理的新境界

压缩传感初探：从正交变换到矩阵分析

最新资源

基于matlab实现的压缩感知中迂回式匹配追踪算法压缩感知