Signal Processing - January 2016 - 69

(a)

(b)

(c)

(d)

[FIg6] Sample denoised images (v = 100) . (a) k-Svd, (b) proposed algorithm, (c) k−Svd (zoomed in), and (d) proposed algorithm
(zoomed in) [78].

Figure 6 and Table 5 show the performance of the resulting
algorithm for dictionary learning in an image denoising problem.
The denoising is performed on the Lena image corrupted by additive Gaussian noise with various variances v 2. As can be seen
from Table 5, the proposed algorithm results in larger PSNR values than the K-SVD method [80] when the noise level is large.
Moreover, the proposed algorithm contains less visual artifacts.
Furthermore, each step of the proposed algorithm is in closed
form and is computationally favorable, while each step of the
K-SVD method requires an inner iterative method.
SPARSE LINEAR dISCRIMINANt ANALySIS
The linear discriminant analysis (LDA), which is closely related to
analysis of variance (ANOVA) and regression analysis, is widely
used in machine learning and statistics for classification and
dimensionality reduction purposes; see, e.g., [81]. Let us, for the
ease of presentation, focus only on the binary classification problem: Let x i ! R p, i = 1, 2, f, N, denote the zero-centered observations, where each observation x i belongs to one and only one of
the two classes C 0 and C 1 . Given the binary classes, the standard
within-class covariance estimate can be calculated by
tw= 1
R
N

/ /

(x i - nt k) (x i - nt k) T,

k ! {0, 1} i ! C k

[TaBle 5] The IMage denoISIng reSulT coMParISon
on The "lena IMage" For dIFFerenT noISe levelS.
valueS are averaged over Ten MonTe carlo
SIMulaTIonS [78].
v /PSnr
20/22.11
60/12.57
100/8.132
140/5.208
180/3.025

dcT
32
26.59
24.42
22.96
21.73

k-Svd
32.38
26.86
24.45
22.93
21.69

t b b. Therefore, in the
class variance can be written as vt b = b T R
LDA problem, we are interested in solving
max

t bb
bT R

s.t.

t w b # 1.
bT R

b

t b = 1 ^ N 0 nt 0 nt T0 + N 1 nt 1 nt T1 h,
R
N
with N 0 (resp. N 1) being the cardinality of the set C 0 (resp. C 1) .
The goal of LDA is to find a lower-dimensional subspace so that the
projection of the observations onto the selected subspace leads to
well-separated classes. In other words, the task is to project data
points into a subspace with large between-class variance relative to
the within-class variance. For simplicity, consider projection onto
one-dimensional subspace defined by the vector b ! R p; see [82]
for details on projection to larger-dimensional subspaces. Then the
inner product G b, x H is the projection of the observation x onto
the selected subspace; and the within-class variance of the prot w b; while the between
jected data points is given by vt w = b T R

(25)

Unfortunately, when the number of features is large relative to N,
t w is rank deficient and therefore (25) is ill posed. To
the matrix R
resolve this issue and to have a small generalization error, [82]
suggests to regularize the optimization problem with a convex
penalty function P ($); and solve
max

t b b - P (b)
bT R

s.t.

t w b # 1.
bT R

b

where nt k = 1/N / i ! C k x i is observations mean in class C k . Similarly, the standard between-class covariance estimate is given by

ProPoSed
algorIThM
30.88
26.37
24.46
23.11
21.96

(26)

Clearly, this optimization problem is nonconvex. As suggested in
[82], one can linearize the first part of the objective in (26) iteratively to obtain a tight upper bound of the objective. It is not hard
to see that the algorithm used in [82] is BSUM with the linear
upper bound given in Table 3.
exTenSIonS
In this section, we discuss extensions and generalizations of the
BSUM framework in various settings.
StOChaStiC OptimizatiOn
Consider the following stochastic optimization problem:
min
x
s.t.

IEEE SIGNAL PROCESSING MAGAZINE [69] jANuARy 2016

f (x) _ E p 6 g (x, p)@
x ! X,

(27)
Table of Contents for the Digital Edition of Signal Processing - January 2016
