Signal Processing - January 2016 - 65

single block of variables, if x ! X is coordinatewise minimum,
then it must be a global minimum solution. Therefore, every
feasible solution x ! X is regular, and the convergence of PPA
is covered by BSUM.
Furthermore, the PPA can be generalized to solve the
multiblock problem (1), where f (:) is convex in each of its
block components, but not necessarily strictly convex. Directly
applying BCD may fail to find a stationary solution for this
problem, as the per-block subproblems can contain multiple
solutions (cf. Example 6). Alternatively, we can consider an
alternating PPA [51], which successively solves the following:
min
f (x i, x -r i) +
xi

c

2

2

x i - x ir , s.t. x i ! X i .

the fOrward-baCkward Splitting algOrithm
The forward-backward splitting (FBS) algorithm (also known as
the proximal splitting algorithm; see, e.g., [52] and the references
therein) for nonsmooth optimization solves the composite problem (4) with a single block of variables (i.e., n = 1), where h is
convex and lower semicontinuous; g is convex and has Lipschitz
continuous gradient, i.e., dg (x) - dg (y) # L x - y ,
6 x, y ! X and for some L 2 0.
Define the proximity operator prox h: X " X as
prox h (x) = arg min
h (y) + 1 x - y 2 .
y!X
2

f (W, H): = 1 V - WH 2F, s.t. W $ 0, H $ 0, (13)
2

where V ! R +M # N is given. The problem has been extensively studied since Lee and Seung's seminal work [32], and it has wide applications in factor analysis, dictionary learning, speech analysis and
so on [54]. In [32], a simple and efficient multiplicative algorithm
is proposed:
[(W r) T V] j,i
, j = 1, g, K, i = 1, g, N
[(W r) T W r H r] j,i
(14a)
[V (H r + 1) T] j,i
r+1
r
[W ] j,i = [W ] j,i
,
[W r H r + 1 (H r + 1) T] j,i
j = 1, g, M, i = 1, g, K.
(14b)
Here, [H r + 1] j,i means the (j, i) th component of matrix H r + 1. In
the following we show that when the iterates are well-defined (i.e.,
[W ijr] 2 0 and [H ijr] 2 0), the NMF iteration (14a) and (14b) is
also covered by BSUM [55].
Let H i and Vi represent the i th column of H and V, respectively. Then, at a given iterate {W r, H r}, the subproblem for optimizing H i is given by
min f (H i, {W r, H r}): = 1 Vi - W r H i
Hi $ 0
2

2
F

+1
2

/

2

V j - W r H rj

F

j!i

.

(15)
Define the upper-bound function u i (H i, {W r, H r}) as
u i (H i, {W r, H r}): = f (H ir, {W r, H r}) + (H i - H ir) T d H i f (H i, {W r, H r})

The FBS iteration is given below [52]:
x r + 1 = prox bh (x r - bdg (x r)) ,
> 144424443

(11)

forward step

where b ! (0, 1/L]. Define
2
u (x, x ): = h (x) + 1 x - x r + G x - x r, dg (x r) H + g (x r), (12)
2b
which is the quadratic upper bound in Table 3, with
U 1: = 1/b I. It is easy to see that the iteration (11) is equivalent
to the following iteration x r + 1 = arg min x ! X u (x, x r), therefore, it again falls under the BSUM framework.
Similar to the previous example, we can generalize the FBS
algorithm to solve multiple block problems of the form (5). The
resulting algorithm, sometimes also known as the BCPG
method, has received significant attention recently due to its
efficiency for solving certain big data optimization problem
such as the least absolute shrinkage and selection operator
(LASSO) [11]. For recent developments and applications for
BCPG, see [5], [39], and [53].
Here we make a special note that, by appealing to the general
convergence rate result in the section "How Fast Does the BSUM
Converge?" the BCPG method with any coordinate selection rules
in Table 2 gives a sublinear convergence rate, when it is used to
solve (5) that satisfies Assumption B.
r

min

W ! R M#K, H ! RK#M

[H r + 1] j,i = [H r] j,i

Clearly this algorithm is a special form of BSUM with strongly
convex proximal upper bound (cf. Table 3). It follows that each
subproblem has a unique optimal solution, and by Theorem 1
it must converge to a stationary solution.

backward step

the nmf algOrithm
Consider the following NMF problem:

+ 1 (H i - H ir) T U i (W r, H ir) (H i - H ir),
2
where U i (W r, H ir) is a diagonal matrix given by
U i (W r, H ir): = Diag e

[(W r) T W r H ir] 1
[(W r) T W r H ir] K
o.
, g,
r
[H i ] 1
[H ir] K

Clearly, U i (W r, H ir) ( 0, and it is easy to show that
U i (W r, H ir) ( (W r) T W r, where (W r) T W r is the Hessian of the
objective of (15) [32]. This implies that u i (H i, {W r, H r}) is the
quadratic upper bound given in Table 3 of f (H i, {W r, H r}). Further, one can check that the subproblem that minimizes
u i (H i, {W r, H r}) has a unique solution, given by (14a). Similar
analysis can be established for the W-block update rule as well.
Therefore, we conclude that the iterates (14a) and (14b) are a special case of BSUM. Finally, we note that it is also possible to use different upper-bound functions to derive more efficient update rules
for the NMF problem (13); see, e.g., [56], where both the concave
upper bound and the Jensen's upper bound (cf. Table 3) are used.
the iterative reweighted leaSt SqUareS methOd
The iterative reweighted least squares (IRLS) method is a popular algorithm used for solving big data problems such as sparse
recovery [57]. Consider

IEEE SIGNAL PROCESSING MAGAZINE [65] jANuARy 2016



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

Signal Processing - January 2016 - Cover1
Signal Processing - January 2016 - Cover2
Signal Processing - January 2016 - 1
Signal Processing - January 2016 - 2
Signal Processing - January 2016 - 3
Signal Processing - January 2016 - 4
Signal Processing - January 2016 - 5
Signal Processing - January 2016 - 6
Signal Processing - January 2016 - 7
Signal Processing - January 2016 - 8
Signal Processing - January 2016 - 9
Signal Processing - January 2016 - 10
Signal Processing - January 2016 - 11
Signal Processing - January 2016 - 12
Signal Processing - January 2016 - 13
Signal Processing - January 2016 - 14
Signal Processing - January 2016 - 15
Signal Processing - January 2016 - 16
Signal Processing - January 2016 - 17
Signal Processing - January 2016 - 18
Signal Processing - January 2016 - 19
Signal Processing - January 2016 - 20
Signal Processing - January 2016 - 21
Signal Processing - January 2016 - 22
Signal Processing - January 2016 - 23
Signal Processing - January 2016 - 24
Signal Processing - January 2016 - 25
Signal Processing - January 2016 - 26
Signal Processing - January 2016 - 27
Signal Processing - January 2016 - 28
Signal Processing - January 2016 - 29
Signal Processing - January 2016 - 30
Signal Processing - January 2016 - 31
Signal Processing - January 2016 - 32
Signal Processing - January 2016 - 33
Signal Processing - January 2016 - 34
Signal Processing - January 2016 - 35
Signal Processing - January 2016 - 36
Signal Processing - January 2016 - 37
Signal Processing - January 2016 - 38
Signal Processing - January 2016 - 39
Signal Processing - January 2016 - 40
Signal Processing - January 2016 - 41
Signal Processing - January 2016 - 42
Signal Processing - January 2016 - 43
Signal Processing - January 2016 - 44
Signal Processing - January 2016 - 45
Signal Processing - January 2016 - 46
Signal Processing - January 2016 - 47
Signal Processing - January 2016 - 48
Signal Processing - January 2016 - 49
Signal Processing - January 2016 - 50
Signal Processing - January 2016 - 51
Signal Processing - January 2016 - 52
Signal Processing - January 2016 - 53
Signal Processing - January 2016 - 54
Signal Processing - January 2016 - 55
Signal Processing - January 2016 - 56
Signal Processing - January 2016 - 57
Signal Processing - January 2016 - 58
Signal Processing - January 2016 - 59
Signal Processing - January 2016 - 60
Signal Processing - January 2016 - 61
Signal Processing - January 2016 - 62
Signal Processing - January 2016 - 63
Signal Processing - January 2016 - 64
Signal Processing - January 2016 - 65
Signal Processing - January 2016 - 66
Signal Processing - January 2016 - 67
Signal Processing - January 2016 - 68
Signal Processing - January 2016 - 69
Signal Processing - January 2016 - 70
Signal Processing - January 2016 - 71
Signal Processing - January 2016 - 72
Signal Processing - January 2016 - 73
Signal Processing - January 2016 - 74
Signal Processing - January 2016 - 75
Signal Processing - January 2016 - 76
Signal Processing - January 2016 - 77
Signal Processing - January 2016 - 78
Signal Processing - January 2016 - 79
Signal Processing - January 2016 - 80
Signal Processing - January 2016 - 81
Signal Processing - January 2016 - 82
Signal Processing - January 2016 - 83
Signal Processing - January 2016 - 84
Signal Processing - January 2016 - 85
Signal Processing - January 2016 - 86
Signal Processing - January 2016 - 87
Signal Processing - January 2016 - 88
Signal Processing - January 2016 - 89
Signal Processing - January 2016 - 90
Signal Processing - January 2016 - 91
Signal Processing - January 2016 - 92
Signal Processing - January 2016 - 93
Signal Processing - January 2016 - 94
Signal Processing - January 2016 - 95
Signal Processing - January 2016 - 96
Signal Processing - January 2016 - 97
Signal Processing - January 2016 - 98
Signal Processing - January 2016 - 99
Signal Processing - January 2016 - 100
Signal Processing - January 2016 - 101
Signal Processing - January 2016 - 102
Signal Processing - January 2016 - 103
Signal Processing - January 2016 - 104
Signal Processing - January 2016 - 105
Signal Processing - January 2016 - 106
Signal Processing - January 2016 - 107
Signal Processing - January 2016 - 108
Signal Processing - January 2016 - 109
Signal Processing - January 2016 - 110
Signal Processing - January 2016 - 111
Signal Processing - January 2016 - 112
Signal Processing - January 2016 - 113
Signal Processing - January 2016 - 114
Signal Processing - January 2016 - 115
Signal Processing - January 2016 - 116
Signal Processing - January 2016 - 117
Signal Processing - January 2016 - 118
Signal Processing - January 2016 - 119
Signal Processing - January 2016 - 120
Signal Processing - January 2016 - 121
Signal Processing - January 2016 - 122
Signal Processing - January 2016 - 123
Signal Processing - January 2016 - 124
Signal Processing - January 2016 - 125
Signal Processing - January 2016 - 126
Signal Processing - January 2016 - 127
Signal Processing - January 2016 - 128
Signal Processing - January 2016 - 129
Signal Processing - January 2016 - 130
Signal Processing - January 2016 - 131
Signal Processing - January 2016 - 132
Signal Processing - January 2016 - 133
Signal Processing - January 2016 - 134
Signal Processing - January 2016 - 135
Signal Processing - January 2016 - 136
Signal Processing - January 2016 - 137
Signal Processing - January 2016 - 138
Signal Processing - January 2016 - 139
Signal Processing - January 2016 - 140
Signal Processing - January 2016 - 141
Signal Processing - January 2016 - 142
Signal Processing - January 2016 - 143
Signal Processing - January 2016 - 144
Signal Processing - January 2016 - 145
Signal Processing - January 2016 - 146
Signal Processing - January 2016 - 147
Signal Processing - January 2016 - 148
Signal Processing - January 2016 - 149
Signal Processing - January 2016 - 150
Signal Processing - January 2016 - 151
Signal Processing - January 2016 - 152
Signal Processing - January 2016 - 153
Signal Processing - January 2016 - 154
Signal Processing - January 2016 - 155
Signal Processing - January 2016 - 156
Signal Processing - January 2016 - 157
Signal Processing - January 2016 - 158
Signal Processing - January 2016 - 159
Signal Processing - January 2016 - 160
Signal Processing - January 2016 - 161
Signal Processing - January 2016 - 162
Signal Processing - January 2016 - 163
Signal Processing - January 2016 - 164
Signal Processing - January 2016 - 165
Signal Processing - January 2016 - 166
Signal Processing - January 2016 - 167
Signal Processing - January 2016 - 168
Signal Processing - January 2016 - Cover3
Signal Processing - January 2016 - Cover4
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_201809
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_201807
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_201805
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_201803
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_201801
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_1117
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0917
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0717
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0517
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0317
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0117
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_1116
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0916
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0716
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0516
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0316
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0116
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_1115
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0915
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0715
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0515
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0315
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0115
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_1114
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0914
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0714
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0514
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0314
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0114
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_1113
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0913
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0713
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0513
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0313
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0113
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_1112
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0912
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0712
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0512
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0312
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0112
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_1111
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0911
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0711
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0511
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0311
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0111
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_1110
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0910
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0710
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0510
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0310
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0110
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_1109
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0909
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0709
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0509
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0309
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0109
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_1108
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0908
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0708
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0508
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0308
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0108
https://www.nxtbookmedia.com