信号自适应稀疏表示的K-SVD算法资源-CSDN文库

稀疏表示

1星需积分: 45 121 浏览量 2011-08-31 15:46:16 上传评论收藏 503KB PDF 举报

资源推荐

资源详情

资源评论

K-SVD: An Algorithm for Designing of

Overcomplete Dictionaries for Sparse

Representation

Michal Aharon Michael Elad Alfred Bruckstein Yana Katz

Department of Computer Science

Technion—Israel Institute of Technology

Technion City, Haifa 32000, Israel

Tel. 972-4-8294925. Fax. 972-4-8293900

e-mail: michalo@cs.technion.ac.il

Abstract

In recent years there has been a growing interest in the study of sparse representation of signals.

Using an overcomplete dictionary that contains prototype signal-atoms, signals are described by sparse

linear combinations of these atoms. Applications that use sparse representation are many and include

compression, regularization in inverse problems, feature extraction, and more. Recent activity in this ﬁeld

concentrated mainly on the study of pursuit algorithms that decompose signals with respect to a given

dictionary. Designing dictionaries to better ﬁt the above model can be done by either selecting one from

a pre-speciﬁed set of linear transforms, or by adapting the dictionary to a set of training signals. Both

these techniques have been considered, but this topic is largely still open.

In this paper we propose a novel algorithm for adapting dictionaries in order to achieve sparse signal

representations. Given a set of training signals, we seek the dictionary that leads to the best representation

for each member in this set, under strict sparsity constraints. We present a new method – the K-SVD

algorithm – generalizing the K-Means clustering process. K-SVD is an iterative method that alternates

between sparse coding of the examples based on the current dictionary, and a process of updating the

dictionary atoms to better ﬁt the data. The update of the dictionary columns is combined with an update

of the sparse representations, thereby accelerating convergence. The K-SVD algorithm is ﬂexible and

can work with any pursuit method (e.g., basis pursuit, FOCUSS, or matching pursuit). We analyze this

algorithm and demonstrate its results on both synthetic tests and in applications on real image data.

Keywords: K-Means, vector quantization, gain-shape VQ, codebook, K-SVD, training, dictionary, atom

decomposition, sparse representation, basis pursuit, matching pursuit, FOCUSS.

I. INTRODUCTION

A. Sparse Representation of Signals

Recent years have witnessed a growing interest in the search for sparse representations of signals. Using

an overcomplete dictionary matrix D ∈ IR

n×K

that contains K prototype signal-atoms for columns,

}

j=1

, a signal y ∈ IR

can be represented as a sparse linear combination of these atoms. The

representation of y may either be exact y = Dx, or approximate, y ≈ Dx, satisfying ky − Dxk

≤ .

The vector x ∈ IR

contains the representation coefﬁcients of the signal y. In approximation methods,

typical norms used for measuring the deviation are the `

-norms for p = 1, 2 and ∞. In this work we

shall concentrate on the case of p = 2.

If n < K and D is a full-rank matrix, an inﬁnite number of solutions are available for the representation

problem, hence constraints on the solution must be set. The solution with the fewest number of nonzero

coefﬁcients is certainly an appealing representation. This sparsest representation is the solution of either

) min

kxk

subject to y = Dx, (1)

0,

) min

kxk

subject to ky − Dxk

≤ , (2)

where k·k

is the l

norm, counting the nonzero entries of a vector.

Applications that can beneﬁt from the sparsity and overcompleteness concepts (together or separately)

include compression, regularization in inverse problems, feature extraction, and more. Indeed, the success

of the JPEG2000 coding standard can be attributed to the sparsity of the wavelet coefﬁcients of

natural images [1]. In denoising, wavelet methods and shift-invariant variations that exploit overcomplete

representation, are among the most effective known algorithms for this task [2], [3], [4], [5]. Sparsity and

overcompleteness have been successfully used for dynamic range compression in images [6], separation

of texture and cartoon content in images [7], [8], inpainting [9], and more.

Extraction of the sparsest representation is a hard problem that has been extensively investigated in the

past few years. We review some of the most popular methods in Section II. In all those methods, there

is a preliminary assumption that the dictionary is known and ﬁxed. In this work we address the issue of

designing the proper dictionary, in order to better ﬁt the sparsity model imposed.

B. The Choice of the Dictionary

An overcomplete dictionary D that leads to sparse representations can either be chosen as a pre-

speciﬁed set of functions, or designed by adapting its content to ﬁt a given set of signal examples.

Choosing a pre-speciﬁed transform matrix is appealing because it is simpler. Also, in many cases it

leads to simple and fast algorithms for the evaluation of the sparse representation. This is indeed the case

for overcomplete wavelets, curvelets, contourlets, steerable wavelet ﬁlters, short-time-Fourier transforms,

and more. Preference is typically given to tight frames that can easily be pseudo-inverted. The success

of such dictionaries in applications depends on how suitable they are to sparsely describe the signals in

question. Multiscale analysis with oriented basis functions and a shift-invariant property are guidelines

in such constructions.

In this paper we consider a different route for designing dictionaries D based on learning. Our goal

is to ﬁnd the dictionary D that yields sparse representations for the training signals. We believe that

such dictionaries have the potential to outperform commonly used pre-determined dictionaries. With

ever-growing computational capabilities, computational cost may become secondary in importance to the

improved performance achievable by methods which adapt dictionaries for special classes of signals.

C. Our Paper’s Contribution and Structure

In this paper we present a novel algorithm for adapting dictionaries so as to represent signals sparsely.

Given a set of training signals {y

}

i=1

, we seek the dictionary D that leads to the best possible

representations for each member in this set with strict sparsity constraints. We introduce the K-SVD

algorithm that addresses the above task, generalizing the K-Means algorithm. The K-SVD is an iterative

method that alternates between sparse coding of the examples based on the current dictionary, and an

update process for the dictionary atoms so as to better ﬁt the data. The update of the dictionary columns is

done jointly with an update of the sparse representation coefﬁcients related to it, resulting in accelerated

convergence. The K-SVD algorithm is ﬂexible and can work with any pursuit method, thereby tailoring

the dictionary to the application in mind. In this work we present the K-SVD algorithm, analyze it,

discuss its relation to prior art, and prove its superior performance. We demonstrate the K-SVD results

in both synthetic tests and applications involving real image data.

In Section II we survey pursuit algorithms that are later used by the K-SVD, together with some

recent theoretical results justifying their use for sparse coding. In Section III we refer to recent work

done in the ﬁeld of sparse-representation dictionary design, and describe different algorithms that were

proposed for this task. In Section IV we describe our algorithm, its possible variations, and its relation to

previously proposed methods. The K-SVD results on synthetic data are presented in Section V, and some

preliminary applications involving real image data are given in Section VI. We conclude and discuss

future possible research direction in Section VII.

II. SPARSE CODING: PRIOR ART

Sparse coding is the process of computing the representation coefﬁcients, x, based on the given signal

y and the dictionary D. This process, commonly referred to as “atom decomposition”, requires solving

(1) or (2), and this is typically done by a “pursuit algorithm” that ﬁnds an approximate solution. In

this section we brieﬂy discuss several such algorithms, and their prospects for success. A more detailed

description of those methods can be found in [10]. Sparse coding is a necessary stage in the K-SVD

method we develop later in this paper, hence it is important to have a good overview of methods for

achieving it.

Exact determination of sparsest representations proves to be an NP-hard problem [11]. Thus,

approximate solutions are considered instead, and in the past decade or so several efﬁcient pursuit

algorithms have been proposed. The simplest ones are the Matching Pursuit (MP) [12] and the Orthogonal

Matching Pursuit (OMP) algorithms [13], [14], [15], [16]. These are greedy algorithms that select the

dictionary atoms sequentially. These methods are very simple, involving the computation of inner products

between the signal and dictionary columns, and possibly deploying some least squares solvers. Both (1)

and (2) are easily addressed by changing the stopping rule of the algorithm.

A second well known pursuit approach is the Basis Pursuit (BP) [17]. It suggests a convexiﬁcation of

the problems posed in (1) and (2), by replacing the `

-norm with an `

-norm. The Focal Under-determined

System Solver (FOCUSS) is very similar, using the `

-norm with p ≤ 1, as a replacement to the `

-norm

[18], [19], [20], [21]. Here, for p < 1 the similarity to the true sparsity measure is better, but the overall

problem becomes non-convex, giving rise to local minima that may mislead in the search for solutions.

Lagrange multipliers are used to convert the constraint into a penalty term, and an iterative method is

derived based on the idea of iterated reweighed least-squares that handles the `

-norm as an `

weighted

norm.

Both the BP and the FOCUSS can be motivated based on Maximum A Posteriori (MAP) estimation,

and indeed several works used this reasoning directly [22], [23], [24], [25]. The MAP can be used to

estimate the coefﬁcients as random variables, by maximizing the posterior P (x|y, D) ∝ P (y|D, x)P (x).

The prior distribution on the coefﬁcient vector x is assumed to be a super-Gaussian iid distribution that

favors sparsity. For the Laplace distribution this approach is equivalent to BP [22].

Extensive study of these algorithms in recent years has established that if the sought solution, x, is

sparse enough, these techniques recover it well in the exact case [16], [26], [27], [28], [29], [30]. Further

work considered the approximated versions and has shown stability in recovery of x [31], [32]. The recent

front of activity revisits those questions within a probabilistic setting, obtaining more realistic assessments

on pursuit algorithm performance and success [33], [34], [35]. The properties of the dictionary D set the

limits on the sparsity of the coefﬁcient vector that consequently leads to its successful evaluation.

III. DESIGN OF DI C T I O NA R I E S : PRIOR ART

We now come to the main topic of the paper, the training of dictionaries based on a set of examples.

Given such set Y = {y

}

i=1

, we assume that there exists a dictionary D that gave rise to the given

signal examples via sparse combinations, i.e., we assume that there exists D, so that solving (P

) for each

example y

gives a sparse representation x

. It is in this setting that we ask what the proper dictionary

D is.

A. Generalizing the K-Means?

There is an intriguing relation between sparse representation and clustering (i.e., vector quantization).

This connection has previously been mentioned in several reports [36], [37], [38]. In clustering, a set of

descriptive vectors {d

}

k=1

is learned, and each sample is represented by one of those vectors (the one

closest to it, usually in the `

distance measure). We may think of this as an extreme sparse representation,

where only one atom is allowed in the signal decomposition, and furthermore, the coefﬁcient multiplying

it must be 1. There is a variant of the vector quantization (VQ) coding method, called Gain-Shape VQ,

where this coefﬁcient is allowed to vary [39]. In contrast, in sparse representations as discussed in this

paper, each example is represented as a linear combination of several vectors {d

}

k=1

. Thus, sparse

representations can be referred to as a generalization of the clustering problem.

剩余28页未读，继续阅读

评论收藏

内容反馈

茶香小怪

2019-04-21

就一篇文章？！

wangxiaoyankx

粉丝: 0
资源: 4

信号自适应稀疏表示的K-SVD算法

K-SVD算法，基于稀疏表示的设计过完备字典算法

ksvd 去噪代码 稀疏表示

稀疏表示需要用到的ksvd工具箱

ksvd稀疏表示字典训练代码

MATLAB实现k-svd和mod信号处理

用于图像分类的极限学习机和自适应稀疏表示

KSVD工具包

极限学习机和自适应稀疏表示算法（EA-SRC）的代码：极限学习机和自适应稀疏表示算法（EA-SRC）的代码-matlab开发

稀疏表示Matlab工具箱

论文研究-基于稀疏表示的OFDM信号的DOA估计.pdf

稀疏表示算法

K-SVD 基于稀疏表示的字典训练算法

基于K_SVD和残差比的低信噪比图像稀疏表示去噪算法.pdf )

k_svd.rar_SVD算法_k-svd图像分解_图像 分解_图像稀疏_稀疏分解 K_SVD

一种基于SVD的非平稳信号重叠分段降噪算法

matlab_k-svd算法用于稀疏表示的图像去噪，字典学习算法

基于K-SVD字典学习程序.zip_K._字典_字典学习_自适应SVD_自适应字典

K-SVD的经典文献

051704000800926_omp_omp去噪_dangerousdde_K-SVD去噪_K-SVD_

跟踪算法的多类研究的参数化模糊自适应K-SVD方法

KSVD工具包—信号处理

SPAMS 信号稀疏表示Matlab工具包（windows版本）

稀疏表示工具箱

Stft短时傅里叶变换matlab实现

稀疏信号L1-SVD算法.txt

信号与图像的稀疏表示

BSIK-SVD：字典学习算法，用于块稀疏表示

MATLAB稀疏表示算法

data_SVD.zip_SVD信号重构_doa——cvx_svd重构_矩阵重构DOA_稀疏重构DOA

83404788K-SVD-dictionary-training-algorithms_svdbeamforming_algo

最新资源

ksvd 去噪代码稀疏表示

k_svd.rar_SVD算法_k-svd图像分解_图像分解_图像稀疏_稀疏分解 K_SVD