Signal Processing - January 2016 - 63

Example 6: Consider the following unconstrained problem
min f (x): = - x 1 x 2 - x 2 x 3 - x 3 x 1 + (x 1 - 1) 2+ + (- x 1 - 1) 2+
+ (x 2 - 1) +2 + (- x 2 - 1) +2 + (x 3 - 1) +2 + (- x 3 - 1) +2 ,
where the notation (z) 2+ means (max {0, z}) 2. In this case, fixing
(x 2, x 3) and optimizing over x 1 yields the following solution
x1 = *

(1 + 1 | x 2 + x 3 |) sign (x 2 + x 3), if x 2 + x 3 ! 0,
2
. (6)
[- 1, 1],
otherwise

A similar solution can be obtained for x 2 and x 3 as well. Suppose
we set u i (x i, z) = f (x) for all i (no approximation is used) and
let (x 01, x 02, x 03) = (- 1 - e, 1 + 1/2e, - 1 - 1/4e) for some e 2 0.
Then it can be shown the applying the cyclic version of the BSUM
algorithm, the iterates will be cycling around six points
(1, 1, - 1), (1, - 1, - 1), (1, - 1, 1), (- 1, - 1, 1), (- 1, 1, 1),
(- 1, 1, - 1), and none of these six points is a stationary solution
of the original problem. The reason for such pathological behavior is that, in any one of the six limit points above, there are at
least two subproblems that have multiple optimal solutions. For
example, at (1, 1, - 1), and fixing x 2, x 3 (resp. x 1, x 3), the optimal solution for x 1 (resp. x 2) is any element in the interval
[- 1, 1]; cf. (6).
A natural question at this point is, can we make the BSUM
work for these examples? The answer is affirmative, but how this
can be done requires a case by case study. To handle the first two
examples (i.e., Example 3 and 4), a generalized version of BSUM
is needed, which will be discussed in the "Extensions" section.
For the third example, one can simply pick a better upper bound
to guarantee convergence. For example, if we pick the proximal
upper bound (cf. Table 3): u i (x i, z) = f (x) + c/2 x i - z i 2, then
each subproblem will have a unique solution, and the algorithm
will not be trapped by the noninteresting solutions given in
Example 6. Notice that the use of c/2 x i - z i 2 inhibits the
move of x i from its current position z i . Thus, the main message
here is that when optimizing each block, it is beneficial, at least
theoretically, to be less greedy so that a conservative step is taken
towards reducing the objective. The extent of the "conservativeness" for the per block update is then naturally characterized by
the chosen upper bounds. Quite interestingly, the difficulty with
the nonunique subproblem solution can also be resolved by
using randomization. Formally, we have the following corollary
to Theorem 1 [38].
Corollary 1: Suppose the level set X 0 = {x f (x) # f (x 0)} is
compact. Then, under the randomized block selection rule, the
iterates generated by the BSUM algorithm converge to the set of
stationary points almost surely, i.e.,
lim d (x r, X *) = 0, almost surely.

r"3

hOw faSt dOeS the bSUm COnverge?
Now that we have examined the convergence of the BSUM, let us
proceed next to characterize the convergence speed of the

algorithm. There is no doubt that this is an important issue, especially so for big data optimization-the sheer size of the data and
limited computational resource makes it difficult to optimize a
problem to global optimality. Consequently, we are generally satisfied with high-quality suboptimal solutions and are mostly concerned with how quickly such solutions can be obtained.
Recently, extensive research efforts have been devoted to analyzing the convergence rate for various BSUM-type algorithms,
most of which use randomized coordinate selection rules and/or
quadratic upper-bound functions (cf. Table 3) to solve convex
problems; for example; see [5], [8], and [39]-[43]. Since it is not
possible to go over all the details of these different variations of
BSUM, here we present, at a high level, a fairly general result
that covers a large family of upper-bound functions satisfying
Assumption A, as well as all coordinate selection rules outlined
in Table 2.
To this end, let us make the following additional assumptions.
Assumption B
n
B1) f (x): = g (x) + / i = 1 h i (x i), where g (x) is a smooth convex
function with Lipschitz continuous gradient, i.e., there exists
a constant L such that dg (x) - dg (y) # L x - y ,
6 x, y ! X. Further both g and h i s are convex functions.
B2) The level set {x f (x) # f (x 0), x ! X} is compact.
B3) Each upper-bound function u i (x i, z) is strongly convex with
respect to x i.
An e - optima l solution x e ! X is defined as an
e
x ! {x x ! X, f (x) - f (x *) # e}, where f (x *) is the globally
optimal objective value of problem (5). Suppose both Assumptions
A and B are satisfied. Then it is shown in [38] and [42] that BSUM
takes at most c/e iterations to find an e-optimal solution, for all
coordinate rules specified in Table 2, where c 2 0 is a constant
only related to the description of the problem. Such a type of convergence rate is known as sublinear convergence. Here, the main
message is that under Assumptions A and B, the algorithm generally converges sublinearly in the order of 1/e. Further, for different special forms of BSUM, the constant c in front of 1/e can be
significantly refined so that it is independent of problem dimension; see [5] and [8]. It is also interesting to note here that when
the objective f is either strongly convex or convex but with certain special structure, the BSUM achieves the linear rate of convergence. That is, BSUM takes at most O (log (c/e)) iterations to
find an e-optimal solution, which is much faster than the sublinear rate; see, e.g., [44] and [45] for the related discussions.
Finally, we briefly mention that it is possible to relax certain
conditions in Assumption B to obtain refined rates. For example,
[42] shows that dropping the per-block strong convexity assumption in (B3) still achieves an O (1/e) sublinear convergence. In
[38], [46] it is shown that, when removing the convexity Assumption (B1), it is also possible to characterize the convergence rate to
stationary solutions. In [42] it is shown that when there are two
blocks of variables, the cyclic version of the BSUM can be accelerated to achieve an improved O (1/ e ) complexity. In a few recent
works [47], [48], it is shown that when randomized block selection
and the quadratic upper bound are used, it is possible to accelerate
the BSUM with any n 2 2 blocks.

IEEE SIGNAL PROCESSING MAGAZINE [63] 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