K-SVD算法：设计适应稀疏表示的字典

5星 · 超过95%的资源需积分: 11 27 浏览量更新于2024-09-11 1 收藏 1.68MB PDF 举报

KSVD（K-Singular Value Decomposition）算法是一种在2006年提出的重要技术，它与小波变换类似，但在信号处理领域展现出了独特的优势。该方法的核心是利用一个过度完备的字典（overcomplete dictionary），即包含多个原型信号原子的矩阵，来表示信号。信号被表示为这些原子的稀疏线性组合，这意味着信号可以通过少数几个关键特征或原子来近似，这对于压缩、逆问题的正则化、特征提取等应用具有显著作用。在近年来的研究中，主要关注点在于如何设计出更适合于稀疏表示模型的字典。KSVD算法在此背景下脱颖而出。与预先设定一组线性变换（如傅立叶变换或小波变换）相比，KSVD算法更侧重于通过适应性方法来调整字典，以更好地适应训练信号。这种方法允许字典在实际应用中自我学习和优化，以达到更高效的信号表示。 KSVD算法的具体流程包括以下几个步骤： 1. **信号重构**：首先，给定一个训练信号集，对每个信号进行表示，目标是找到最接近原始信号且表示系数尽可能稀疏的字典表示。 2. **字典更新**：通过迭代过程，每次迭代都会更新字典中的原子，使得它们更符合训练信号的稀疏表示需求。这通常涉及到奇异值分解（SVD）和最小化重构误差。 3. **稀疏编码**：对于新的未知信号，使用优化过的字典执行稀疏编码，找出最接近信号的稀疏表示。 4. **在线学习与扩展**：对于实时或在线应用， KSVD算法可以采用增量学习的方式，不断更新字典以适应新的信号数据。尽管已有了一些设计字典的方法，如基于固定变换的选择和基于训练信号的自适应调整，但KSVD算法的独特之处在于其迭代优化过程，能够自动调整字典结构，从而提升信号表示的质量。这种灵活性使得KSVD在众多领域中展现出强大的潜力，特别是在那些信号复杂、需要高效压缩和分析的场景中。随着技术的发展，KSVD及其变种算法将继续为未来的信号处理和机器学习提供强大工具。

AHARON et al.: -SVD: ALGORITHM FOR DESIGNING OVERCOMPLETE DICTIONARIES 4313

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 rep-

resented as a linear combination of several vectors

Thus, sparse representations can be referred to as a generaliza-

tion of the clustering problem.

Since the

-means algorithm (also known as the generalized

Lloyd algorithm—GLA [39]) is the most commonly used pro-

cedure for training in the vector quantization setting, it is nat-

ural to consider generalizations of this algorithm when turning

to the problem of dictionary training. The clustering problem

and its

-means solution will be discussed in more detail in

Section IV-A, since our work approaches the dictionary training

problem by generalizing the

-means. Here we shall brieﬂy

mention that the

-means process applies two steps per each it-

eration: i) given

, assign the training examples to their

nearest neighbor; and ii) given that assignment, update

to better ﬁt the examples.

The approaches to dictionary design that have been tried so

far are very much in line with the two-step process described

above. The ﬁrst step ﬁnds the coefﬁcients given the dictio-

nary—a step we shall refer to as “sparse coding.” Then, the

dictionary is updated assuming known and ﬁxed coefﬁcients.

The differences between the various algorithms that have been

proposed are in the method used for the calculation of coefﬁ-

cients and in the procedure used for modifying the dictionary.

B. Maximum Likelihood Methods

The methods reported in [22]–[25] use probabilistic rea-

soning in the construction of

. The proposed model suggests

that for every example

the relation

(3)

holds true with a sparse representation

and Gaussian white

residual vector

with variance . Given the examples

, these works consider the likelihood function

and seek the dictionary that maximizes it. Two assumptions are

required in order to proceed: the ﬁrst is that the measurements

are drawn independently, readily providing

(4)

The second assumption is critical and refers to the “hidden vari-

able”

. The ingredients of the likelihood function are computed

using the relation

(5)

Returning to the initial assumption in (3), we have

(6)

The prior distribution of the representation vector

is assumed

to be such that the entries of

are zero-mean i.i.d., with Cauchy

[24] or Laplace distributions [22], [23]. Assuming for example

a Laplace distribution, we get

(7)

This integration over

is difﬁcult to evaluate, and indeed, Ol-

shausen and Field [23] handled this by replacing it with the ex-

tremal value of

. The overall problem turns into

(8)

This problem does not penalize the entries of

as it does for

those of

. Thus, the solution will tend to increase the dictio-

nary entries’ values, in order to allow the coefﬁcients to become

closer to zero. This difﬁculty has been handled by constraining

the

-norm of each basis element, so that the output variance

of the coefﬁcients is kept at an appropriate level [24].

An iterative method was suggested for solving (8). It includes

two main steps in each iteration: i) calculate the coefﬁcients

using a simple gradient descent procedure and then ii) update

the dictionary using [24]

(9)

This idea of iterative reﬁnement, mentioned before as a general-

ization of the

-means algorithm, was later used again by other

researchers, with some variations [36], [37], [40]–[42].

A different approach to handle the integration in (7) was sug-

gested by Lewicki and Sejnowski [25]. They approximated the

posterior as a Gaussian, enabling an analytic solution of the inte-

gration. This allows an objective comparison of different image

models (basis or priors). It also removes the need for the ad-

ditional rescaling that enforces the norm constraint. However,

this model may be too limited in describing the true behaviors

expected. This technique and closely related ones have been re-

ferred to as approximated ML techniques [37].

There is an interesting relation between the above method and

the independent component analysis (ICA) algorithm [43]. The

latter handles the case of a complete dictionary (the number of

elements equals the dimensionality) without assuming additive

noise. The above method is then similar to ICA in that the algo-

rithm can be interpreted as trying to maximize the mutual infor-

mation between the inputs (samples) and the outputs (the coef-

ﬁcients) [24], [22], [25].

C. The MOD Method

An appealing dictionary training algorithm, named method

of optimal directions (MOD), is presented by Engan et al. [36],

剩余11页未读，继续阅读

淮阳县令

粉丝: 1
资源: 5

K-SVD算法：设计适应稀疏表示的字典

基于LC-KSVD字典学习的变化光照下人脸识别方法.pdf

压缩感知+KSVD+字典学习+降噪/重构

【图像重建】基于matlab字典学习W-KSVD图像低秩重建（含PSNR）【含Matlab源码 1763期】.mp4

【图像重建】字典学习KSVD图像低秩重建（含PSNR）【含Matlab源码 1762期】.zip

【图像重建】基于matlab字典学习KSVD图像低秩重建（含PSNR）【含Matlab源码 1762期】.mp4

【图像重建】基于matlab字典学习KSVD图像低秩重建（含PSNR）【含Matlab源码 1762期】.md

【图像重建】字典学习W-KSVD图像低秩重建（含PSNR）【含Matlab源码 1763期】.zip

【图像重建】基于matlab字典学习W-KSVD图像低秩重建（含PSNR）【含Matlab源码 1763期】.md

D-KSVD用于基因表达谱上的肿瘤分类

基于拓展稀疏表示模型和LC-KSVD的人脸识别.pdf

最新资源