Signal Processing - January 2016 - 74

102

101

101

100

100
Relative Error

Relative Error

102

10−1
10−2
10−3

10−1
10−2
10−3

10−4

10−4

10−5

10−5

10−6

0

1

2

3
4
Time (seconds)

Cyclic BCD
Randomized BCD
Cyclic PSCA q = 32
Randomized PSCA q = 32

5

6

7

Cyclic PSCA q = 8
Randomized PSCA q = 8
Cyclic PSCA q = 4
Randomized PSCA q = 4

10−6

0

100

200

300
400
Time (seconds)

Randomized BCD
Cyclic BCD
Randomized PSCA q = 8
Cyclic PSCA q = 8

(a)

500

600

Randomized PSCA q = 16
Cyclic PSCA q = 16
Randomized PSCA q = 32
Cyclic PSCA q = 32
(b)

[FIg10] a comparison of the serial Bcd with PSca method for solving the laSSo problem: min x Ax - b 2 + m x 1 . The matrix a and
vector b are generated according to [102]; and q denotes the number of processors used in each experiment. The dimension of a is
2, 000 # 10, 000 for (a) and 1, 000 # 100, 000 for (b). The experiments are done over a computer cluster using the Message Passing
Interface in c [18].

block j, then at each iteration r + 1, core j's problem of interest
can be written as
min

,

A jx j - b j

2

+ m x j 1,

where blj _ b - / i ! j A i x . Notice that the value of blj can be calculated by letting each node i compute the value of A i x i and
broadcast it to other nodes. Under this architecture, each node
does not need to know the complete matrix A and only local
information is enough for a distributed implementation of the
PSCA method.
r
i

praCtiCal COnSideratiOnS
There are a number of factors that we need to consider when
using the BSUM framework. The first consideration is about the
choice of the upper bound. What is a good bound for a given application? The answer is generally problem dependent, as we have
already seen in a few examples. The general guideline is that a
good upper bound should be able to ensure algorithm convergence, best exploit the problem structure, and make the subproblems easily solvable (preferably in closed form). For example, a
simple proximal upper bound is not likely to perform well for the
transceiver design problem discussed in the section "Wireless
Communication and Transceiver Design" as the resulting subproblems will not decompose over the variables.
The second consideration is about the choice of the block
update rules. As we have seen in the section "How Fast Does the
BSUM Converge?" different update rules lead to quite distinct convergence behavior. For convex problems, deterministic rules such
as the cyclic rule promise the worst-case convergence rates, while

the randomized rule ensures convergence rate in either averaged
or high-probability sense. Further, there is barely any theoretical
rate analysis for nonconvex problems, regardless of the block
selection rules. Therefore, the best strategy in practice is to perform an extensive numerical study and pick the best rule for the
application at hand. For example, researchers have found that the
MBI rule is effective for certain tensor decomposition problems
[13]; the cyclic rule can be superior to the randomized rule for
certain LASSO problems, and certain G-So rules can outperform
the randomized rule [43], [14].
The third consideration is about the choice of the parallelization schemes. There has been extensive research on parallelizing
various special cases and variations of the BSUM type algorithm;
see [17], [19], [99], [103]-[106], and the references therein. These
algorithms differ in a number of implementation details and in
their applicability. For example, most of the implementations use
randomized block selection rules to pick the variable blocks, while
[99] and [105] additionally use certain variations of the G-So rule.
The majority of the schemes only work for convex problems, with
the exception of [99] and [103], which work for general nonsmooth and nonconvex problems in the form of (5). When assessing whether a given problem is suitable for parallelization, it is
important to know that oftentimes the number of blocks that can
be updated in parallel is data dependent. For example, when solving LASSO problems, it is shown in [105] and [106] that the
degree of parallelization is dependent on the maximum eigenvalue
of certain submatrices of the data matrix. Some recent results
[107] show that for a certain randomized coordinate descent
method, such dependency could be mild. For solving general

IEEE SIGNAL PROCESSING MAGAZINE [74] jANuARy 2016
Table of Contents for the Digital Edition of Signal Processing - January 2016
