iss压缩感知算法文献资源-CSDN文库

需积分: 9 38 浏览量 2014-05-28 14:47:07 上传评论 2 收藏 1.15MB PDF 举报

### ISS压缩感知算法知识点 #### 一、ISS算法概述 ISS算法是一种新的压缩感知（Compressed Sensing, CS）算法，旨在解决常见的ℓ1最小化问题。该算法基于逆尺度空间方法（Inverse Scale Space, ISS），能够高效地计算出最小化解，通过求解一系列低维非负最小二乘问题来实现。 #### 二、压缩感知理论基础压缩感知是一种信号处理技术，用于在数据采样阶段减少所需的数据量。它利用了信号的稀疏性或可压缩性这一特性，可以在远低于奈奎斯特采样率的情况下恢复信号。 **线性系统与稀疏表示**：在压缩感知中，通常面对的是一个欠定的线性系统 \[ Au = f \] 其中 \( A \in \mathbb{R}^{m \times n} \)，且 \( m \ll n \)。目标是找到最稀疏的解 \( u \in \mathbb{R}^n \)。 **ℓ0-范数与ℓ1-范数**：最稀疏的解通常通过最小化 \( u \) 的零元素个数（即 ℓ0-范数）来寻找，但这是一个非凸优化问题，计算复杂度高。因此，通常采用更易于处理的凸优化问题——最小化 ℓ1-范数，即 \[ \min_u \| u \|_1 \text{ s.t. } Au = f \] #### 三、ISS算法核心思想 ISS算法的核心在于利用逆尺度空间方法来求解上述的优化问题。这种方法可以高效地计算出最小化解，尤其适用于大规模问题。具体来说，该方法通过一系列迭代步骤，将原问题转化为一系列低维的非负最小二乘问题进行求解。 #### 四、算法流程 1. **初始化**：选择初始解 \( u^0 \) 和参数设置。 2. **迭代步骤**： - 对于每一步 \( k \)，构造一个适当的问题，使其能够在低维空间中求解。 - 解决这些低维非负最小二乘问题，得到解 \( u^{k+1} \)。 3. **收敛条件**：当满足一定的收敛标准时停止迭代过程。 #### 五、算法优势与应用场景 - **高效性**：通过低维问题的求解，显著减少了计算复杂度。 - **灵活性**：适用于不同类型的压缩感知问题，包括噪声情况下的正则化问题。 - **适用范围广泛**：可用于图像处理、数据压缩等多种领域。 #### 六、数学分析与实验结果 - **收敛性分析**：ISS算法提供了详细的收敛性分析，在一般情况下以及特殊条件下都有明确的结果。 - **实验观察**：通过多个数值实验验证了算法的有效性和性能。 #### 七、相关研究工作 - **参考文献**：例如[CT04a, CT04a, DE03, D06]等文献讨论了 ℓ0 与 ℓ1 最小化问题之间的等价性条件。 - **现有方法**：迭代阈值法 [BD09, DDD04] 及其变种 [DTD+06, NV09, TG07] 是另一种常用的求解方法。 #### 八、结论与展望 ISS算法作为一种新颖的方法，为压缩感知中的ℓ1最小化问题提供了一种高效的解决方案。通过利用逆尺度空间方法，该算法不仅能够有效地处理大规模问题，还具有良好的收敛性和鲁棒性。未来的研究方向可能包括进一步提高算法的效率、扩展其应用领域以及与其他技术的结合等方面。

资源推荐

资源详情

资源评论

An Adaptive Inverse Scale Space Method for

Compressed Sensing

Martin Burger

∗

Michael M¨oller

∗,†

Martin Benning

∗

Stanley Osher

†

Abstract

In this paper we introduce a novel adaptive approach for solving `

-minimization prob-

lems as frequently arising in compressed sensing, which is based on the recently introduced

inverse scale space method. The scheme allows to eﬃciently compute minimizers by solving

a sequence of low-dimensional nonnegative least-squares problems.

We provide a detailed convergence analysis in a general setup as well as reﬁned re-

sults under special conditions. In addition we discuss experimental observations in several

numerical examples.

Key words: Compressed Sensing, Inverse Scale Space, Sparsity, Adaptivity, Greedy

Methods.

1 Introduction

Compressed sensing and techniques exploiting sparsity in data analysis, image processing, and

inverse problems recently gained enormous interest. Representing unknowns for (underdeter-

mined) systems of linear equations in appropriate bases or dictionaries can be reformulated as

ﬁnding the sparsest solution of a linear system

Au = f, (1.1)

with a matrix A ∈ R

m×n

, usually with m much smaller than n. In a natural way sparsity is

measured via the number of nonzero elements in the vector u ∈ R

(the `

-norm), which however

leads to highly nonconvex problem when trying to ﬁnd the sparsest solution. In order to avoid

the high complexity of `

-minimization, one uses a convex relaxation to minimize the `

-norm

instead, i.e.,

kuk

→ min

subject to Au = f. (1.2)

Various important results have been obtained on the equivalence of `

and `

-minimization under

diﬀerent conditions, we refer e.g. to [CT04a, CT04a, DE03, D06].

Instead of a nonconvex problem, the `

approach solves a convex problem with linear equality

constraints, however still with a nonsmooth objective functional. Thus, the eﬃcient numerical

solution is often a challenge, in particular in large dimensions. A similar argument applies to

regularized problems used in the case of noisy data, where one minimizes

(u) =

kAu − fk

+ αkuk

. (1.3)

Methods proposed for these problems are e.g. iterative thresholding [BD09, DDD04] and vari-

ants [DTD

06, NV09, TG07]. A method receiving particular attention due to its eﬃciency for

∗

Westf¨alische Wilhelms-Universit¨at M¨unster, Institut f¨ur Numerische und Angewandte Mathematik, Einste-

instr. 62, D 48149 M¨unster, Germany ({martin.benning,martin.burger}@wwu.de)

†

Department of Mathematics, University of California Los Angeles. Portola Plaza, Los Angeles CA 90095,

USA. ({michaelm,sjo}@math.ucla.edu)

many problems is the Bregman iteration [OBG

05, YOG

08] respectively its linearized version

[COS09a, COS09b]. These methods are formulated in general for problems of the form

J(u) → min

u∈X

subject to Au = f, (1.4)

where J : X → R ∪ {∞} is a convex functional on a Banach space X and A : X → Y is a

bounded linear operator between Banach spaces. The Bregman iteration constructs a sequence

as minimizers of

(u) =

kAu − fk

+ J(u) − hp

k−1

, ui, (1.5)

where p

k−1

is an element of the subdiﬀerential of J at u

k−1

, p

k−1

∈ ∂J(u

k−1

) = {p : J(u) −

J(u

k−1

) − hp, u − u

k−1

i ≥ 0 ∀u}. Each step is a penalized least squares problem with the

(generalized) Bregman distance between u and u

k−1

being the regularization functional. From

the optimality condition a simple update scheme for the subgradients can be obtained as

= p

k−1

+ λA

∗

(f − Au

), (1.6)

which also allows to prove equivalence of the Bregman iteration to the well-known augmented

Lagrangian method. The linearized Bregman iteration uses a ﬁrst-order Taylor expansion of the

least-squares term around the last iterate, i.e. u

is determined from minimizing

(u) =

kAu

k−1

− f k

+ λhA(u − u

k−1

), Au

k−1

− f i + J(u) − hp

k−1

, ui. (1.7)

The dual variable is obtained correspondingly from

= p

k−1

+ λA

∗

(f − Au

k−1

). (1.8)

The application to compressed sensing appears obvious for J(u) = kuk

, care needs to be taken

however for the linearized Bregman iterations since the functional E

is possibly unbounded

from below in the `

-case, one therefore frequently uses the elastic net

J(u) =

2δ

kuk

+ kuk

with δ large. This does not harm the convergence to an `

-minimizing problem, equivalence can

be shown for δ above a threshold (cf. [Y10]).

Interpreting λ as a time step of an evolution, one observes that the Bregman and linearized

Bregman methods are backward respectively forward time stepping on the evolution equation

(respectively inclusion)

∂

p(t) = A

∗

(f − Au(t)), p(t) ∈ ∂J(u(t)), (1.9)

which is called inverse scale space method and analyzed in [BGO

06]. The inverse scale space

method appears not to be practical as a minimization technique at the ﬁrst glance, since it is

a nonlinear evolution equation. However, for total variation regularization it has been observed

already in numerical experiments that the evolution has a discrete nature (also conﬁrmed partly

by theoretical results, cf. [BGO

06, BFO

07, B08]). There seem to be only few time steps where

the solution u actually changes, while the dual variable evolves continuously. This observation

is one of the motivations for this paper, in which we aim to obtain a similar or even more precise

characterization of the inverse scale space for the compressed sensing setup (1.2) in detail and

deduce an eﬃcient numerical scheme.

Our second motivation are adaptive discretizations of operator equations (cf. [CDD01,

CDD02, DDU02]), in particular greedy techniques, which are iterative methods that slowly

but eﬃciently increase the number of degrees of freedom (often by one in each iteration step). It

is rather natural to look for such adaptive discretizations also in the compressed sensing frame-

work, because one looks for solutions with only few degrees of freedom (associated with the

nonzero entries in u). One might hope to construct methods that slowly increase the support

of the iterates towards the one of the sparsest solution, solving only (low-dimensional) linear

problems on the support of the iterates in each step. Usually such adaptive methods are guided

by a-posteriori error analysis and as we shall see below, a simple a-posteriori approach to `

minimization indicates that the supremum of A

∗

(Au−f) should be made small, which is exactly

what the inverse scale space achieves (examine for instance the right-hand side in (1.9) and the

convergence analysis in [BGO

06, BFO

07] reviewed in the next section).

Our motivations suggest that the inverse scale space method applied to the compressed

sensing setup will provide an eﬃcient and adaptive approach when carefully analyzed and im-

plemented, and this is indeed one of our main ﬁndings in this paper. We will show that there

exists a discrete set of time steps t

at which the primal solution of the inverse scale space is

changing and where u

= u(t

) can be computed by solving low-dimensional systems of linear

equations with nonnegativity constraints (which can often be even omitted in practice). The

evolution of the dual variable is characterized as linear between the discrete time steps and hence

can be computed explicitly as well. Moreover, the discrete time steps can be obtained from the

supremum norm of the dual variable (respectively the residuum). Finally, the behaviour of p

also provides the key to the adaptive reﬁnement, i.e. the small index sets on which A has to

be considered and the linear equations need to be solved. In addition to the setup in (1.2) we

shall also consider the regularized problem of minimizing the functional in (1.3). This yields an

inverse scale space ﬂow of the form

∂

p(t) = −αp(t) + A

∗

(f − Au(t)), p(t) ∈ ∂J(u(t)), (1.10)

which has not yet been investigated in detail in literature, but for which we can obtain analogous

results to the case α = 0.

The convergence behavior of the explicit discretization of the inverse scale space ﬂow, also

known as linearized Bregman, has been studied before by Osher et al. in [OMD

10] where it

was discovered that the primal variable alternates between quickly converging to a new solution

and stagnating, i.e. staying constant for long times. This fact was used to determine the

stagnation time and immediately ‘kick’ the primal variable to a time where the next change of

solution happens. Hence, ‘kicking’ is the ﬁrst work to use the discrete nature of the inverse scale

space ﬂow. However, opposed to the method we propose in this paper, linearized Bregman is a

discretization of (1.9). By analyzing the behavior of the subgradient we will be able to solve the

(continuous) ﬂow (1.9) exactly, without discretization of the underlying diﬀerential equation. The

times at which the solution changes can be calculated exactly such that a stagnation is entirely

avoided. Any change in the continuous inverse scale space ﬂow solution happens instantaneously

at discrete times.

Besides linearized Bregman with kicking our approach is also related to the technique of

orthogonal matching pursuit (OMP) (cf. [PRK93, MZ93, TG07]), which is a greedy method to

solving the sparse approximation problem and iteratively adds components to the support of u

whose correlation to the current residual is maximal. To be more precise the pseudo code for

OMP is given in Algorithm 1 below. Although the motivation of OMP is very diﬀerent than the

one of inverse scale space methods, we will see that the ﬁrst iteration of OMP coincides with

the ﬁrst step of our proposed approach to solve (1.9). We will discuss the diﬀerences to OMP

in more detail throughout the paper and will furthermore provide a numerical comparison in

Section 5.

Algorithm 1 Orthogonal Matching Pursuit

1. Parameters: A, f, threshold > 0

2. Initialization: r

= f, I

= ∅

while kr

k > threshold do

Compute I

= I

k−1

∪ i with i such that |(A

)

| = kA

∞

Compute u

= arg min



kAP

u − fk



Update r

k+1

= f − AP

end while

return u

Another technique that aims at iteratively reconstructing the support of a sparse signal is

iterative support detection (ISD) proposed by Wang and Yin in [WY10]. They iteratively solve

a truncated `

minimization problem on the coeﬃcients that are currently not in the detected

support and update the set of support coeﬃcients by thresholding. Similar to the framework we

propose in this paper, ISD can also change the support of the solution arbitrarily and does not

lead to increasing, nested supports as OMP. However, ISD is not based on the inverse scale space

ﬂow (1.9) and does not aim at solving (1.2), which is a fundamental diﬀerence to our method. In

fact, the ﬁrst iteration of ISD requires to fully solve (1.2) already, such that the method proposed

in this paper could even be combined with ISD.

The remaining part of the paper is organized as follows: In Section 2 we provide a review

of the most important properties and convergence analysis of inverse scale space methods as

well as their extension to the case of regularized variational problems, which allows for a reﬁned

convergence analysis. Section 3 discusses the specialization of inverse scale space methods to

the compressed sensing setup and provides a characterization allowing to adaptively choose time

steps and low dimensional discretizations in each step. In Section 4 we provide some further

convergence analysis and subsequently discuss various numerical test examples illustrating the

behaviour of the methods and a comparison to the well-known OMP method in Section 5.

2 Inverse Scale Space Methods

In the following we provide some basic facts about Bregman iterations and inverse scale space

methods arising as their asymptotic limit. In this section we consider the general case as described

in (1.4). In Section 2.2 we shall further discuss the application to the regularized problem

kAu − fk

+ αJ(u) → min

u∈X

. (2.1)

Starting point of the analysis is the Bregman distance associated with the functional J. For

a subgradient p ∈ ∂J(u) the Bregman distance is deﬁned as

(v, u) = J(v) − J(u) − hp, v − ui. (2.2)

Using the Bregman distance between subsequent iterations as a penalty in the least-squares

problem, we obtain the Bregman iteration (cf. [OBG

05]), computing u

as the solution of

kAu − fk

+ D

k−1

(u, u

k−1

) → min

u∈X

. (2.3)

Note that by subtracting constant terms not changing the minimizer this is equivalent to (1.5).

The optimality condition characterizing the minimizer u

is given by

λA

∗

(Au

− f ) + p

− p

k−1

= 0. (2.4)

Interpreting ∆t = λ as a time step and p

= p(k∆t) we ﬁnd the equivalent relation

p(t) − p(t − ∆t)

∆t

= A

∗

(f − Au(t)),

which is a backward Euler discretization of the time-continuous ﬂow (1.9), i.e.

∂

p(t) = A

∗

(f − Au(t)), p(t) ∈ ∂J(u(t)),

called inverse scale space method (ISS). The inverse scale space ﬂow is a diﬀerential inclusion,

it can also be formulated as a dual gradient ﬂow using the relation p = A

∗

q for some q, which

allows to write

∂

q(t) = f − Au(t), u(t) ∈ ∂

∗

q), (2.5)

hence

∂

q(t) ∈ −∂E

∗

(q), (2.6)

with the dual energy functional

∗

(q) = J

∗

q) − hf, qi., (2.7)

where J

∗

denotes the convex conjugate of J (cf. [ET99]).

2.1 Convergence Properties

As a consequence of the limit from the Bregman iteration and the obvious decrease of the least-

squares functional in the Bregman iteration (cf. [OBG

05]) we ﬁnd

kAu(t) − fk ≤ kAu(s) − fk, ∀ t ≥ s. (2.8)

A second useful property concerns the decrease of the Bregman distance and the dissipation of

the least-squares functional. If ˆu is a solution of Au = f minimizing J then taking the duality

product with u − ˆu reveals

p(t)

(ˆu, u(t)) = −kAu(t) − fk

. (2.9)

From this inequalty one can infer the major convergence properties of the inverse scale space

method, namely

kAu(t) − fk = O(t

−1/2

) (2.10)

and - under appropriate conditions on J - the weak or weak-* convergence of u(t) to solutions of

Au = f with minimal J along subsequences. Improved convergence properties can be obtained

for data satisfying a source condition

∃ˆq : A

∗

ˆq ∈ ∂J(ˆu). (2.11)

Under such a condition one further obtains (cf. [BRH07])

p(t)

(ˆu, u(t)) = O(t

−1/2

) (2.12)

and q(t) remains bounded.

In the compressed sensing setup this means that u(t) converges to an `

-minimizing solution

of Au = f (along subsequences if the latter is not unique). Moreover, (2.11) is automatically

satisﬁed, which can be seen from the optimality condition in ﬁnite dimensions (which is the

Lagrange-multiplier corresponding to Au = f). Thus, the Bregman distance with respect to the

-norm converges at least at order t

−1/2

In addition to the above properties some regularizing features of the inverse scale space

method have been shown under appropriate stopping rules for noisy data f; we refer to [BGO

06]

for further discussion.

剩余26页未读，继续阅读

评论收藏

内容反馈

qq_15873837

粉丝: 0
资源: 1

iss压缩感知算法文献

SolveLasso.rar_CS and matlab_cs-iss_solvelasso_压缩感知_鍘嬬缉鎰熺煡

内在形状签名(ISS)算法，用于点云关键点提取，matlab实现，带例程

ISS

欧式聚类，区域生长，ISS特征点等算法实现

压缩感知文献

压缩感知文献综述

压缩感知文献10篇

基于压缩感知的相关外文文献

压缩感知算法

基于ISS-CPD算法的三维激光点云数据处理技术.pdf

基于PCL的点云ISS特征点提取算法c++

通过ISS打包ISS脚本

基于ISS特征点结合改进ICP的点云配准算法

十大经典数据挖掘算法概论，视频资源

matlab 各种算法例程

iss安装文件包

ISS.rar_ISS服务器_iss

loan-iss只能语音

ISS5.1一键安装

基于压缩感知的DOA估计文献

分布式压缩感知经典文献

小木虫压缩感知文献

压缩感知CoSaMP算法

压缩感知重构算法

ifiss3.1

最新资源